Title :
Optimal broadcast in all-port wormhole-routed hypercubes
Author :
Ho, Ching-Tien ; Kao, Ming-Yang
Author_Institution :
IBM Res. Div., Almaden Res. Center, San Jose, CA, USA
fDate :
2/1/1995 12:00:00 AM
Abstract :
We give an optimal algorithm that broadcasts on an n-dimensional hypercube in O(n/ log2 (n+1)) routing steps with wormhole, e-cube routing and all-port communication. Previously, the best algorithm of P.K. McKinley and C. Trefftz (1993) requires [n/2] routing steps. We also give routing algorithms that achieve tight time bounds for n ⩽7
Keywords :
hypercube networks; all-port communication; all-port wormhole-routed hypercubes; e-cube routing; optimal algorithm; optimal broadcast; Algebra; Bandwidth; Broadcasting; Circuit topology; Hypercubes; Multicast algorithms; Parallel algorithms; Parallel processing; Routing; System recovery;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
