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