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.
- 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.Google ScholarCross Ref
- R. Balescu, Aspects of Anomalous Transport in Plasmas, Institute of Physics Publishing, 2005.Google Scholar
- 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.Google Scholar
- P. Bogdan and R. Marculescu, "Quantum-like Effects in Networks-on-Chip Buffers Behavior," DAC, 2007. Google ScholarDigital Library
- A. Jantsch and H. Tenhunen (Eds.), Networks on Chip, Kluwer Academic Publishers, 2003. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- A. A. Kilbas, H. M. Srivastava, and J. J. Trujillo, Theory and Applications of Fractional Differential Equations, North-Holland Mathematics Studies, 204, Elsevier, 2006. Google ScholarDigital Library
- A. N. Kolmogorov, A. N. Shiriaev, V. M. Tikhomirov, Selected Works of A.N. Kolmogorov: Probability theory and mathematical statistics, Springer, 1992.Google Scholar
- 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. Google ScholarDigital Library
- B. B. Mandelbrot and J. W. Van Ness, "Fractional Brownian Motion, Fractional Noises and Applications," SIAM Review, 10, 422--437, 1968.Google ScholarDigital Library
- S. Manolache, P. Eles and Z. Peng, "Buffer Space Optimisation with Communication Synthesis and Traffic Shaping for NoCs," DATE, 2006. Google ScholarDigital Library
- R. N. Mantegna and H. E. Stanley, An Introduction to Econophysics: Correlations and Complexity in Finance, Cambridge Univ. Press, 2000. Google ScholarDigital Library
- K. B. Oldham and J. Spanier, The Fractional Calculus: The Theory of Differentiation and Integration to Arbitrary Order, Academic Press, 2006.Google Scholar
- K. Park and W. Willinger, Self-similar Network Traffic and Performance Evaluation, John Wiley&Sons, ISBN: 0471319740. New York, NY, 2000. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- L. Pitaevskii and S. Stringari, Bose-Einstein Condensation, Oxford University Press, 2003.Google Scholar
- 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.Google ScholarCross Ref
- A. D. Polyanin and A. V. Manshirov, Handbook of Mathematics for Engineers and Scientists, Taylor and Francis Group, 2007.Google Scholar
- I. Prigogine and R. Herman, Kinetic Theory of Vehicular Traffic, American Elsevier Publishing Company, Inc., New York, 1971.Google Scholar
- G. Rainer, R. Klages, and I. M. Sokolov, Anomalous Transport: Foundations and Applications, Wiley-VCH Verlag GmbH&Co. KGaA, Berlin, 2008.Google Scholar
- A. Scherrer, A. Fraboulet and T. Risset, "Automatic Phase Detection for Stochastic On-Chip Traffic Generation," CODES, October 22 - 25, 2006. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- G. Varatkar and R. Marculescu, "Traffic Analysis for On-Chip Networks Design of Multimedia Applications," Design Automation Conference, 2002. Google ScholarDigital Library
- K. G. Wilson, "The Renormalization Group: Critical Phenomena and the Kondo Problem," Rev. Mod. Phys. 47, 4, 773, 1975.Google ScholarCross Ref
- Wormsim {online}. Available: http://www.ece.cmu.edu/~sld/Google Scholar
Index Terms
- Statistical physics approaches for network-on-chip traffic characterization
Recommendations
Workload characterization and its impact on multicore platform design
CODES/ISSS '10: Proceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesisNetworks-on-chip (NoCs) have been proposed as a scalable solution to solving the communication problem in multicore systems. Although the queuing-based approaches have been traditionally used for performance analysis purposes, they cannot properly ...
ParIS: a parameterizable interconnect switch for networks-on-chip
SBCCI '04: Proceedings of the 17th symposium on Integrated circuits and system designNetworks-on-Chip (NoCs) emerge as the solution for the problem of interconnecting cores (or IPs) in Systems-on-Chip (SoCs) which require reusable and scalable communication architectures. The building block of a NoC is its router (or switch), whose ...
Design space exploration comparing homogeneous and heterogeneous network-on-chip architectures
SBCCI '05: Proceedings of the 18th annual symposium on Integrated circuits and system designNetworks-on-chip (NoCs) are communication architecture alternatives for complex Systems-on-Chip (SoCs) designs, due to their high scalability and bandwidth. In this paper, we consider a heterogeneous NoC as an alternative to match performance and energy ...
Comments