nach oben

The Journal of Supercomputing

Erschienen in:

01.11.2016

Application mapping onto mesh-based network-on-chip using constructive heuristic algorithms

verfasst von: Chi-Hsiang Cheng, Wei-Mei Chen

Erschienen in: The Journal of Supercomputing | Ausgabe 11/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Application mapping is an important part of network-on-chip (NoC) design, it tries to map the application onto a NoC-based platform. Because mapping an application onto the mesh architecture is NP-hard, there is no known algorithm for solving this problem in polynomial time. In this study, we propose a new application mapping algorithm for mapping an application onto the mesh topology NoC architecture to minimize the energy consumption. We compare the proposed algorithm with some previously proposed algorithm and exact mapping technique. Our experiments on multimedia benchmarks show that the proposed mapping algorithm obtains the same solutions as the optimal solutions that are generated by IPL on most of cases. On random benchmarks containing higher number of cores, we use less execution time to find better solution than CastNet and NMAP in large-scale mesh-based NoC.

Vorheriger Artikel ShenZhen transportation system (SZTS): a novel big data benchmark suite

Nächster Artikel High-throughput state-machine replication using software transactional memory

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Arabnia HR, Oliver MA (1989) A transputer network for fast operations on digitised images. Comput Graph Forum 8(1):3–12CrossRef

Bhandarkar SM, Arabnia HR (1995) The REFINE multiprocessor: theoretical properties and algorithms. Parallel Comput 21(11):1783–1806CrossRef

Darbari FM, Khademzadeh A, Fard GG (2009) CGMAP: a new approach to network-on-chip mapping problem. IEICE Electron Express 6(1):27–34CrossRef

Dick RP, Rhodes DL, Wolf W (1998) TGFF: task graphs for free. In: Proc. Int. Workshop Hardware/Software Codesign, pp 97–101

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman

Hemani A, Jantsch A, Kumar S, Postula A, Oberg J, Millberg M, Lindqvist D (2000) Network on a chip: an architecture for billion transistor era. In: Proc. of the IEEE NorChip conference

Hu J, Marculescu R (2005) Energy- and performance-aware mapping for regular NoC architectures. IEEE Trans Comput Aided Des Integr Circ Syst 24(4):551–562CrossRef

Leighton FT (1992) Introduction to parallel algorithms and architectures: arrays trees hypercubes. Morgan Kaufmann, San MateoMATH

Marculescu R, Ogras UY, Peh LS, Jerger NE, Hoskote Y (2009) Outstanding research problems in NoC design: systems, microarchitecture, and circuit perspectives. IEEE Trans Comput Aided Des Integr Circ Syst 28(1):3–21CrossRef

10.

Murali S, De Micheli G (2004) Bandwidth constrained mapping of cores onto NoC architectures. In: Proceedings of design, automation and test in europe conference and exhibition (DATE), vol 2, pp 896–901

11.

Sahni S, Gonzalez T (1976) P-complete approximation problems. J Assoc Comput Mach 23(3):555–565MathSciNetCrossRefMATH

12.

Sahu PK, Chattopadhyay S (2013) A survey on application mapping strategies for network-on-chip design. J Syst Archit 59(1):60–76MathSciNetCrossRef

13.

Sahu PK, Shah T, Manna K, Chattopadhyay S (2014) Application mapping onto mesh based network-on-chip using discrete particle swarm optimization. IEEE Trans Very Large Scale Integr (VLSI) Syst 22(2):300–312CrossRef

14.

Sahu PK, Venkatesh P, Gollapalli S, Chattopadhyay S (2011) Application mapping onto mesh structured network-on-chip using particle swarm optimization. In: IEEE computer society annual symposium on VLSI, pp 335–336

15.

Shen T, Chao CH, Lien YK, Wu AY (2007) A new binomial mapping and optimization algorithm for reduced-complexity mesh-based on-chip network. In: Proceedings of NOCS07, pp. 317–322

16.

Tavanpour M, Khademzadeh A, Pourkiani S, Yaghobi M (2010) GBMAP: an evolutionary approach to mapping cores onto a mesh-based NoC architecture. J Commun Comput 7(3):1–7

17.

Tosun S, Ozturk O, Ozen M (2009) An ILP formulation for application mapping onto network-on-chips. In: International conference on application of information and communication technologies (AICT), pp 1–5

18.

Tosun S, Ozturk O, Ozen M (2015) Application mapping algorithms for mesh-based network-on-chip architectures. J Supercomput 71(3):995–1017CrossRef

19.

Tosun S (2011) New heuristic algorithm for energy aware application mapping and routing on mesh-based NoCs. J Syst Archit 57(1):69–78CrossRef

20.

Tosun S (2011) Clustered-based application mapping method for network-on-chip. Adv Eng Softw 42(10):868–874CrossRef

21.

Zhou L, Jing M, Yu Z, Zeng X (2012) Task-binding based branch-and-bound algorithm for NoC mapping. In: Circuits and systems (ISCAS), 2012 IEEE international symposium on. (ISCAS’12), pp 648–651

Titel: Application mapping onto mesh-based network-on-chip using constructive heuristic algorithms
verfasst von: Chi-Hsiang Cheng
Wei-Mei Chen
Publikationsdatum: 01.11.2016
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 11/2016
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-016-1746-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 11/2016

Symmetric searchable encryption with efficient range query using multi-layered linked chains

GPU-based parallel genetic approach to large-scale travelling salesman problem

Design and implementation of an automated monitoring system

Exploiting in-memory storage for improving workflow executions in cloud platforms

Cellular automata labeling of connected components in n-dimensional binary lattices

Introduction to sustainable ultrascale computing systems and applications

Premium Partner