For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Efficient Broadcasting in an Arrangement Graph Using Multiple Spanning Trees
Yuh-Shyan CHEN Tong-Ying JUANG En-Huai TSENG
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/01/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
arrangement graph, broadcast, interconnection network, parallel processing, routing,
Full Text: PDF(840.7KB)>>
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.