OPTIMAL BROADCASTING ON THE STAR GRAPH

被引：98

作者：

MENDIA, VE ^{[1
]}

SARKAR, D ^{[1
]}

机构：

[1] UNIV MIAMI,DEPT MATH & COMP SCI,CORAL GABLES,FL 33124

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1992年 / 3卷 / 04期

关键词：

INTERCONNECTION NETWORKS; ONE-TO-ALL AND ALL-TO-ALL BROADCASTING; PARALLEL ALGORITHMS; STAR GRAPHS; TIME COMPLEXITY;

D O I：

10.1109/71.149958

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Recently the star graph has been shown as an attractive alternative to the widely used n-cube. Like the n-cube, the star graph possesses rich structure and symmetry as well as fault-tolerant capabilities, but has a smaller diameter and degree. However, very few algorithms exist to show its potential as a multiprocessor interconnection network. Many fast and efficient parallel algorithms require broadcasting as a basic step. In this paper, we propose an optimal algorithm for one-to-all broadcasting in the star graph. The algorithm can broadcast a message to N processors in O(log2 N) time. The algorithm exploits the rich structure of the star graph and works by recursively partitioning the original star graph into smaller star graphs. In addition, we develop an optimal all-to-all broadcasting algorithm.

引用

页码：389 / 396

页数：8

共 8 条

[1]

Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393

[2] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].