Statistical physics approaches for network-on-chip traffic characterization

ABSTRACT

In order to face the growing complexity of embedded applications, we aim to build highly efficient Network-on-Chip (NoC) architectures which can connect in a scalable manner various computational modules of the platform. For such networked platforms, it is increasingly important to accurately model the traffic characteristics as this is intimately related to our ability to determine the optimal buffer size at various routers in the network and thus provide analytical metrics for various power-performance trade-offs. In this paper, we show that the main limitations of queueing theory and Markov chain approaches to solving the buffer sizing problem can be overcome by adopting a statistical physics approach to probability density characterization which incorporates the power law distribution, correlations, and scaling properties exhibited within an NoC architecture due to various network transactions. As experimental results show, this new approach represents a breakthrough in accurate traffic modeling under non-equilibrium conditions. As such, our results can be directly used to solve the buffer sizing problem for multiprocessor systems where communication happens via the NoC approach.

REFERENCES

• 1: I. Antoniou, V. V. Ivanov and Yu. L. Kalinovsky, "Kinetic Model of Network Traffic," Physica A: Statistical Mechanics and its Applications, 308 (1-4), pp. 533--544, 2002.
• 2: R. Balescu, Aspects of Anomalous Transport in Plasmas, Institute of Physics Publishing, 2005.
• 3: S. Bates and S. McLaughlin, "Is VBR Video Non-Stationary or Self-Similar? Implications for ATM Traffic Characterisation," in Proc. of the European Simulation Multi-conference, 1996.
• 4: P. Bogdan and R. Marculescu, "Quantum-like Effects in Networks-on-Chip Buffers Behavior," DAC, 2007.
• 5: A. Jantsch and H. Tenhunen (Eds.), Networks on Chip, Kluwer Academic Publishers, 2003.
• 6: J. Hu, U. Y. Ogras and R. Marculescu, "System-Level Buffer Allocation for Application-Specific Networks-on-Chip Router Design," in IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol.25, No.12, pp. 2919--2933, Dec. 2006.
• 7: A. A. Kilbas, H. M. Srivastava, and J. J. Trujillo, Theory and Applications of Fractional Differential Equations, North-Holland Mathematics Studies, 204, Elsevier, 2006.
• 8: A. N. Kolmogorov, A. N. Shiriaev, V. M. Tikhomirov, Selected Works of A.N. Kolmogorov: Probability theory and mathematical statistics, Springer, 1992.
• 9: W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson, "On the Self-similar Nature of Ethernet Traffic," IEEE/ACM Transactions on Networking, Vol. 2, No. 1, pp. 1--15, Feb. 1994.
• 10: B. B. Mandelbrot and J. W. Van Ness, "Fractional Brownian Motion, Fractional Noises and Applications," SIAM Review, 10, 422--437, 1968.
• 11: S. Manolache, P. Eles and Z. Peng, "Buffer Space Optimisation with Communication Synthesis and Traffic Shaping for NoCs," DATE, 2006.
• 12: R. N. Mantegna and H. E. Stanley, An Introduction to Econophysics: Correlations and Complexity in Finance, Cambridge Univ. Press, 2000.
• 13: K. B. Oldham and J. Spanier, The Fractional Calculus: The Theory of Differentiation and Integration to Arbitrary Order, Academic Press, 2006.
• 14: K. Park and W. Willinger, Self-similar Network Traffic and Performance Evaluation, John Wiley & Sons, ISBN: 0471319740. New York, NY, 2000.
• 15: V. Paxson and S. Floyd, "Wide-area Traffic: the Failure of Poisson Modeling," IEEE/ACM Transactions on Networking, Vol. 3, No. 3, pp. 226--244, June 1995.
• 16: L. Pitaevskii and S. Stringari, Bose-Einstein Condensation, Oxford University Press, 2003.
• 17: C. K. Peng, S. Havlin, H. E. Stanley, and A. L. Goldberger, "Quantification of Scaling Exponents and Crossover Phenomena in Nonstationary Heartbeat Time Series," Chaos 5, 82--87, 1995.
• 18: A. D. Polyanin and A. V. Manshirov, Handbook of Mathematics for Engineers and Scientists, Taylor and Francis Group, 2007.
• 19: I. Prigogine and R. Herman, Kinetic Theory of Vehicular Traffic, American Elsevier Publishing Company, Inc., New York, 1971.
• 20: G. Rainer, R. Klages, and I. M. Sokolov, Anomalous Transport: Foundations and Applications, Wiley-VCH Verlag GmbH & Co. KGaA, Berlin, 2008.
• 21: A. Scherrer, A. Fraboulet and T. Risset, "Automatic Phase Detection for Stochastic On-Chip Traffic Generation," CODES, October 22 - 25, 2006.
• 22: V. Soteriou, H. Wang and L.-S. Peh, "A Statistical Traffic Model for On-Chip Interconnection Networks," in Proc. of the IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, Monterey, California, September 2006.
• 23: G. Varatkar and R. Marculescu, "Traffic Analysis for On-Chip Networks Design of Multimedia Applications," Design Automation Conference, 2002.
• 24: K. G. Wilson, "The Renormalization Group: Critical Phenomena and the Kondo Problem," Rev. Mod. Phys. 47, 4, 773, 1975.
• 25: Wormsim [online]. Available: http://www.ece.cmu.edu/~sld/

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
fractional calculus, master equation, multi-processor systems, networks-on-chip, systems-on-chip