Design and performance of multipath MIN architectures
Frederic T. Chong, Thomas F. Knight · 1992
In this paper, we discuss the use of multipath multistage interccmnection networks (MINs) in the &sign of a fault-tolerant parallel computer.Multipath networks have multiple paths between any input and any output.In particular, we examine networks with either the property of expansion or maximal+mout.We present an Q(rz* ) lower time bound for a worst-case permutation on deterministic maximal-fanout networks.We further show how a randomized approach to msximal-fanout avoids the regularity from which this worst case arises.Unlike most previous work, we examine systems which can tolerate node failure and isolation.We describe mechanisms for fault identification and system reconfiguration.In reconfiguring a faulty system, a naive approach is to preserve processing power by maximizing the number of processing nodes left in operation.However, our results show that the synchronization requirements of applications make it critical to eliminate nodes with poor network connections.We find that a conservative fault-propagatwn algorithm for reconfiguration, adapted from work by Leighton and Maggs [LM92], performs well for all of our multipath networks.We also address some practical issues of network construction and present performance simulations based upon the MIT Transit architecture [DcH90], Simulation resul@ for 1024 node systems demonstrate that multipath networks, reconfigured with our faultpropagation algorithm, perform well not only in theory, but also in practice.In fact, our systems suffer only a small decrease in performance from network faults; the degradation is linear in the percentage of network failure.