Projects


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

Abstract

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.

News

"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

Synopsis

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:

Application:

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.

Results:

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

Publications

[1] Nidhi Anantharajaiah, Tamim Asfour, Michael Bader, Lars Bauer, Jürgen Becker, Simon Bischof, Marcel Brand, Hans-Joachim Bungartz, Christian Eichler, Khalil Esper, Joachim Falk, Nael Fasfous, Felix Freiling, Andreas Fried, Michael Gerndt, Michael Glaß, Jeferson Gonzalez, Frank Hannig, Christian Heidorn, Jörg Henkel, Andreas Herkersdorf, Benedict Herzog, Jophin John, Timo Hönig, Felix Hundhausen, Heba Khdr, Tobias Langer, Oliver Lenke, Fabian Lesniak, Alexander Lindermayr, Alexandra Listl, Sebastian Maier, Nicole Megow, Marcel Mettler, Daniel Müller-Gritschneder, Hassan Nassar, Fabian Paus, Alexander Pöppl, Behnaz Pourmohseni, Jonas Rabenstein, Phillip Raffeck, Martin Rapp, Santiago Narváez Rivas, Mark Sagi, Franziska Schirrmacher, Ulf Schlichtmann, Florian Schmaus, Wolfgang Schröder-Preikschat, Tobias Schwarzer, Mohammed Bakr Sikal, Bertrand Simon, Gregor Snelting, Jan Spieck, Akshay Srivatsa, Walter Stechele, Jürgen Teich, Furkan Turan, Isaías A. Comprés Ureña, Ingrid Verbauwhede, Dominik Walter, Thomas Wild, Stefan Wildermann, Mario Wille, Michael Witterauf, and Li Zhang. Invasive Computing. FAU University Press, August 16, 2022. [ DOI ]
[2] Xingfu Wu, Aniruddha Marathe, Siddhartha Jana, Ondrej Vysocky, Jophin John, Andrea Bartolini, Lubomir Riha, Michael Gerndt, Valerie Taylor, and Sridutt Bhalachandra. Toward an end-to-end auto-tuning framework in hpc powerstack. In Energy Efficient HPC State of Practice 2020, 2020. accepted for publication.
[3] Mohak Chadha, Jophin John, and Michael Gerndt. Extending slurm for dynamic resource-aware adaptive batch scheduling. In IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC) 2020, 2020. accepted for publication.
[4] Ao Mo-Hellenbrand. Resource-Aware and Elastic Parallel Software Development for Distributed-Memory HPC Systems. Dissertation, Technische Universität München, Munich, 2019. [ http ]
[5] Jophin John, Santiago Narvaez R, and Michael Gerndt. Invasive computing for power corridor management. In Proceedings of the ParCo 2019: International Conference on Parallel Computing, 2019. accepted for publication.
[6] Mohak Chadha and Michael Gerndt. Modelling dvfs and ufs for region-based energy aware tuning of hpc applications. In IEEE International Parallel and Distributed Processing Symposium (IPDPS 2019), 2019.
[7] Jeeta Ann Chacko, Isaías Alberto Comprés Ureña, and Michael Gerndt. Integration of apache spark with invasive resource manager. In 2019 IEEE SmartWorld, Ubiquitous Intelligence and Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation, 2019. Best Paper Award.
[8] Santiago Narvaez. Power model for resource-elastic applications. Master thesis, Technische Universität München, Munich, 2018. [ http ]
[9] Carsten Uphoff, Sebastian Rettenberger, Michael Bader, Stephanie Wollherr, Thomas Ulrich, Elizabeth H. Madden, and Alice-Agnes Gabriel. Extreme scale multi-physics simulations of the tsunamigenic 2004 Sumatra megathrust earthquake. In SC17: The International Conference for High Performance Computing, Networking, Storage and Analysis Proceedings. ACM, 2017. [ DOI ]
[10] Ao Mo-Hellenbrand, Isaías Comprés, Oliver Meister, Hans-Joachim Bungartz, Michael Gerndt, and Michael Bader. A large-scale malleable tsunami simulation realized on an elastic MPI infrastructure. In Proceedings of the Computing Frontiers Conference (CF), pages 271–274. ACM, 2017. [ DOI ]
Keywords: Malleable Applications, Elastic Computing, Resource Aware Computing, Adaptive Mesh Refinement, Elastic MPI, Message Passing, SLURM, Autonomous Resource Management
[11] Isaías Alberto Comprés Ureña. Resource-Elasticity Support for Distributed Memory HPC Applications. Dissertation, Technical University of Munich, Munich, 2017. [ arXiv | http ]
[12] Jürgen Teich. Invasive computing – editorial. it – Information Technology, 58(6):263–265, November 24, 2016. [ DOI ]
[13] 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 ]
[14] 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
[15] 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 ]
[16] 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 ]
[17] 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 ]
[18] 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 ]
[19] 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.
[20] 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.
[21] Martin Schreiber, Tobias Weinzierl, and Hans-Joachim Bungartz. Cluster optimization and parallelization of simulations with dynamically adaptive grids. In Euro-Par 2013, August 2013.
[22] 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 ]
[23] 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.
[24] 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 ]
[25] 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.
[26] 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 ]
Keywords: resource management; resource awareness; numa; parallel programming; OpenMP
[27] 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.
[28] 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 ]
[29] 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 ]
[30] 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 ]
[31] Jürgen Teich. Invasive algorithms and architectures. it - Information Technology, 50(5):300–310, 2008.
[32] Andreas Hollmann and Michael Gerndt. Invasive computing: An application assisted resource management approach. In MSEPT, pages 82–85. [ DOI ]
[33] Andreas Hollmann and Michael Gerndt. iOMP language specification 1.0. Internal Report.
[34] Isaías A. Comprés Ureña and Michael Gerndt. Improved RCKMPI's SCCMPB channel: Scaling and dynamic processes support. 4th MARC Symposium.