Hypercube Communication Delay with Wormhole Routing

Jong Kim; Chita R. Das

doi:10.1109/12.293259

Hypercube Communication Delay with Wormhole Routing

Jong Kim, Chita R. Das

Computer Science and Engineering

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

97 Scopus citations

Abstract

We present an analytical model for the performance evaluation of hypercube computers. This analysis is aimed at modeling a deadlock-free wormhole routing scheme prevalent on second generation hypercube systems. Probability of blocking and average message delay are the two performance measures discussed here. We start with the communication traffic to find the probability of blocking. The traffic analysis can capture any message destination distribution. Next, we find the average message delay that consists of two parts. The first part is the actual message transfer delay between any source and destination nodes. The second part of the delay is due to blocking caused by the wormhole routing scheme. The analysis is also extended to virtual cut-through routing and random wormhole routing techniques. The validity of the model is demonstrated by comparing analytical results with those from simulation.

Original language	English (US)
Pages (from-to)	806-814
Number of pages	9
Journal	IEEE Transactions on Computers
Volume	43
Issue number	7
DOIs	https://doi.org/10.1109/12.293259
State	Published - Jul 1994

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computational Theory and Mathematics

Access to Document

10.1109/12.293259

Cite this

@article{313358dfb8a04e89be522c75ebf0346e,

title = "Hypercube Communication Delay with Wormhole Routing",

abstract = "We present an analytical model for the performance evaluation of hypercube computers. This analysis is aimed at modeling a deadlock-free wormhole routing scheme prevalent on second generation hypercube systems. Probability of blocking and average message delay are the two performance measures discussed here. We start with the communication traffic to find the probability of blocking. The traffic analysis can capture any message destination distribution. Next, we find the average message delay that consists of two parts. The first part is the actual message transfer delay between any source and destination nodes. The second part of the delay is due to blocking caused by the wormhole routing scheme. The analysis is also extended to virtual cut-through routing and random wormhole routing techniques. The validity of the model is demonstrated by comparing analytical results with those from simulation.",

author = "Jong Kim and Das, {Chita R.}",

note = "Funding Information: Manuscript received June 26, 1991; revised July 14, 1992. This work was supported in part by the National Science Foundation under grants CCR-8810131 and ME'-9104485. This work was presented in part at the 11th ICDCS, May 1991.",

year = "1994",

month = jul,

doi = "10.1109/12.293259",

language = "English (US)",

volume = "43",

pages = "806--814",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "7",

}

TY - JOUR

T1 - Hypercube Communication Delay with Wormhole Routing

AU - Kim, Jong

AU - Das, Chita R.

N1 - Funding Information: Manuscript received June 26, 1991; revised July 14, 1992. This work was supported in part by the National Science Foundation under grants CCR-8810131 and ME'-9104485. This work was presented in part at the 11th ICDCS, May 1991.

PY - 1994/7

Y1 - 1994/7

N2 - We present an analytical model for the performance evaluation of hypercube computers. This analysis is aimed at modeling a deadlock-free wormhole routing scheme prevalent on second generation hypercube systems. Probability of blocking and average message delay are the two performance measures discussed here. We start with the communication traffic to find the probability of blocking. The traffic analysis can capture any message destination distribution. Next, we find the average message delay that consists of two parts. The first part is the actual message transfer delay between any source and destination nodes. The second part of the delay is due to blocking caused by the wormhole routing scheme. The analysis is also extended to virtual cut-through routing and random wormhole routing techniques. The validity of the model is demonstrated by comparing analytical results with those from simulation.

AB - We present an analytical model for the performance evaluation of hypercube computers. This analysis is aimed at modeling a deadlock-free wormhole routing scheme prevalent on second generation hypercube systems. Probability of blocking and average message delay are the two performance measures discussed here. We start with the communication traffic to find the probability of blocking. The traffic analysis can capture any message destination distribution. Next, we find the average message delay that consists of two parts. The first part is the actual message transfer delay between any source and destination nodes. The second part of the delay is due to blocking caused by the wormhole routing scheme. The analysis is also extended to virtual cut-through routing and random wormhole routing techniques. The validity of the model is demonstrated by comparing analytical results with those from simulation.

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

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

U2 - 10.1109/12.293259

DO - 10.1109/12.293259

M3 - Article

AN - SCOPUS:0028467067

SN - 0018-9340

VL - 43

SP - 806

EP - 814

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 7

ER -

Hypercube Communication Delay with Wormhole Routing

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this