Evaluation of routing algorithms and their implementations

Abstract

Routing algorithms in interconnection networks can greatly impact system performance. Deterministic routing is simple resulting in small cycle times but does not perform well under congestion. Adaptive routing does perform well under congestion but is more complex resulting in high router cycle times. This dissertation offers a comprehensive evaluation of the routing algorithms for k-ary n-cube networks under virtual cut-through switching. The results include router cycle times for each routing algorithm simulated. A pipelined hybrid routing scheme is then proposed combining the advantages of small deterministic router cycle times with adaptive router flexibility. Multicast communication is a common operation in parallel computing and its efficient implementation is critical to the performance of multiprocessors. In this dissertation, a hardware tree-based routing algorithm (HTA) is presented for multicast communication. HTA is designed to keep the probability of message blocking at each intermediate node along a message's path low. By keeping the blocking probability low, the probability of deadlock is reduced. The algorithm is fully compatible with existing unicast routing schemes and relies on deadlock detection and recovery.