Broadcasting in All-Output-Port Meshes of Trees with Distance-Insensitive Switching
✍ Scribed by Petr Salinger; Pavel Tvrdı́k
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 648 KB
- Volume
- 62
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Meshes of trees are hybrids of meshes and trees with outstanding properties, namely small degree and diameter and large bisection width. Moreover, they are known to be area universal, i.e., they can simulate any network with the same wire area with only a polylogarithmic slowdown. Meshes of trees are known to outperform meshes in execution of algorithms with local communication patterns, e.g., sorting, for which distance-sensitive switching, such as store-and-forward, suffices. Nowadays, parallel machines use distanceinsensitive, e.g., wormhole, switching. A challenging problem is to design optimal or efficient algorithms for one-to-all broadcast in all-output-port networks with distance-insensitive switching, since the lower bound on the number of rounds, log Dþ1 N , where D is the node degree, is very strict. This problem has been solved for tori and hypercubes quite recently. In this paper, we present nearly optimal algorithms for one-to-all broadcast in both square and rectangular 2-D meshes of trees and cube 3-D meshes of trees. The algorithms need at most one round more than the trivial lower bound. We also show requirements for deadlock-free execution of the algorithms. Meshes of trees are not node-symmetric, they are not even regular. This paper shows that, in contrast to meshes, the irregularity is not an obstacle for designing efficient schemes for such an intensive communication pattern, as the all-output-port broadcast.