skip to main content
research-article

Analysis and optimization of prediction-based flow control in networks-on-chip

Published: 06 February 2008 Publication History

Abstract

Networks-on-Chip (NoC) communication architectures have emerged recently as a scalable solution to on-chip communication problems. While the NoC architectures may offer higher bandwidth compared to traditional bus-based communication, their performance can degrade significantly in the absence of effective flow control algorithms. Unfortunately, flow control algorithms developed for macronetworks, either rely on local information, or suffer from large communication overhead and unpredictable delays. Hence, using them in the NoC context is problematic at best. For this reason, we propose a predictive closed-loop flow control mechanism and make the following contributions: First, we develop traffic source and router models specifically targeted to NoCs. Then, we utilize these models to predict the possible congestion in the network. Based on this information, the proposed scheme controls the packet injection rate at traffic sources in order to regulate the total number of packets in the network. We also illustrate the proposed traffic source model and the applicability of the proposed flow controller to actual designs using real NoC implementations. Finally, simulations and experimental study using our FPGA prototype show that the proposed controller delivers a better performance compared to the traditional switch-to-switch flow control algorithms under various real and synthetic traffic patterns.

References

[1]
Adriahantenaina, A. and Greiner, A. 2003. Micro-network for SoC: Implementation of a 32-Port SPIN network. In Proceedings of the Design Automation and Test in Europe Conference.
[2]
Ascia, G., Catania, V., and Palesi, M. 2004. Multi-objective mapping for mesh-based NoC architectures. In Proceedings of International Conference on Hardware/Software Codesign and System Synthesis.
[3]
Baydal, E., Lopez, P., and Duato, J. 2005. A family of mechanisms for congestion control in wormhole networks, IEEE Trans. Paral. Distrib. Syst. 16, 9.
[4]
Benini, L. and De Micheli, G. 2002. Networks on chips: A new SoC paradigm. IEEE Comput. 35, 1.
[5]
Bertsekas, D. and Gallager, R. 1992. Data Networks. Prentice Hall, Englewood Cliffs, NJ.
[6]
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 Design Automation and Test in Europe Conference.
[7]
Bolotin, E., Cidon, I., Ginosar, R., and Kolodny, A. 2004. Cost considerations in network on chip. Integr. VLSI J. 38, 1.
[8]
Bolotin, E., Cidon, I., Ginosar, R., and Kolodny. 2004. QNoC: QoS architecture and design process for network on chip. J. Syst. Archite.: EUROMICRO J. 50, 2--3.
[9]
Chien, A. A. 1998. A cost and speed model for k-ary n-cube wormhole routers. IEEE Trans. Paral. Distrib. Syst. 9, 2.
[10]
Dally, W. J. 1992, Virtual-channel flow control. IEEE Trans. Paral. Distrib. Syst. 3, 2.
[11]
Dally, W. J. and Towles, B. 2001. Route packets, not wires: On-chip interconnection networks. In Proceedings of Design Automation Conference.
[12]
Dally, W. J. and Towles, B. 2004. Principles and Practices of Interconnection Networks. Morgan Kaufmann, San Francisco, CA.
[13]
Dielissen, J., Radulescu, A., Goossens, K., and Rijpkema, E. 2003. Concepts and implementation of the Philips network-on-chip. In Proceedings of the IP-Based SoC Design.
[14]
Duato, J., Yalamanchili, S., and Ni, L. M. 2002. Interconnection Networks: An Engineering Approach. Morgan Kaufmann, San Francisco, CA.
[15]
Lopez, P., Martinez, J. M., and Duato, J. 1998. DRIL: Dynamically reduced message injection limitation mechanism for wormhole networks. In Proceedings of the International Conference on Parallel Processing.
[16]
Gerla, M. and Kleinrock, L. 1980. Flow control: A comparative survey. IEEE Trans. Commun. 28, 4.
[17]
Guerrier, P. and Greiner, A. 2000. A generic architecture for on-chip packet switched interconnections. In Proceedings of the Design Automation and Test in Europe Conference.
[18]
Jalabert, M. S., Benini, L., and De Micheli, G. 2004. XpipesCompiler: A tool for instantiating application specific networks on chip. In Proceedings of the Design Automation and Test in Europe Conference.
[19]
Harmanci, M., Escudero, N., Leblebici, Y., and Ienne, P. 2004. Providing QoS to connection-less packet-switched NoC by implementing DiffServ functionalities. In Proceedings of the International Symposium on System-on-Chip.
[20]
Harmanci, M., Escudero, N., Leblebici, Y., and Ienne, P. 2005. Quantitative modeling and comparison of communication schemes to guarantee quality-of-service in networks-on-chip. In Proceedings of the International Symposium on Circuits and Systems (ISCAS).
[21]
Hedetniemi, S. M., Hedetniemi, S. T., and Liestman, A. L. 1988. A survey of gossiping and broadcasting in communication networks. Networks 18, 4.
[22]
Hemani, A., Jantsch, A., Kumar, S., Postula, A., Oberg, J., Millberg, M., and Lindvist, D. 2000. Network on a chip: An architecture for billion transistor era. InProceedings of the IEEE NorChip Conference.
[23]
Hu, J. and Marculescu, R. 2005. Energy- and performance-aware mapping for regular NoC architectures. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 24, 4.
[24]
Hyatt, C. and Agrawal, D. P. 1997. Congestion control in the wormhole-routed torus with clustering and delayed deflection. In Proceedings of Parallel Computing, Routing, and Communications Workshop.
[25]
Jantsch, A. and Tenhunen, H. Eds. 2003. Networks on Chip. Kluwer.
[26]
Lee, H. G., Chang. N, Ogras, U. Y., and Marculescu, R. 2007. On-chip communication architecture exploration: A quantitative evaluation of point-to-point, bus, and network-on-chip approaches. ACM Trans. Des. Automat. Elect. Syst. 12, 3.
[27]
Liang, L., Laffely, A., Srinivasan, S., and Tessier, R. 2004. An architecture and compiler for scalable on-chip communication. IEEE Trans. VLSI Syst. 12, 1.
[28]
Mendel, J. M. 1995. Lessons in Estimation Theory for Signal Processing, Communications, and Control. Prentice Hall, Englewood Cliffs, NJ.
[29]
Millberg, M., Nilsson, E., Thid, R., and Jantsch, A. 2004. Guaranteed bandwidth using looped containers in temporally disjoint networks within the nostrum network on chip. In Proceedings of the Design Automation and Test in Europe Conference.
[30]
Murali, S., Benini, L., and De Micheli, G. 2005. Mapping and physical planning of networks on chip architectures with quality-of-service guarantees. In Proceedings of the Asia and South Pacific Design Automation Conference.
[31]
Nilsson, E., Millberg, M., Oberg, J., and Jantsch, A. 2003. Load distribution with the proximity congestion awareness in a network on chip. In Proceedings of the Design Automation and Test in Europe Conference.
[32]
Ogras, U. Y. and Marculescu, R. 2005. Energy- and performance-driven NoC communication architecture synthesis using a decomposition approach. In Proceedings of the Design Automation and Test in Europe Conference.
[33]
Ogras, U. Y. and Marculescu, R. 2006. “It's a small world after all”: NoC performance optimization via long-range link insertion. IEEE Trans. VLSIS (Special Section on Hardware/Software Codesign and System Synthesis) 14, 7.
[34]
Ogras, U. Y. and Marculescu, R. 2007. Analytical router modeling for networks-on-chip performance analysis. In Proceedings of the Design Automation and Test in Europe Conference.
[35]
Paganini, F., Doyle, J., and Low, S. 2001. Scalable laws for stable network congestion control, In Proceedings of IEEE Conference on Decision and Control.
[36]
Park, K. and Willinger, W. Eds. 2000. Self-Similar Network Traffic and Performance Evaluation. Wiley Interscience.
[37]
Peh, L. S. and Dally, W. J. 2001. A delay model for router micro-architectures. IEEE Micro.
[38]
Pinto, A. and Sangiovanni-Vincentelli, A. 2003. Efficient synthesis of networks on chip. In Proceedings of the 21st International Conference on Computer Design.
[39]
Pullini, A., Angiolini, F., Bertozzi, D., and Benini, L. 2005. Fault tolerance overhead in network-on-chip flow control schemes. InProceedings of Symposium on Integrated Circuits and System Design.
[40]
Radulescu, et al. 2005. An efficient on-chip ni offering guaranteed services, shared-memory abstraction, and flexible network configuration. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 24, 1.
[41]
The Semiconductor Industry Association. 2006. The International Technology Roadmap for Semiconductors (ITRS). San Jose, CA.
[42]
Qiu, D. and Shro, N. B. 2004. A predictive flow control mechanism to provide QoS and efficient network utilization, IEEE Trans. Network. 12, 1.
[43]
Sgroi, M., Sheets, M., Mihal, A., Keutzer, K., Malik, S., Rabaey, J., and Sangiovanni-Vincentelli, A. 2001. Addressing the system-on-a-chip interconnect woes through communication-based design. In Proceedings of Design Automation Conference.
[44]
Smai, A. and Thorelli, L. 1998. Global Reactive Congestion Control in Multicomputer Networks. In Proceedings of the 5th International Conference on High Performance Computing.
[45]
Srinivasan, K., Chatha, K. S., and Konjevod, G. 2004. Linear programming based techniques for synthesis of network-on-chip architectures. In Proceedings of the IEEE International Conference on Computer Design.
[46]
Thottethodi, M., Lebeck, A. R., and Mukherjee, S. S. 2001. Self-tuned congestion control for multiprocessor networks. In Proceedings of the 7th International Symposium on High-Performance Computer Architecture.
[47]
Varatkar, G. and Marculescu, R. 2004. On-Chip traffic modeling and synthesis for MPEG-2 video applications. IEEE Trans. VLSI 12, 1, 108--119.
[48]
Zeferino, C. A., Santo, F. M. E., and Susin, A. A. 2004. Paris: A parameterizable interconnect switch for networks-on-chip, InProceedings of Symposium on Integrated Circuits and Systems Design.

Cited By

View all
  • (2021)Energy-Efficient Networks-on-Chip Architectures: Design and Run-Time OptimizationNetwork-on-Chip Security and Privacy10.1007/978-3-030-69131-8_3(55-75)Online publication date: 22-Jan-2021
  • (2020)Robust Model Predictive Control for Markovian Jump Systems with All Unstable Modes2020 16th International Conference on Control, Automation, Robotics and Vision (ICARCV)10.1109/ICARCV50220.2020.9305314(614-619)Online publication date: 13-Dec-2020
  • (2019)Odd-even based adaptive two-way routing in mesh NoCs for hotspot mitigationProceedings of the 20th International Conference on Distributed Computing and Networking10.1145/3288599.3288611(248-252)Online publication date: 4-Jan-2019
  • Show More Cited By

Index Terms

  1. Analysis and optimization of prediction-based flow control in networks-on-chip

    Recommendations

    Comments

    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
    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

    Publication History

    Published: 06 February 2008
    Accepted: 01 August 2007
    Revised: 01 March 2007
    Received: 01 June 2006
    Published in TODAES Volume 13, Issue 1

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Multi-processor systems
    2. congestion control
    3. flow control
    4. networks-on-chip

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)8
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Energy-Efficient Networks-on-Chip Architectures: Design and Run-Time OptimizationNetwork-on-Chip Security and Privacy10.1007/978-3-030-69131-8_3(55-75)Online publication date: 22-Jan-2021
    • (2020)Robust Model Predictive Control for Markovian Jump Systems with All Unstable Modes2020 16th International Conference on Control, Automation, Robotics and Vision (ICARCV)10.1109/ICARCV50220.2020.9305314(614-619)Online publication date: 13-Dec-2020
    • (2019)Odd-even based adaptive two-way routing in mesh NoCs for hotspot mitigationProceedings of the 20th International Conference on Distributed Computing and Networking10.1145/3288599.3288611(248-252)Online publication date: 4-Jan-2019
    • (2018)QoS and MPLS design issues in NoCs2018 South-Eastern European Design Automation, Computer Engineering, Computer Networks and Society Media Conference (SEEDA_CECNSM)10.23919/SEEDA-CECNSM.2018.8544942(1-4)Online publication date: Sep-2018
    • (2018)A Hybrid Design Approach for Output Feedback Exponential Stabilization of Markovian Jump SystemsIEEE Transactions on Automatic Control10.1109/TAC.2018.279134963:5(1404-1417)Online publication date: May-2018
    • (2016)A survey of routing algorithm for mesh Network-on-ChipFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-5431-810:4(591-601)Online publication date: 1-Aug-2016
    • (2015)Markovian Models Based Stochastic Communication in Networks-in-PackageIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.235821826:10(2806-2821)Online publication date: 1-Oct-2015
    • (2015)Dynamic Guaranteed Service Communication on Best-Effort Networks-on-ChipProceedings of the 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing10.1109/PDP.2015.47(353-360)Online publication date: 4-Mar-2015
    • (2014)SRNoCMicroelectronics Journal10.1016/j.mejo.2014.05.00845:8(1103-1117)Online publication date: 1-Aug-2014
    • (2013)An analytical model for on-chip interconnects in multimedia embedded systemsACM Transactions on Embedded Computing Systems10.1145/2536747.253675113:1s(1-19)Online publication date: 6-Dec-2013
    • Show More Cited By

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media