DEADLOCK-FREE MULTICAST WORMHOLE ROUTING IN 2-D MESH MULTICOMPUTERS

被引：164

作者：

LIN, XO ^{[1
]}

MCKINLEY, PK ^{[1
]}

NI, LM ^{[1
]}

机构：

[1] MICHIGAN STATE UNIV,DEPT COMP SCI,E LANSING,MI 48824

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1994年 / 5卷 / 08期

基金：

美国国家科学基金会;

关键词：

MULTICOMPUTERS; MASSIVELY PARALLEL COMPUTERS; HEURISTIC ALGORITHMS; 2-D MESH TOPOLOGY; MULTICAST COMMUNICATION; WORMHOLE ROUTING; DEADLOCK-FREE ROUTING;

D O I：

10.1109/71.298203

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2,-a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms.

引用

页码：793 / 804

页数：12

共 31 条

[1]

ATHAS WC, 1908, IEEE COMPUT, P9

[2]

Borkar S., 1988, Proceedings. Supercomputing '88 (IEEE Cat. No.88CH2617-9), P330, DOI 10.1109/SUPERC.1988.44670

[3]

BYRD GT, 1989, 1989 P INT C PAR PRO, P196

[4]

DALLY WJ, 1987, IEEE T COMPUT, V36, P547, DOI 10.1109/TC.1987.1676939