Fault-Tolerant Compact Routing based on Reduced Structural Information in Wormhole-Switching based Networks*
Johan Vounckx, Geert Deconinck, Rudy Lauwereins, Jan A. Peperstraete · McGill-Queen's University Press eBooks · 1995
To satisfy the ever increasing demand for computational power massively parallel computers are mandatory. Such machines require as well a compact routing scheme for scalability as an optimd routing algorithm to minimine the communication delay. Combination of both requirements is reported for regular structures. Yet in a massively parallel machine the probability of failures becomes significant. The rep ular structure is then corrupted. To overcome this problem this paper describes a compact fault-tolerant routing algorithm for meshes. It is an interval routing scheme which is optimal without failures and nearly-optimal in the presence of failures. To minimise the number of intervals a reduced amount of structural information is used. As a result no extra intervals compared to the fault-free case are needed. We indicate how to make this routing scheme deadlock-free for wormhole routing without extra hardware or buffering. Unfortunately the number of intervals then grows drastically. Therefore we introduce an extension to interval routing, which allows the routing information to remain extremely compact.