Small n*n switches are key components of interconnection networks used in multiprocessors and multicomputers. The architecture of these n*n switches, particularly their internal buffers, is critical for achieving high-throughput low-latency communication with cost-effective implementations. Several buffer structures are discussed and compared in terms of implementation complexity, inter-switch handshaking requirements, and their ability to deal with variations in traffic patterns and message lengths. A design for buffers that provide non-FIFO message handling and efficient storage allocation for variable size packets using linked lists managed by a simple on-chip controller is presented. The new buffer design is evaluated by comparing it to several alternative designs in the context of a multistage interconnection network. The modeling and simulation show that the new buffer outperforms alternative buffers and can thus be used to improve the performance of a wide variety of systems currently using less efficient buffers.>

The micro-architecture and VLSI implementation of a dynamically allocated multiqueue (DAMQ) buffer are presented. Design tradeoffs for the DAMQ buffer's datapath are discussed and a floorplan and the timing of the major functional units are presented. It is shown that in VLSI switches, with buffers than can store multiple packets, additional chip area is better used for the control of DAMQ buffers than for increased buffer space in simpler FIFO buffers.>

A type of buffer called a dynamically allocated multiqueue (DAMQ) buffer, designed for use in n*n switches, is presented. This buffer provides efficient handling of variable-length packets and the forwarding of packets in non-FIFO (first-in-first-out) order. The microarchitecture of the DAMQ buffer and its controller is described in the context of the ComCoBB communication coprocessor for multicomputers. The DAMQ buffer can be efficiently implemented in LVSI to support packet transmission and reception at the rate of one byte per clock cycle. With a hardwired linked-list manager and a fast-routing mechanism, the ComCoBB chip will support virtual cut-through of messages with a latency of four cycles. The performance of the DAMQ buffer is compared with that of three alternative buffers in the context of a multistage interconnection network. Simulations show that for uniform traffic the DAMQ buffer results in significantly lower latencies and higher maximal throughput than other designs with the same total buffer storage capacity.>

The design of small n*n switches that can be used to construct communication networks that provide low-latency communication for high-priority traffic, which is required for both multistage interconnection networks used in multiprocessors and direct networks used in multicomputers. The focus is on the design of the internal buffers, specifically on the design of buffers that provide non-FIFO handling of messages. Alternative designs and configurations are evaluated in the context of a multistage interconnection network. Simulation shows that a slightly modified version of the recently introduced dynamically allocated multiqueue buffer can provide superior support for high-priority traffic.>