Top

Published in:

2018 | OriginalPaper | Chapter

5. Hybrid Application Mapping

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

Previously, a new class of distributed application run-time mapping algorithms called self-embedding was presented. They are not designed for hard real-time applications which require an upper bound for end-to-end latency. To achieve predictability or even *-predictability, a static (performance) analysis is inevitable to determine and optimize upper and lower bounds. Therefore, a novel hybrid application mapping methodology (consisting of a design-time analysis and run-time mapping) is introduced. In contrast to related work, a packet-switched NoC communication, as in the invasive NoC, is considered.

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 Self-embedding

next chapter Hybrid Mapping for Increased Security

In this chapter, we assume tiles with a single processing core. However, with an adapted schedulability analysis, this approach could also be applied to systems with multiple cores per tile.

Generally, the service intervals on different tiles or resource types could be of different lengths. Our approach could still work here, but for keeping notations simple, we make these assumptions.

Direct predecessors of a task \( \text {pred}(t)\) in our application graph model are always messages. To determine the predecessor task in a path of the mapped application graph we, therefore, use the function \( \text {pred}_{T}(t)\).

\(o_{5,r}\) depends on the number of resource types (\(|R|\)). For each resource type, one individual optimization objective is added to the multi-objective optimization.

Equivalent is meant in the sense of nonfunctional properties of execution (objectives).

Note the difference of the binding and routing to \(\beta \) and \(\rho \) during DSE.

The mapping of the constraint graph is a variant of task mapping. Note also, that assigning tasks to a heterogeneous many-core systems is a generalized assignment problem which is already NP-complete [20].

The OPs are selected by the knapsack heuristic based on the tile availability. Thus, there are sufficient tiles of the desired resource type available. However, Algorithm 5.1 proves the absence of feasible routings, when mapping all selected OPs.

If the DSE is conducted with the the same architecture which is used for run-time mapping, each OP, respectively constraint graph, has at least one feasible mapping in an empty system.

In both variants, only operating points are used which do not violate the deadline, hence both satisfy the real-time requirements.

For connections with a long wire length, registers with an additional delay may be used to reduce the critical path and enable high frequencies in synchronous designs.

In some related work, time multiplexed arbitration with fixed time slots is referred as time division multiplexing (TDM). In this book, we use TDM and TDMA synonymously.

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

Akesson B, Minaeva A, Sucha P, Nelson A, Hanzálek Z (2015) An efficient configuration methodology for time-division multiplexed single resources. In: Proceedings of real-time and embedded technology and applications symposium (RTAS). IEEE, pp 161–171. https://doi.org/10.1109/RTAS.2015.7108439

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 CrossRef

Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, CambridgeCrossRefMATH

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

Carara E, Almeida GM, Sassatelli G, Moraes FG (2011) Achieving composability in NoC-based MPSoCs through QoS management at software level. In: Proceedings of the design, automation and test in Europe (DATE). IEEE, pp 407–412. https://doi.org/10.1109/DATE.2011.5763071

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

Che W, Chatha KS (2010) Scheduling of synchronous data flow models on scratchpad memory based embedded processors. In: Proceedings of the international conference on computer-aided design (ICCAD). IEEE, pp 205–212. https://doi.org/10.1109/ICCAD.2010.5654150

Choi J, Oh H, Kim S, Ha S (2012) Executing synchronous dataflow graphs on a SPM-based multicore architecture. In: Proceedings of the design automation conference (DAC). ACM, pp 664–671. https://doi.org/10.1145/2228360.2228480

10.

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 CrossRef

11.

Dally WJ, Towles B (2001) Route packets, not wires: on-chip inteconnection networks. In: Proceedings of the design automation conference (DAC). ACM, pp 684–689. https://doi.org/10.1145/378239.379048

12.

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

13.

Glaß M, Lukasiewycz M, Haubelt C, Teich J (2010a) Towards scalable system-level reliability analysis. In: Proceedings of the design automation conference (DAC). ACM, pp 234–239. https://doi.org/10.1145/1837274.1837334

14.

Glaß M, Lukasiewycz M, Reimann F, Haubelt C, Teich J (2010b) Symbolic system level reliability analysis. In: Proceedings of the international conference on computer-aided design (ICCAD). IEEE, pp 185–189. https://doi.org/10.1109/ICCAD.2010.5654134

15.

Goossens K, Hansson A (2010) The Aethereal network on chip after ten years: goals, evolution, lessons, and future. In: Proceedings of the design automation conference (DAC). ACM, pp 306–311. https://doi.org/10.1145/1837274.1837353

16.

Goossens K, Dielissen J, Radulescu A (2005) Æthereal network on chip: concepts, architectures, and implementations. IEEE Des Test Comput 22(5):414–421. https://doi.org/10.1109/MDT.2005.99 CrossRef

17.

Graf S, Reimann F, Glaß M, Teich J (2014) Towards scalable symbolic routing for multi-objective networked embedded system design and optimization. In: Proceedings of the conference on hardware/software codesign and system synthesis (CODES+ISSS). ACM, pp 2:1–2:10. https://doi.org/10.1145/2656075.2656102

18.

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

19.

Henkel J, Bauer L, Dutt N, Gupta P, Nassif SR, Shafique M, Tahoori MB, Wehn N (2013) Reliable on-chip systems in the nano-era: lessons learnt and future trends. In: Proceedings of the design automation conference (DAC). ACM, pp 99:1–99:10. https://doi.org/10.1145/2463209.2488857

20.

Hölzenspies PKF, Hurink J, Kuper J, Smit GJM (2008) Run-time spatial mapping of streaming applications to a heterogeneous multi-processor system-on-chip (MPSOC). In: Proceedings of the design, automation and test in Europe (DATE). ACM, pp 212–217. https://doi.org/10.1109/DATE.2008.4484688

21.

Hu J, Marculescu R (2003) Energy-aware mapping for tile-based NoC architectures under performance constraints. In: Proceedings of the Asia and South Pacific design automation conference (ASPDAC). ACM, pp 233–239. https://doi.org/10.1145/1119772.1119818

22.

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

23.

Lukasiewycz M, Glaß M, Haubelt C, Teich J (2008) Efficient symbolic multi-objective design space exploration. In: Proceedings of the Asia and South Pacific design automation conference (ASPDAC). IEEE, pp 691–696. https://doi.org/10.1109/ASPDAC.2008.4484040

24.

Mariani G, Sima VM, Palermo G, Zaccaria V, Silvano C, Bertels K (2012) Using multi-objective design space exploration to enable run-time resource management for reconfigurable architectures. In: Proceedings of the design, automation and test in Europe (DATE). IEEE, pp 1379–1384. https://doi.org/10.1109/DATE.2012.6176578

25.

Ngo TD, Martin KJ, Diguet JP (2015) Move based algorithm for runtime mapping of dataflow actors on heterogeneous MPSoCs. J Sig Process Syst: 1–18

26.

Orsila H, Kangas T, Salminen E, Hämäläinen TD, Hännikäinen M (2007) Automated memory-aware application distribution for multi-processor system-on-chips. J Syst Architecture 53(11):795–815. https://doi.org/10.1016/j.sysarc.2007.01.013 CrossRef

27.

Quan W, Pimentel AD (2015) A hybrid task mapping algorithm for heterogeneous MPSoCs. ACM Trans Embed Comput Syst (TECS) 14(1):14:1–14:25. https://doi.org/10.1145/2680542

28.

Schor L, Bacivarov I, Rai D, Yang H, Kang S, Thiele L (2012) Scenario-based design flow for mapping streaming applications onto on-chip many-core systems. In: Proceedings of the international conference on compilers, architecture, and synthesis for embedded systems (CASES). ACM, pp 71–80. https://doi.org/10.1145/2380403.2380422

29.

Shad F, Todd TD, Kezys V, Litva J (2001) Dynamic slot allocation (DSA) in indoor SDMA/TDMA using smart antenna basestation. IEEE/ACM Trans Netw 9(1):69–81. https://doi.org/10.1109/90.909025 CrossRef

30.

Shojaei H, Basten T, Geilen M, Davoodi A (2013) A fast and scalable multidimensional multiple-choice knapsack heuristic. ACM Trans Des Autom Electron Syst (TODAES) 18(4):51. https://doi.org/10.1145/2541012.2541014

31.

Singh AK, Kumar A, Srikanthan T (2012) Accelerating throughput-aware runtime mapping for heterogeneous mpsocs. ACM Trans Des Autom Electron Syst (TODAES) 18(1):9. https://doi.org/10.1145/2390191.2390200

32.

Singh AK, Shafique M, Kumar A, Henkel J (2013) Mapping on multi/many-core systems: survey of current and emerging trends. In: Proceedings of the design automation conference (DAC). ACM, pp 1:1–1:10. https://doi.org/10.1145/2463209.2488734

33.

Singh AK, Dziurzanski P, Mendis HR, Indrusiak LS (2017) A survey and comparative study of hard and soft real-time dynamic resource allocation strategies for multi-/many-core systems. ACM Comput Surv 50(2):24:1–24:40. https://doi.org/10.1145/3057267

34.

van Stralen P, Pimentel AD (2010) Scenario-based design space exploration of MPSoCs. In: Proceedings of the international conference on computer design (ICCD). IEEE, pp 305–312. https://doi.org/10.1109/ICCD.2010.5647727

35.

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

36.

Thiele L, Chakraborty S, Naedele M (2000) Real-time calculus for scheduling hard real-time systems. In: Proceedings of the international symposium on circuits and systems (ISCAS), vol 4. IEEE, pp 101–104. https://doi.org/10.1109/ISCAS.2000.858698

37.

Weichslgartner A, Gangadharan D, Wildermann S, Glaß M, Teich J (2014) DAARM: design-time application analysis and run-time mapping for predictable execution in many-core systems. In: Proceedings of the conference on hardware/software codesign and system synthesis (CODES+ISSS). ACM, pp 34:1–34:10. https://doi.org/10.1145/2656075.2656083

38.

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

39.

Wildermann S, Reimann F, Ziener D, Teich J (2011) Symbolic design space exploration for multi-mode reconfigurable systems. In: Proceedings of the conference on hardware/software codesign and system synthesis (CODES+ISSS). ACM, pp 129–138. https://doi.org/10.1145/2039370.2039393

40.

Wildermann S, Glaß M, Teich J (2014) Multi-objective distributed run-time resource management for many-cores. In: Proceedings of the design, automation and test in Europe (DATE), EDAA, pp 1–6. https://doi.org/10.7873/DATE.2014.234

41.

Wildermann S, Weichslgartner A, Teich J (2015) Design methodology and run-time management for predictable many-core systems. In: Proceedings of the workshop on self-organizing real-time systems (SORT). IEEE, pp 103–110. https://doi.org/10.1109/ISORCW.2015.48

42.

Wolkotte PT, Smit GJM, Kavaldjiev N, Becker JE, Becker J (2005) Energy model of networks-on-chip and a bus. In: Proceedings of the international symposium on system-on-chip (ISSOC). IEEE, pp 82–85. https://doi.org/10.1109/ISSOC.2005.1595650

43.

Ykman-Couvreur C, Nollet V, Catthoor F, Corporaal H (2006) Fast multi-dimension multi-choice knapsack heuristic for MP-SoC run-time management. In: Proceedings of the international symposium on system-on-chip (ISSOC), pp 1–4. https://doi.org/10.1109/ISSOC.2006.321966

Title: Hybrid Application Mapping
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_5