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

research-article

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

Authors:

G. D. Pifarré,

S. A. Felperin,

J. L. C. SanzAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 5, Issue 3

Pages 247 - 263

https://doi.org/10.1109/71.277792

Published: 01 March 1994 Publication History

Abstract

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 beshown for the hypercube, the two-dimensional mesh, and the shuffle-exchange. Althoughthe new techniques are designed for packet routing, they can be used alternatively forvirtual cut-through routing models. The techniques presented for hypercubes and meshesare fully-adaptive and minimal. A fully-adaptive and minimal routing is one in which allpossible minimal paths between a source and a destination are of potential use at thetime a message is injected into the network. Minimal paths followed by messagesultimately depend on the local congestion encountered in each node of the network. Allof the new techniques are completely free of deadlock situations.

References

[1]

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

Digital Library

[2]

{2} A. Ranade, S. Bhat, and S. Johnson, "The Fluent abstract machine," in Fifth MIT Conference on Advanced Research in VLSI, J. Allen and F. Leighton, Eds. Cambridge, MA: The MIT press, Mar. 1988, pp. 71-93.

[3]

{3} A. Ranade, "How to emulate shared memory," in Foundations of Comput. Sci., 1985, pp. 185-194.

[4]

{4} E. Upfal, "An O(log N) deterministic packet routing scheme," presented at the 21st Annu. ACM-SIGACT Symp. Theory of Computing, May 1989.

[5]

{5} T. Leighton and B. Maggs, "Expanders might be practical: Fast algorithms for routing around faults on multibutterflies," in 30th Annu. Symp. on Foundations of Comput. Sci., Oct. 1989, pp. 384-389.

Digital Library

[6]

{6} L. Valiant, "General purpose parallel architectures," in Handbook of Theoretical Computer Science, J. van Leeuwen, Ed. Amsterdam: North-Holland, 1988.

[7]

{7} S. Konstantinidou and L. Snyder, "The Chaos router: A practical application of randomization in network routing," in 2nd. Annu. ACM SPAA, 1990, pp. 21-30.

[8]

{8} J. Ngai and C. Seitz, "A framework for adaptive routing," Tech. Rep. 5246:TR:87, Comput. Sci. Dep., Cal. Inst. of Technol., 1987.

Digital Library

[9]

{9} D. Hillis, The Connection Machine. Cambridge, MA: The MIT Press, 1985.

[10]

{10} F. Chong, E. Egozy, A. DeHon, and T. Knight, "Multipath fault tolerance in multistage interconnection network," Transit note #48, MIT, June 1991.

[11]

{11} S. Borkar, R. Cohn, G. Cox, S. Gleason, T. Gross, H. Kung, et al., "iwarp: An integrated solution to high-speed parallel computing," in Proc. Supercomputing 88, ACM, 1988.

Digital Library

[12]

{12} D. Lenoski, J. Landon, K. Gharachorloo, W. Weber, A. Goopta, and J. Hennessy, "Overview and status of the Stanford Dash multiprocessor," presented at the Int. Symp. Shared Memory Multiprocessing. Tokyo, Japan, Apr. 1991.

[13]

{13} C. Kruskal and M. Snir, "The performance of multistage interconnection networks for multiprocessors," IEEE Trans. Comput., vol. C-32, pp. 1091-1098, Dec. 1983.

[14]

{14} S. Felperin, L. Gravano, G. Pifarré and J. Sanz, "Routing techniques for massively parallel communication," Proc. IEEE (special issue on massively parallel computers) vol. 79, Apr. 1991.

[15]

{15} M. Fulgham, R. Cypher and J. Sam, "A comparison of SIMD hypercube routing strategies," RJ 7722 (71587), IBM Almaden Res. Ctr., 1990. (Also presented at the Proc. ICPP '91, Int. Conf. Parallel Processing, 1991.)

[16]

{16} L. Ni and P. McKinley, "A survey of routing techniques in wormhole networks," MSU-CPS-ACS-46, Dep. of Comput. Sci., Michigan State Univ., Oct. 1991.

[17]

{17} P. Kermani and L. Kleinrock, "Virtual Cut-Through: A new computer communication switching technique," Comput. Networks, no. 3, pp. 267-286, 1979.

[18]

{18} N. Pippenger, "Parallel communication with limited buffers," in Foundations of Computer Science, pp. 127-136, 1984.

[19]

{19} T. Leighton, B. Maggs, and S. Rao, "Universal packet routing algorithms," 1988.

[20]

{20} D. Gelernter, "A DAG-based algorithm for prevention of store-and-forward deadlock in packet networks," IEEE Trans. Comput., vol. C-30, pp. 709-715, Oct. 1981.

[21]

{21} S. Konstantinidou, "Adaptive, minimal routing in hypercubes," in 6th. MIT Conf. Advanced Res. in VLSI, 1990, pp. 139-153.

[22]

{22} Y. Birk, P. Gibbons, D. Soroker and J. Sanz, "A simple mechanism for efficient barrier synchronization in MIMD machines," RJ 7078 (67141) Comput. Sci., IBM Almaden Res. Ctr., Oct. 1989.

[23]

{23} K. Günther, "Prevention of deadlocks in packet-switched data transport system," IEEE Trans. on Communications, vol. com-29, April 1981.

[24]

{24} P. Merlin and P. Schweitzer, "Deadlock avoidance in store-and-forward networks. 1: Store-and-forward deadlock," IEEE Trans. Commun., vol. 28, March 1980.

[25]

{25} W. Dally and H. Aoki, "Adaptive Routing using Virtual Channels," tech. rep., MIT, 1990.

[26]

{26} T. Leighton, "Average case analysis of greedy routing algorithms on arrays," in SPAA, 1990.

[27]

{27} P. Raghavan and E. Upfal, "A theory of wormhole routing in parallel computers," RJ:8512 (76733), IBM Res., Dec. 1991.

[28]

{28} G. Pifarré, L. Gravano, S. Felperin and J. Sanz, "Fully-Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and Other Networks," in Proc. the 3rd Annu. ACM Symp. Parallel Algorithms and Architectures, 1991.

[29]

{29} R. Cypher and L. Gravano, "Adaptive deadlock-free packet routing in torus-networks with minimal storage," RJ:8571 (77350), IBM Almaden Res. Ctr., Jan. 1992. (Also presented at the ICPP'92.)

[30]

{30} R. Cypher and L. Gravano, "Requirements for deadlock-free, adaptive packet routing," tech. rep., IBM Almaden Res. Ctr., Feb. 1992. (Also presented at the PODC' 92.)

[31]

{31} K. Bolding and L. Snyder, "Mesh and torus chaotic routing," UW CS91-04-04, Univ. of Washington, 1991. Also presented at the MIT/Brown Advanced Res. in VLSI and Parallel Syst. Conf., Mar. 1992.

[32]

{32} W. Dally, "Virtual-Channel Flow Control, " in the 17th Annu. Int. Symp. Comput. Architecture, May 1990.

[33]

{33} D. Linder and J. Harden, "An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes," IEEE Trans. Comput., vol. 40, pp. 2-12, Jan. 1991.

Digital Library

[34]

{34} S. Felperin, L. Gravano, G. Pifarré, and J. Sanz, "Fully-adaptive routing: Packet switching performance and worm-hole algorithms," in Supercomputing, 1991.

[35]

{35} L. Gravano, G. Pifarré, S. Felperin, and J. Sanz, "Adaptive deadlock-free worm-hole routing with all minimal paths," TR: 91-21, IBM Argentina, CRAAG, Aug. 1991.

[36]

{36} P. Berman, L. Gravano, G. Pifarré, and J. Sanz, "Adaptive deadlock-and livelock-free routing with all minimal paths in torus networks," tech. rep., IBM Almaden Res. Ctr., 1992. (Also presented in ACM SPAA'92, San Diego, CA.)

[37]

{37} B. Hajek and A. Greenberg, "Deflection routing in hypercube networks," IEEE Trans. Commun., vol. 40, pp. 1070-1081, June 1992.

[38]

{38} B. Hajek, "Bounds on evacuation time for deflection routing," Distributed Computing, vol. 5, pp. 1-6, 1991.

Digital Library

[39]

{39} S. Felperin, H. Laffitte, G. Buranits, and J. Sanz, "Deadlock-free minimal packet routing in the torus network," TR: 91-22, IBM Argentina, CRAAG, 1991.

[40]

{40} G. Pifarré, L. Gravano, S. Felperin, and J. Sanz, "Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks," Tech. Rep., IBM Argentina, CRAAG, 1991.

Digital Library

[41]

{41} L. Valiant and G. Brebner, "Universal schemes for parallel communication," ACM STOC, pp. 263-277, 1981.

[42]

{42} L. Valiant, "Optimality of a two-phase strategy for routing in interconnection networks," Mar. 1982.

[43]

{43} E. Upfal, "Efficient schemes for parallel communication," JACM, vol. 31, pp. 507-517, July 1984.

Digital Library

[44]

{44} T. Leighton, D. Lisinski and B. Maggs, "Empirical evaluation of randomly-wired multistage networks," presented at the ICCD'90, 1990.

[45]

{45} S.Konstantinidou and E. Upfal, "Experimental comparison of multistage interconnection networks," RJ:8451 (76459). IBM Almaden Res. Ctr., Nov. 1991.

[46]

{46} R. Cypher and C. Plaxton, "Deterministic sorting in nearly logarithmic time on the hypercube and related computers," in 22nd. Annu. Symp. Theoy of Computing, 1990, pp. 193-203.

[47]

{47} D. Nassimi and S. Sahni, "Parallel permutation and sorting algorithms and a new generalized connection network," JACM, vol. 29, pp. 642-667, July 1982.

Digital Library

[48]

{48} J. Patel, "Performance of processor-memory interconnections for multiprocessors," IEEE Trans. Comput., vol. C-30, pp. 771-780, Oct. 1981.

[49]

{49} D. Dias and J. Jump, "Analysis and simulations of buffered delta networks," IEEE Trans. Comput., vol. C-30, pp. 273-282, Apr. 1981.

[50]

{50} G. Pfister and V. Norton, "'Hot Spot' contention and combining in multistage interconnection networks," IEEE Trans. Comput., vol. C-34, pp. 943-948, Oct. 1985.

[51]

{51} J. Ngai and C. Seitz, "Adaptive routing in multicomputers," in Opportunities and Constraints of Parallel Computing, J. Sanz, Ed. New York: Springer Verlag, 1989.

Cited By

Gajjar KJha AKumar MLahiri A(2024)Reconfiguring Shortest Paths in GraphsAlgorithmica10.1007/s00453-024-01263-y86:10(3309-3338)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00453-024-01263-y
Liu YRuan YLai Z(2013)New heuristic algorithms for low-energy mapping and routing in 3D NoCInternational Journal of Computer Applications in Technology10.1504/IJCAT.2013.05429747:1(1-13)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1504/IJCAT.2013.054297
Gajin SJovanović Z(2006)Explanation of Performance Degradation in Turn ModelThe Journal of Supercomputing10.1007/s11227-006-6454-y37:3(271-295)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1007/s11227-006-6454-y
Show More Cited By

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

Recommendations

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 ...
Storage-Efficient, Deadlock-Free Packet Routing Algorithms for Torus Networks

We present two new packet routing algorithms for parallel computers with torus interconnection networks of arbitrary size and dimension. Both algorithms use only minimal length paths, are fully adaptive in the sense that all minimal length paths may be ...
Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions

The simplicity of regular mesh topology Network on Chip (NoC) architecture leads to reductions in design time and manufacturing cost. A weakness of the regular shaped architecture is its inability to efficiently support cores of different sizes. A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 5, Issue 3

March 1994

115 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © Copyright © 1994 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 March 1994

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
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

Gajjar KJha AKumar MLahiri A(2024)Reconfiguring Shortest Paths in GraphsAlgorithmica10.1007/s00453-024-01263-y86:10(3309-3338)Online publication date: 1-Oct-2024
Liu YRuan YLai Z(2013)New heuristic algorithms for low-energy mapping and routing in 3D NoCInternational Journal of Computer Applications in Technology10.1504/IJCAT.2013.05429747:1(1-13)Online publication date: 1-Jun-2013
Gajin SJovanović Z(2006)Explanation of Performance Degradation in Turn ModelThe Journal of Supercomputing10.1007/s11227-006-6454-y37:3(271-295)Online publication date: 1-Sep-2006
Avresky DNatchev N(2005)Dynamic Reconfiguration in Computer Clusters with Irregular Topologies in the Presence of Multiple Node and Link FailuresIEEE Transactions on Computers10.1109/TC.2005.7654:5(603-615)Online publication date: 1-May-2005
Ok MPark M(2005)Minimizing hotspot delay by fully utilizing the link bandwidth on 2d mesh with virtual cut-through switchingProceedings of the 8th international conference on Parallel Computing Technologies10.1007/11535294_22(249-262)Online publication date: 5-Sep-2005
Solworth J(2002)Integrated Network BarriersIEEE Transactions on Parallel and Distributed Systems10.1109/71.99581413:4(337-348)Online publication date: 1-Apr-2002
Duato JYalamanchili SNi L(2002)Interconnection NetworksundefinedOnline publication date: 6-Aug-2002
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
Park HAgrawal D(2001)A Generic Design Methodology for Deadlock-Free Routing in Multicomputer NetworksJournal of Parallel and Distributed Computing10.1006/jpdc.2001.174861:9(1225-1248)Online publication date: 1-Sep-2001
Aronson L(2000)Homogeneous Routing for Homogeneous Traffic Patterns on MeshesIEEE Transactions on Parallel and Distributed Systems10.1109/71.87793711:8(781-793)Online publication date: 1-Aug-2000
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents