Top

Published in:

2018 | OriginalPaper | Chapter

4. Self-embedding

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

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

Publisher: Springer Singapore

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

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one 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

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

previous chapter Fundamentals

next chapter 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

Title: Self-embedding
Authors: Andreas Weichslgartner
Stefan Wildermann
Michael Glaß
Jürgen Teich
Publisher: Springer Singapore
Book: 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 Year: 2018
DOI: https://doi.org/10.1007/978-981-10-7356-4_4