Performance Analysis of Fully Adaptive Routing Algorithms in Wormhole-Switched Interconnect Networks ∗
Abstract
As the number of elements in large-scale massively parallel computers, Multiprocessors System-on-Chip (MP-SoCs), and peer-to-peer communication networks increases, the probability of component failure becomes significant. Consequently, fault-tolerance turns out to be a key issue in the design of such systems. Adaptive routing algorithms have been frequently suggested as a means of improving communication performance in such systems. These algorithms, unlike deterministic routing, can utilize network state information to exploit the presence of multiple paths. Before such schemes can be successfully incorporated in networks, it is necessary to have a clear understanding of the factors which affect their performance potential. This paper investigates the performance of nine prominent adaptive fault-tolerant routing algorithms in wormhole-switched 2-D tori with a routing scheme suggested by Chalasani and Boppana [1], as an instance of a fault-tolerant method. The suggested scheme is widely used in the literature to achieve high adaptivity and support interprocessor communications in massively parallel computers due to its ability to preserve both communication performance and fault-tolerant demands in these networks. The performance measures studied in the paper are the throughput, average message latency and average usage of virtual channels per node. Results obtained through simulation suggest two classes of presented routing schemes as high performance candidates in most faulty networks. Furthermore, we propose an analytical model to assess the performance behavior of a fully adaptive routing which has been shown to be one of the most efficient routings in the torus networks. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.
Keywords
Massively parallel computers, Interconnect networks, Torus, Adaptive routing, Virtual channels, Message latency, Queuing Theory, Performance evaluation
