Efficient Broadcasting In An Arrangement GraphUsing Multiple Spanning Trees
Yuh‐Shyan Chen, Tong Ying Juang, En Huai Tseng · 2000
The arrangement graph An,k is not only a generalization of star graph (n − k = 1), but also more flexible. Designing efficient broadcasting algorithm on a regular interconnection network is a fundamental issue for the parallel processing techniques. Two contributions are proposed in this paper. Initially, we elucidate a first result to construct n − k edge-disjoint spanning trees in an An,k. Second, we present efficient (one/all)to-all broadcasting algorithms by using constructed n − k spanning trees, where height of each spanning tree is 2k − 1. The arrangement graph is assumed to use one-port and all-port communication models and packet-switching (or store-and-forward) technique. Using n − k spanning trees allows us to present efficient broadcasting algorithm in the arrangement graphs and outperforms previous results. This is justified by our performance analysis. key words: arrangement graph, broadcast, interconnection network, parallel processing, routing