Multinode broadcasting in a wormhole-routed 2-D torus using an aggregation-then-distribution strategy

An efficient multinode broadcasting algorithm in a wormhole-routed 2-D tot- us is presented where there are an unknown number of s source nodes located on unknown positions each intending to broadcast a message of size m bytes to the rest of network. The torus is assumed to use the all-port model and the popular dimension-ordered routing. Most existing results are derived b ased on finding multiple edge-disjoint spanning trees in the network. The m ain technique used is an aggregation-then-distribution strategy. First, the broadcast messages are aggregated into some positions of the torus. Then, a number of independent subnetworks are constructed from the torus. These s ubnetworks, which are responsible for distributing the messages, can well e xploit the communication parallelism and the characteristic of wormhole rou ting. It is shown that such an approach is more appropriate than those usin g edge-disjoint trees for fixed-connection network such as tori. This is ju stified by performance analysis.