Abstract
Relentless technology downscaling provides a promising prospect to realize heterogeneous system-on-chip (SoC) and homogeneous chip-multiprocessor (CMP) based on the networks-on-chip (NoCs) paradigm with augmented scalability, modularity and performance. In many cases in such systems, scheduling and managing communication resources are the major design and implementation challenges instead of the computing resources. Moreover, adaptive packets routing in such systems are susceptible to routing deadlock, which could lead to performance degradation or system failure. Past research efforts were mainly focused on complex design-time approaches to avoid deadlock or simple heuristic run-time approaches to detect and recover from deadlock. The later, however, consider only local or partial information about the network which may produce substantial false detections, especially with the network close to saturation where blocked packets could be fagged as deadlocked.This chapter studies deadlock detection and recovery strategy in NoCs as opposed to deadlock avoidance. It presents a deadlock detection method that utilizes run-time transitive-closure (TC) computation to discover the existence of deadlock-equivalence sets, which imply loops of requests in NoCs. This detection scheme guarantees the discovery of all true-deadlocks without false alarms in contrast with state-of-the-art approximation and heuristic methods. A distributed TC-network architecture, which couples with the network-on-chip (NoC) infrastructure, is also presented to realize the detection mechanism efficiently. Detailed hardware realization architectures and schematics are also discussed. The captured results based on a cycle-accurate simulator demonstrate the effectiveness of the proposed method. It drastically outperforms timing-based deadlock detection mechanisms by eliminating false detections and, thus, reducing energy wastage in retransmission for various traffic scenarios including real-world application.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This kind of traffic pattern is the most commonly used traffic in network evaluation [14], even though it is very gentle because it naturally balances the load all over the network.
- 2.
Each node with binary address {b n−1, b n−2, \(\ldots\), b 0} sends a packet to the node with address {b 0, b 1, \(\ldots\), b n−1}.
- 3.
A network starts saturating when an increase in injection rate does not result in a linear increase in throughput [6].
References
R. Al-Dujaily, T. Mak, F. Xia, A. Yakovlev, M. Palesi, Run-time deadlock detection in networks-on-chip using coupled transitive closure networks, in Design, Automation Test in Europe Conference Exhibition (DATE), Grenoble-France, Mar 2011, pp. 1–6
R. Al-Dujaily, T. Mak, F. Xia, A. Yakovlev, M. Palesi, Embedded transitive closure network for runtime deadlock detection in networks-on-chip. IEEE Trans. Parallel Distrib. Syst. 23(7), 1205–1215 (2012)
K.V. Anjan, T.M. Pinkston, DISHA: a deadlock recovery scheme for fully adaptive routing, in Proceedings of the 9th International Parallel Processing Symposium, Santa Barbara-CA, 1995, pp. 537–543
K.V. Anjan, T.M. Pinkston, J. Duato, Generalized theory for deadlock-free adaptive wormhole routing and its application to disha concurrent. Proc. 10th Int. Parallel Processing Symp., Honolulu-Hawaii, Apr. 1996. IEEE Computer Society
G. Ascia, V. Catania, M. Palesi, Multi-objective mapping for mesh-based noc architectures, in Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, Stockholm, Sweden (ACM), pp. 182–187 (2004).
G. Ascia, V. Catania, M. Palesi, D. Patti, Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip. IEEE Trans. Comput. 57(6), 809–820 (2008)
L. Benini, G. De Micheli, Networks on chips: a new SoC paradigm. IEEE Comput. 35(1), 70–78 (2002)
A. Chandrakasan, J.M. Rabaey, B. Nikolic, Digital Integrated Circuits: A Design Perspective (Prentice Hall, London/Upper Saddle River, 2002)
G-M Chiu, The odd-even turn model for adaptive routing. IEEE Trans. Parallel Distrib. Syst. 11(7), 729–738 (2000)
J.G. Christopher, L.M. Ni, The turn model for adaptive routing. Proc. Int. Parallel Process. Symp. 41(5), 874–902 (1994)
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms (MIT/McGraw-Hill, Cambridge, Mass., 2001)
W.J. Dally, C.L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks. IEEE Trans. Comput. C-36(5), 547–553 (1987)
W.J. Dally, B. Towles, Route packets, not wires: on-chip interconnection networks, DAC’2001, Las Vegas, Nevada, USA (ACM) pp. 684–689, (2001)
W.J. Dally, B. Towles, Principles and Practices of Interconnection Networks (Morgan Kaufmann, Amsterdam/San Francisco, 2004)
J. Duato, S. Yalamanchili, L.M. Ni, Interconnection Networks: An Engineering Approach (Morgan Kaufmann/San Francisco, CA, 2003)
F. Fazzino, M. Palesi, D. Patti, Noxim: network-on-chip simulator, 2010, http://noxim.sourceforge.net/
J. Hu, R. Marculescu, Energy- and performance-aware mapping for regular noc architectures. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 24(4), 551–562 (2005)
J.H. Kim, L. Ziqiang, A.A. Chien, Compressionless routing: a framework for adaptive and fault-tolerant routing. IEEE Trans. Parallel Distrib. Syst. 8(3), 229–244 (1997)
S-Y. Kung, S-C. Lo, P.S. Lewis, Optimal systolic design for the transitive closure and the shortest path problems. IEEE Trans. Comput. C-36(5), 603–614 (1987)
K.P. Lam, C.W. Tong, Closed semiring connectionist network for the Bellman-Ford computation. IEE Proc. Comput. Digit. Tech. 143(3), 189–195 (1996)
A. Lankes, T. Wild, A. Herkersdorf, S. Sonntag, R. Reinig, Comparison of deadlock recovery and avoidance mechanisms to approach message dependent deadlocks in on-chip networks, in NOCS’10, Grenoble-France, 2010, pp. 17–24
P. Lopez, J.M. Martinez-Rubio, J. Duato, A very efficient distributed deadlock detection mechanism for wormhole networks, in HPCA’98, Las Vegas-Nevada (IEEE Computer Society, 1998)
T. Mak, P.Y.K. Cheung, W. Luk, K.P. Lam, A DP-network for optimal dynamic routing in network-on-chip, in CODES+ISSS’09, Grenoble-France (ACM, 2009), pp. 119–128
J.M. Martínez-Rubio, P. López, J. Duato, A cost-effective approach to deadlock handling in wormhole networks. IEEE Trans. Parallel Distrib. Syst. 12(7), 716–729 (2001)
J.M. Martinez-Rubio, P. Lopez, J. Duato, FC3D: flow control-based distributed deadlock detection mechanism for true fully adaptive routing in wormhole networks. IEEE Trans. Parallel Distrib. Syst. 14(8), 765–779 (2003)
L.M. Ni, P.K. McKinley, A survey of wormhole routing techniques in direct networks. Computer 26, 62–76 (1993)
T.M. Pinkston, S. Warnakulasuriya, Characterization of deadlocks in k-ary n-cube networks. IEEE Trans. Parallel Distrib. Syst. 10(9), 904–921 (1999)
PTM: Predictive technology model, (Dec. 2010) http://ptm.asu.edu/
C. Seiculescu, S. Murali, L. Benini, G. De Micheli, A method to remove deadlocks in networks-on-chips with wormhole flow control, in DATE’10, Dresden-Germany, 2010, pp. 1625–1628
L. Soojung, A deadlock detection mechanism for true fully adaptive routing in regular wormhole networks. Comput. Commun. 30(8), 1826–1840 (2007)
S.R. Vangal, J. Howard, G. Ruhl, S. Dighe, H. Wilson, J. Tschanz, D. Finan, A. Singh, T. Jacob, S. Jain, V. Erraguntla, C. Roberts, Y. Hoskote, N. Borkar, S. Borkar, An 80-tile sub-100-w teraflops processor in 65-nm CMOS. IEEE J. Solid State Circuits 43(1), 29–41 (2008)
V.I. Varshavsky (Ed.), Self-timed Control of Concurrent Processes: The Design of Aperiodic Logical Circuits in Computers and Discrete Systems (Kluwer Academic, Norwell, MA, USA, 1990)
S. Warnakulasuriya, T. Pinkston, Characterization of deadlocks in interconnection networks, in IPPS’97, Geneva-Switzerland (IEEE Computer Society, 1997), pp. 80–86
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer Science+Business Media New York
About this chapter
Cite this chapter
Al-Dujaily, R., Mak, T., Xia, F., Yakovlev, A., Palesi, M. (2014). Run-Time Deadlock Detection. In: Palesi, M., Daneshtalab, M. (eds) Routing Algorithms in Networks-on-Chip. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-8274-1_3
Download citation
DOI: https://doi.org/10.1007/978-1-4614-8274-1_3
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-8273-4
Online ISBN: 978-1-4614-8274-1
eBook Packages: EngineeringEngineering (R0)