An analytical model for Network-on-Chip with finite input buffer

Abstract

An analytical model is proposed for input buffer router architecture Network-on-Chip (NoC) with finite size buffers. The model is developed based on M/G/1/K queuing theory and takes into consideration the restriction of buffer sizes in NoC. It analyzes the packet’s sojourn time in each buffer and calculates the packets average latency in NoC The validity of the model is verified through simulation. By comparing our analytical outcomes to the simulation results, we show that the proposed model successfully captures the performance characteristics of NoC, which provides an efficient performance analysis tool for NoC design.

Keywords

analytical model / finite buffer / Network-on-Chip (NoC) / queue system

References

[1] Grecu C, Pande P P, Ivanov A, Saleh R. Structured interconnect architecture: a solution for the non-scalability of bus-based socs. In: Proceedings of Great Lakes symp. VLSI. Washington DC: Elsevier, 2004, 192–195

[2] Henkel J, Wolf W, Chakradhar S. On-chip networks: a scalable, communication-centric embedded system design paradigm. In: Proceedings of the 17th International Conference on VLSI Design. Piscataway, NJ, USA: IEEE Press, 2004, 845–851

[3] Dally W J, Towles B. Route packets, not wires: on-chip interconnection networks. In: Design Automation Conference. Las Vegas, USA: ACM Press, 2001: 684–689

[4] Pande P P, Grecu C, Jones M, Ivanov A, Saleh R. Performance evaluation and design trade-offs for network-on-chip interconnect architectures. IEEE Transactions on Computers, 2005, 54(8): 1025–1040

[5] Guerrier P, Greiner A. A generic architecture for on-chip packet-switched interconnections. In: Proc. Design and Test in Europe. Paris, France: IEEE Press, 2000, 250–256

[6] Kumar S, Jantsch A, Soininen J, Forsell M, Millberg M, Oberg J, Tiensyrja K, Hemani A. A network on chip architecture and design methodology. In: Proc ISVLSI. Pittsburgh, PA, USA: IEEE Press2002, 117–124

[7] Karim F, Nguyen A, Dey S. An interconnect architecture for networking systems on chips. IEEE Micro, 2002, 22(5): 36–45

[8] Pande P P, Grecu C, Ivanov A, Saleh R. Design of a switch for network on chip applications. In: Proc, Symp. Circuits and Systems (ISCAS), Bangkok, Thailand: IEEE Press, 2003, 217–220

[9] Hemani A, Jantsch A, Kumar S. Postula A, Oberg J, Millberg M, Lindqvist D. Network on a chip: an architecture for billion transistor era. In: IEEE NorChip Conf, Turku, Finland: IEEE Press, 2000, 166–173

[10] Marculescu R, Ogras U Y, Nicholas H Z. Computation and communication refinement for multiprocessor soc design a system-level perspective. ACM Trans. Design Autom. Elect. Syst. 2006, 11(3): 564–592

[11] Bogdan P, Marculescu R. Quantum-like effects in network-on-chip buffers behavior. In: Design Automation Conference 2007, Pacifico Yokohama: IEEE Press, 2007, 266–267

[12] Agarwal A. Limits on interconnection network performance. IEEE Transactions on Parallel and Distributed Systems, 1991, 4(2): 398–412

[13] Dally W J. Performance analysis of k-ary n-cube interconnection networks. Computer, 1990, 39(6): 775–785

[14] Adve V S, Vernon M K. Performance analysis of mesh interconnection networks with deterministic routing. IEEE Transactions on Parallel and Distributed Systems, 1994, 3(5): 225–246

[15] Boudec J Y L, Thiran P. Network Calculus. New York: Springer-Verlag, 2001

[16] Chandra V, Xu A, Schmit H, Pileggi L. An interconnect channel design for high performance integrated circuits. In: Proc. DATE Conf. Paris, France: IEEE Press, 2004, 1138–1143

[17] Beekhuizen P, Denteneer D, Adan I. Analysis of a tandem network model of a single-router. Annals of Operations Research, 2008, 162 (1): 19–34

[18] Guz Z, Walter I, Bolotin E, Cidon I, Ginosar R, Kolodny A. Efficient link capacity and qos design for network-on-chip. In: Design, Automation and Test in Europe 2006, Munich, Germany: IEEE Press, 2006, 1–6

[19] Hu J, Ogras U Y, Marculescu R. Application-specific buffer space allocation for networks-on-chip router design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(12): 2919–2933

[20] Hillier F S, Lieberman G J. Introduction to Operation Research. 6th edition. Hong Kong: McGraw-Hill, 1995, 661–732.

[21] Gelenbe E, Pujolle G. Introduction to Queueing Network. New York: Joh Wiley and Sons, 1987

[22] Medhi J. Stochastic Models in Queuing Theory. London: Academic Press, 1991

Acknowledgements

The authors thank the National Natural Science Foundation of China for its financial support.

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg