Prediction-based flow control for network-on-chip traffic

ABSTRACT

Networks-on-Chip (NoC) architectures provide a scalable solution to on-chip communication problem but the bandwidth offered by NoCs can be utilized efficiently only in presence of effective flow control algorithms. Unfortunately, the flow control algorithms pub-lished to date 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 con-trol 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 cases of 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. Evaluations involving real and synthetic traffic patterns show that the proposed controller delivers a superior performance compared to the traditional switch-to-switch flow control algorithms.

REFERENCES

• 1: 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]
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: 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]
• 4: 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]
• 5: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 6: M. Gerla and L. Kleinrock, Flow control: A comparative survey, IEEE Trans. on Communications COM-28, no 4, 1980.
• 7: 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
• 8: J. Hu and R. Marculescu, Energy- and performance-aware mapping for regular NoC architectures, IEEE Trans. on Computer-Aided Design of Inte-grated Circuits and Systems, Vol.24, No.4, April 2005.
• 9: Axel Jantsch , Hannu Tenhunen, Networks on chip, Kluwer Academic Publishers, Hingham, MA, 2003
• 10: J. M. Mendel. Lessons in Estimation Theory for Signal Processing, Communications, and Control. Prentice Hall, 1995.
• 11: 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
• 12: F. Paganini, J. Doyle, S. Low. Scalable Laws for Stable Network Con-gestion Control, In Proc. IEEE Conf. on Decision and Control, Dec., 2001.
• 13: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 14: 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]
• 15: 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]
• 16: A. Radulescu et. al. An efficient on-chip ni offering guaranteed ser-vices, shared-memory abstraction, and flexible network configuration, IEEE Trans. on CAD of ICs and Systems, 24(1) 2005.
• 17: 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]
• 18: 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:
congestion control, flow control, multi-processor systems, networks-on-chip