nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

4. Self-embedding

verfasst von : Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, Jürgen Teich

Erschienen in: Invasive Computing for Mapping Parallel Programs to Many-Core Architectures

Verlag: Springer Singapore

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this chapter, a self-embedding algorithm is presented which solves the mapping problem consisting of task binding to tiles, respectively processors, and message routing to NoC links as formalized in the previous chapter in an autonomous way. In the realm of invasive computing, self-embedding tackles the problem in a resource-aware, decentralized, and adaptive manner. Contrary to related work, the application itself initiates and performs its own mapping autonomously. The main idea of the algorithm is that each task, or i-let in invasive computing, embeds its succeeding task and the respective communication towards it.

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

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

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

Vorheriges Kapitel Fundamentals

Nächstes Kapitel Hybrid Application Mapping

In the following, the term task is used synonymously with actor or vertex of an application graph.

In the case of an i-NoC-based architecture and GS channels, the corresponding service levels can be calculated according to Eq. (3.7).

The function \({ \text {succ}}\) determines the set of successors of a vertex in an application graph.

The serialization always starts with the root vertex. In case of multiple vertices without any predecessor, a heuristic (e.g., number of outgoing edges or bandwidth of succeeding messages) may be used to determine the first task to serialize.

Normally, the number of bits correspond to the link width \({ \text {LW}}\).

Brião EW, Barcelos D, Wagner FR (2008) Dynamic task allocation strategies in MPSoC for soft real-time applications. In: Proceedings of the design, automation and test in Europe (DATE), ACM, pp 1386–1389. https://doi.org/10.1109/DATE.2008.4484934

Carvalho E, Calazans N, Moraes F (2007) Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs. In: Proceedings of the international workshop on rapid system prototyping (RSP), IEEE, pp 34–40. https://doi.org/10.1109/RSP.2007.26

Chou C, Marculescu R (2010) Run-time task allocation considering user behavior in embedded multiprocessor networks-on-chip. IEEE Trans Comput-Aided Des Integr Circuits Syst 29(1):78–91. https://doi.org/10.1109/TCAD.2009.2034348

Chou C, Ogras ÜY, Marculescu R (2008) Energy- and performance-aware incremental mapping for networks on chip with multiple voltage levels. IEEE Trans Comput-Aided Des Integr Circuits Syst 27(10):1866–1879. https://doi.org/10.1109/TCAD.2008.2003301

Dasgupta S, Long PM (2005) Performance guarantees for hierarchical clustering. J Comput Syst Sci 70(4):555–569. https://doi.org/10.1016/j.jcss.2004.10.006

Dick R (2010) Embedded system synthesis benchmarks suite (E3S). http://ziyang.eecs.umich.edu/dickrp/e3s/. Accessed 25 Sep 2016

Dick R, Rhodes DL, Wolf WH (1998) TGFF: task graphs for free. In: Proceedings of the conference on hardware/software codesign (CODES). IEEE, pp 97–101. https://doi.org/10.1145/278241.278309

Faruque MAA, Krist R, Henkel J (2008) ADAM: run-time agent-based distributed application mapping for on-chip communication. In: Proceedings of the design automation conference (DAC). ACM, pp 760–765. https://doi.org/10.1145/1391469.1391664

Frahling G, Sohler C (2008) A fast k-means implementation using coresets. Int J Comput Geom Appl 18(6):605–625. https://doi.org/10.1142/S0218195908002787

10.

Hosseinabady M, Núñez-Yáñez JL (2009) Run-time resource management in fault-tolerant network on reconfigurable chips. In: Proceedings of the international conference on field programmable logic and applications (FPL). IEEE, pp 574–577. https://doi.org/10.1109/FPL.2009.5272400

11.

Li K (2009) A random-walk-based dynamic tree evolution algorithm with exponential speed of convergence to optimality on regular networks. In: International conference on frontier of computer science and technology (FCST). IEEE, pp 80–85. https://doi.org/10.1109/FCST.2009.74

12.

Strobach P (1990) Tree-structured scene adaptive coder. IEEE Trans Commun 38(4):477–486. https://doi.org/10.1109/26.52659

13.

Tarjan RE (1972) Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2):146–160. https://doi.org/10.1137/0201010

14.

Weichslgartner A, Teich J (2016) Position paper: towards redundant communication through hybrid application mapping. In: Proceedings of the international workshop on multi-objective many-core design (MOMAC), VDE, pp 1–4. http://ieeexplore.ieee.org/document/7499234/

15.

Weichslgartner A, Wildermann S, Teich J (2011) Dynamic decentralized mapping of tree-structured applications on NoC architectures. In: Proceedings of the international symposium on networks-on-chip (NOCS), ACM, pp 201–208. https://doi.org/10.1145/1999946.1999979

16.

Weichslgartner A, Heisswolf J, Zaib A, Wild T, Herkersdorf A, Becker J, Teich J (2015) Position paper: towards hardware-assisted decentralized mapping of applications for heterogeneous NoC architectures. In: Proceedings of the international workshop on multi-objective many-core design (MOMAC), VDE, pp 1–4. http://ieeexplore.ieee.org/document/7107099/

17.

Zaib A, Heisswolf J, Weichslgartner A, Wild T, Teich J, Becker J, Herkersdorf A (2015) Network interface with task spawning support for NoC-based DSM architectures. In: Proceedings of the international conference on architecture of computing systems (ARCS), Springer, Lecture Notes in Computer Science, vol 9017, pp 186–198. https://doi.org/10.1007/978-3-319-16086-3_15

Titel: Self-embedding
verfasst von: Andreas Weichslgartner
Stefan Wildermann
Michael Glaß
Jürgen Teich
Verlag: Springer Singapore
Buch: Invasive Computing for Mapping Parallel Programs to Many-Core Architectures
Print ISBN: 978-981-10-7355-7

Electronic ISBN: 978-981-10-7356-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-981-10-7356-4_4

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence_ieS/© Springer Fachmedien Wiesbaden GmbH, Search Icon, Banner Hanser, Bunte Männchen, die Kunden darstelle, werden von einem riesigen Magneten angezogen. /© Oleksiy Mark, Dr. Daniel Schneider/© Fraunhofer IESE, Interview Level Ten PPA Bild/© LevelTen, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence 2024/© AndreyPopov / Getty Images / iStock, 2023_Antrieb/© supervisuell, ATZ-Webinar: Prototypenfreie Entwicklung durch Offline- und Driver-in-the-Loop-HiL-Tests /© (c) VI-grade

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+Technik"

Springer Professional "Technik"

Neuer Inhalt

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

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