Top

Published in:

2018 | OriginalPaper | Chapter

3. Fundamentals

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

This chapter introduces the required formal foundation on which the mapping algorithms in later chapters build on. It details the formal application and architecture models which abstract from any actual invasive hardware and software. Further, important concepts of predictability and composability are presented. To build a formal foundation for the mapping algorithms in Chaps. 4–6, this chapter introduces the required formal models and notations. It details the formal application and architecture models which abstract from any actual invasive hardware and software. Further, important concepts of predictability and composability are given. They are essential for assuring nonfunctional properties through the HAM methodology from Chaps. 5 and 6.

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 Invasive Computing

next chapter Self-embedding

Often also referred as task graph [4] or problem graph [2].

Note that we omit routers and NAs in this representation, whereas in the physical hardware, routers would be connected by links, and tiles could only access this network via NAs (see Sect. 2.5). In 2D mesh NoC architectures, every router is connected to a tile with the same X- and Y-coordinate; thus, we model the router as part of a tile \(u\) in our formal notation. Finally, we do not explicitly draw directed edges (see Fig. 3.2) for the links \(l\in L\) but assume unidirectional links as realized in an i-NoC (see Sect. 2.5).

We assume only tiles with processing cores of the same resource type. In fact, the scheduling analysis in Chap. 5 is based on tiles with a single processing core.

Akesson B, Molnos AM, Hansson A, Ambrose JA, Goossens K (2011) Composability and predictability for independent application development, verification, and execution. In: Hübner M, Becker J (eds) Multiprocessor system-on-chip—hardware design and tool integration. Springer, pp 25–56. https://doi.org/10.1007/978-1-4419-6460-1_2

Blickle T, Teich J, Thiele L (1998) System-level synthesis using evolutionary algorithms. Des Autom Embed Syst 3(1):23–58. https://doi.org/10.1023/A:1008899229802

Buchwald S, Mohr M, Zwinkau A (2015) Malleable invasive applications. In: Gemeinsamer Tagungsband der workshops der Tagung software engineering, CEUR-WS.org, CEUR workshop proceedings, vol 1337, pp 123–126. http://ceur-ws.org/Vol-1337/paper22.pdf

Dick RP, 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

Ferdinand C, Heckmann R (2004) aiT: worst case execution time prediction by static program analysis. In: Proceedings of the IFIP world computer congress, topical sessions, IFIP 156. Kluwer/Springer, pp 377–383. https://doi.org/10.1007/978-1-4020-8157-6_29

Gangadharan D, Sousa E, Lari V, Hannig F, Teich J (2014) Application-driven reconfiguration of shared resources for timing predictability of MPSoC platforms. In: Proceedings of the asilomar conference on signals, systems, and computers (ASSC). IEEE, pp 398–403. https://doi.org/10.1109/ACSSC.2014.7094471

Hansson A, Goossens K, Bekooij M, Huisken J (2009) CoMPSoC: a template for composable and predictable multi-processor system on chips. ACM Trans Des Autom Electron Syst (TODAES) 14(1). https://doi.org/10.1145/1455229.1455231

Heisswolf J, König R, Kupper M, Becker J (2013) Providing multiple hard latency and throughput guarantees for packet switching networks on chip. Comput Electr Eng 39(8):2603–2622. https://doi.org/10.1016/j.compeleceng.2013.06.005

Kobbe S, Bauer L, Lohmann D, Schröder-Preikschat W, Henkel J (2011) DistRM: Distributed resource management for on-chip many-core systems. In: Proceedings of the conference on hardware/software codesign and system synthesis (CODES+ISSS). ACM, pp 119–128. https://doi.org/10.1145/2039370.2039392

10.

Li X, Yun L, Mitra T, Roychoudhury A (2007) Chronos: a timing analyzer for embedded software. Sci Comput Program 69(1–3):56–67. https://doi.org/10.1016/j.scico.2007.01.014 MathSciNetCrossRefMATH

11.

Lickly B, Liu I, Kim S, Patel HD, Edwards SA, Lee EA (2008) Predictable programming on a precision timed architecture. In: Proceedings of the international conference on compilers, architecture, and synthesis for embedded systems (CASES). ACM, pp 137–146. https://doi.org/10.1145/1450095.1450117

12.

Liu I, Reineke J, Lee EA (2010) A PRET architecture supporting concurrent programs with composable timing properties. In: Proceedings of the Asilomar conference on signals, systems, and computers (ASSC). IEEE, pp 2111–2115

13.

Reineke J, Grund D, Berg C, Wilhelm R (2007) Timing predictability of cache replacement policies. Real-Time Syst 37(2):99–122. https://doi.org/10.1007/s11241-007-9032-3

14.

Teich J (2008) Invasive algorithms and architectures. IT—Information Technology 50(5):300–310. https://doi.org/10.1524/itit.2008.0499

15.

Teich J, Henkel J, Herkersdorf A, Schmitt-Landsiedel D, Schröder-Preikschat W, Snelting G (2011) Invasive computing: an overview. In: Hübner M, Becker J (eds) Multiprocessor system-on-chip—hardware design and tool integration. Springer, pp 241–268. https://doi.org/10.1007/978-1-4419-6460-1_11

16.

Teich J, Glaß M, Roloff S, Schröder-Preikschat W, Snelting G, Weichslgartner A, Wildermann S (2016) Language and compilation of parallel programs for *-predictable MPSoC execution using invasive computing. In: Proceedings of the international symposium on embedded multicore/many-core systems-on-chip. IEEE, pp 313–320. https://doi.org/10.1109/MCSoC.2016.30

17.

Ungerer T, Cazorla FJ, Sainrat P, Bernat G, Petrov Z, Rochange C, Quiñones E, Gerdes M, Paolieri M, Wolf J, Cassé H, Uhrig S, Guliashvili I, Houston M, Kluge F, Metzlaff S, Mische J (2010) Merasa: Multicore execution of hard real-time applications supporting analyzability. IEEE Micro 30(5):66–75. https://doi.org/10.1109/MM.2010.78

18.

Weichslgartner A, Wildermann S, Gangadharan D, Glaß M, Teich J (2017) A design-time/run-time application mapping methodology for predictable execution time in MPSoCs. ArXiv e-prints pp 1–30. arXiv: 1711.05932

19.

Wildermann S, Ziermann T, Teich J (2013) Game-theoretic analysis of decentralized core allocation schemes on many-core systems. In: Proceedings of the design, automation and test in Europe (DATE). ACM, pp 1498–1503. https://doi.org/10.7873/DATE.2013.305

20.

Wilhelm R, Engblom J, Ermedahl A, Holsti N, Thesing S, Whalley D, Bernat G, Ferdinand C, Heckmann R, Mitra T, Mueller F, Puaut I, Puschner P, Staschulat J, Stenström P (2008) ACM Trans Embed Comput Syst (TECS). The worst-case execution-time problem–overview of methods and survey of tools (3):36:1–36:53. https://doi.org/10.1145/1347375.1347389

Title: Fundamentals
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_3