Optimal broadcast in all-port wormhole-routed hypercubes

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. © 1994 IEEE.