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

A. Khonsari; H. Sarbazi-Azad; M. Ould-Khaoua

doi:10.1142/S012962640500212X

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

A. Khonsari, H. Sarbazi-Azad, M. Ould-Khaoua

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	153-168
Number of pages	16
Journal	Parallel Processing Letters
Volume	15
Issue number	1-2
DOIs	https://doi.org/10.1142/S012962640500212X
Publication status	Published - Mar 2005
Externally published	Yes

Keywords

M/G/1 queues
Performance modelling
Wormhole switching

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture

Access to Document

10.1142/S012962640500212X

Cite this

@article{62b1e09117794d5c96e9e69cc84ef714,

title = "A Performance Model of Software-Based Deadlock Recovery Routing Algorithm in Hypercubes",

abstract = "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.",

keywords = "M/G/1 queues, Performance modelling, Wormhole switching",

author = "A. Khonsari and H. Sarbazi-Azad and M. Ould-Khaoua",

year = "2005",

month = mar,

doi = "10.1142/S012962640500212X",

language = "English",

volume = "15",

pages = "153--168",

journal = "Parallel Processing Letters",

issn = "0129-6264",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "1-2",

}

TY - JOUR

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

AU - Khonsari, A.

AU - Sarbazi-Azad, H.

AU - Ould-Khaoua, M.

PY - 2005/3

Y1 - 2005/3

N2 - 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.

AB - 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.

KW - M/G/1 queues

KW - Performance modelling

KW - Wormhole switching

UR - http://www.scopus.com/inward/record.url?scp=23844472661&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23844472661&partnerID=8YFLogxK

U2 - 10.1142/S012962640500212X

DO - 10.1142/S012962640500212X

M3 - Article

AN - SCOPUS:23844472661

SN - 0129-6264

VL - 15

SP - 153

EP - 168

JO - Parallel Processing Letters

JF - Parallel Processing Letters

IS - 1-2

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this