A4: Design-Time Characterisation and Analysis of Invasive Algorithmic Patterns

Principal Investigators:

Prof. M. Glaß, Prof. M. Bader

Scientific Researchers:

A. Pöppl, T. Schwarzer, Dr. S. Wildermann B. Pourmohseni


The project investigates existing, develops novel, and analyses invasive algorithmic patterns wrt. qualities of execution to exploit the resource awareness of invasive computing. The research focuses on (a) stencil computations and non-regular tree traversals as invasive algorithmic patterns and (b) design-time characterisation techniques for the derivation of sets of optimised and diverse operating points by considering symmetries and system services of a given heterogeneous invasive manycore architecture.


The management and exploitation of dynamically-adapting and heterogeneous resources substantially increases the complexity of invasive algorithm design and invasive scheduling decisions: not just a certain amount of resources, but the best suitable combination of computation and communication resources needs to be selected and invaded at run time. To enforce a predictable quality of execution, applications need to carefully define their quality requirements and provide a precise characterisation of achievable qualities, which depend on the available resources (on a given manycore platform). Moreover, exposing requirement definitions and scheduling strategies to application developers opens new opportunities for the design of invasive algorithms in the sense of a co-design of algorithms, hardware, and resource management.
This project therefore investigates existing, develops novel, and characterises invasive algorithmic patterns and addresses the following main research questions: (a) How to derive and pass knowledge about the algorithms' and respective applications' performance characteristics on heterogeneous resources to a run-time system? (b) How to support online scheduling decisions based on this knowledge to improve (and/or enforce) quality requirements and system constraints? (c) How to develop invasion-aware algorithms such that they benefit from invasion on heterogeneous platforms?


Project A4 aims at contributing to the entire invasion chain by developing invasive algorithmic patterns, by a design-time characterisation of these patterns on available platforms, by derivation of sets of optimised operating points, and finally by evaluating the performance gain on concrete invasive platforms. As depicted in the above figure, the core of this project's research focuses on the interplay of algorithm development and invasive scheduling and mapping decisions that shall be guided by application characteristics automatically determined at design time. This characterisation that delivers which quality numbers may be achieved by a certain claim assembly and mapping (specified by claim constraints) is also indispensable for program execution at predictable quality. The two main research areas of A4 are thus: (a) Novel invasion-driven algorithmic patterns tailored to maximise performance and/or significantly enhance predictability of corresponding applications. (b) Automatic multi-objective characterisation of applications on concrete (heterogeneous tiled) architectures to guide the claim assembling performed by the invasive run-time system, particularly to enforce the predictability of application execution quality.


[1] Jan Spieck, Stefan Wildermann, Tobias Schwarzer, Jürgen Teich, and Michael Glaß. Data-Driven Scenario-based Application Mapping for Heterogeneous Many-Core Systems. In Multicore/Many-core Systems-on-Chip (MCSoC 2019), October 2019.
[2] Dirk Gabriel, Walter Stechele, and Stefan Wildermann. Resource-aware parameter tuning for real-time applications. In Martin Schoeberl, Christian Hochberger, Sascha Uhrig, Jürgen Brehm, and Thilo Pionteck, editors, Architecture of Computing Systems – ARCS 2019, pages 45–55. Springer International Publishing, 2019. [ DOI ]
[3] Jürgen Teich, Pouya Mahmoody, Behnaz Pourmohseni, Sascha Roloff, Wolfgang Schröder-Preikschat, and Stefan Wildermann. Run-Time Enforcement of Non-functional Program Properties on MPSoCs. Springer, 2019. to appear.
[4] Behnaz Pourmohseni, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Hard Real-Time Application Mapping Reconfiguration for NoC-Based Many-Core Systems. Real-Time Systems, pages 1–37, 2019. [ DOI ]
[5] Behnaz Pourmohseni, Fedor Smirnov, Stefan Wildermann, and Jürgen Teich. Isolation-aware timing analysis and design space exploration for predictable and composable many-core systems. In 31th Euromicro Conference on Real-Time Systems (ECRTS 2019), pages 12:1–12:24, 2019. [ DOI ]
[6] Behnaz Pourmohseni, Fedor Smirnov, Heba Khdr, Stefan Wildermann, Jürgen Teich, and Jörg Henkel. Thermally composable hybrid application mapping for real-time applications in heterogeneous many-core systems. In 40th IEEE Real-Time Systems Symposium (RTSS), 2019. accepted for publication.
[7] Tobias Schwarzer, Joachim Falk, Simone Müller, Martin Letras, Christian Heidorn, Stefan Wildermann, and Jürgen Teich. Compilation of Dataflow Applications for Multi-cores using Adaptive Multi-objective Optimization. ACM Transactions on Design Automation of Electronic Systems, 2019. accepted for publication.
[8] Alexander Pöppl, Scott Baden, and Michael Bader. A UPC++ actor library and its evaluation on a shallow water proxy application. In Parallel Applications Workshop, Alternatives To MPI+X, Denver, Colorado, United States of America, Nov 2019. IEEE, IEEE.
[9] Andreas Weichslgartner, Stefan Wildermann, Deepak Gangadharan, Michael Glaß, and Jürgen Teich. A design-time/run-time application mapping methodology for predictable execution time in mpsocs. ACM Transactions on Embedded Computing Systems (TECS), 17(5):89:1–89:25, November 2018. [ DOI ]
[10] Jörg Henkel, Jürgen Teich, Stefan Wildermann, and Hussam Amrouch. Dynamic resource management for heterogeneous many-cores. In Proceedings of the International Conference on Computer-Aided Design (ICCAD), pages 60:1–60:6. ACM, November 2018. [ DOI ]
[11] Tobias Schwarzer, Sascha Roloff, Valentina Richthammer, Rami Khaldi, Stefan Wildermann, Michael Glaß, and Jürgen Teich. On the Complexity of Mapping Feasibility in Many-Core Architectures. In Proceedings of Multicore/Many-core Systems-on-Chip (MCSoC-2018), September 2018.
[12] Valentina Richthammer, Tobias Schwarzer, Stefan Wildermann, Jürgen Teich, and Michael Glaß. Architecture Decomposition in System Synthesis of Heterogeneous Many-Core Systems. In 55th ACM/EDAC/IEEE Design Automation Conference (DAC 2018), June 2018.
[13] Tobias Schwarzer, Andreas Weichslgartner, Michael Glaß, Stefan Wildermann, Peter Brand, and Jürgen Teich. Symmetry-eliminating Design Space Exploration for Hybrid Application Mapping on Many-Core Architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(2):297–310, February 2018. [ DOI ]
[14] Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Invasive Computing for Mapping Parallel Programs to Many-Core Architectures. Springer, January 15, 2018. [ DOI ]
[15] Alexander Pöppl, Marvin Damschen, Florian Schmaus, Andreas Fried, Manuel Mohr, Matthias Blankertz, Lars Bauer, Jörg Henkel, Wolfgang Schröder-Preikschat, and Michael Bader. Shallow water waves on a deep technology stack: Accelerating a finite volume tsunami model using reconfigurable hardware in invasive computing. In Dora B. Heras, Luc Bougé, Gabriele Mencagli, Emmanuel Jeannot, Rizos Sakellariou, Rosa M. Badia, Jorge G. Barbosa, Laura Ricci, Stephen L. Scott, Stefan Lankes, and Josef Weidendorfer, editors, Euro-Par 2017: Proceedings of the 10th Workshop on UnConventional High Performance Computing (UCHPC 2017), Lecture Notes in Computer Science (LNCS), pages 676–687, Cham, 2018. Springer International Publishing.
[16] Michael Glaß, Jürgen Teich, Martin Lukasiewycz, and Felix Reimann. Hybrid optimization techniques for system-level design space exploration. In Soonhoi Ha and Jürgen Teich, editors, Handbook of Hardware/Software Codesign, volume 1, pages 217–246. Springer, Dordrecht, The Netherlands, September 2017. [ DOI ]
[17] Hananeh Aliee. Reliability Analysis and Optimization of Embedded Systems using Stochastic Logic and Importance Measures. Dissertation, Hardware/Software Co-Design, Department of Computer Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany, March 15, 2017.
[18] Behnaz Pourmohseni, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Predictable run-time mapping reconfiguration for real-time applications on many-core systems. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS). IEEE, 2017. Outstanding paper award. [ DOI ]
[19] Behnaz Pourmohseni, Michael Glaß, and Jürgen Teich. Automatic Operating Point Distillation for Hybrid Mapping Methodologies. In Proceedings of Design, Automation and Test in Europe Conference Exhibition (DATE), pages 1135–1140. IEEE, 2017. [ DOI ]
[20] Jürgen Teich. Invasive computing – editorial. it – Information Technology, 58(6):263–265, November 24, 2016. [ DOI ]
[21] Alexander Pöppl, Michael Bader, Tobias Schwarzer, and Michael Glaß. SWE-X10: Simulating shallow water waves with lazy activation of patches using ActorX10. In Proceedings of the 2nd International Workshop on Extreme Scale Programming Models and Middleware (ESPM2), pages 32–39. IEEE, November 2016. [ .pdf ]
[22] Stefan Wildermann, Michael Bader, Lars Bauer, Marvin Damschen, Dirk Gabriel, Michael Gerndt, Michael Glaß, Jörg Henkel, Johny Paul, Alexander Pöppl, Sascha Roloff, Tobias Schwarzer, Gregor Snelting, Walter Stechele, Jürgen Teich, Andreas Weichslgartner, and Andreas Zwinkau. Invasive computing for timing-predictable stream processing on MPSoCs. it – Information Technology, 58(6):267–280, September 30, 2016. [ DOI ]
[23] Jürgen Teich, Michael Glaß, Sascha Roloff, Wolfgang Schröder-Preikschat, Gregor Snelting, Andreas Weichslgartner, and Stefan Wildermann. Language and compilation of parallel programs for *-predictable MPSoC execution using invasive computing. In Proceedings of the 10th IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC), pages 313–320, Lyon, France, September 2016. [ DOI ]
[24] Sascha Roloff, Alexander Pöppl, Tobias Schwarzer, Stefan Wildermann, Michael Bader, Michael Glaß, Frank Hannig, and Jürgen Teich. ActorX10: An actor library for X10. In Proceedings of the 6th ACM SIGPLAN X10 Workshop (X10), pages 24–29. ACM, June 14, 2016. [ DOI ]
[25] Andreas Weichslgartner, Stefan Wildermann, Johannes Götzfried, Felix Freiling, Michael Glaß, and Jürgen Teich. Design-time/run-time mapping of security-critical applications in heterogeneous mpsocs. In Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems (SCOPES), pages 153–162. ACM, May 23, 2016. [ DOI ]
[26] Hans Michael Gerndt, Michael Glaß, Sri Parameswaran, and Barry L. Rountree. Dark Silicon: From Embedded to HPC Systems (Dagstuhl Seminar 16052). Dagstuhl Reports, 6(1):224–244, 2016. [ DOI ]
[27] Alexander Pöppl and Alexander Herz. A cache-aware performance prediction framework for gpgpu computations. In Sascha Hunold, Jesper Larsson Träff, and Francesco Versaci, editors, Euro-Par 2015: Parallel Processing Workshops, Lecture Notes in Computer Science, Berlin, Heidelberg, 2016. Springer-Verlag.
[28] Alexander Pöppl and Michael Bader. Swe-x10: An actor-based and locally coordinated solver for the shallow water equations. In Proceedings of the 6th ACM SIGPLAN Workshop on X10, X10 2016, pages 30–31. ACM, 2016. [ DOI ]
Keywords: APGAS, Actor Model, Parallel Algorithms, Shallow Water Equations
[29] Michael Bader. Performance optimzation vs. power - experiences with petascale earthquake simulations on supermuc. Talk at the Workshop on Power-Bounded HPC Performance Optimisation at Schloss Dagstuhl, August 2015.
[30] Alexander Breuer, Alexander Heinecke, Leonhard Rannabauer, and Michael Bader. High-order ader-dg minimizes energy- and time-to-solution of seissol. In High Performance Computing, 30th International Conference, ISC High Performance 2015, Frankfurt, Germany, July 12-16, 2015, Proceedings, volume 9137 of Lecture Notes in Computer Science, pages 340–357. Springer, July 2015.
[31] Michael Bader. Vectorization of riemann solvers for the shallow water equations. Minisymposium Flooding the Cores - Computing Flooding Events with Many-Core and Accelerator Technologies at SIAM Conference on Computational Science and Engineering, March 2015.
[32] Sebastian Graf, Felix Reimann, Michael Glaß, and Jürgen Teich. Towards scalable symbolic routing for multi-objective networked embedded system design and optimization. In Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS 2014), pages 2:1–2:10, October 12, 2014. [ DOI ]
[33] Andreas Weichslgartner, Deepak Gangadharan, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Daarm: Design-time application analysis and run-time mapping for predictable execution in many-core systems. In Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS 2014), pages 1–10, October 2014. [ DOI ]
[34] Tobias Weinzierl, Michael Bader, Kristof Unterweger, and Roland Wittmann. Block fusion on dynamically adaptive spacetree grids for shallow water waves. Parallel Processing Letters, 24(3):1441006, September 2014.
[35] Michael Glaß, Michael Bader, Jürgen Teich, and Stefan Wildermann. Assisting run-time optimization of many-core systems by design-time characterization. HiPEAC Spring Computing Systems Week, Barcelona, Invited Talk, May 13, 2014.
[36] Stefan Wildermann, Michael Glaß, and Jürgen Teich. Multi-objective distributed run-time resource management for many-cores. In Proceedings of Design, Automation and Test in Europe (DATE), pages 1–6, March 2014. [ DOI ]
[37] Michael Bader. On the performance of adaptive mesh-based simulations on modern hpc architectures. Invited presentation at SIAM Conference on Parallel Processing in Scientific Computing - SIAM PP 2014, February 2014. [ .pdf ]
[38] Michael Bader. Exploiting locality properties of space-filling curves in scientific computing. Colloquium talk at TU Eindhoven, November 2013.