Please use this identifier to cite or link to this item:
|標題:||Efficient broadcasting in an arrangement graph using multiple spanning trees||作者:||Chen, Y.S.
|關鍵字:||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.
|Appears in Collections:||期刊論文|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.