More Web Proxy on the site http://driver.im/

Article

Free access

Compressionless routing: a framework for adaptive and fault-tolerant routing

Authors:

A. A. ChienAuthors Info & Claims

ISCA '94: Proceedings of the 21st annual international symposium on Computer architecture

Pages 289 - 300

https://doi.org/10.1145/191995.192050

Published: 01 April 1994 Publication History

Abstract

Compressionless Routing (GR) is a new adaptive routing framework which provides a unified framework for efficient deadlock-free adaptive routing and fault-tolerance. CR exploits the tight-coupling between wormhole routers for flow control to detect potential deadlock situations and recover from them. Fault-tolerant Compressionless Routing (FCR) extends Compressionless Routing to support end-to-end fault-tolerant delivery. Detailed routing algorithms, implementation complexity and performance simulation results for CR and FCR are presented.CR has the following advantages: deadlock-free adaptive routing in torus networks with no virtual channels, simple router designs, order-preserving message transmission, applicability to a wide variety of network topologies, and elimination of the need for buffer allocation messages. FCR has the following advantages: tolerates transient faults while maintaining data integrity (nonstop fault-tolerance), tolerates permanent faults, can be applied to a wide variety of network topologies, and eliminates the need for software buffering and retry for reliability. These advantages of CR and FCR not only simplify hardware support for adaptive routing and fault-tolerance, they also can simplify communication software layers.

References

[1]

BBN Advanced Computers, Inc. Butterfly Products Overview, October 1987.

[2]

A. A. Chien and J. H. Khn. Planar-adaptive routing: Low-cost adaptive networks for multiprocessors. In Proceedings of the International Symposium on Computer Architecture, pages 268-77, May 1992.

Digital Library

[3]

Andrew A. Chien. A cost and performance model for k-ary n-cube wormhole routers. In Proceedings of Hot Interconnects Workshop, August 1993.

[4]

W. Dally and C. Seitz. Deadlock-free message routing in multiprocessor interconnection networks. IEEE Transactions on Computers, C-36(5), 1987.

Digital Library

[5]

W. J. Dally. Virtual channel flow control. IEEE Transactions on Parallel and Distributed Systems, 3(2):194-205, 1992.

Digital Library

[6]

W. J. Dally and C. Seitz. The torus routing chip. Distributed Computing, pages 187-196, 1986.

[7]

J. Duato. On the design of deadlock-free adaptive routing algorithms for multicomputers: design methodologies. In Proceedings of Parallel Architec. tutus and Languages Europe, 1991.

Digital Library

[8]

M. Homewood and M. McLaren. Meiko CS-2 interconnect Elan- Elite design. In Proceedings of the IEEE Hot Interconnects Symposium. IEEE TCMM, August 1993.

[9]

Intel Corporation. Paragon XP/S Product Overview, 1991.

[10]

C. F. Joerg. Design and implementation of a packet switched routing chip. Master's thesis, Massachusetts Institute of Technology, 1990. MIT/LCS/TR-482.

Digital Library

[11]

T. F. Knight. Technologies for low latency interconnection switches. In Proceedings of A CM Symposium on Parallel Algorithms and Architectures, 1989.

Digital Library

[12]

D. Linder and J. Harden. An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes. IEEE Transactions on Computers, C-40(1):2-12, January 1991.

Digital Library

[13]

L. Ni and C. Glass. The turn model for adaptive routhag. In Proceedings of the International Symposium on Computer Architecture, 1992.

Digital Library

[14]

D. Reeves, E. Gehringer, and A. Chandiramani. Adaptive routing and deadlock recovery: A simulation study. In Proceedings of the 4th Conference on Hypercube Concurrent Computers and Applications, 1989.

[15]

Thinking Machines Corporation, Cambridge, Massachusets. CM5 Technical Summary, October 1991.

Cited By

Lankes AWild TWallentowitz SHerkersdorf A(2012)Benefits of selective packet discard in networks-on-chipACM Transactions on Architecture and Code Optimization10.1145/2207222.22072289:2(1-21)Online publication date: 15-Jun-2012
https://dl.acm.org/doi/10.1145/2207222.2207228
Martínez Rubio JLópez PDuato J(2003)FC3DIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2003.122505614:8(765-779)Online publication date: 1-Aug-2003
https://dl.acm.org/doi/10.1109/TPDS.2003.1225056
Garcés IFranco DLamont GHaddad HPapadopoulos GPanda B(2002)Analysis of Distributed Routing Balancing behaviorProceedings of the 2002 ACM symposium on Applied computing10.1145/508791.508951(817-824)Online publication date: 11-Mar-2002
https://dl.acm.org/doi/10.1145/508791.508951
Show More Cited By

Index Terms

Compressionless routing: a framework for adaptive and fault-tolerant routing

Recommendations

Compressionless Routing: A Framework for Adaptive and Fault-Tolerant Routing

Compressionless Routing (CR) is a new adaptive routing framework which provides a unified framework for efficient deadlock-free adaptive routing and fault-tolerance. CR exploits the tight-coupling between wormhole routers for flow control to detect and ...
Compressionless routing: a framework for adaptive and fault-tolerant routing
Special Issue: Proceedings of the 21st annual international symposium on Computer architecture (ISCA '94)

Compressionless Routing (GR) is a new adaptive routing framework which provides a unified framework for efficient deadlock-free adaptive routing and fault-tolerance. CR exploits the tight-coupling between wormhole routers for flow control to detect ...
A performance model of compressionless routing in k-ary n-cube networks

Several analytical models of fully adaptive routing in wormhole-routed networks have recently been reported in the literature. All these models, however, have been discussed for routing algorithms with deadlock avoidance. Recent studies have revealed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '94: Proceedings of the 21st annual international symposium on Computer architecture

April 1994

394 pages

ISBN:0818655100

Chairman:
David A. Patterson
Univ. of California, Berkeley, CA

ACM SIGARCH Computer Architecture News Volume 22, Issue 2
Special Issue: Proceedings of the 21st annual international symposium on Computer architecture (ISCA '94)
April 1994
386 pages
ISSN:0163-5964
DOI:10.1145/192007
Editor:
Doug DeGroot
Dallas, TX
Issue’s Table of Contents

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS\TCCA: TC on Computer Arhitecture

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 April 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

21ISCA94

Sponsor:

SIGARCH
IEEE-CS\TCCA

21ISCA94: 21st International Symposium on Computer Architecture

April 18 - 21, 1994

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
418
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)7

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lankes AWild TWallentowitz SHerkersdorf A(2012)Benefits of selective packet discard in networks-on-chipACM Transactions on Architecture and Code Optimization10.1145/2207222.22072289:2(1-21)Online publication date: 15-Jun-2012
https://dl.acm.org/doi/10.1145/2207222.2207228
Martínez Rubio JLópez PDuato J(2003)FC3DIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2003.122505614:8(765-779)Online publication date: 1-Aug-2003
https://dl.acm.org/doi/10.1109/TPDS.2003.1225056
Garcés IFranco DLamont GHaddad HPapadopoulos GPanda B(2002)Analysis of Distributed Routing Balancing behaviorProceedings of the 2002 ACM symposium on Applied computing10.1145/508791.508951(817-824)Online publication date: 11-Mar-2002
https://dl.acm.org/doi/10.1145/508791.508951
Duato JPinkston T(2001)A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of ResourcesIEEE Transactions on Parallel and Distributed Systems10.1109/71.97055612:12(1219-1235)Online publication date: 1-Dec-2001
https://dl.acm.org/doi/10.1109/71.970556
Martínez-Rubio JLópez PDuato J(2001)A Cost-Effective Approach to Deadlock Handling in Wormhole NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/71.94074612:7(716-729)Online publication date: 1-Jul-2001
https://dl.acm.org/doi/10.1109/71.940746
Warnakulasuriya SPinkston T(2000)A Formal Model of Message Blocking and Deadlock Resolution in Interconnection NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/71.84173911:3(212-229)Online publication date: 1-Mar-2000
https://dl.acm.org/doi/10.1109/71.841739
Suh JDao BDuato JYalamanchili S(2000)Software-Based Rerouting for Fault-Tolerant Pipelined CommunicationIEEE Transactions on Parallel and Distributed Systems10.1109/71.84173811:3(193-211)Online publication date: 1-Mar-2000
https://dl.acm.org/doi/10.1109/71.841738
Franco DGarcés ILuque EPapatheodorou TValero MPolychronopoulos CMuraoka YLabarta J(1999)A new method to make communication latency uniformProceedings of the 13th international conference on Supercomputing10.1145/305138.305195(210-219)Online publication date: 20-Jun-1999
https://dl.acm.org/doi/10.1145/305138.305195
Lacy WCruz-Rivera JWills D(1998)The Offset CubeIEEE Transactions on Parallel and Distributed Systems10.1109/71.7222229:9(893-908)Online publication date: 1-Sep-1998
https://dl.acm.org/doi/10.1109/71.722222
Warnakulasuriya SPinkston T(1997)Characterization of Deadlocks in Interconnection NetworksProceedings of the 11th International Symposium on Parallel Processing10.5555/645607.661822(80-86)Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.5555/645607.661822
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents