Networks on Chip(NoC) has emerged as the paradigm for designing scalable communication architecture for Systems on Chips (SoCs). Avoiding the conditions that can lead to deadlocks in the network is critical for using NoCs in real designs. Methods that can lead to deadlock-free operation with minimum power and area overhead are important for designing application-specific NoCs. The deadlocks that can occur in NoCs can be broadly categorized into two classes: routingdependentdeadlocks and message-dependentdeadlocks. In this work, we present methods to design NoCs that avoid both types of deadlocks. The methods are integrated with the topology synthesis phase of the NoC design flow. We show that by considering the deadlock avoidance issue during topology synthesis, we can obtain a significantly better NoC design than traditional methods, where the deadlock avoidance issue is dealt with separately. Our experiments on several SoC benchmarks show that our proposed scheme provides large reduction in NoC power consumption (an average of 38.5%) and NoC area (an average of 30.7%) when compared to traditional approaches. Keywords: Networks on Chips, Systems on Chips, Message-dependent deadlocks, routing-dependent deadlocks, topology, synthesis.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
L. Benini and G. De Micheli, “Networks on Chips: A New SoC Paradigm”, IEEE Computers, pp. 70-78, Jan. 2002.
M. Sgroi et al., “Addressing the System-on-a-Chip Interconnect Woes Through Communication-Based Design”, Proc. DAC, pp. 667-672, June 2001.
S. Kumar et al., “A Network on Chip Architecture and Design Methodology”, Proc. ISVLSI, pp. 117-122, April 2002
P. Guerrier, A. Greiner, “A generic architecture for on-chip packet-switched inter- connections”, Proc. DATE, pp. 250-256, March 2000.
K. Goossens et al., “The Aethereal network on chip: Concepts, architectures, and implementations”, IEEE Design and Test of Computers, Vol. 22(5), pp. 21-31, Sept-Oct 2005.
W. Dally, B. Towles, “Route Packets, not Wires: On-Chip Interconnection Net-works”, Proc. DAC, pp. 684-689, June 2001.
Y. H. Song, T. M. Pinkston, “A Progressive Approach to Handling Message-Dependent Deadlock in Parallel Computer Systems”, IEEE TPDS, Vol. 14(3), pp. 259-275, March 2003.
Y. Choi, “Deadlock Recovery Based Router Architectures for High Performance Networks”, PhD Dissertation, University of Southern California, June 2001.
G. Chiu, “The Odd-Even Turn Model for Adaptive Routing”, IEEE TPDS, Vol. 11 (7), pp. 729-738, July 2000.
C. Glass, L. Ni, “The turn model for adaptive routing”, Proc. ISCA, pp. 278-287, 1992.
J. Duato, “A New Theory of Deadlock-Free Adaptive Routing in Wormhole Net-works”, IEEE TPDS, Vol. 8(8), pp. 790-802, Aug 1997.
D. Starobinksi et al., “Application of network calculus to general topologies using turn-prohibition”, IEEE/ACM Transactions on Networking, Vol. 11, Issue 3, pp. 411-421, June 2003.
W. J. Dally, H. Aoki, “Deadlock-Free Adaptive Routing in Multi-computer Net-works Using Virtual Channels”, IEEE TPDS, Vol. 4(4), pp. 466-475, April 1993.
S. Scott, G. Thorson, Optimized Routing in the Cray T3D”, Proc. Workshop Parallel Computer Routing and Comm., pp. 281-294, May 1994.
S. Scott, G. Thorson, “The Cray T3E Network: Adaptive Routing in a High Per-formance 3D Torus”, Proc. Symp. Hot Interconnects IV, pp. 147-156, Aug. 1996.
J. Carbonaro, Cavallino, “The Teraflops Router and NIC”, Proc. Symp. Hot In-terconnects IV, pp. 157-160, Aug. 1996.
S.S. Mukherjee et al., “The Alpha 21364 Network Architecture”, Proc. Symp. HOT Interconnects 9, pp. 113-117, Aug. 2001.
L. Widdoes, S. Correll, :The S-1 Project: Developing High Performance Comput-ers”, Proc. COMPCON, pp. 282-291, Spring 1980.
J. Laudon, D. Lenoski,” The SGI Origin: A ccNUMA Highly Scalable Server”, Proc. ISCA, pp. 241-251, June 1997.
D. Lenoski et al., “ The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor”, Proc. ISCA, pp. 148-159, 1990.
A. Hansson, K. Goossens, A. Radulescu, “UMARS: A Unified Approach to Map-ping and Routing on a Combined Guaranteed Service and Best-Effort Network-on-Chip Architecture”, Technical Report 2005/00340, Philips Research, April 2005.
B. Gebremichael et al., “Deadlock Prevention in the Aethereal Protocol”, Proc. Working Conference on Correct Hardware Design and Verification Methods (CHARME), Oct 2005.
J. Hu, R. Marculescu, ’Exploiting the Routing Flexibility for Energy/Performance Aware Mapping of Regular NoC Architectures’, Proc. DATE, March 2003.
S. Murali, G. De Micheli, “SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs”, Proc. DAC 2004.
S. Murali et al., “Mapping and Physical Planning of Networks on Chip Architec-tures with Quality-of-Service Guarantees”, Proc. ASPDAC 2005.
A.Pinto et al., “Efficient Synthesis of Networks on Chip”, ICCD 2003, pp. 146-150, Oct 2003.
W.H.Ho, T.M.Pinkston, “A Methodology for Designing Efficient On-Chip Inter-connects on Well-Behaved Communication Patterns”, HPCA 2003, pp. 377-388, Feb 2003.
T. Ahonen et al. ”Topology Optimization for Application Specific Networks on Chip”, Proc. SLIP 04.
K. Srinivasan et al., “An Automated Technique for Topology and Route Generation of Application Specific On-Chip Interconnection Networks”, Proc. ICCAD ’05.
A. Hansson et al., “A unified approach to constrained mapping and routing on network-on-chip architectures”, pp. 75-80, Proc. ISSS 2005.
S. Murali et al., “Designing Application-Specific Networks on Chips using Floor-plan Information”, Proc. ICCAD 2006.
W. J. Dally, B. Towles, ”Principles and Practices of Interconnection Networks”, Morgan Kaufmann , Dec 2003.
S. Stergiou et al., “×pipesLite: a Synthesis Oriented Design Library for Networks on Chips”, pp. 1188-1193, Proc. DATE 2005.
F. Angiolini et al., “Contrasting a NoC and a Traditional Interconnect Fabric with Layout Awareness”, pp. 124-129, Proc. DATE 2006.
A. Pullini, F. Angiolini, D. Bertozzi, L. Benini, “Fault Tolerance Overhead in Network-on-Chip Flow Control Schemes”, Proc. SBCCI, pp. 224-229, 2005.
D. Bertozzi et al., ”NoC Synthesis Flow for Customized Domain Specific Multi-Processor Systems-on-Chip”, IEEE Transactions on Parallel and Distributed Sys-tems, Feb 2005.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 International Federation for Information Processin
About this paper
Cite this paper
Murali, S. et al. (2008). Designing Routing and Message-Dependent Deadlock Free Networks on Chips. In: De Micheli, G., Mir, S., Reis, R. (eds) VLSI-SoC: Research Trends in VLSI and Systems on Chip. IFIP International Federation for Information Processing, vol 249. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74909-9_19
Download citation
DOI: https://doi.org/10.1007/978-0-387-74909-9_19
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-74908-2
Online ISBN: 978-0-387-74909-9
eBook Packages: Computer ScienceComputer Science (R0)