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 language||English (US)|
|Journal||Proceedings of the International Conference on Parallel Processing|
|State||Published - Jan 1 1994|
|Event||23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States|
Duration: Aug 15 1994 → Aug 19 1994
ASJC Scopus subject areas
- Hardware and Architecture