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

research-article

A tool for automatic detection of deadlock in wormhole networks on chip

Authors:

Jean-Lou Desbarbieux,

Emmanuelle EncrenazAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 13, Issue 1

Article No.: 6, Pages 1 - 22

https://doi.org/10.1145/1297666.1297672

Published: 06 February 2008 Publication History

Abstract

We present an extension of Duato's necessary and sufficient condition a routing function must satisfy in order to be deadlock-free, to support environment constraints inducing extra-dependencies between messages. We also present an original algorithm to automatically check the deadlock-freeness of a network with a given routing function. A prototype tool has been developed and automatic deadlock checking of large scale networks with various routing functions have been successfully achieved. We provide comparative results with standard approach, highlighting the benefits of our method.

References

[1]

Bjerregaard, T. and Sparso, J. 2005. A router architecture for connection-oriented service guarantees in the MANGO clockless network-on-chip. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE). IEEE Computer Society, Washington, DC, 1226--1231.

Digital Library

[2]

Bolotin, E., Cidon, I., Ginosar, R., and Kolodny, A. 2004. QNoC: QoS architecture and design process for network on chip. J. Syst. Archit. 50, 2-3, 105--128.

Digital Library

[3]

Bolotin, E., Cidon, I., Ginosar, R., and Kolodny, A. 2007. Routing table minimization for irregular mesh NoCs. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE).

Digital Library

[4]

Charlery, H., Greiner, A., Encrenaz, E., Mortiez, L., and Andriahantenaina, A. 2004. Using VCI in a on-chip system around SPIN network. In Proceedings of the 11th International Conference on Mixed Design of Integrated Circuits and Systems. 571--576.

[5]

Chien, A. A. 1998. A cost and speed model for k-ary n-cube wormhole routers. IEEE Trans. Paral. Distrib. Syst. 9, 2, 150--162.

Digital Library

[6]

Dally, W. J. and Seitz, C. L. 1987. Deadlock-free message routing in multiprocessor interconnection networks. IEEE Trans. Comput. 36, 5, 547--553.

Digital Library

[7]

Dally, W. J. and Towles, B. 2001. Route packets, not wires: On-chip interconnection networks. In Proceedings of the ACM 10th Annual Conference on Design Automation. 684--689.

Digital Library

[8]

Duato, J. 1991. On the design of deadlock-free adaptive routing algorithms for multicomputers: Design methodologies. In Proceedings of the Parallel Architectures and Languages Europe. 505, 390--405.

Digital Library

[9]

Duato, J. 1995. A necessary and sufficient condition for deadlock-free adaptive routing in wormhole networks. IEEE Trans. Paral. Distrib. Syst. 6, 10, 1055--1067.

Digital Library

[10]

Fleury, E. and Fraigniaud, P. 1998. A general theory for deadlock avoidance in wormhole-routed networks. IEEE Trans. Paral. Distrib. Syst. 9, 7, 626--638.

Digital Library

[11]

Goossens, K., Dielissen, J., Gangwal, O. P., Pestana, S. G., Radulescu, A., and Rijpkema, E. 2005. A design flow for application-specific networks on chip with guaranteed performance to accelerate SOC design and verification. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE). IEEE Computer Society, 1182--1187.

Digital Library

[12]

Goossens, K., Dielissen, J., and Radulescu, A. 2005. AEthereal network on chip: Concepts, architectures, and implementations. IEEE Design and Test of Computers 22, 5, 414--421.

Digital Library

[13]

Guerrier, P. and Greiner, A. 2000. A generic architecture for on-chip packet-switched interconnections. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE). IEEE Computer Society, 250--256.

Digital Library

[14]

Ianni, M. D. 1997. Wormhole deadlock prediction. In Proceedings of the European Conference on Parallel Computing. (Euro-Par). C. Lengauer, M. Griebl, and S. Gorlatch, Eds. Lecture Notes in Computer Science, vol. 1300. Springer, 188--195.

Digital Library

[15]

Jayasimha, D. N., Schwiebert, L., Manivannan, D., and May, J. A. 2003. A foundation for designing deadlock-free routing algorithms in wormhole networks. J. ACM 50, 2, 250--275.

Digital Library

[16]

Kim, J., Park, D., Theocharides, T., Vijaykrishnan, N., and Das, C. R. 2005. A low latency router supporting adaptivity for on-chip interconnects. In Proceedings of the 42nd Annual Conference on Design Automation (DAC). ACM Press, New York, NY, 559--564.

Digital Library

[17]

Knuth, D. E. 1993. The Stanford GraphBase: A Platform for Combinatorial Computing.

[18]

Lin, X., McKinley, P. K., and Ni, L. M. 1995. The message flow model for routing in wormhole-routed networks. IEEE Trans. Paral. Distrib. Syst. 6, 7, 755--760.

Digital Library

[19]

Ni, L. M. and McKinley, P. K. 1993. A survey of wormhole routing techniques in direct networks. Comput. 26, 2, 62--76.

Digital Library

[20]

Panades, I. M., Greiner, A., and Sheibanyrad, A. 2006. A low cost network-on-chip with guaranteed service well suited to the GALS approach. NanoNet.

[21]

Schwiebert, L. and Jayasimha, D. N. 1996. A necessary and sufficient condition for deadlock-free wormhole routing. J. Parall. Distrib. Comput. 32, 1, 103--117.

Digital Library

[22]

Stergiou, S., Angiolini, F., Carta, S., Raffo, L., Bertozzi, D., and Micheli, G. D. 2005. ×pipes Lite: A synthesis oriented design library for networks on chips. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE). IEEE Computer Society, Washington, DC, 1188--1193.

Digital Library

Cited By

Sathis Kumar KParamasivam K(2022)Novel Power-Aware Optimization Methodology and Efficient Task Scheduling AlgorithmComputer Systems Science and Engineering10.32604/csse.2022.01953141:1(209-224)Online publication date: 2022
https://doi.org/10.32604/csse.2022.019531
Charif ACoelho AZergainoh NNicolaidis M(2020)A Dynamic Sufficient Condition of Deadlock-Freedom for High-Performance Fault-Tolerant Routing in Networks-on-ChipsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2017.27769098:3(642-654)Online publication date: 1-Jul-2020
https://doi.org/10.1109/TETC.2017.2776909
Verbeek FYaghini PEghbal ABagherzadeh N(2018)A Compositional Approach for Verifying Protocols Running on On-Chip NetworksIEEE Transactions on Computers10.1109/TC.2017.278672367:7(905-919)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1109/TC.2017.2786723
Show More Cited By

Index Terms

A tool for automatic detection of deadlock in wormhole networks on chip
1. Hardware
  1. Communication hardware, interfaces and storage
    1. Buses and high-speed links
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Formal software verification
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods

Recommendations

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 ...
Deadlock Avoidance for Switches Based on Wormhole Networks
ICPP '99: Proceedings of the 1999 International Conference on Parallel Processing

We consider the use of wormhole routed networks as internal interconnects of switches. The interconnection of two wormhole networks that are free from deadlocks does not necessarily produce a deadlock free network. This is problematic when wormhole ...
Multidestination Message Passing in Wormhole k-ary n-cube Networks with Base Routing Conformed Paths

This paper proposes multidestination message passing on wormhole k-ary n-cube networks using a new base-routing-conformed-path (BRCP) model. This model allows both unicast (single-destination) and multidestination messages to co-exist in a given network ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 13, Issue 1

January 2008

496 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1297666

Issue’s Table of Contents

Copyright © 2008 ACM.

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

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 06 February 2008

Accepted: 01 July 2007

Revised: 01 June 2007

Received: 01 June 2006

Published in TODAES Volume 13, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
393
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sathis Kumar KParamasivam K(2022)Novel Power-Aware Optimization Methodology and Efficient Task Scheduling AlgorithmComputer Systems Science and Engineering10.32604/csse.2022.01953141:1(209-224)Online publication date: 2022
https://doi.org/10.32604/csse.2022.019531
Charif ACoelho AZergainoh NNicolaidis M(2020)A Dynamic Sufficient Condition of Deadlock-Freedom for High-Performance Fault-Tolerant Routing in Networks-on-ChipsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2017.27769098:3(642-654)Online publication date: 1-Jul-2020
https://doi.org/10.1109/TETC.2017.2776909
Verbeek FYaghini PEghbal ABagherzadeh N(2018)A Compositional Approach for Verifying Protocols Running on On-Chip NetworksIEEE Transactions on Computers10.1109/TC.2017.278672367:7(905-919)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1109/TC.2017.2786723
Poornajaf M(2018)Optimizing of Deadlock Detection Methods in Routing of Multicomputer Networks by Fuzzy Here TechniquesFundamental Research in Electrical Engineering10.1007/978-981-10-8672-4_57(757-763)Online publication date: 26-Jul-2018
https://doi.org/10.1007/978-981-10-8672-4_57
Poornajaf M(2018)Deadlock Detection in Routing of Interconnection Networks Using Blocked Channel Fuzzy Method and Traffic Average in Input and Output ChannelsFundamental Research in Electrical Engineering10.1007/978-981-10-8672-4_56(749-756)Online publication date: 26-Jul-2018
https://doi.org/10.1007/978-981-10-8672-4_56
Gholami SSarjoughian H(2017)Modeling and verification of network-on-chip using constrained-DEVSProceedings of the Symposium on Theory of Modeling & Simulation10.5555/3108905.3108914(1-12)Online publication date: 23-Apr-2017
https://dl.acm.org/doi/10.5555/3108905.3108914
Verbeek FYaghini PEghbal ABagherzadeh N(2017)Deadlock Verification of Cache Coherence Protocols and Communication FabricsIEEE Transactions on Computers10.1109/TC.2016.258406066:2(272-284)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TC.2016.2584060
Hu WGuo HZhang KLiu JLiu XShi Q(2017)An energy-efficient design of microkernel-based on-chip OS for NOC-based manycore systemThe Journal of Supercomputing10.1007/s11227-016-1700-473:8(3344-3365)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s11227-016-1700-4
ZhuanSun ZLi KChen G(2017)Multipath routing algorithm for application‐specific wormhole NoCsConcurrency and Computation: Practice and Experience10.1002/cpe.402729:16Online publication date: 29-Mar-2017
https://doi.org/10.1002/cpe.4027
Kashif HPatel HFischmeister S(2016)Path Selection for Real-Time Communication on Priority-Aware NoCsACM Transactions on Design Automation of Electronic Systems10.1145/286657221:3(1-25)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2866572
Show More Cited By

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents