Search

Typically, a scheduling algorithm for an n x n packet switch with a crossbar as the data fabric divides time into slots, each of duration tp sufficient to transmit a packet. If a scheduling round requires tr > tp time, then the switch can transmit multiple packets, up to s = ⌊tr/tp⌋, between each mapped input-output pair under the current mapping. If s = 1, there exists a frame-based scheduling algorithm with Θ(log n) delay. For uniform random traffic, we establish that the delay is Ω(n) for any s > 1, hence, s = 1 is the only case where a Θ(log n) delay is achievable.Given the importance of achieving a low s, it is imperative to develop extremely fast scheduling algorithms (that reduce tr) on a mesh-based structure (corresponding to the crossbar topology of the switch). We present results for a fast scheduling algorithm that runs on a mesh-of-trees topology that can be overlaid on the crossbar switching fabric.

A decoder is a hardware module that expands an x-bit input into an n-bit output, where x << n. It can be viewed as producing a set S of subsets of an n-element set Zn. If this set S can be altered by the user, the decoder is said to be configurable. We propose a class of configurable decoders (called "mapping-unit" based decoders or simply MU-decoders) that facilitate efficient selection of elements in an FPGA (in general, in any chip). Conventional solutions for this selection use either (a) a fixed (non-reconfigurable) decoder that lacks the flexibility to generate many subsets quickly, or (b) a large look-up table (LUT) which is flexible, but too expensive. The proposed class of MU-decoders have much of the flexibility of the large-LUT solution (also called a LUT decoder here) at the cost of the fixed decoder solution. Specifically, we show that for any fixed gate cost, the a MU-decoder can produce any set of subsets that the LUT decoder can; in addition, the MU-decoder can exploit any available structure in the application at hand to produce many more subsets than the LUT decoder. We illustrate this ability in the context of totally ordered sets of subsets