A Performance Model of Software-Based Deadlock Recovery Routing Algorithm in Hypercubes

被引：4

作者：

Khonsari, A. ^{[1
]}

Sarbazi-Azad, H. ^{[2
]}

Ould-Khaoua, M. ^{[3
]}

机构：

[1] Inst Studies Fundamental Sci IPM, Sch Comp Sci, Tehran, Iran

[2] Sharif Univ Technol, Sch Comp Sci, Inst Studies Fundamental Sci IPM, Dept Comp Engn, Tehran, Iran

[3] Univ Glasgow, Dept Comp Sci, Glasgow G12 8RZ, Lanark, Scotland

来源：

PARALLEL PROCESSING LETTERS | 2005年 / 15卷 / 1-2期

关键词：

Wormhole switching; performance modelling; M/G/l queues;

D O I：

10.1142/S012962640500212X

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Recent studies have revealed that deadlocks are generally infrequent in the network. Thus the hardware resources, e.g. virtual channels, dedicated for deadlock avoidance are not utilised most of the time. This consideration has motivated the development of novel adaptive routing algorithms with deadlock recovery. This paper describes a new analytical model to predict message latency in hypercubes with a true fully adaptive routing algorithm with progressive deadlock recovery. One of the main features of the proposed model is the use of results from queueing systems with impatient customers to capture the effects of the timeout mechanism used in this routing algorithm for deadlock detection. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.

引用

页数：16

共 25 条

[1] PERFORMANCE OF THE DIRECT BINARY N-CUBE NETWORK FOR MULTIPROCESSORS [J].

ABRAHAM, S ;

PADMANABHAN, K .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (07) :1000-1011

[2]

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

[3]

BOURA Y, 1994, P INT WORKSH PAR PRO, P11

[4]

Daley D., 1965, J APPL PROBAB, V2, P186, DOI DOI 10.2307/3211884

[5]

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

[6] VIRTUAL-CHANNEL FLOW-CONTROL [J].

DALLY, WJ .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1992, 3 (02) :194-205

[7] A COMPREHENSIVE ANALYTICAL MODEL FOR WORMHOLE ROUTING IN MULTICOMPUTER SYSTEMS [J].

DRAPER, JT ;

GHOSH, J .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1994, 23 (02) :202-214

[8] 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

[9]

Duato J., 1997, INTERCONNECTION NETW

[10] Analysis of true fully adaptive routing with software-based deadlock recovery [J].

Khonsari, A ;

Sarbazi-Azad, H ;

Ould-Khaoua, M .

JOURNAL OF SYSTEMS AND SOFTWARE, 2004, 71 (03) :259-270

← 1 2 3 →