An improved fault-tolerant routing algorithm in meshes with convex faults

被引：2

作者：

Chang, HH ^{[1
]}

Chiu, GM ^{[1
]}

机构：

[1] Natl Taiwan Univ Sci & Technol, Dept Comp Sci & Informat Engn, Taipei, Taiwan

来源：

PARALLEL COMPUTING | 2002年 / 28卷 / 01期

关键词：

convex faults; mesh; routing; virtual channel; wormhole routing;

D O I：

10.1016/S0167-8191(01)00125-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we propose an improved fault-tolerant routing algorithm for meshes with convex faults. By fully utilizing virtual channels of each class and properly enforcing routing constraints, the proposed scheme requires only two virtual channels per physical channel to ensure deadlock-free property in two-dimensional meshes. This is significant from both theoretical and practical points of view. Our distributed routing algorithm requires only local knowledge of faults and works correctly for any combination of convex faults. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：133 / 149

页数：17

共 12 条

[1] FAULT-TOLERANT WORMHOLE ROUTING ALGORITHMS FOR MESH NETWORKS [J].

BOPPANA, RV ;

CHALASANI, S .

IEEE TRANSACTIONS ON COMPUTERS, 1995, 44 (07) :848-864

[2]

BOURA YM, 1995, P 1995 INT C PAR PRO

[3] Communication in multicomputers with nonconvex faults [J].

Chalasani, S ;

Boppana, RV .

IEEE TRANSACTIONS ON COMPUTERS, 1997, 46 (05) :616-622

[4]

CHIEN AA, 1992, ACM COMP AR, V20, P268, DOI 10.1145/146628.140383

[5]

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

[6] DEADLOCK-FREE ADAPTIVE ROUTING IN MULTICOMPUTER NETWORKS USING VIRTUAL CHANNELS [J].

DALLY, WJ ;

AOKI, H .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1993, 4 (04) :466-475

[7] A NEW THEORY OF DEADLOCK-FREE ADAPTIVE ROUTING IN WORMHOLE NETWORKS [J].

DUATO, J .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1993, 4 (12) :1320-1331

[8]

*INT CORP, 1991, PAR XP S PROD OV

[9] AN ADAPTIVE AND FAULT TOLERANT WORMHOLE ROUTING STRATEGY FOR KAPPA-ARY NORMAL-CUBES [J].

LINDER, DH ;

HARDEN, JC .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (01) :2-12

[10]

SEITZ CL, 1988, P 3 C HYP CONC COMP, P33

← 1 2 →