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

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: Adrijean Andriahantenaina , Alain Greiner, Micro-Network for SoC: Implementation of a 32-Port SPIN network, Proceedings of the conference on Design, Automation and Test in Europe, p.11128, March 03-07, 2003
• 2: Giuseppe Ascia , Vincenzo Catania , Maurizio Palesi, Multi-objective mapping for mesh-based NoC architectures, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016765]
• 3: Elvira Baydal , Pedro Lopez , Jose Duato, A Family of Mechanisms for Congestion Control in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.9, p.772-784, September 2005 [doi>10.1109/TPDS.2005.102]
• 4: Luca Benini , Giovanni De Micheli, Networks on Chips: A New SoC Paradigm, Computer, v.35 n.1, p.70-78, January 2002 [doi>10.1109/2.976921]
• 5: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 6: Tobias Bjerregaard , Jens Sparso, A Router Architecture for Connection-Oriented Service Guarantees in the MANGO Clockless Network-on-Chip, Proceedings of the conference on Design, Automation and Test in Europe, p.1226-1231, March 07-11, 2005 [doi>10.1109/DATE.2005.36]
• 7: Evgeny Bolotin , Israel Cidon , Ran Ginosar , Avinoam Kolodny, Cost considerations in network on chip, Integration, the VLSI Journal, v.38 n.1, p.19-42, October 2004 [doi>10.1016/j.vlsi.2004.03.006]
• 8: Evgeny Bolotin , Israel Cidon , Ran Ginosar , Avinoam Kolodny, QNoC: QoS architecture and design process for network on chip, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.2-3, p.105-128, February 2004 [doi>10.1016/j.sysarc.2003.07.004]
• 9: Andrew A. Chien, A Cost and Speed Model for k-ary n-Cube Wormhole Routers, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.150-162, February 1998 [doi>10.1109/71.663877]
• 10: W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
• 11: William J. Dally , Brian Towles, Route packets, not wires: on-chip inteconnection networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 12: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 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: Jose Duato , Sudhakar Yalamanchili , Ni Lionel, Interconnection Networks: An Engineering Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2002
• 15: Pedro López , Juan Miguel Martínez , José Duato, DRIL: Dynamically Reduced Message Injection Limitation Mechanism for Wormhole Networks, Proceedings of the 1998 International Conference on Parallel Processing, p.535-542, August 10-14, 1998
• 16: Gerla, M. and Kleinrock, L. 1980. Flow control: A comparative survey. IEEE Trans. Commun. 28, 4.
• 17: Pierre Guerrier , Alain Greiner, A generic architecture for on-chip packet-switched interconnections, Proceedings of the conference on Design, automation and test in Europe, p.250-256, March 27-30, 2000, Paris, France [doi>10.1145/343647.343776]
• 18: Antoine Jalabert , Srinivasan Murali , Luca Benini , Giovanni De Micheli, ×pipesCompiler: A Tool for Instantiating Application Specific Networks on Chip, Proceedings of the conference on Design, automation and test in Europe, p.20884, February 16-20, 2004
• 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: Craig Hyatt , Dharma P. Agrawal, Congestion Control in the Wormhole-Routed Torus with Clustering and Delayed Deflection, Proceedings of the Second International Workshop on Parallel Computer Routing and Communication, p.33-38, June 26-27, 1997
• 25: Axel Jantsch , Hannu Tenhunen, Networks on chip, Kluwer Academic Publishers, Hingham, MA, 2003
• 26: Hyung Gyu Lee , Naehyuck Chang , Umit Y. Ogras , Radu Marculescu, On-chip communication architecture exploration: A quantitative evaluation of point-to-point, bus, and network-on-chip approaches, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.3, p.1-20, August 2007 [doi>10.1145/1255456.1255460]
• 27: Jian Liang , Andrew Laffely , Sriram Srinivasan , Russell Tessier, An architecture and compiler for scalable on-chip communication, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.7, p.711-726, July 2004 [doi>10.1109/TVLSI.2004.830919]
• 28: Mendel, J. M. 1995. Lessons in Estimation Theory for Signal Processing, Communications, and Control. Prentice Hall, Englewood Cliffs, NJ.
• 29: Mikael Millberg , Erland Nilsson , Rikard Thid , Axel Jantsch, Guaranteed Bandwidth Using Looped Containers in Temporally Disjoint Networks within the Nostrum Network on Chip, Proceedings of the conference on Design, automation and test in Europe, p.20890, February 16-20, 2004
• 30: Srinivasan Murali , Luca Benini , Giovanni De Micheli, Mapping and physical planning of networks-on-chip architectures with quality-of-service guarantees, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120737]
• 31: Erland Nilsson , Mikael Millberg , Johnny Oberg , Axel Jantsch, Load Distribution with the Proximity Congestion Awareness in a Network on Chip, Proceedings of the conference on Design, Automation and Test in Europe, p.11126, March 03-07, 2003
• 32: Umit Y. Ogras , Radu Marculescu, Energy- and Performance-Driven NoC Communication Architecture Synthesis Using a Decomposition Approach, Proceedings of the conference on Design, Automation and Test in Europe, p.352-357, March 07-11, 2005 [doi>10.1109/DATE.2005.137]
• 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: Umit Y. Ogras , Radu Marculescu, Analytical router modeling for networks-on-chip performance analysis, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 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: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 37: Li-Shiuan Peh , William J. Dally, A Delay Model for Router Microarchitectures, IEEE Micro, v.21 n.1, p.26-34, January 2001 [doi>10.1109/40.903059]
• 38: Alessandro Pinto , Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Efficient Synthesis of Networks On Chip, Proceedings of the 21st International Conference on Computer Design, p.146, October 13-15, 2003
• 39: Antonio Pullini , Federico Angiolini , Davide Bertozzi , Luca Benini, Fault tolerance overhead in network-on-chip flow control schemes, Proceedings of the 18th annual symposium on Integrated circuits and system design, September 04-07, 2005, Florianolpolis, Brazil [doi>10.1145/1081081.1081138]
• 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: Dongyu Qiu , Ness B. Shroff, A predictive flow control scheme for efficient network utilization and QoS, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.161-172, February 2004 [doi>10.1109/TNET.2003.822638]
• 43: M. Sgroi , M. Sheets , A. Mihal , K. Keutzer , S. Malik , J. Rabaey , A. Sangiovanni-Vencentelli, Addressing the system-on-a-chip interconnect woes through communication-based design, Proceedings of the 38th conference on Design automation, p.667-672, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379045]
• 44: A. Smai , L. Thorelli, Global Reactive Congestion Control in Multicomputer Networks, Proceedings of the Fifth International Conference on High Performance Computing, p.179, December 17-20, 1998
• 45: Krishnan Srinivasan , Karam S. Chatha , Goran Konjevod, Linear Programming based Techniques for Synthesis of Network-on-Chip Architectures, Proceedings of the IEEE International Conference on Computer Design, p.422-429, October 11-13, 2004
• 46: Mithuna Thottethodi , Alvin R. Lebeck , Shubhendu S. Mukherjee, Self-Tuned Congestion Control for Multiprocessor Networks, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.107, January 20-24, 2001
• 47: Girish V. Varatkar , Radu Marculescu, On-chip traffic modeling and synthesis for MPEG-2 video applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.1, p.108-119, January 2004 [doi>10.1109/TVLSI.2003.820523]
• 48: Cesar Albenes Zeferino , Frederico G. M. E. Santo , Altamiro Amadeu Susin, ParIS: a parameterizable interconnect switch for networks-on-chip, Proceedings of the 17th symposium on Integrated circuits and system design, September 07-11, 2004, Pernambuco, Brazil [doi>10.1145/1016568.1016624]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

General Terms:
Algorithms, Design, Performance

Keywords:
Multi-processor systems, congestion control, flow control, networks-on-chip