On the merits of hypermeshes and tori with adaptive routing

S. Loucif, M. Ould-Khaoua*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)795-806
Number of pages12
JournalJournal of Systems Architecture
Issue number9
Publication statusPublished - Mar 2002
Externally publishedYes


  • Adaptive routing
  • Graph
  • Hypergraph
  • Message latency
  • Multicomputer networks
  • Performance analysis

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture


Dive into the research topics of 'On the merits of hypermeshes and tori with adaptive routing'. Together they form a unique fingerprint.

Cite this