Top

The Journal of Supercomputing

Published in:

01-12-2013

Architecture and design of high-throughput, low-latency, and fault-tolerant routing algorithm for 3D-network-on-chip (3D-NoC)

Authors: Akram Ben Ahmed, Abderazek Ben Abdallah

Published in: The Journal of Supercomputing | Issue 3/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Despite the higher scalability and parallelism integration offered by Network-on-Chip (NoC) over the traditional shared-bus based systems, it is still not an ideal solution for future large-scale Systems-on-Chip (SoCs), due to limitations such as high power consumption, high-cost communication, and low throughput. Recently, extending 2D-NoC to the third dimension (3D-NoC) has been proposed to deal with these problems; however, 3D-NoC systems are exposed to a variety of manufacturing and design factors making them vulnerable to different faults that cause corrupted message transfer or even catastrophic system failures. Therefore, a 3D-NoC system should be fault tolerant to transient malfunctions or permanent physical damages.

In this paper, we propose a low-latency, high-throughput, and fault-tolerant routing algorithm named Look-Ahead-Fault-Tolerant (LAFT). LAFT reduces the communication latency and enhances the system performance while maintaining a reasonable hardware complexity and ensuring fault tolerance. We implemented the proposed algorithm on a real 3D-NoC architecture (3D-OASIS-NoC) and prototyped it on FPGA, then we evaluated its performance over various applications. Evaluation results show that the proposed algorithm efficiently reduces the communication latency that can reach an average of 38 % and 16 %, when compared to conventional XYZ and our early designed Look-Ahead-XYZ routing algorithms, respectively, and enhances the throughput with up to 46 % and 29 %.

previous article Virtual machine consolidation based on interference modeling

next article Learning automata-based algorithms for finding cover sets in wireless sensor networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Torres L, Benoit P, Sassatelli G, Robert M, Clermidy F, Puschini D (2011) An introduction to multi-core system on chip trends and challenges. In: Multiprocessor system-on-chip: hardware design and tool integration, pp 1–21 CrossRef

Leary G, Chatha KS (2010) Design of NoC for SoC with multiple use cases requiring guaranteed performance. In: 23rd international conference on VLSI design, pp 200–205

Benini L, De Micheli G (2002) Networks on chips: a new SoC paradigm. IEEE Comput 35(1):70–78 CrossRef

Xu Y, Zhao B, Zhang Y, Yang J (2010) Simple virtual channel allocation for high throughput and high frequency on-chip routers. In: The 16th IEEE international symposium on high-performance computer architecture, pp 1–11

Carloni LP, Pande P, Xie Y (2009) Networks-on-chip in emerging interconnect paradigms: advantages and challenges. In: Proceedings of the 3rd ACM/IEEE international symposium on networks-on-chip, pp 93–102

Sibai FN (2012) On-chip network for interconnecting thousands of cores. IEEE Trans Parallel Distrib Syst 23(2):193–201 CrossRef

Ben Abdallah A, Sowa M (2006) Basic network-on-chip interconnection for future gigascale MCSoCs applications: communication and computation orthogonalization. In: Proceedings of the TJASSST2006 symposium on science

Mori K, Ben Abdallah A, Kuroda K (2009) Design and evaluation of a complexity effective network-on-chip architecture on FPGA. In: Proceedings of the 19th intelligent system symposium (FAN 2009), pp 318–321

Mori K, Esch A, Ben Abdallah A, Kuroda K (2010) Advanced design issues for OASIS network-on-chip architecture. In: IEEE proceedings of the 5th international conference on broadband, wireless computing, communication and applications, pp 74–79 CrossRef

10.

Ben Ahmed A, Ben Abdallah A, Kuroda K (2010) Architecture and design of efficient 3D network-on-chip (3D NoC) for custom multicore SoC. In: IEEE proceedings of the 5th international conference on broadband, wireless computing, communication and applications, pp 67–73 CrossRef

11.

Wu X, Zhao W, Nakamoto M, Nimmagadda C, Lisk D, Gu S, Radojcic R, Nowak M, Xie Y (2012) Electrical characterization for intertier connections and timing analysis for 3-D ICs. IEEE Trans Very Large Scale Integr (VLSI) Syst 20(1):186–191 CrossRef

12.

Philip G, Christopher B, Ramm P (2008) Handbook of 3D integration: technology and applications of 3D integrated circuits. Wiley-VCH, New York

13.

Xie Y, Loh GH, Black B, Bernstein K (2006) Design space exploration for 3D architectures. ACM J Emerg Technol Comput Syst 2(2):65–103 CrossRef

14.

Topol AW, La Tulipe JDC, Shi L, Frank DJ, Bernstein K, Steen SE, Kumar A, Singco GU, Young AM, Guarini KW, Ieong M (2006) Three-dimensional integrated circuits. IBM J Res Dev 50(4/5):491–506 CrossRef

15.

Dong X, Wu X, Sun G, Xie Y, Li H, Chen Y (2008) Circuit and microarchitecture evaluation of 3D stacking magnetic RAM (MRAM) as a universal memory replacement. In: Proceedings of the 45th annual design automation conference, pp 554–559

16.

Sun G, Dong X, Xie Y, Li J, Chen Y (2009) A novel 3D stacked MRAM cache architecture for CMPs. In: IEEE 15th international symposium high performance computer architecture, pp 239–249

17.

Ramanujam RS, Lin B (2009) A layer-multiplexed 3D on-chip network architecture. IEEE Embed Syst Lett 1(2):50–55 CrossRef

18.

Yan S, Lin B (2008) Design of application-specific 3D networks-on-chip architectures. In: Proceedings of the international conference on computer design, pp 142–149

19.

Matsutani H, Koibuchi M, Amano H (2007) Tightly-coupled multi-layer topologies for 3-D NoCs. In: Proceedings of the international conference on parallel processing, pp 75–84

20.

Kim J, Nicopoulos C, Park D, Das R, Xie Y, Narayanan V, Yousif MS, Das CR (2007) A novel dimensionally-decomposed router for on-chip communication in 3D architectures. In: Proceedings of the ACM international symposium on computer architecture, pp 138–149

21.

Park D, Eachempati S, Das R, Mishra AK, Yuan X, Vijaykrishnan N, Das CR (2008) MIRA: a multi-layered on-chip interconnect router architecture. In: Proceedings of the 35th international symposium on computer architecture, pp 251–261

22.

Xu Y, Du Y, Zhao B, Zhou X, Zhang Y, Yang J (2009) A low-radix and low-diameter 3D interconnection network design. In: International symposium on high-performance computer architecture (HPCA), pp 30–42

23.

Pande PP, Grecu C, Jones M, Ivanov A, Saleh R (2005) Performance evaluation and design trade-offs for network-on-chip interconnect architectures. IEEE Trans Comput 54(8):1025–1040 CrossRef

24.

Benini L, De Micheli G (2006) Networks on chips: technology and tools. Morgan Kauffmann, San Mateo

25.

Lehtonen T, Liljeberg P, Plosila J (2007) Online reconfigurable self-timed links for fault tolerant NoC. In: VLSI design 2007, pp 1–13

26.

Rahmani A-M, Vaddina KR, Latif K, Liljeberg P, Plosila J, Tenhunen H (2012) Design and management of high-performance, reliable and thermal-aware 3D networks-on-chip. IET Circuits Devices Syst 6(5):308–321 CrossRef

27.

Feng Ch, Zhang M, Li J, Jiang J, Lu Z, Jantsch A (2011) A low-overhead fault-aware deflection routing algorithm for 3D network-on-chip. In: IEEE computer society annual symposium on VLSI, pp 19–24

28.

Feng Ch, Lu Z, Jantsch A, Li J, Zhang M (2010) A reconfigurable fault-tolerant deflection routing algorithm based on reinforcement learning for network-on-chip. In: The 3rd international workshop on network on chip architectures, pp 11–16 CrossRef

29.

Chien AA, Kim JH (1992) Planar-adaptive routing: low-cost adaptive networks for multiprocessors. In: The 19th annual international symposium on computer architecture, pp 268–277 CrossRef

30.

Wu J (2000) Fault-tolerant adaptive and minimal routing in mesh-connected multicomputer using extended safety levels. IEEE Trans Parallel Distrib Syst 11(2):149–159 CrossRef

31.

Wu J (2000) A fault-tolerant adaptive and minimal routing approach in 3-D meshes. In: The 7th international conference on parallel and distributed systems, pp 149–159

32.

Jiang Z, Wu J, Wang D (2008) A new fault information model for fault-tolerant adaptive and minimal routing in 3-D meshes. IEEE Trans Reliab 57(1):149–162 CrossRef

33.

Xiang D, Zhang Y, Pan Y (2009) Practical deadlock-free fault-tolerant routing based on the planar network fault model. IEEE Trans Comput 58(5):620–633 MathSciNetCrossRef

34.

Pasricha S, Zou Y (2011) A low overhead fault tolerant routing scheme for 3D networks-on-chip. In: The 12th international symposium on quality electronic design, pp 1–8

35.

Wu J (2003) A simple fault-tolerant adaptive and minimal routing approach in 3-D meshes. J Comput Sci Technol 18(1):1–13 CrossRefMATH

36.

Akbari S, Shafieey A, Fathy M, Berangi R (2012) AFRA: a low cost high performance reliable routing for 3D mesh NoCs. In: Design, automation & test in Europe conference & exhibition, pp 332–337

37.

Ben Ahmed A, Ben Abdallah A (2012) LA-XYZ: low latency, high throughput look-ahead routing algorithm for 3D network-on-chip (3D-NoC) architecture. In: The 6th IEEE international symposium on embedded multicore SoCs, pp 167–174 CrossRef

38.

Ben Ahmed A, Ben Abdallah A (2012) Low-overhead routing algorithm for 3D network-on-chip. In: IEEE proceedings of the third international conference on networking and computing

39.

Sullivan H, Bashkow TR (1977) Large scale, homogeneous, fully distributed parallel machine. In: Annual symposium on computer architecture. ACM, New York, pp 105–117

40.

Valiant LG, Brebner GJ (1981) Universal schemes for parallel communication. In: ACM symposium on the theory of computing, pp 263–277

41.

Nesson T, Johnsson SL (1995) ROMM routing on mesh and torus networks. In: ACM symposium on parallel algorithms and architectures, pp 275–287

42.

Seo D, Ali A, Lim W-T, Rafique N, Thottethodi M (2005) Near-optimal worst-case throughput routing for two-dimensional mesh networks. In: International symposium on computer architecture, pp 432–443

43.

Ramanujam RS, Lin B (2008) Near-optimal oblivious routing on three-dimensional mesh networks. In: IEEE international conference on computer design, pp 134–141

44.

Chao CH, Jheng KY, Wang HY, Wu JC, Wu A-Y (2010) Traffic and thermal-aware run-time thermal management scheme for 3D NoC systems. In: Proceedings of the ACM/IEEE international symposium on networks-on-chip (NoCS), pp 223–230

45.

Lahiri K, Raghunathan A, Dey S (2000) Efficient exploration of the SoC communication architecture design space. In: Proceedings of the 2000 IEEE/ACM international conference on computer-aided design, pp 424–430

46.

Dev K (2002) Multi-objective optimization using evolutionary algorithms. Wiley, New York, pp 245–253

47.

Xin L, Choy C-S (2010) A low-latency NoC router with lookahead bypass. In: IEEE international symposium on circuits and systems, pp 3981–3984

48.

Mullins R, West A, Moore S (2004) Low-latency virtual-channel routers for on-chip networks. In: Proceedings of the 31st annual international symposium on computer architecture, pp 188–197

49.

Kumar A, Kundu P, Singh AP, Peh L-S, Jha NK (2007) A 4.6 tbits/s 3.6 GHz single-cycle NoC router with a novel switch allocator in 65 nm CMOS. In: Proceedings of the 2007 IEEE international conference on computer design, pp 63–70 CrossRef

50.

Kim J, Nicopoulos C, Park D, Narayanan V, Yousif MS, Das CR (2006) A gracefully degrading and energy-efficient modular router architecture for on-chip networks. In: Proceedings of the 33rd international symposium on computer architecture, pp 4–15

51.

Sadawarte YA, Gaikwad MA, Patrikar RM (2011) Comparative study of switching techniques for network on chip architectures. In: International conference on communication computing & security, pp 243–246

52.

Agarwal A, Iskander C, Shankar R (2009) Survey of network on chip (NoC) architectures and contributions. J Eng Comput Archit 3(1):21–27

53.

Fu Z, Ling X (2010) The design and implementation of arbiters for network-on-chips. In: 2nd IEEE international conference on industrial and information systems, vol 1, pp 292–295

54.

http://www.altera.com

55.

Chan P, Dai K, Wu D, Rao J, Zou X (2010) The parallel algorithm implementation of matrix multiplication based on ESCA. In: IEEE ASIA pacific conference on circuits and systems, pp 1091–1094 CrossRef

56.

Zekri AS, Sedukin SG (2006) The general matrix multiply-add operation on 2D torus. In: The 20th IEEE international parallel and distributed processing symposium

57.

Chien AA, Kim JH (1995) Planar-adaptive routing: low-cost adaptive networks for multiprocessors. J ACM 42(1):91–123 CrossRefMATH

58.

Rahmani AM, Kusha AA, Pedram M (2009) NED: a novel synthetic traffic pattern for power/performance analysis of network-on-chips using negative exponential distribution. J Low Power Electron 5(3):396–405 CrossRef

59.

Feero B, Pande PP (2007) Performance evaluation for three-dimensional networks-on-chip. In: Proceedings of IEEE computer society annual symposium on VLSI (ISVLSI), pp 305–310 CrossRef

Title: Architecture and design of high-throughput, low-latency, and fault-tolerant routing algorithm for 3D-network-on-chip (3D-NoC)
Authors: Akram Ben Ahmed
Abderazek Ben Abdallah
Publication date: 01-12-2013
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 3/2013
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-013-0940-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 3/2013

Data center selection based on neuro-fuzzy inference systems in cloud computing environments

Component survivability at runtime for mission-critical distributed systems

Improving CompactMatrix phase in gang scheduling by changing transference condition and utilizing exchange

On-demand service hosting on production grid infrastructures

Learning automata-based algorithms for finding cover sets in wireless sensor networks

Enhanced dynamic credential generation scheme for protection of user identity in mobile-cloud computing

Premium Partner