Efficient Broadcasting in an Arrangement Graph Using Multiple Spanning Trees

概要

論文の詳細を見る
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 are 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.
社団法人電子情報通信学会の論文
2000-01-25