Article

Free access

Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks

Authors:

Gustavo D. Pifarré,

Luis Gravano,

Sergio A. Felperin,

Jorge L. C. SanzAuthors Info & Claims

SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architectures

Pages 278 - 290

https://doi.org/10.1145/113379.113405

Published: 01 June 1991 Publication History

PDF eReader

References

[1]

Y. Birk, P.B. Gibbons, D. Soroker, a, ld J.L.C. Sanz. A simple lnechanisn~ for efticient barrier synchronization in MIMD machines. RJ 7078 (67141) Computer Science, IBM Almaden Research Center, October 1989.

Google Scholar

[2]

A. Borodin and J.E. Hopcroft. Routing, Merging and Sorting on Parallel Models of Colnputation. Ill Symposium on Theory of Comp'utiT~g, pages 338---344, I982.

Digital Library

Google Scholar

[3]

W. Dally and C. Seitz. Deadlock-fi'ee routing in multiprocessor interconnection network. 5206:TR:86, Computer Science Det)a.rtlnellt, California Institute of Technology, i986.

Google Scholar

[4]

W.J. Dally alld C. L. Seitz. The Torus Routing Chip. Distributed Computing, (1):187- 196, 1986.

Google Scholar

[5]

M.L. Fulghaxn, R. Cyplmr, and J.L.C. Sanz. A comparison of SIMD hypercube routi~lg strategies. RJ 7722 (71587), IBM Almaden Research Center, 1990.

Google Scholar

[6]

D. Gelernter. A DAG-based a.lgorithnl for prevention of store-and-forward deadlock in packet networks. IEEE Transactions on Compuiers, c-30:709-715, October 1981.

Digital Library

Google Scholar

[7]

L. Gravano, G.D. PifarrS, and J.L.C. Sanz. Adaptive Worm-hole Routing in Tori and Itypercubes. T R:91-10, IBM Argentina- CRAAG, March 199i.

Google Scholar

[8]

K.D. Gunther. Prevention of deadlocks in packet-switched data transport system. IEEE Trausaclions on Co~nmunications, com-29(4), April 1981.

Google Scholar

[9]

D. ttillis. The Connection Machinc. The MIT Press, 1985.

Google Scholar

[10]

P. Kermani and L. Kleinrock. Virtual Cut- Through: A new computer communication switching technique. Compuier Networks, (3):267-286, 1979.

Google Scholar

[11]

5. Konstantinidou. Adaptive, minimal routing in hypercube. In 6th. MIT Conference on Advanced Research in VLSI, pages 139-153, 1990.

Digital Library

Google Scholar

[12]

S. Konstantinidoll and L. Snyder. The Chaos router: A t)ractical application of randomization in network routing. In 2ud. AT~,ual A CM SPAA, pages 21--30, 1990.

Digital Library

Google Scholar

[13]

T. Leighton. Average (',ase Analysis of Greedy Routing Algorithnls on Arrays. In,5'PA A, 1990.

Digital Library

Google Scholar

[14]

D.tl. LiJlder and J.(',. Harden. An Adaptive and Faadt Tolerant Wormhole Rout.i~lg Strategy for k-ary 7~-cubes. IEEE 7}'al~sactions on Computers, 40(1):2-12, January 1991.

Digital Library

Google Scholar

[15]

T. Leighton and B. Maggs. Expanders might be practical: Fast algorithms for routing around faults on lnultib~ltterflies. In IEEE, editor, 30th AT~nual,5'y~posium on Foundations of Co~.pulcr,_.C;ciencc, pages 384--389, October 1989.

Google Scholar

[16]

T, Leighton, B. Ma.ggs, and S. I{3o. Universal packet routing algoritlLn~s. 1988.

Google Scholar

[17]

P.M. Merlin and P.I. Schweitzer. Deadlock avoidance in store-and-forward networks. 1: Store-and-forward deadlock. IEEE Transaclions on CoT~muntcatiou.s, 28(3), March 1980.

Google Scholar

[18]

L.M. Ni. Comlnunication Issues in Multicolnputers. In Proceedings of the First Work- .shop on Parallel Processing, Tai'wan, 1990.

Google Scholar

[19]

I~.M. Ni, February 1991. Personal Colnmunication.

Google Scholar

[20]

J.Y. Ngai and C.L. Seitz. A framework for adaptive routing. 5246 :TR :87, ('olJlputer Science l)epartnlent, Califorl~ia Institute of Techllology.

Digital Library

Google Scholar

[21]

G.D. Pifa.rr~, S.A. Felperin, L. Gra.vano, and J.L.C. Sanz. New techniques for combination, adaptivity, deadlock-fi'eedom and synchronization in massively parallel routing. In Preparation, 1991.

Google Scholar

[22]

G.D. Pifarr6, L. Gravauo, S.A. Felperin, and J.L.C. Sanz. Fully-Adaptive Mini~ml Deadlock-Free Pa.cket I'/outing in Ilypercubes, Meshes, and Other Networks. Technical report, IBM Alnm.den Research Center, 1991.

Google Scholar

[23]

N. Pippenger. Parallel colnmunication with limited buffers. In Foundal.iol~.s of Computer Science, pages 127- 136, 1984.

Google Scholar

[24]

A.G. Ranade. {low to e~nulate shared memory. In Foundations of Com pulcr Scicuce, pages 185- 194, 1985.

Google Scholar

[25]

A.G. Ra.nade, S.N. Bhat, and S.L. Jollnson. The Fluent Abstract Machine. In J. Allen and F.T. Leighton, editors, Fifth MIT con-,ferel~.ce on. advanccd ~vsearch i~. VL5I, pages 71- 93. Tlm MIT press, March 1988.

Digital Library

Google Scholar

[26]

E. UI)fa.1. An O(log N)~letenninistic packet roui, ing scheme. Ill 21st AnT~,ual AC'~ll- SIGACT Syln.posium on Theory of Compulil~.g, May 1989.

Digital Library

Google Scholar

[27]

L.G. Valiant. Optinlality of a two-phase strategy for ro~lting in interconnection networks. March 1982.

Google Scholar

[28]

L.G. Valiant. General purpose parallel archit, ectures. In J. van Leeuwen, editor, Handbook of Theoretical Co~putcr Science. Nortl~-Ilolland, 1988.

Google Scholar

Cited By

View all

Camarero CCano AMartínez CBeivide R(2024)Achieving High-Performance Fault-Tolerant Routing in HyperX Interconnection NetworksProceedings of the SC '24 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis10.1109/SCW63240.2024.00069(472-483)Online publication date: 17-Nov-2024
https://dl.acm.org/doi/10.1109/SCW63240.2024.00069
Puente VGregorio JVallejo FBeivide R(2008)ImmunetIEEE Transactions on Computers10.1109/TC.2008.9557:12(1676-1689)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1109/TC.2008.95
Bermond JDi Ianni MFlammini MPerennes S(2005)Acyclic orientations for deadlock prevention in interconnection networksGraph-Theoretic Concepts in Computer Science10.1007/BFb0024487(52-64)Online publication date: 17-Jun-2005
https://doi.org/10.1007/BFb0024487
Show More Cited By

Index Terms

Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks

Recommendations

Fully Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and other Networks: Algorithms and Simulations

This paper deals with the problem of packet-switched routing in parallel machines.Several new routing algorithms for different interconnection networks are presented.While the new techniques apply to a wide variety of networks, routing algorithms will ...
Adaptive Fault-Tolerant Deadlock-Free Routing in Meshes and Hypercubes

We present an adaptive deadlock-free routing algorithm which decomposes a given network into two virtual interconnection networks, VIN1 and VIN2. VIN1 supports deterministic deadlock-free routing, and VIN2 supports fully-adaptive routing. Whenever a ...
Adaptive Deadlock- and Livelock-Free Routing with All Minimal Paths in Torus Networks

This paper consists of two parts. In the first part, two new algorithms for deadlock- andlivelock-free wormhole routing in the torus network are presented. The first algorithm,called Channels, is for the n-dimensional torus network. This technique is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architectures

June 1991

368 pages

ISBN:0897914384

DOI:10.1145/113379

Chairman:
Tom Leighton
Massachusetts Institute of Technology, Cambridge

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SPAA91

Sponsor:

SPAA91: 3rd Annual ACM Symposium on Parallel Algorithms & Architecture

July 21 - 24, 1991

South Carolina, Hilton Head, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
347
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)10

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Camarero CCano AMartínez CBeivide R(2024)Achieving High-Performance Fault-Tolerant Routing in HyperX Interconnection NetworksProceedings of the SC '24 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis10.1109/SCW63240.2024.00069(472-483)Online publication date: 17-Nov-2024
https://dl.acm.org/doi/10.1109/SCW63240.2024.00069
Puente VGregorio JVallejo FBeivide R(2008)ImmunetIEEE Transactions on Computers10.1109/TC.2008.9557:12(1676-1689)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1109/TC.2008.95
Bermond JDi Ianni MFlammini MPerennes S(2005)Acyclic orientations for deadlock prevention in interconnection networksGraph-Theoretic Concepts in Computer Science10.1007/BFb0024487(52-64)Online publication date: 17-Jun-2005
https://doi.org/10.1007/BFb0024487
Bolding KYost W(2005)Design of a router for fault-tolerant networksParallel Computer Routing and Communication10.1007/3-540-58429-3_40(226-240)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-58429-3_40
Nesson TJohnsson L(2005)ROMM routing: A class of efficient Minimal routing algorithmsParallel Computer Routing and Communication10.1007/3-540-58429-3_37(185-199)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-58429-3_37
Ganesan EPradhan D(2003)Wormhole routing in de Bruijn networks and hyper-de Bruijn networksProceedings of the 2003 International Symposium on Circuits and Systems, 2003. ISCAS '03.10.1109/ISCAS.2003.1205158(III-870-III-873)Online publication date: 2003
https://doi.org/10.1109/ISCAS.2003.1205158
Bermond JDi Ianni MFlammini MPérennès S(2003)Deadlock prevention by acyclic orientationsDiscrete Applied Mathematics10.1016/S0166-218X(02)00232-9129:1(31-47)Online publication date: 15-Jun-2003
https://dl.acm.org/doi/10.1016/S0166-218X%2802%2900232-9
(2003)ReferencesInterconnection Networks10.1016/B978-155860852-8/50015-8(569-592)Online publication date: 2003
https://doi.org/10.1016/B978-155860852-8/50015-8
RuŽička P(2002)Efficient Communication SchemesSOFSEM’ 98: Theory and Practice of Informatics10.1007/3-540-49477-4_17(244-263)Online publication date: 24-Sep-2002
https://doi.org/10.1007/3-540-49477-4_17
Laing ACypher RMiller GGibbons P(1998)Deadlock-free routing in arbitrary networks via the flattest common supersequence methodProceedings of the tenth annual ACM symposium on Parallel algorithms and architectures10.1145/277651.277671(55-66)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1145/277651.277671
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Fully Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and other Networks: Algorithms and Simulations

Adaptive Fault-Tolerant Deadlock-Free Routing in Meshes and Hypercubes

Adaptive Deadlock- and Livelock-Free Routing with All Minimal Paths in Torus Networks