Please use this identifier to cite or link to this item:
標題: Efficient broadcasting in an arrangement graph using multiple spanning trees
作者: Chen, Y.S.
Juang, T.Y.
Tseng, E.H.
關鍵字: arrangement graph;broadcast;interconnection network;parallel;processing;routing;star graphs
Project: Ieice Transactions on Fundamentals of Electronics Communications and Computer Sciences
期刊/報告no:: Ieice Transactions on Fundamentals of Electronics Communications and Computer Sciences, Volume E83A, Issue 1, Page(s) 139-149.
The arrangement graph A(n,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 ale proposed in this paper. Initially, we elucidate a first result to construct n - k edge-disjoint spanning trees in an A(n,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.
ISSN: 0916-8508
Appears in Collections:期刊論文

Show full item record
TAIR Related Article

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.