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 language | English (US) |
---|---|
Article number | 5727852 |
Pages (from-to) | III167-III171 |
Journal | Proceedings of the International Conference on Parallel Processing |
Volume | 3 |
DOIs | |
State | Published - 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
- Software
- General Mathematics
- Hardware and Architecture