Optimal broadcasting and gossiping in one-port meshes of trees 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 polylogarithmic factor of slowdown. They are known to outperform meshes in execution of algorithms 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. The performance of a machine with such a fast switching depends on the existence of efficient algorithms for commonly used collective communication operations. Little is known about collective communication properties of meshes of trees with distance-insensitive switching. We show that 2-D meshes of trees with distance-insensitive switching can execute optimally or asymptotically optimally two basic global communication operations, one-to-all broadcast and all-to-all broadcast, if routers with one-port and packet combining capabilities are used. Our algorithms work optimally for both square and rectangular meshes of trees.
broadcast gossip mesh of trees distance-insensitive switching interconnection network node-disjoint paths link-disjoint paths one-port capability