Dagstuhl Seminar 15161
Advanced Stencil-Code Engineering
( Apr 12 – Apr 17, 2015 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/15161
Organizers
- Matthias Bolten (Bergische Universität Wuppertal, DE)
- Robert D. Falgout (LLNL - Livermore, US)
- Christian Lengauer (Universität Passau, DE)
- Olaf Schenk (University of Lugano, CH)
Contact
- Andreas Dolzmann (for scientific matters)
- Christina Schwarz (for administrative matters)
The seminar will investigate and further the state of the art of stencil-code engineering. Stencil codes have extremely high significance and value for a good-sized community of scientific computing experts in academia and industry. They see wide-spread use in computing the discrete solutions of partial differential equations and systems composed of such equations. Connected to the implementation of stencil codes is the use of efficient solver technology, i.e., iterative solvers that rely on the application of a stencil and that provide good convergence properties. Major application areas are the natural sciences and engineering.
Stencil codes are algorithms with a pleasantly high regularity: the data structures are higher-dimensional grids and the computations follow a static, locally contained dependence pattern and are typically arranged in nested loops with linearly affine bounds. This invites massive parallelism and raises the hope for easily achieved high performance. However, serious challenges remain:
- Because of the large numbers and varieties of stencil code implementations, deriving each of them individually, even if by code modification from one another, is not practical. Not even the use of program libraries is practical; instead, a domain-specific metaprogramming approach is needed.
- Efficiency, i.e., a high ratio of speedup to the degree of parallelism, is impaired by the low mathematical density, i.e., the low ratio of computation steps to data transfers of stencil codes.
- An inappropriate use of the execution platform may act as a performance brake.
Stencil-code engineering has received increased attention in the last few years, which is evidenced by the appearance of a number of stencil-code programming languages and frameworks, such as Liszt/DeLite, Pochoir, PATUS, HIPACC and others. To reach the highest possible execution speed and to conserve hardware resources and energy, the stencil code must be tuned cleverly to the specific application problem at hand and the execution platform used. This circumstance and a variety of optimization techniques make the spectrum of concrete stencil codes so wide that it can only be managed reliably by an automated software technology. In addition, to predict the performance of a stencil code, a performance model and mathematical tools for forecasting the expected convergence properties are necessary.
The goal of the seminar is to raise the level of abstraction for application programmers significantly and to support this raise with an automated software technology that generates highly efficient massively parallel implementations which are tuned to the specific problem at hand and the execution platform used. Concepts whose place in and benefit for stencil code engineering will be discussed include domain-specific programming languages, program skeletons, software product lines, autotuning, machine learning, polyhedral loop optimization and others.
The seminar will bring together experts on stencil codes from mathematics, computer science, high-performance computing, and software engineering, as well as from application domains such as physics and engineering. Members of the projects mentioned above are on the invitation list. A special issue on the seminar in a high-quality international journal will be compiled subsequently.
Stencil codes are compute-intensive algorithms, in which data points arranged in a large grid are being recomputed repeatedly from the values of data points in a predefined neighborhood. This fixed neighborhood pattern is called a stencil. Stencil codes see wide-spread use in computing the discrete solutions of partial differential equations and systems composed of such equations. Connected to the implementation of stencil codes is the use of efficient solver technology, i.e., iterative solvers that rely on the application of a stencil and that provide good convergence properties like multigrid methods. Major application areas are the natural sciences and engineering. Although, in many of these applications, unstructured adaptive discretizations are employed for an efficient use of exascale supercomputers whose architectures possibly include accelerators or are of a heterogeneous nature, the use of structured discretizations and, thus, stencil codes has turned out to be helpful.
Stencil codes come in large varieties: there are many thousands! Deriving each of them individually, even if by code modification from one another, is not practical. The goal of the seminar is to raise the level of abstraction for application programmers significantly and to support this raise with an automated software technology that generates highly efficient massively parallel implementations which are tuned to the specific problem at hand and the execution platform used.
Research Challenges
Stencil codes are algorithms with a pleasantly high regularity: the data structures are higher-dimensional grids and the computations follow a static, locally contained dependence pattern and are typically arranged in nested loops with linearly affine bounds. This invites massive parallelism and raises the hope for easily achieved high performance. However, serious challenges remain:
- Because of the large numbers and varieties of stencil code implementations, deriving each of them individually, even if by code modification from one another, is not practical. Not even the use of program libraries is practical; instead, a domain-specific metaprogramming approach is needed.
- Reaching petascale to exascale execution speed is a challenge in the frequently used so-called multigrid algorithms, which work on a hierarchy of increasingly larger grids. The coarse grids in the upper part of the hierarchy are too small for massive parallelism.
- Efficiency, i.e., a high ratio of speedup to the degree of parallelism, is impaired by the low mathematical density, i.e., the low ratio of computation steps to data transfers of stencil codes.
- An inappropriate use of the execution platform may act as a performance brake.
Stencil-code engineering has received increased attention in the last few years, which is evidenced by the appearance of a number of stencil-code programming languages and frameworks. To reach the highest possible execution speed and to conserve hardware resources and energy, the stencil code must be tuned cleverly to the specific application problem at hand and the execution platform used. One approach that could be followed has been demonstrated by the previous U.S. project SPIRAL, whose target was the domain of linear transforms: domain-specific optimization at several levels of abstraction -- from the mathematical equations over an abstract, domain-specific program and, in further steps, to the actual target code on the execution platform used. At each level, one makes aggressive use of knowledge of the problem and platform and employs up-to-date, automated software technology suitable for that level.
Questions and Issues Addressed
The charter of the seminar was to foster international cooperation in the development of a radically new, automatic, optimizing software technology for the effective and flexible exploitation of massively parallel architectures for dedicated, well delineated problem domains.
The central approaches in achieving this technology are:
- the aggressive use of domain knowledge for optimization at different levels of abstraction
- the exploitation of commonalities and variabilities in application codes via product-line technology and domain engineering
- the use of powerful models for program optimization, like the polyhedron model for loop parallelization and feature-orientation for software product lines
Among the issues discussed were:
- What are suitable abstraction, modularization, composition and generation mechanisms for stencil codes?
- What are the appropriate language features of a domain-specific language for stencil codes?
- What are the commonalities and variabilities of stencil codes?
- What are the computational performance barriers, especially, of multigrid methods using stencils and how can they be overcome?
- What are the performance barriers caused by data exchanges and how can they be overcome? How can communication be avoided in multilevel algorithms?
- What are the roles of nested loops and divide-and-conquer recursions in stencil codes?
- How can other solvers and preconditioners benefit from autotuned stencil codes?
- What role should techniques like autotuning and machine learning play in the optimization of stencil codes?
- What options of mapping stencil codes to a heterogeneous execution platform exist and how can an educated choice be made?
- Which techniques can be employed to make clever use of large-scale hybrid architectures, e.g., by the combination of multigrid with mathematical domain decomposition?
On the informatics side, one important role of the seminar was to inform the international stencils community about the techniques used in ExaStencils: software product lines, polyhedral loop optimization and architectural metaprogramming. Equally important was for ExaStencils members to learn about the experiences made with other techniques like divide-and-conquer, multicore optimization in parallel algorithms or autotuning. The application experts contributed to a realistic grounding of the research questions.
On the mathematics side, the seminar fostered the cooperation of experts in parallel solver technology with the groups from informatics to enable them to make use of the advanced techniques available. Further, different strategies for improving the scalability of iterative methods were discussed and the awareness of the opportunities and complexities of modern architectures in the numerical mathematics community was advanced.
Creative Commons BY 3.0 Unported license
Matthias Bolten, Robert D. Falgout, Christian Lengauer, and Olaf Schenk
- Sven Apel (Universität Passau, DE) [dblp]
- Mauro Bianco (CSCS - Lugano, CH) [dblp]
- Matthias Bolten (Bergische Universität Wuppertal, DE) [dblp]
- Uday Bondhugula (Indian Institute of Science - Bangalore, IN) [dblp]
- Rezaul Chowdhury (Stony Brook University, US) [dblp]
- Simplice Donfack (University of Lugano, CH) [dblp]
- Christian Engwer (Universität Münster, DE) [dblp]
- Robert D. Falgout (LLNL - Livermore, US) [dblp]
- Franz Franchetti (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Michael Freitag (Universität Passau, DE) [dblp]
- Stephanie Friedhoff (KU Leuven, BE) [dblp]
- Francisco Jose Gaspar (University of Zaragoza, ES) [dblp]
- Björn Gmeiner (Universität Erlangen-Nürnberg, DE) [dblp]
- Alexander Grebhahn (Universität Passau, DE) [dblp]
- Tobias Grosser (ETH Zürich, CH) [dblp]
- Armin Größlinger (Universität Passau, DE) [dblp]
- Gundolf Haase (Universität Graz, AT) [dblp]
- Georg Hager (Universität Erlangen-Nürnberg, DE) [dblp]
- Frank Hannig (Universität Erlangen-Nürnberg, DE) [dblp]
- Juraj Kardos (Brno University of Technology, CZ)
- Paul H. J. Kelly (Imperial College London, GB) [dblp]
- Hans-Peter Kersken (DLR - Köln, DE) [dblp]
- Harald Köstler (Universität Erlangen-Nürnberg, DE) [dblp]
- Stefan Kronawitter (Universität Passau, DE) [dblp]
- Sebastian Kuckuk (Universität Erlangen-Nürnberg, DE) [dblp]
- Bradley C. Kuszmaul (MIT - Cambridge, US) [dblp]
- Christian Lengauer (Universität Passau, DE) [dblp]
- Dmitry Mikushin (University of Lugano, CH) [dblp]
- Marcus Mohr (LMU München, DE) [dblp]
- Carlos Osuna Escamilla (ETH Zürich, CH)
- Ekanathan Palamadai Natarajan (MIT - Cambridge, US) [dblp]
- Dirk Pflüger (Universität Stuttgart, DE) [dblp]
- Louis-Noël Pouchet (Ohio State University - Columbus, US) [dblp]
- Hannah Rittich (Bergische Universität Wuppertal, DE) [dblp]
- Carmen Rodrigo Cardiel (University of Zaragoza, ES) [dblp]
- Ulrich Rüde (Universität Erlangen-Nürnberg, DE) [dblp]
- P. (Saday) Sadayappan (Ohio State University - Columbus, US) [dblp]
- Olaf Schenk (University of Lugano, CH) [dblp]
- Christian Schmitt (Universität Erlangen-Nürnberg, DE) [dblp]
- Armando Solar-Lezama (MIT - Cambridge, US) [dblp]
- Jürgen Teich (Universität Erlangen-Nürnberg, DE) [dblp]
- Wim Vanroose (University of Antwerp, BE) [dblp]
- Christian Waluga (TU München, DE) [dblp]
- Gabriel Wittum (Universität Frankfurt, DE) [dblp]
- Barbara Wohlmuth (TU München, DE) [dblp]
- Ulrike Meier Yang (LLNL - Livermore, US) [dblp]
Classification
- modelling / simulation
- programming languages / compiler
- software engineering
Keywords
- stencil codes
- architectural metaprogramming
- linear solvers
- multigrid methods
- supercomputing
- software engineering
- massive parallelism
