TY - JOUR
T1 - On the merits of hypermeshes and tori with adaptive routing
AU - Loucif, S.
AU - Ould-Khaoua, M.
PY - 2002/3
Y1 - 2002/3
N2 - Most existing multicomputers employ the torus topology along with deterministic routing to ensure simple router implementation, and thus fast communication. Efficient adaptive routing algorithms with minimum implementation requirements have recently been proposed to overcome the limitations of deterministic routing. Such algorithms have been incorporated in the latest generation of multicomputers, e.g. the Cray T3E, which are still based on low-dimensional k-ary n-cubes. Our previous studies have shown that a hypergraph network, referred to as the distributed crossbar switch hypermesh (DCSH), has several topological and performance advantages over traditional k-ary n-cubes when deterministic routing is used. This paper evaluates the relative merits of the DCSH and a variant of k-ary n-cubes, the torus, in the context of adaptive routing. The evaluation takes into account the effects of increased switching delays due to adaptivity, and implementation costs for various technologies (e.g. VLSI and multiple-chip technology). The results reveal that the DCSH is a potential alternative as a future high-performance multicomputer network, which can fully exploit the benefits of adaptive wormhole routing. Even though the torus has higher bandwidth channels than its DCSH counterpart, due to its simpler interconnect structure, adaptivity cannot reduce its higher message blocking delays inherent in its topology.
AB - Most existing multicomputers employ the torus topology along with deterministic routing to ensure simple router implementation, and thus fast communication. Efficient adaptive routing algorithms with minimum implementation requirements have recently been proposed to overcome the limitations of deterministic routing. Such algorithms have been incorporated in the latest generation of multicomputers, e.g. the Cray T3E, which are still based on low-dimensional k-ary n-cubes. Our previous studies have shown that a hypergraph network, referred to as the distributed crossbar switch hypermesh (DCSH), has several topological and performance advantages over traditional k-ary n-cubes when deterministic routing is used. This paper evaluates the relative merits of the DCSH and a variant of k-ary n-cubes, the torus, in the context of adaptive routing. The evaluation takes into account the effects of increased switching delays due to adaptivity, and implementation costs for various technologies (e.g. VLSI and multiple-chip technology). The results reveal that the DCSH is a potential alternative as a future high-performance multicomputer network, which can fully exploit the benefits of adaptive wormhole routing. Even though the torus has higher bandwidth channels than its DCSH counterpart, due to its simpler interconnect structure, adaptivity cannot reduce its higher message blocking delays inherent in its topology.
KW - Adaptive routing
KW - Graph
KW - Hypergraph
KW - Message latency
KW - Multicomputer networks
KW - Performance analysis
UR - http://www.scopus.com/inward/record.url?scp=0036497258&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0036497258&partnerID=8YFLogxK
U2 - 10.1016/S1383-7621(01)00032-7
DO - 10.1016/S1383-7621(01)00032-7
M3 - Article
AN - SCOPUS:0036497258
SN - 1383-7621
VL - 47
SP - 795
EP - 806
JO - Journal of Systems Architecture
JF - Journal of Systems Architecture
IS - 9
ER -