research-article

An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cubes

Authors:

Daniel H. Linder,

Jim C. HardenAuthors Info & Claims

IEEE Transactions on Computers, Volume 40, Issue 1

Pages 2 - 12

https://doi.org/10.1109/12.67315

Published: 01 January 1991 Publication History

Publisher Site

Abstract

The concept of virtual channels is extended to multiple virtual communication systems that provide adaptability and fault tolerance in addition to being deadlock-free. A channel dependency graph is taken as the definition of what connections are possible, and any routing function must use only those connections defined by it. Virtual interconnection networks allowing adaptive, deadlock-free routing are examined for three k-ary n-cube topologies: unidirectional, torus-connected bidirectional, and mesh-connected bidirectional.

References

[1]

{1} W. C. Athas and C. L. Seitz, "Multicomputers," Tech. Rep. 5244:TR:87, Dep. Comput. Sci., California Instit. Technol., 1987.

Crossref

Google Scholar

[2]

{2} C. L. Seitz, "The Cosmic Cube," Commun. ACM, vol. 28, pp. 22-23, Jan. 1985.

Digital Library

Google Scholar

[3]

{3} I. S. Gopal, "Prevention of store and forward deadlock in computer networks," IEEE Trans. Commun., vol. COM-33, no. 12, pp. 1258-1264, Dec. 1985.

Google Scholar

[4]

{4} K. D. Gunther, "Prevention of deadlocks in packet-switched data transport systems," IEEE Trans. Comput., vol. C-29, no. 4, pp. 512-524, Apr. 1981.

Google Scholar

[5]

{5} S. Toueg and J. D. Ullman, "Deadlock-free packet switching networks," SIAM J. Comput., vol. 10, no. 3, pp. 594-611.

Google Scholar

[6]

{6} W. J. Dally and C. L. Seitz, "Deadlock-free message routing in multiprocessor interconnection networks," IEEE Trans. Comput., vol. C-36, no. 5, pp. 547-553, May 1987.

Crossref

Google Scholar

[7]

{7} Submicron Systems Architecture Semiannual Technical Report, Tech. Rep. 5235:TR:86, Dep. Comput. Sci., California Instit. Technol., 1986.

Google Scholar

[8]

{8} W. D. Hillis, "The connection machine," Scient. Amer., vol. 256, no. 6, pp. 108-115, June 1987.

Digital Library

Google Scholar

[9]

{9} W. Welch, "Message-driven solver for Euler fluid dynamics equations," in Proc. 1988 ACM Southeast Regional Conf., Apr. 1988.

Google Scholar

[10]

{10} B. Carre', Graphs and Networks. Oxford, England: Clarendon, 1979, pp. 50-51.

Google Scholar

[11]

{11} J. Blazewicz, J. Brzezniski, and G. Gambosi, "Time-stamp approach to store-and-forward deadlock prevention," IEEE Trans. Commun., vol. COM-35, no. 5, pp. 490-495, May 1987.

Google Scholar

[12]

{12} J. Y. Ngai and C. L. Seitz, "A framework for adaptive routing," Tech. Rep. 5246:TR:87, Dep. Comput. Sci., California Instit. Technol., 1987.

Digital Library

Google Scholar

[13]

{13} W. J. Dally, A VLSI Architecture for Concurrent Data Structures. Boston, MA: Kluwer Academic, 1987, pp. 144-161.

Crossref

Google Scholar

Cited By

View all

Moudi MOthman M(2021)A survey on emerging issues in interconnection networksInternational Journal of Internet Technology and Secured Transactions10.1504/ijitst.2021.11351211:2(131-159)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1504/ijitst.2021.113512
Xiang DChakrabarty KFujiwara H(2018)Fault-Tolerant Unicast-Based Multicast for Reliable Network-on-Chip TestingACM Transactions on Design Automation of Electronic Systems10.1145/324321423:6(1-23)Online publication date: 6-Dec-2018
https://dl.acm.org/doi/10.1145/3243214
Jha SFormicola VMartino CDalton MKramer WKalbarczyk ZIyer R(2018)Resiliency of HPC Interconnects: A Case Study of Interconnect Failures and Recovery in Blue WatersIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.273753715:6(915-930)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1109/TDSC.2017.2737537
Show More Cited By

Index Terms

An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cubes

Recommendations

Adaptive wormhole routing in k-ary n-cubes
A simple mathematical model of adaptive routing in wormhole k-ary n-cubes
SAC '02: Proceedings of the 2002 ACM symposium on Applied computing

Many fully-adaptive algorithms have been proposed for k-ary n-cubes over the past decade. The performance characteristics of most of these algorithms have been analysed by means of software simulation only. This paper proposes a simple yet reasonably ...
A comparison of adaptive wormhole routing algorithms
Special Issue: Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93)

Improvement of message latency and network utilization in torus interconnection networks by increasing adaptivity in wormhole routing algorithms is studied. A recently proposed partially adaptive algorithm and four new fully-adaptive routing algorithms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 40, Issue 1

January 1991

125 pages

ISSN:0018-9340

Editor:
Earl Swartzlander
Univ. of Texas at Austin, Austin

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 January 1991

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

138
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Moudi MOthman M(2021)A survey on emerging issues in interconnection networksInternational Journal of Internet Technology and Secured Transactions10.1504/ijitst.2021.11351211:2(131-159)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1504/ijitst.2021.113512
Xiang DChakrabarty KFujiwara H(2018)Fault-Tolerant Unicast-Based Multicast for Reliable Network-on-Chip TestingACM Transactions on Design Automation of Electronic Systems10.1145/324321423:6(1-23)Online publication date: 6-Dec-2018
https://dl.acm.org/doi/10.1145/3243214
Jha SFormicola VMartino CDalton MKramer WKalbarczyk ZIyer R(2018)Resiliency of HPC Interconnects: A Case Study of Interconnect Failures and Recovery in Blue WatersIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.273753715:6(915-930)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1109/TDSC.2017.2737537
Ebrahimi MDaneshtalab M(2017)EbDaACM SIGARCH Computer Architecture News10.1145/3140659.308025345:2(703-715)Online publication date: 24-Jun-2017
https://dl.acm.org/doi/10.1145/3140659.3080253
Ebrahimi MDaneshtalab M(2017)EbDaProceedings of the 44th Annual International Symposium on Computer Architecture10.1145/3079856.3080253(703-715)Online publication date: 24-Jun-2017
https://dl.acm.org/doi/10.1145/3079856.3080253
Yu ZXiang DWang X(2015)Balancing virtual channel utilization for deadlock-free routing in torus networksThe Journal of Supercomputing10.1007/s11227-015-1428-671:8(3094-3115)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1007/s11227-015-1428-6
Yu CYang XHe LZhang J(2014)Optimal wavelength assignment in the implementation of parallel algorithms with ternary n-cube communication pattern on mesh optical networkTheoretical Computer Science10.5555/2846455.2846493524:C(68-77)Online publication date: 6-Mar-2014
https://dl.acm.org/doi/10.5555/2846455.2846493
Wachter EErichsen AAmory AMoraes FMacii E(2013)Topology-agnostic fault-tolerant NoC routing methodProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485667(1595-1600)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485667
Wang XXiang DYu Z(2013)TMThe Journal of Supercomputing10.1007/s11227-013-0922-y66:1(514-538)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1007/s11227-013-0922-y
Bargi ASarbazi-Azad H(2011)Task migration in three-dimensional meshesThe Journal of Supercomputing10.1007/s11227-010-0381-756:3(328-352)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s11227-010-0381-7
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Adaptive wormhole routing in k-ary n-cubes

A simple mathematical model of adaptive routing in wormhole k-ary n-cubes

A comparison of adaptive wormhole routing algorithms

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations