D3: Multilevel Approaches and Adaptivity in Scientific Computing

Principal Investigators:

Prof. Bungartz, Prof. Gerndt

Scientific Researchers:

Prof. Michael Bader, Andreas Hollmann, Tobias Neckel, Martin Schreiber, Josef Weidendorfer, Tobias Weinzierl


In subproject D3, the potential of invasive computing for scientific computing is explored. We examine how numerical algorithms need to be adapted to invasion-enabled hardware, and how invasive applications can be realised on standard HPC systems based on iOpenMP, an extension of OpenMP. We demonstrate the advantages of invasion in scientific computing via implementations of algorithmic building blocks on invasive hardware and, as a demonstrator, Tsunami simulations on classical multi- and many-core HPC systems. Thus, subproject D3 will have a strong impact on both scientific computing and invasive programming.


"In their paper, titled Invasive Computing on High Performance Shared Memory Systems, three researchers from the Department of Informatics, at Garching, Germany, offer new approaches for improving the throughput of runtime-adaptive applications on cutting-edge HPC systems"
HPC Wire


All hardware platforms for scientific computing follow the general trend to more parallelism, via multi- and many-core processors, GPUs, FPGAs, MPSoCs, and processor arrays. On the application side, the complexity of scientific computing algorithms is increasing as well. Hierarchy and dynamic adaptivity are essential paradigms for large-scale numerical simulations.

In contrast, programming models and the management of cores and memories in HPC architectures are still dominated by static allocation. Resources are allocated by batch scheduling systems, and the standard programming interfaces OpenMP and MPI focus on the efficient execution of applications on an initially given set of resources. Most applications on HPC systems are adapted to this static resource allocation. Either there is no additional parallelism in program phases that can be exploited or this parallelism is not exploited to not reduce the overall efficiency.

Hence, the goal of subproject D3 is to study invasion as a paradigm to bring together the varying amount of parallelism in multilevel adaptive applications with growing numbers of cores. We identify algorithmic approaches and best practices to implement key components of scientific applications on the basis of the invasion principle and on invasive hardware. In addition, we determine extensions to the resource management of HPC architectures and the standard programming interfaces MPI and OpenMP to enable invasive programming on future HPC systems for existing simulation codes.

In the algorithmic part, we study invasive approaches for dynamically adaptive multilevel solvers. Partitions are allowed to dynamically grow and shrink—w. r. t. partition size, refinement level, and multigrid levels—and especially to split and merge in terms of parallel threads according to the invasion paradigm, to tackle the resulting load-balancing challenges. The respective core algorithms are extracted from an existing hierarchical approach to compute wave propagation in the context of Tsunami simulation, which we choose as a realistic and challenging demonstrator. We implement these core algorithms using invasive programming languages and on first prototypes of invasive hardware.

To demonstrate the advantages of invasive computing to the HPC community, extensions to OpenMP and MPI for invasive programming are required to be minimal, to enable an incremental invasification, but also support data locality. We concentrate on iOpenMP, an invasive version of OpenMP, since OpenMP already supports flexible utilisation of a fixed set of resources, and since the first invasive hardware developments are of shared memory type, too. A prototypical implementation of iOpenMP is realised on standard shared memory HPC systems to serve as programming model for an invasive Tsunami simulation. The step towards clusters of such compute nodes, that is, hybrid systems, is planned for the second funding phase.

Hence, subproject D3 has a double impact: It tackles urgent problems in HPC and it helps to widen the scope of invasion towards HPC, which is essential for invasive computing to become a widely accepted paradigm for parallel programming.

Current state:


Example: Interactive adaptive simulation based on Shallow Water Equation and Discontinuous Galerkin Discretization. Parallelization is achieved via massive-tree splits and joins.

Visualization of the grid.

Invasive Resource Manager:

Scalability graph for the above mentioned problem. Depending on the probme size which is given by the number of cells, the scalability changes. Changing of scalability is forwarded to the resource manager.


Four shallow water simulations are started with a small delay. The resource manager distributes the cores to the application to maximize global throughput depending on the current scalability graph of the application. During start of the 2nd application (blue), less cores are assigned to it compared to the first application (red) since the scalability is worse.

Tsunami Simulation:

Tsunami Simulation for Tohoku Tsunami (In Germany known as the 'Fukushima Tsunami')
More information about simulation framework is available at Sierpinski


[1] 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 | http ]
[2] Weifeng Liu, Michael Gerndt, and Bin Gong. Model-based MPI-IO tuning with Periscope tuning framework. Concurrency and Computation: Practice and Experience, 28(1):3–20, 2016. [ DOI ]
Keywords: parallel I/O, automatic tuning, MPI-IO, performance model, high-performance computing
[3] 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üurgen Teich, Andreas Weichslgartner, and Andreas Zwinkau. Invasive computing for timing-predictable stream processing on MPSoCs. it - Information Technology, 2016. To appear.
[4] Martin Schreiber, Christoph Riesinger, Tobias Neckel, Hans-Joachim Bungartz, and Alexander Breuer. Invasive compute balancing for applications with shared and hybrid parallelization. International Journal of Parallel Programming, September 2014. [ DOI | http ]
[5] Carsten Tradowsky, Martin Schreiber, Malte Vesper, Ivan Domladovec, Maximilian Braun, Hans-Joachim Bungartz, and Jürgen Becker. Towards dynamic cache and bandwidth invasion. In Reconfigurable Computing: Architectures, Tools, and Applications, volume 8405 of Lecture Notes in Computer Science, pages 97–107. Springer International Publishing, April 2014. [ DOI ]
[6] Martin Schreiber. Cluster-Based Parallelization of Simulations on Dynamically Adaptive Grids and Dynamic Resource Management. Dissertation, Institut für Informatik, Technische Universität München, January 2014. [ .pdf ]
[7] Martin Schreiber, Christoph Riesinger, Tobias Neckel, and Hans-Joachim Bungartz. Invasive compute balancing for applications with hybrid parallelization. In Proceedings of the International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD). IEEE, October 2013.
[8] Martin Schreiber, Tobias Weinzierl, and Hans-Joachim Bungartz. Sfc-based communication metadata encoding for adaptive mesh refinement. In Michael Bader, editor, Proceedings of the International Conference on Parallel Computing (ParCo), October 2013. In press.
[9] Martin Schreiber, Tobias Weinzierl, and Hans-Joachim Bungartz. Cluster optimization and parallelization of simulations with dynamically adaptive grids. In Euro-Par 2013, August 2013.
[10] Hans-Joachim Bungartz, Christoph Riesinger, Martin Schreiber, Gregor Snelting, and Andreas Zwinkau. Invasive computing in HPC with X10. In X10 Workshop (X10'13), X10 '13, pages 12–19, New York, NY, USA, 2013. ACM. [ DOI ]
[11] Michael Gerndt, Andreas Hollmann, Marcel Meyer, Martin Schreiber, and Josef Weidendorfer. Invasive computing with iOMP. In Proceedings of the Forum on Specification and Design Languages (FDL), pages 225–231, September 2012.
[12] Isaías A. Comprés Ureña, Michael Riepen, Michael Konow, and Michael Gerndt. Invasive MPI on intel's single-chip cloud computer. In Andreas Herkersdorf, Kay Römer, and Uwe Brinkschulte, editors, Proceedings of the 25th International Conference on Architecture of Computing System (ARCS), volume 7179 of Lecture Notes in Computer Science, pages 74–85. Springer, February 2012. [ DOI ]
[13] Michael Bader, Hans-Joachim Bungartz, and Martin Schreiber. Invasive computing on high performance shared memory systems. In Facing the Multicore-Challenge III, volume 7686 of Lecture Notes in Computer Science, pages 1–12, 2012.
[14] Andreas Hollmann and Michael Gerndt. Invasive computing: An application assisted resource management approach. In Victor Pankratius and Michael Philippsen, editors, Multicore Software Engineering, Performance, and Tools, volume 7303 of Lecture Notes in Computer Science, pages 82–85. Springer Berlin Heidelberg, 2012. [ DOI | http ]
Keywords: resource management; resource awareness; numa; parallel programming; OpenMP
[15] Martin Schreiber, Hans-Joachim Bungartz, and Michael Bader. Shared memory parallelization of fully-adaptive simulations using a dynamic tree-split and -join approach. In Proceedings of HiPC 2012, pages 1–10. IEEE, 2012.
[16] Michael Bader, Hans-Joachim Bungartz, Michael Gerndt, Andreas Hollmann, and Josef Weidendorfer. Invasive programming as a concept for HPC. In Proceedings of the 10th IASTED International Conference on Parallel and Distributed Computing and Networks 2011 (PDCN), February 2011. [ DOI ]
[17] Hans-Joachim Bungartz, Bernhard Gatzhammer, Michael Lieb, Miriam Mehl, and Tobias Neckel. Towards multi-phase flow simulations in the PDE framework peano. Computational Mechanics, 48(3):365–376, 2011. [ .pdf ]
[18] Jürgen Teich, Jörg Henkel, Andreas Herkersdorf, Doris Schmitt-Landsiedel, Wolfgang Schröder-Preikschat, and Gregor Snelting. Invasive computing: An overview. In Michael Hübner and Jürgen Becker, editors, Multiprocessor System-on-Chip – Hardware Design and Tool Integration, pages 241–268. Springer, Berlin, Heidelberg, 2011. [ DOI ]
[19] Jürgen Teich. Invasive algorithms and architectures. it - Information Technology, 50(5):300–310, 2008.
[20] Isaías A. Comprés Ureña and Michael Gerndt. Improved RCKMPI's SCCMPB channel: Scaling and dynamic processes support. 4th MARC Symposium.
[21] Andreas Hollmann and Michael Gerndt. iOMP language specification 1.0. Internal Report.
[22] Andreas Hollmann and Michael Gerndt. Invasive computing: An application assisted resource management approach. In MSEPT, pages 82–85.