Optimal Broadcast in All-Port Wormhole-Routed Hypercubes

Ching Tien Ho, Ming Yang Kao

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

We give an optimal algorithm that broadcasts on an n- dimensional hypercube in Θ(n/ log2 (n +1)) routing steps with wormhole, e-cube routing and all-port communication. Previously, the best algorithm of McKinley and Trefftz requires [n/2] routing steps. We also give routing algorithms that achieve tight time bounds for n ≤ 7.

Original languageEnglish (US)
Pages (from-to)200-204
Number of pages5
JournalIEEE Transactions on Parallel and Distributed Systems
Volume6
Issue number2
DOIs
StatePublished - Feb 1995

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Optimal Broadcast in All-Port Wormhole-Routed Hypercubes'. Together they form a unique fingerprint.

Cite this