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

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.

Authors:

• Faizal A. Samman
• Thomas Hollstein
• Manfred Glesner

Keywords:

• Network-on-Chip
• Parallel Pipeline Router Architecture
• Wormhole Switching
• Two-Level Priority Service.

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.