Optimal broadcasting and gossiping in one-port meshes of tress with distance-insensitive routing

摘要

Meshes of trees are an ingenious hybrid of meshes and trees. They have very interesting Properties, namely small degree and diameter and large bisection width. Also they are area Universal, i.e., they can simulate any network with the same VLSI wire area with only polylog- arithmic factor of slowdown. They are known to outperform meshes in execution of algo- rithms with local communication patterns, for which distance-sensitive switching, such as Store-and-forward, suffices. Nowadays, parallel machines use distance-insensitive switching, Such as wormhole.