CUBE CONNECTED MOBIUS LADDERS - AN INHERENTLY DEADLOCK-FREE FIXED DEGREE NETWORK

被引：4

作者：

PRITCHARD, DJ ^{[1
]}

NICOLE, DA ^{[1
]}

机构：

[1] UNIV SOUTHAMPTON,DEPT ELECTR & COMP SCI,SOUTHAMPTON SO9 5NH,HANTS,ENGLAND

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1993年 / 4卷 / 01期

关键词：

CAYLEY GRAPH; CUBE CONNECTED CYCLES; CYCLE OF DEPENDENCY; DEADLOCK-FREE; DEFINING RELATIONS; DIAMETER; E-CUBE ROUTING; HOMOGENEOUS; INTERVAL ROUTING; VIRTUAL LINK;

D O I：

10.1109/71.205658

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper presents a new multiprocessor interconnection network, known as cube connected mobius ladders, which has an inherently deadlock-free routing strategy and hence has none of the buffering and computational overheads required by deadlock-avoidance message passing algorithms. The basic network has a diameter phi of 4n - 1 for n2n+2 nodes and has a fixed node degree of 4. The network can be interval routed in two stages and can be represented as a Cayley graph. This is the only practical fixed degree topology of size O(2phi) which has an inherently deadlock-free routing strategy, making it ideally suited for medium and large sized transputer networks.

引用

页码：111 / 117

页数：7

共 18 条

[1] ARDEN BW, 1982, IEEE T COMPUT, V31, P60, DOI 10.1109/TC.1982.1675886
[2] DALLY WJ, 1987, IEEE T COMPUT, V36, P547, DOI 10.1109/TC.1987.1676939
[3] De Bruijn NG, 1946, KONINKLIJKE NEDERLAN, V49, P758
[4] DEBBAGE M, 1991, VIRTUAL CHANNEL ROUT
[5] GELERNTER D, 1981, IEEE T COMPUT, V30, P709, DOI 10.1109/TC.1981.1675690
[6] Grossman I., 1964, GROUPS THEIR GRAPHS
[7] PREVENTION OF DEADLOCKS IN PACKET-SWITCHED DATA TRANSPORT-SYSTEMS
GUNTHER, KD
[J]. IEEE TRANSACTIONS ON COMMUNICATIONS, 1981, 29 (04) : 512 - 524
[8] Jesshope C. R., 1989, 16th Annual International Symposium on Computer Architecture (Cat. No.89CH2705-2), P150, DOI 10.1109/ISCA.1989.714549
[9] KUMAR VP, 1984, 4TH P INT C DISTR CO, P448
[10] LANG CR, 1982, THESIS CALTECH

← 1 2 →