DESIGN AND ANALYSIS OF ROUTING SCHEMES AND ROUTERS FOR WORMHOLE-ROUTED MESH ARCHITECTURES

Younes M. BOURA

A fundamental requirement in designing high performance multiprocessors is the availability of high-throughput low-latency communication networks. The network topol­ogy, switching mechanism, and routing algorithm play a major role in determining net­work performance. The objective of this research is to design and evaluate low cost oblivious, partially adaptive, and fully adaptive routing algorithms for a class of direct networks, known as n-dimensional meshes, which has recently received increasing atten­tion to build large scale multiprocessors. All these algorithms are based on the wormhole switching paradigm.

This research has five parts. First, a basic framework is developed to design a class of deadlock free partially adaptive routing algorithms that need no extra hardware. These algorithms are simple, versatile, easy to implement, and provide competitive per­formance compared to other existing schemes. Second, a fully adaptive routing algorithm is developed by adding only one virtual channel to each physical channel. It is shown that this algorithm has not only minimal cost like other reported schemes, but can also utilize the virtual channels more efficiently. This should be beneficial in reducing network latency specifically under heavy traffic. Third, the proposed fully adaptive routing algo­rithm is extended to support node and link failures. The resulting fault-tolerant routing algorithm tolerates any number of faults at a cost of three virtual channels per physical channel. The fourth part of this research investigates the design of a high performance crossbar switch for implementing the network router. The investigated crossbar design is based on including virtual channels in the middle between the inputs and outputs of a switch to maximize the utilization of the output ports and handle uniform and nonuniform traffic more efficiently. Finally, Analytical modeling tools are developed to study network performance under a myriad of varying parameters. A major contribu­tion of this research is the availability of adaptive and fault-tolerant routing algorithms, high performance communication switches, and mathematical modeling tools that help designers build efficient interconnection networks for parallel architectures.