A crucial component of massively parallel multicomputers is the interconnection network which links all of the nodes of the computer together. The nodes communicate data and coordinate their efforts by sending and receiving messages through the network. Consequently, the achieved performance of such machines depends critically on that of their routing networks.
Network performance can be improved by allowing multipath, adaptive routing. Adaptive routing allows more freedom in paths taken by messages, spreading the load over the physical channels in a network more evenly. However, the flexibility of adaptive routing introduces new possibilities of deadlock.
The objective of this thesis is to develop a framework for deadlock-free and adaptive routing in multicomputer networks. For this purpose, we propose new flow control policies which provide backtracking operations in the routers. Architectural supports and operation protocols for them are described as well.
First, we propose a new flow control policy, called $\em{drop-and-reroute}$, for adaptive wormhole routing. Drop-and-reroute flow control further exploits the adaptivity achieved by adaptive routing by allowing a blocked packet to be routed again in the preceding node, and it improves the performance of adaptive routing algorithms. Then, based on the drop-and-reroute flow control policy, we propose a deadlock-free flow control policy, called $\em{channel bypassing}$, for providing adaptivity to deterministic routing in multicomputer networks. The proposed flow control policy does not require extra virtual channels for providing deadlock-free, adaptive routing. Instead, it requires only a single packet buffer for each input channel. The channel bypassing flow control achieves deadlock freedom by keeping the blocked packets from creating cycles in the channel dependency graph. The routing scheme based on this flow control is fully adaptive and can be minimal or nonminimal.
We evaluate the performance of the proposed flow control policies via extensive simulation under a variety of networks and traffic models. First, to show the performance improvement achieved by drop-and-reroute flow control, we simulate minimal fully adaptive routing algorithms for various networks. Our simulation results say that under nonuniform traffic patterns, bit-reversal and transpose, drop-and-reroute flow control considerably improves the network performance of the adaptive routing algorithms regardless of network topology. We also show the merits of channel bypassing flow control comparing the performance of it with those of dimension-order routing and the turn model, which provides partially adaptive routing without using virtual channels. In most cases considered, the adaptive routing scheme based on channel bypassing flow control significantly outperforms the dimension-order routing and turn model, providing lower latency and higher throughput.
