A TIGHT LOWER-BOUND ON THE NUMBER OF CHANNELS REQUIRED FOR DEADLOCK-FREE WORMHOLE ROUTING

Authors
LIBESKINDHADAS R
Citation
R. Libeskindhadas, A TIGHT LOWER-BOUND ON THE NUMBER OF CHANNELS REQUIRED FOR DEADLOCK-FREE WORMHOLE ROUTING, I.E.E.E. transactions on computers, 47(10), 1998, pp. 1158-1160
Citations number
10
Categorie Soggetti
Computer Science Hardware & Architecture","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture
Journal title
I.E.E.E. transactions on computers → ACNP
ISSN journal
00189340
Volume
47
Issue
10
Year of publication
1998
Pages
1158 - 1160
Database
ISI
SICI code
0018-9340(1998)47:10<1158:ATLOTN>2.0.ZU;2-7
Abstract
Wormhole routing is widely employed in current generation multicompute rs and the design of deadlock-free wormhole routing algorithms is an i mportant problem. In this note, we prove a tight lower bound on the nu mber of channels required by a broad class of deadlock-free wormhole r outing algorithms. This result has applications in proving that certai n topologies do not admit deadlock-free wormhole routing algorithms, a s well as applications in the design and analysis of fault-tolerant wo rmhole routing algorithms.