Communication delay in hypercubes in the presence of bit-reversal traffic

H. Sarbazi-Azad, M. Ould-Khaoua*, L. M. Mackenzie

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


A number of studies have recently proposed analytical models of adaptive routing in wormhole-switched hypercubes under the uniform traffic pattern. However, there has been hardly any work reported yet that deals with other important non-uniform traffic patterns found in many parallel applications. This paper describes a new analytical model of adaptive routing in wormhole-switched hypercubes in the presence of highly non-uniform traffic generated by bit-reversal permutations, which is an important communication operation in parallel applications such as FFT computations. The analysis focuses Duato's fully adaptive routing algorithm [J. Duato, IEEE Trans. Parallel Distrib. Syst. 4(12) (1993) 320], which is widely accepted as the most general algorithm for achieving adaptivity in wormhole-routed networks while allowing for an efficient router implementation. Results obtained through simulation experiments confirm that the proposed model exhibits a good degree of accuracy in predicting message latency under different traffic conditions.

Original languageEnglish
Pages (from-to)1801-1816
Number of pages16
JournalParallel Computing
Issue number13
Publication statusPublished - Dec 1 2001
Externally publishedYes


  • Adaptive routing
  • Bit-reversal permutation
  • Interconnection networks
  • Multicomputers
  • Non-uniform traffic
  • Performance modelling
  • Wormhole routing

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


Dive into the research topics of 'Communication delay in hypercubes in the presence of bit-reversal traffic'. Together they form a unique fingerprint.

Cite this