COMMUNICATIONS IN A TREE ARCHITECTURE
Oregon Graduate Institute
Beaverton, OR 97006
Broadcasting and point-to-point communication are common primitives in parallel computations. Efficient implementations of these primitives are of interest in order to improve the performance of these computations. In this paper, we concentrate on the tree architecture and give lower bounds and algorithms for 1) singlenode broadcasts 2) multinode broadcasts 3) scattering and 4) total exchange.
Tree architectures arise naturally in real time measurement and control systems , divide and conquer strategies , and searching applications . The popularity of the tree architecture stems from the following properties :
1) It has the least number of arcs possible for the interconnection of a given set of nodes.
2) Trees have important properties for path control, especially in packet switching networks.
3) Trees have preorder, inorder and postorder capabilities.
4) They can implement lookahead logic used in carry lookahead adders, priority circuits and shift-registers.
5) They can naturally implement arithmetic operations and operations that collect data, such as a maximum of a set of numbers.
6) The tree architecture is strongly inductive.
Some of the common data communication patterns in parallel numerical methods are [5,O6]:
1) Singlenode broadcasting: which involves transfer of the same data from one processor to all other processors in the network.
2) Multinode broadcasting: which involves concurrent broadcasting from all nodes to all other nodes in the network.
3) Scattering: which is singlenode broadcasting with the difference that different packets are transferred to different nodes.
4) Total exchange: which involves transfer of a different packet from each node to every other node.
Broadcasting finds applications in a variety of linear algebra algorithms , such as matrix-vector multiplication, matrix-matrix multiplication, LU-factorization, and also in database queries and transitive closure algorithms . Scattering and total exchange operations occur in transposing a