research-article

A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of Resources

Authors:

J. Duato,

T. M. PinkstonAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 12, Issue 12

Pages 1219 - 1235

https://doi.org/10.1109/71.970556

Published: 01 December 2001 Publication History

Publisher Site

Abstract

This paper presents a theoretical framework for the design of deadlock-free fully adaptive routing algorithms for a general class of network topologies and switching techniques in a single, unified theory. A general theory is proposed that allows the design of deadlock avoidance-based as well as deadlock recovery-based wormhole and virtual cut-through adaptive routing algorithms that use a homogeneous or a heterogeneous (mixed) set of resources. The theory also allows channel queues to be allocated nonatomically, utilizing resources efficiently. A general methodology for the design of fully adaptive routing algorithms applicable to arbitrary network topologies is also proposed. The proposed theory and methodology allow the design of efficient network routers that require minimal resources for handling infrequent deadlocks.

References

[1]

CS. Stunkel et al., 'The SP2 High-Performance Switch," IBM Systems J., vol. 34, no. 2, pp. 185-204, 1995.]]

Digital Library

Google Scholar

[2]

S.L. Scott and G.M. Thorson, "The Cray T3E Network; Adaptive Routing in a High Performance 3D Torus," Proc. Symp. Hot Interconnects IV, pp. 147-156, Aug. 1996.]]

Google Scholar

[3]

3. Laudon and 0. Lenoski, "The SGI Origin: A ccNUMA Mighty Scalable Server," Proc. 24th Int'l Symp. Computer Architecture, pp. 241-251, June 1997.]]

Digital Library

Google Scholar

[4]

M.D. Schroeder et al., "Autonet; A High-Speed, Self-Configuring Local Area Network Using Point-to-Point Links,' Technical Report SRC Research Report 59 (DEC), Apr. 1990.]]

Google Scholar

[5]

N. 3. Boden, D. Cohen, RE. Feiderman, A.E. Dulawik, C.L. Seitz, J. Seizovic, and W. Su, "Myrinet-A Gigabit per Second Local Area Network," IEEE Micro, vol. 15, no. 1, pp. 29-36, Feb. 1995.]]

Digital Library

Google Scholar

[6]

0. Garcia and W. Watson, "ServerNet 11," Proc. Second Parallel Computer Routing Comm. Workshop, pp. 119-135, June 1997.]]

Google Scholar

[7]

W. Daily and C. Seitz, "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks," IEEE Trans. Computers, vol. 36, no. 5, pp. 547-553, May 1987.]]

Digital Library

Google Scholar

[8]

P. Kerrnani and L. Kleinrock, "Virtual Cut-Through; A New Computer Communication Switching Technique," Computer Networks, pp. 267-286, 1979.]]

Google Scholar

[9]

R Horst, "ServerNet Deadlock Avoidance and Fractahedral Topologies," Proc. Int'l Parallel Processing Symp, pp. 275-280, Apr 1996.]]

Digital Library

Google Scholar

[10]

J Carbonate, "Cavallino; The Terafiops Router and NEC," Proc. Syinp Hot Interconnects IV, pp. 157-160, Aug. 1996.]]

Google Scholar

[11]

M. Galles, "Spider; A High Speed Network interconnect," Proc. Symp. Hot Interconnects IV, pp. 141-146, Aug. 1996.]]

Google Scholar

[12]

S.L. Scott and J. Goodman, "The Impact of Pipelined Channels on k-Ary n-Cube Networks," IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 1, pp. 1-16, Jan. 1994.]]

Digital Library

Google Scholar

[13]

W. Daily, 'Virtual Channel Flow Control," IEEE Trans. Parallel and Distributed Systems, vol. 3, no. 2, pp. 194-205, Mar. 1992.]]

Digital Library

Google Scholar

[14]

F. Sills, M.P. Malumbres, A. Robles, P. Lopez, and J. Duato, "Efficient Adaptive Routing in Networks of Workstations with Irregular Topogy," Proc. Workshop Comm., Architecture, and Applications for Network-Based Parallel Computing, Feb. 1997.]]

Digital Library

Google Scholar

[15]

F. Silla and 3. Doom, "On the Use of Virtual Channels in Networks of Workstations with Irregular Topology." Proc. Second Parallel Computer Routing Comm. Workshop, pp. 203-216, June 1997.]]

Google Scholar

[16]

5. Konstantinidou and L. Snyder, "Chaos Router; Architecture and Performance," Proc. 18th Int'l Symp. Computer Architecture, pp. 212221, May 1991.]]

Digital Library

Google Scholar

[17]

D. Linder and 3. Harden, "An Adaptive and Fault Tolerant Wormhole Routing Strategy for kAry n-Cubes," IEEE Trans Computers, vol. 40, no. 1, pp. 2-12, Jan. 1991.]]

Digital Library

Google Scholar

[18]

W. Daily and H. Aoki, "Deadlock-Free Adaptive Routing in Multicomputer Networks using Virtual Channels," IEEE Trans. Parallel and Distributed Systems, vol. 4, no, 4, pp. 466-475, Apr. 1993.]]

Digital Library

Google Scholar

[19]

J. Duato, "A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks," IEEE Trans. Parallel and Distributed Systems, vol. 4, no. 12, pp. 1320-1331, Dec. 1993.]]

Digital Library

Google Scholar

[20]

J. Kim, Z. Liu, and A. Chien, "Compressioniess Routing; A Framework for Adaptive and Fault-Tolerant Routing," Proc. 21st Int'l Symp. Computer Architecture, pp. 289-300, Apr. 1994.]]

Digital Library

Google Scholar

[21]

Anjan K.V. and TM. Pinkston, "An Efficient, Fully Adaptive Deadlock Recovery Scheme: DISHA," Proc. 22nd Int'l Symp. Computer Architecture, pp. 201-210, June 1995.]]

Digital Library

Google Scholar

[22]

P. Palazzari and M. Coli, "Virtual Cut-Through Implementation of the Hole-Based Packet Switching Routing Algorithm," Proc. Sixth Euromicro Workshop Parallel and Distributed Processing, pp. 416-421, Jan. 1998.]]

Crossref

Google Scholar

[23]

W. Daily, L. Dennison, D. Harris, K. Kan, and T. Zanthopoulos, "Architecture and Implementation of the Reliable Router," Proc. Hot Interconnects It Symp., Aug. 1994.]]

Crossref

Google Scholar

[24]

TM. Pinkston, Y. Choi, and M. Raksapatcharawong, "Architecture and Optoelectronic Implementation of the WARRP Router," Proc. Fifth Symp. Hot Interconnects, pp. 181-189, Aug. 1997.]]

Google Scholar

[25]

J. Duato, "A Necessary and Sufficient Condition for DeadlockFree Adaptive Routing in Wormhole Networks," IEEE Trans. Parallel and Distributed Systems, vol. 6, no, 10, pp. 10551067. Oct. 1995.]]

Digital Library

Google Scholar

[26]

Anjan K.V., TM. Pinkston, and J. Duato, "Generalized Theory for Deadlock-Free Adaptive Wormhole Routing and Its Application to Disha Concurrent," Proc. 10th Int'l Parallel Processing Symp, pp. 815-821, Apr. 1996.]]

Digital Library

Google Scholar

[27]

TM. Pinkston, "Flexible and Efficient Routing Based on Progressive Deadlock Recovery," IEEE Trans. Computers, vol. 48, no. 7, pp. 649-669, July 1999.]]

Digital Library

Google Scholar

[28]

5. Scott and G. Thorson, "Optimized Routing in the Cray T3D," Proc. Workshop Parallel Computer Routing and Comm., pp. 281-294, May 1994.]]

Digital Library

Google Scholar

[29]

L.-S. Peh and W. Daily, "A Delay Model for Router Microarchitectures," IEEE Micro, vol. 21, no. 1, pp. 26-34, Jan/Feb. 2001.]]

Digital Library

Google Scholar

[30]

J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach. Los Alamitos, Calif.; IEEE CS Press, 1997.]]

Digital Library

Google Scholar

[31]

5. Warnakulasuriya and TM. Pinkston, "Characterization of Deadlocks in Irregular Networks," Proc 1999 Int'l Coif Parallel Processing, pp. 75-84, Sept. 1999.]]

Digital Library

Google Scholar

[32]

S. Wamakulasuriya and TM. Pinkston, "Characterization of Deadlocks in k-Ary n-Cube Networks," IEEE Trans. Parallel and Distributed Systems, vol. 10, no. 9, pp. 904-921, Sept. 1999,]]

Digital Library

Google Scholar

[33]

P. Lopez, 3M. Martinez, and 3, Duato, "A Very Efficient Distributed Deadlock Detection Mechanism for Wormhole Networks," Proc. High Performance Computer Architecture Symp., pp. 57-66, Feb. 1998.]]

Digital Library

Google Scholar

[34]

TM. Pinkston and S. Warnakulasuriya, "On Deadlocks in Interconnection Networks," Proc. 24th Int'l Symp. Computer Architecture, pp. 38-49, June 1997.]]

Digital Library

Google Scholar

[35]

3M. Martinez, P. Lopez, J. Duato, and TM. Pinkston, "SoftwareBased Deadlock Recovery for True Fully Adaptive Routing in Wormhole Networks," Proc. 1997 Int'l Conf. Parallel Processing, pp. 182-189, Aug. 1997.]]

Digital Library

Google Scholar

[36]

s. Tamir and G. Frazier, "Dynamically-Allocated Multi-Queue Buffers for VLSI Communication Switches," IEEE Trans. Computers, vol. 41, no, 6, pp. 725-734, June 1990,]]

Digital Library

Google Scholar

[37]

J. Duato, "A Necessary and Sufficient Condition for DeadlockFree Routing in Cut-Through and Store-and-Forward Networks," IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 8, pp. 841854, Aug. 1996.]]

Digital Library

Google Scholar

[38]

S. Warnakulasuriya and T.M. Pinkston, "A Formal Model of Message Blocking and Deadlock Resolution in Interconnection Networks," IEEE Trans. Parallel and Distributed Systems, vol. 11, no, 3, pp. 212-229, Mar. 2000.]]

Digital Library

Google Scholar

[39]

3. Duato, "A Necessary and Sufficient Condition for DeadlockFree Adaptive Routing in Wormhole Networks,' Proc. 1994 Int'l Conf. Parallel Processing, vol. 1, pp. 142-149, Aug. 1994.]]

Digital Library

Google Scholar

[40]

F. Petrini and M. Vanneschi, "Performance Analysis of Minimal Adaptive Wormhole Routing with Time-Dependent Deadlock Recovery," Proc. 11th Int'l Parallel Processing Syrnp., pp. 589-595, Apr. 1997.]]

Digital Library

Google Scholar

[41]

Anjan Ky. and T.M. Pinkston, "DISHA; A Deadlock Recovery Scheme for Fully Adaptive Routing," Proc. Ninth Int'l Parallel Processing Symp., pp. 537-543, Apr. 1995.]]

Digital Library

Google Scholar

[42]

X. Lin and L.M. Ni, "Multicast Communication in Multicomputer Networks," IEEE Trans. Parallel and Distributed Systems, vol. 4, no. 10, pp. 1104-1117, Oct. 1993.]]

Digital Library

Google Scholar

[43]

CD. Pifarre et al., "Fully Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and Other Networks: Algorithms and Simulations," IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 3, pp. 247-263, Mar. 1994.]]

Digital Library

Google Scholar

[44]

X. Lin, P.K. McKinley, and L.M. Ni, "The Message Flow Model for Routing in WormholeRouted Networks," IEEE Trans. Parallel and Distributed Systems, vol. 6, no. 7, pp. 755-760, July 1995.]]

Digital Library

Google Scholar

[45]

L. Schwiebert and U.N. Jayasimha, "A Universal Proof Technique for Deadlock-Free Routing in Interconnection Networks," Proc. Symp. Parallel Algorithms and Architecture, pp. 175-184, July 1995.]]

Digital Library

Google Scholar

[46]

L. Schwiebert and D.N. Jayasimha, "A Necessary and Sufficient Condition for DeadlockFree Wormhole Routing," J. Parallel and Distributed Computing, vol. 32, no. 1, pp. 103-117, Jan. 1996.]]

Digital Library

Google Scholar

[47]

B. Abali, "A Deadlock Avoidance Method for Computer Networks," Proc. Workshop Comm. and Architectural Support for Network-Based Parallel Computing, pp. 61-72, Feb. 1997.]]

Digital Library

Google Scholar

[48]

W. Qiao and L.M. Ni, "Adaptive Routing in Irregular Networks Using Cut-Through Switches," Proc. 1996 Int'l Conf. Parallel Processing, pp. 52-60, Aug. 1996.]]

Google Scholar

[49]

P.M. Merlin and P.3. Schweitzer, "Deadlock Avoidance in Storeand-Forward Networks-I: Store-and-Forward Deadlock," IEEE Trans. Comm., vol. 3, pp. 345-354, Mar. 1980.]]

Crossref

Google Scholar

[50]

K.D. Gunther, "Prevention of Deadlocks in Packet-Switched Data Transport Systems," IEEE Trans. Comm., vol. 4, pp. 512-524, Apr. 1981.]]

Crossref

Google Scholar

[51]

F. Fleury and P. Fraigniaud, "A General Theory for Deadlock Avoidance in WormholeRouted Networks," IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 7, pp. 626-638, July 1998.]]

Digital Library

Google Scholar

[52]

P.T. Gaughan and S. Yalamanchili, "A Family of Fault-Tolerant Routing Protocols for Direct Multiprocessor Networks," IEEE Trans. Parallel and Distributed Systems, vol. 6, no. 5, pp. 482-497, May 1995.]]

Digital Library

Google Scholar

[53]

CR. Jesshope, P.R. Miller, and J.T. Yantchev, "High Performance Communications in Processor Networks," Proc. 16th Int'l Symp. Computer Architecture, pp. 150-157, May 1989.]]

Digital Library

Google Scholar

[54]

D.S. Reeves, E.F. Gehringer, and A. Chandiramani, 'Adaptive Routing and Deadlock Recovery: A Simulation Study," Proc. Fourth Conf. Hypercube Concurrent Computers and Applications, Mar. 1989.]]

Google Scholar

[55]

3. Kim, Z. Liu, and A. Chien, "Compressionless Routing: A Framework for Adaptive and Fault-Tolerant Routing," IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 3, pp. 229244, Mar. 1997.]]

Digital Library

Google Scholar

[56]

M. Coli and P. Palazzari, "An Adaptive Deadlock and Livelock Free Routing Algorithm," Proc. Third Euromicro Workshop Parallel and Distributed Processing, pp. 288-295, Jan. 1995.]]

Digital Library

Google Scholar

[57]

C. Carrion, R. Beivide, {A. Gregorio, and F. Vallejo, "A Flow Control Mechanism to Prevent Message Deadlock in k-Ary n-Cube Networks," Proc. 1997 Int'l Conf. High Performance Computing, Dec. 1997.]]

Digital Library

Google Scholar

Cited By

View all

Yang YLi TDai YWang BMa SSun Y(2023)Absorb: Deadlock Resolution for 2.5D Modular Chiplet Based SystemsAlgorithms and Architectures for Parallel Processing10.1007/978-981-97-0834-5_27(474-487)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-97-0834-5_27
Picornell TFlich JHernández CDuato J(2021)Enforcing Predictability of Many-Cores With DCFNoCIEEE Transactions on Computers10.1109/TC.2020.298779770:2(270-283)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1109/TC.2020.2987797
Dai YLu KChang JQi XCao JZhang J(2021)Microarchitecture of a Configurable High-Radix Router for the Post-Moore EraHigh Performance Computing10.1007/978-3-030-78713-4_1(3-17)Online publication date: 24-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-78713-4_1
Show More Cited By

Index Terms

A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of Resources

Recommendations

Adaptive-Trail Routing and Performance Evaluation in Irregular Networks Using Cut-Through Switches

Cut-through switching promises low latency delivery and has been used in new generation switches, especially in high speed networks demanding low communication latency. The interconnection of cut-through switches provides an excellent network platform ...
Adaptive Deadlock- and Livelock-Free Routing in the Hypercube Network

This paper consists of two parts. In the first one, two new algorithms for wormholerouting on the hypercube network are presented. These techniques are adaptive and areensured to be deadlock- and livelock-free. These properties are guaranteed by using ...
Efficient deadlock-free wormhole routing in shuffle based networks
SPDP '95: Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing

To provide deadlock-free wormhole routing in simple regular networks, virtual channels have recently been introduced. This paper presents a deadlock-free routing scheme for a class of shuffle-based directed and undirected networks. First, the network ...

Reviews

Reviewer: Maulik A Dave

When programming communicating network-based systems, deadlocks are a major concern. The currently popular network model typically consists of a network of routers, with each router connected to processor nodes. Network routing algorithms can be deadlock avoidance-based, or deadlock recovery-based. This paper presents a theoretical framework for designing routing algorithms to be used by routers. The theory works for any class of network topology and for switching networks. It is general enough to cover both avoidance and recovery-based routing algorithms. The routing algorithm derived from this theory can use mixed resources (various types of queues), making this a doubly general theory. The theory consists of three theorems, which are nothing but conditions for deadlock freedom. The paper presents the necessary formalism for the problem, and states the assumptions. It then describes the theorems, and their proofs. The paper also discusses how a routing algorithm can be designed using the theory, providing two examples. In the concluding section, the paper claims that by relaxing the atomic queue allocation requirement, the theory allows resources to be used more efficiently than in previous theories. On the whole, this paper will be useful as a reference for designers of routing algorithms who are seeking freedom from deadlocks. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

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 12, Issue 12

December 2001

148 pages

ISSN:1045-9219

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2001

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yang YLi TDai YWang BMa SSun Y(2023)Absorb: Deadlock Resolution for 2.5D Modular Chiplet Based SystemsAlgorithms and Architectures for Parallel Processing10.1007/978-981-97-0834-5_27(474-487)Online publication date: 20-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-97-0834-5_27
Picornell TFlich JHernández CDuato J(2021)Enforcing Predictability of Many-Cores With DCFNoCIEEE Transactions on Computers10.1109/TC.2020.298779770:2(270-283)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1109/TC.2020.2987797
Dai YLu KChang JQi XCao JZhang J(2021)Microarchitecture of a Configurable High-Radix Router for the Post-Moore EraHigh Performance Computing10.1007/978-3-030-78713-4_1(3-17)Online publication date: 24-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-78713-4_1
Parasar MJerger NGratz PMiguel JKrishna T(2019)SWAPProceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3352460.3358255(873-885)Online publication date: 12-Oct-2019
https://dl.acm.org/doi/10.1145/3352460.3358255
Qian KCheng WZhang TRen FWu JHall W(2019)Gentle flow controlProceedings of the ACM Special Interest Group on Data Communication10.1145/3341302.3342065(75-89)Online publication date: 19-Aug-2019
https://dl.acm.org/doi/10.1145/3341302.3342065
McDonald NIsaev MFlores ADavis AKim JTaufer MBalaji PPeña A(2019)Practical and efficient incremental adaptive routing for HyperX networksProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3295500.3356151(1-13)Online publication date: 17-Nov-2019
https://dl.acm.org/doi/10.1145/3295500.3356151
Hu SZhu YCheng PGuo CTan KPadhye JChen K(2019)TaggerIEEE/ACM Transactions on Networking10.1109/TNET.2019.290287527:2(889-902)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2902875
Ramrakhyani AGratz PKrishna T(2018)Synchronized progress in interconnection networks (SPIN)Proceedings of the 45th Annual International Symposium on Computer Architecture10.1109/ISCA.2018.00064(699-711)Online publication date: 2-Jun-2018
https://dl.acm.org/doi/10.1109/ISCA.2018.00064
Hu SZhu YCheng PGuo CTan KPadhye JChen K(2017)TaggerProceedings of the 13th International Conference on emerging Networking EXperiments and Technologies10.1145/3143361.3143382(451-463)Online publication date: 28-Nov-2017
https://dl.acm.org/doi/10.1145/3143361.3143382
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
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Adaptive-Trail Routing and Performance Evaluation in Irregular Networks Using Cut-Through Switches

Adaptive Deadlock- and Livelock-Free Routing in the Hypercube Network

Efficient deadlock-free wormhole routing in shuffle based networks

Reviews

Access critical reviews of Computing literature here

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