A general theory for deadlock-free adaptive routing using a mixed set of resources

被引：51

作者：

Duato, J

Pinkston, TM

机构：

[1] Univ Politecn Valencia, Fac Informat, E-46071 Valencia, Spain

[2] Univ So Calif, Dept EE Syst, SMART Interconnects Grp, Los Angeles, CA 90089 USA

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2001年 / 12卷 / 12期

基金：

美国国家科学基金会;

关键词：

general theory for deadlock-free fully adaptive routing; regular networks; irregular networks; nonatomic queue allocation;

D O I：

10.1109/71.970556

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper presents a theoretical framework for the design of deadlock-free fully adaptive routing algorithms for a general class of network topologies and switching techniques in a single, unified theory, A general theory is proposed that allows the design of deadlock avoidance-based as well as deadlock recovery-based wormhole and virtual cut-through adaptive routing algorithms that use a homogeneous or a heterogeneous (mixed) set of resources. The theory also allows channel queues to be allocated nonatomically, utilizing resources efficiently. A general methodology for the design of fully adaptive routing algorithms applicable to arbitrary network topologies is also proposed. The proposed theory and methodology allow the design of efficient network routers that require minimal resources for handling infrequent deadlocks.

引用

页码：1219 / 1235

页数：17

共 57 条

[1]

ABALI B, 1997, P 1 INT WORKSH COMM, P61

[2]

Anjan K. V., 1995, Proceedings 9th International Parallel Processing Symposium (Cat. No.95TH8052), P537, DOI 10.1109/IPPS.1995.395983

[3]

Anjan K.V., 1996, P 10 INT PAR PROC S, P815

[4]

ANJAN KV, 1995, ACM COMP AR, P201, DOI 10.1109/ISCA.1995.524561

[5]

[Anonymous], P 24 INT S COMP ARCH

[6]

[Anonymous], 1996, P INT S HIGH PERF IN

[7] MYRINET - A GIGABIT-PER-SECOND LOCAL-AREA-NETWORK [J].

BODEN, NJ ;

COHEN, D ;

FELDERMAN, RE ;

KULAWIK, AE ;

SEITZ, CL ;

SEIZOVIC, JN ;

SU, WK .

IEEE MICRO, 1995, 15 (01) :29-36

[8]

Carbonaro J., 1996, P S HIGH PERF INT HO, P157

[9]

CARRION C, 1997, P 1997 INT C HIGH PE

[10]

Coli M., 1995, Proceedings Euromicro Workshop on Parallel and Distributed Processing, P288, DOI 10.1109/EMPDP.1995.389126

← 1 2 3 4 5 6 →