Projects at UCSC

This page gives a brief summary of the research projects I have done while at UCSC.

Java Virtual Router

We implemented a virtual router in Java to simulate routing protocols. The router uses point-to-point UDP links and IP multicast groups to simulate physical media. This project could be used to study routing protocols in an easy-to-understand environment with object-oriented code rather than in complex C-based environments.

PDF

A 16-bit Booth Multiplier with 32-bit Accumulate

I wrote a VHDL description of a 16x16+32 bit Booth encoded multiplier with a common 16-bit I/O bus between operand registers. The VHDL description uses 2-phase clocking and a 3-stage pipeline. There is also a Magic layout for the core multiplier using a double-rail pass-logic design. The Magic layout is for a 3-metal AMI C5N 0.5 micron process. The layout is non-pipelined and simulates at 188 MHz. The design is based on work by Abu-Khater, Bellaouar, and Elmasry.

PDF

Multiple Polling Slots for RICH RTR Packets

The RICH wireless protocol use receiver initiated polling of known sources on a common wireless channel. Since RICH does not use carrier sense, the common polling channel functions like a slotted ALOHA system. We study two techniques to boost polling success rate. First, we introduce a new scheme of listing multiple receivers in a single Request to Receive (RTR) packet. Second, we examine through simulation the effects of Dual Poll (DP) mode in the RICH protocols. Our analysis also presents two Discrete Time Markov models of the original RICH protocols.

We find that multiple scheduling slots does not have a significant affect on the number of concurrent conversations. Multiple slots may have beneficial effects on the mean waiting time of the transmit queue when packets are short. One of our Markov models has a good approximation of simulation for short packet lengths.

PDF

A Software Acquisition Life Cycle Model

We present a software acquisition meta-model, called SAMM, for Commercial-Off-The-Shelf software acquisition. Our model is a meta-model in that it includes sections that use other, detailed, models for specific tasks. SAMM is a complete life-cycle model that begins with an end-user need and ends with software maintenance. We have adapted several other models in to SAMM and added several novel features that we think appropriate for acquisition of commercial software. Our model also addresses issues of process automation.

PostScript and PDF

A Two Level Virtual Cache with Deferred Physical Address Translation Based on the MIPS R4400

This paper investigates virtually indexed / virtually tagged L1 Instruction and Data caches with a unified virtually indexed, physically tagged L2 cache. The TLB is moved to the L2 level. Based on the MIPS R4400MC, we construct an architecture which enforces Multilevel Inclusion and a Write-Invalidate/Write-Update cache coherency protocol. Using trace simulations derived from SimOS SPECint92 workloads, we analyze the behavior of the system. We find that this architecture suffers from a large number of forced L1 and L2 invalidations, which are required to maintain consistency with the TLB and between cache levels. We explore a variety of invalidation schemes to reduce these negative effects.

PDF

Packet iSlip

This paper examines input/output buffered crossbar switches under combined packet and cell data. Our switch architecture uses input buffering with Virtual Output Queues to avoid Head of Line Blocking. The switch fabric is a crossbar with no speedup. We use a modified iSlip [Mc95] crossbar scheduler geared towards packet data, called piSlip. Cell ports are largely unmodified from standard iSlip behavior. For packet output ports, we introduce changes to the "grant pointer" which minimizes output latency caused by packet reassembly. Our model uses several output states, including packet cut-through. From simulation results, we show that piSlip with virtual cut-through offers latency characteristics significantly better than unmodified iSlip with similar packet port interfaces. Simulation using SIM from Stanford further shows that piSlip and iSlip have similar maximum and average buffering requirements.

PDF and PowerPoint Summary

Heterogeneous k-Server Fork/Join Blocking Queue Approximation with Deferred Job Pickup

We review the literature related to Fork-Join queues, as applicable to the class project. Based on several articles, we propose a simplified reduced state solution that only tracks the number of tasks in the fastest queue, the slowest queue, and the number of tasks waiting in the join area. This yields a continuous time Markov chain with three state variables. We model transitions caused by intermediate servers as a service rate times a probability that the server is busy. We base the conditional probability on the number of jobs in the fastest and slowest queues. Using an m-Erlang distribution for the time to complete m jobs, we estimate the probability that an intermediate queue is ahead of the fastest or slowest queues. We also present simulation results for the system over various system parameters.

PDF and

An Analysis of Forward Error Correction in Shared Loss Multicast Trees

See my research page for this one

An Object Oriented Combinations Class with Multinomials

I developed a C++ class structure to generate combinations and their multinomial. It returns an STL SLL object with pointers to "permutation return" objects. The class solves the problem of how to allocate V marbles between N urns, where each urn may only hold at most M marbles. The class caches values under the assumption that it will be called in ever expanding M and V values. My estimate is that it executes in O(k²log²k), where k=min(M,V). I also estimate that it runs in space O(kilo-big).

It would be a simple modification to the class to generate all permutations. From the list of combinations, one could find all arrangements. For my purposes, it was sufficient to assume "identical" children, thus the multinomial was sufficient.

You can try out permtest on the web!

This problem is useful in multicast tree analysis. If there is some event that occurs at leaf nodes, such as successfully decoding a C(n,k) FEC code, then this class allows us to enumerate the state space.

Let N be the number of child nodes (adjacent descendents) of a node, say n_i. Call the child nodes c_k, k=1...N. Let V be the number of successful events under n_i. Under c_k, let M be the total number of leaf nodes, which is where these events occur (this assumes a tree of fixed degree sequence per level).

Then, this object class allows us to generate all the possible state spaces immediately descendant to n_i where 0...V events happen under each child of n_i, but no child receives more than M events, since there are only M leaf nodes under each child c_k.

Marc Mosko
http://www.cse.ucsc.edu/~mmosko
mmosko@cse.ucsc.edu