A high-speed fault-tolerant interconnect fabric for large-scale multiprocessors

Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001.Includes bibliographical references (p. 89-91).This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.This thesis describes the design and synthesis of an updated routing block for a nextgeneration wave propagation limited fault-tolerant interconnect fabric for a large-scale shared-memory multiprocessor system. The design is based on the metro multistage interconnection network, and is targeted at minimizing message latency. The design incorporates an efficient new tree-based allocation mechanism and an idempotent messaging protocol. A fat tree topology is the basis for the network. A Verilog implementation of the design is simulated and synthesized into physical hardware, running at speeds as high as 90MHz in an FPGA. Techniques are discussed to vastly improve performance in a potential future design using custom hardware. Further, two potential modifications to the network are considered. First, the performance effect of allocating dedicated physical wires to streamline the idempotent messaging protocol is analyzed. The modification increases the success rate of messages significantly, but the increased latency due to the space taken by the wires overwhelms the potential performance advantage. Second, a scheme for prioritizing messages is developed. This scheme improves the message success rates almost as much as the first modification, reducing the latency of idempotent messages by over 10%. However, this scheme does not increase the number of wires, and has a much smaller overhead. In addition to providing a significant performance advantage, prioritizing messages can help avoid deadlock and livelock situations.by Robert Woods-Corwin.M.Eng