Optimal broadcasting on incomplete star graph interconnection networks

被引：8

作者：

Chen, TS

Wang, NC ^{[1
]}

机构：

[1] Chaoyang Univ Technol, Dept Comp Sci & Informat Engn, Taichung 413, Taiwan

[2] Natl Univ Tainan, Dept Informat & Learning Technol, Tainan 700, Taiwan

来源：

JOURNAL OF SYSTEMS ARCHITECTURE | 2005年 / 51卷 / 02期

关键词：

broadcast; incomplete star graphs; optimal; parallel computing; star graphs;

D O I：

10.1016/j.sysarc.2004.10.003

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Broadcasting is an important collective communication operation in many applications which use parallel computing. In this paper, we focus on designing broadcasting algorithms for general incomplete star graphs. We propose two optimal one-to-all broadcasting algorithms for incomplete star graphs with a single-port communication model. An incomplete star graph with N nodes, where (n - 1)! < N < n!, is a subgraph of an n-dimensional star graph. The first scheme is single-message one-to-all broadcasting that takes O(n log n) steps. The second one is multi-message one-to-all broadcasting that takes O(n log n + m) steps. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：143 / 150

页数：8