Flexible Wormhole-Switched Network-on-chip with Two-Level Priority Data Delivery Service

Authors: Faizal A. Samman, Thomas Hollstein, Manfred Glesner

Abstract:

A synchronous network-on-chip using wormhole packet switching and supporting guaranteed-completion best-effort with low-priority (LP) and high-priority (HP) wormhole packet delivery service is presented in this paper. Both our proposed LP and HP message services deliver a good quality of service in term of lossless packet completion and in-order message data delivery. However, the LP message service does not guarantee minimal completion bound. The HP packets will absolutely use 100% bandwidth of their reserved links if the HP packets are injected from the source node with maximum injection. Hence, the service are suitable for small size messages (less than hundred bytes). Otherwise the other HP and LP messages, which require also the links, will experience relatively high latency depending on the size of the HP message. The LP packets are routed using a minimal adaptive routing, while the HP packets are routed using a non-minimal adaptive routing algorithm. Therefore, an additional 3-bit field, identifying the packet type, is introduced in their packet headers to classify and to determine the type of service committed to the packet. Our NoC prototypes have been also synthesized using a 180-nm CMOS standard-cell technology to evaluate the cost of implementing the combination of both services.

Keywords: Network-on-Chip, Parallel Pipeline Router Architecture, Wormhole Switching, Two-Level Priority Service.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079658

References:

[1] P. Martin, "Design of a Virtual Component Neutral Network-on- Chip Transaction Layer," Proc. Design, Automation and Test in Europe Conf. and Exhibition (DATE-05), pp. 336-337, 2005.
[2] D. Wingard, "MicroNetwork-Based Integration for SOCs," Proc. Design Automation Conf. (DAC-01), pp. 673-677, 2001.
[3] L. Benini and G. De Micheli, "Networks on Chips: A New SoC Paradigm," IEEE Computer, vol. 35, pp. 70-78, Jan. 2002.
[4] A. Jantsch and H. Tenhunen, Networks on Chip, Kluwer Academic Publisher, Hingham, MA, USA, 2003.
[5] M. Millberg, E. Nilsson, R. Thid and A. Jantsch, "Guaranteed Bandwidth using Looped Containers in Temporally Disjoint Networks within the Nostrum Network on Chip," Proc. Design, Automation and Test in Europe Conf. and Exhibition (DATE-04), pp. 890-895, 2004.
[6] D. Wiklund and D. Liu, "SoCBUS: Switched Network on Chip for Hard Real TIme Embedded Systems," Proc. IEEE Int-l Parallel and Distributed Processing Symposium (IPDPS-03), 8 pp., 2003.
[7] M. B. Taylor, J. Kim, J. Miller, D. Wentzlaff, F. Ghodrat, B. Greenwald, H. Hoffman, et. al., "The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs," IEEE Micro, vol. 22, issue 2, pp. 25-35, Mar-Apr. 2002.
[8] C. Hilton and B. Nelson, "PNOC: a flexible circuit-switched NoC for FPGA-based systems," IEE Proc. Computers and Digital Techniques, vol. 153, no.3, pp. 181-188, May 2006.
[9] S. Kumar, A. Jantsch, J. -K. Soininen, M. Forsell, M. Millberg, J. O¨ berg, K. Tiensyrja and A. Hemani, "A Network on Chip Architecture and Design Methodology," Proc. IEEE Computer Society Annual Symposium on VLSI, pp. 105-112, 2002.
[10] M. K. -F. Sch¨afer, T. Hollstein, H. Zimmer, M. Glesner, "Deadlock- Free Routing and Component Placement for Irregular Mesh-based Network-on-Chip," IEEE/ACM Int-l Conf. on CAD (ICCAD-05), pp. 238-245, 2005.
[11] F. Karim, A. Nguyen and S. Dey, "An Interconnect Architecture for Networking Systems on Chips," IEEE Micro, vol. 22, issue 5, pp. 36-45, Sept-Oct. 2002.
[12] P. Guerrier and A. Greiner, "A Generic Architecture for On-Chip Packet-Switched Interconnection," Proc. Design, Automation and Test in Europe Conf. and Exhibition (DATE-00), pp. 250-256, 2000.
[13] I. M. Panades, A. Greiner and A. Sheibanyrad, "A Low Cost Network-on-Chip with Guaranteed Service Well Suited to the GALS Approach," Proc. the 1st Int-l Conf. and Workshop on Nano- Networks), pp. 1-5, 2006.
[14] T. A. Bartic, J. -Y. Mignolet, V. Nollet, T. Marescaux, D. Verkest, S. Vernalde and R. Lauwereins, "Topology adaptive network-onchip design and implementation," IEE Proc. Computers and Digital Techniques, vol. 152, no.4, pp. 467-472, July 2005.
[15] L. Benini and D. Bertozzi, "Network-on-chip architectures and design methods," IEE Proc. Computers and Digital Techniques, vol. 152, no.2, pp. 261-272, Mar. 2005.
[16] J. Xu, W. Wolf, J. Henkel and S. Chakradhar, "A Design Methodology for application-Specific Networks-on-Chip," ACM Trans. on Embedded Computing Systems, vol. 5, no. 2, pp. 263-280, May 2006.
[17] J. Bainbridge and S. Furber, "Chain: A Delay-Insensitive Chip Area Interconnect," IEEE Micro, vol. 22, issue 5, pp. 16-23, Sept-Oct. 2002.
[18] M. Amde, T. Felicijan, A. Efthymiou, D. Edwards and L. Lavagno, "Asynchronous on-chip networks," IEE Proc. Computers and Digital Techniques, vol. 152, no. 2, pp. 273-283, Mar. 2005.
[19] M. Sgroi, M. Sheets, K. Keutzer, S. Malik, J. Rabaey and A. S. Vincentelli, "Addressing the System-on-a-Chip Interconnect Woes Through Communication-Based Design," The 38th ACM Design Automation Conf. (DAC-01), pp. 667-672, 2001.
[20] I. Saastamoinen, D. S. -Tortosa and J. Nurmi, "Interconnect IP Node for Future System-on-Chip Designs," The 1st IEEE Int-l Workshop on Electronic Design, Test and Applications (DELTA-02), pp. 116- 120, 2002.
[21] E. Beign'e, F. Clermidy, P. Vivet, A. Clouard and M. Renaudin, "An Asynchronous NOC Architecture Providing Low Latency Service and its Muti-level Design Framework," Proc. the 11th IEEE Int-l Symp. on Asynchronous Circuits and Systems, pp. 54-63, 2005.
[22] T. Bjerregaard and J. Spars├©, "Implementation of guaranteed services in the MANGO clockless network-on-chip," IEE Proc. Computers and Digital Techniques, vol. 153, no.4, pp. 217-229, July 2006.
[23] E. Rijpkema, K. Goossens, A. Radulescu, J. Dielissen, J. van Meerbergen, P. Wielage and E. Waterlander, "Trade-offs in the design of a router with both guaranteed and best-effort services for networks on chip," IEE Proc. Computers and Digital Techniques, vol. 150, no. 5, pp. 294-302, Sep. 2003.
[24] S. M. Parker et. al., "SpaceWire: Links, Nodes, Routers and Networks," European Cooperation for Space Standardization, Standard No. ECSS-E50-12A,Issue 1, January 2003.
[25] Intel Corp., "Overview, Installing and Using Priority Packet II," available online: http://www.intel.com/support/network/adapter/ppack/sb/cs- 013750.htm.
[26] Free Patents online, "Transmission of high-priority, real-time traffic on low-speed communications links", available online: http://www.freepatentsonline.com/EP1128612.html.
[27] Patent Storm, US Patent 7120113, "Systems and methods for limiting low priority traffic from blocking high priority traffic," available online: http://www.patentstorm.us/patents/7120113.html.
[28] J. S. Choi and C. K. Un, "Delay performance of an input queueing packet switch with twopriority classes," IEE Proceeding, Communications, Volume 145, Issue 3, pp. 141-144, Jun 1998.
[29] J. Duato, S. Yalamanchili and L. Ni, Interconnection Networks: An Engineering Approach, Revised Printing, San Fransisco, USA: Morgan Kaufmann Publishers, 2003.
[30] C. J. Glass and L. M. Ni "The Turn Model for Adaptive Routing, " The 19th Int-l Symposium on Computer Architecture, pp. 278-287, 1992.
[31] C. J. Glass and L. M. Ni "Adaptive Routing in Mesh-Connected Networks, " The 12th Int-l Conference on Distributed Computing Systems, pp. 12-19, 1992.
[32] J. Kim, D. Park, N. Vijaykrishnan and C. R. Das, "A Low Latency Router Supporting Adaptivity for On-Chip Interconnects, " ACM Design Automation Conf. (DAC-05), pp. 559-564, 2005.
[33] D. Seo, A. Ali, W. -T. Lim and N. Rafique, "Near-Optimal Worstcase Throughput Routing for Two-Dimensional Mesh Networks, " The 32nd Int-l Symp. on Computer Architecture, pp. 432-443, 2005.
[34] G. -M. Chiu, "The Odd-Even Turn Model for Adaptive Routing, " IEEE Trans. on Parallel and Distributed Systems, vol. 11, no. 7, pp. 729-738, July 2000.
[35] J. Hu and R. Marculescu, "DyAD - Smart Routing for Network-on- Chip, " ACM Design Automation Conf., pp. 260-263, 2004.
[36] G. Ascia, V. Catania, M. Palesi and D. Patti "Neighbor-on-Path: A New Selection Strategy for On-Chip Networks, " IEEE/ACM/IFIP Workshop on Embedded Systems for Real-Time Multimedia, pp. 79- 84, 2006.