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 条

[11]

KUMAR V, 1991, ACTOODS05890 TECH RE

[12] MULTICAST IN HYPERCUBE MULTIPROCESSORS [J].

LAN, Y ;

ESFAHANIAN, AH ;

NI, LM .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1990, 8 (01) :30-41

[13]

LAN Y, 1989, INTEGRATION VLSI J, V7, P103

[14]

Law A. L., 2007, SIMULATION MODELING

[15]

LI K, 1989, 1989 P INT C PAR PRO, V1, P125

[16]

LIN X, 1990, 1990 P INT C PAR PRO, V3, P114

[17]

McKinley P. K., 1992, Proceedings. Supercomputing '92. (Cat. No.92CH3216-9), P478, DOI 10.1109/SUPERC.1992.236656

[18]

MCKINLEY PK, 1992, 1992 P INT C PAR PRO, V2, P10

[19]

MCKINLEY PK, 1993, 1993 P INT WORKSH MO, P57

[20]

METCALF M, 1990, FORTRAN 90 EXPLAINED

← 1 2 3 4 →