The Devito compiler

In Devito, an Operator carries out three fundamental tasks: generation of low-level code, JIT compilation, and execution. Overall, the lowering process performed by an Operator – from high-level equations to dynamically compiled and executable code – consists of multiple compiler passes, summarized in the Figure bellow. The following series of notebooks will describe these compilation passes in a hands-on fashion. We will explore the heart of the Operator class, which orchestrates code generation and compilation. For more details, see the Operator class.

compiler-stages

The reader of this series of tutorials is expected to be familiar with the basic Devito API (i.e., Grid, Function/TimeFunction, Operator, …). Otherwise, the CFD tutorials in examples/cfd are a better place to start.

Many of the examples and exercises shown here are extracted from test cases found in the folder devito/tests, or from the documentation itself.

Outline

• Preliminaries
  • Data regions
  • Data dependence analysis
• Lowering
  • Indexification
  • Substitutions
  • Domain alignment
  • Eq -> LoweredEq
• Clustering
• Symbolic optimization via a set of compilation passes operating on symbolic expressions
• Tree-fication (from symbolic expressions to Abstract Syntax Tree)
  • Clusters -> ScheduleTree
  • ScheduleTree -> Iteration/Expression Tree (IET)
  • IET examples
    • Part A: top-down inspection
    • Part B: bottom-up construction
• IET analysis
• Loop optimization via a set of compilation passes operating on the IET
  • Classic transformations (SIMD, blocking, …)
  • OpenMP shared-memory parallelism
  • MPI distributed-memory parallelism
• Finalization

References

F. Luporini, M. Lange, M. Loubotin, N. Kukreja, J. Huckelheim, C. Yount, P. Witte, P. Kelly, G. Gorman, F. Herrmann. Architecture and Performance of Devito, A System for Automated Stencil Computation. ACM Trans. Math. Softw. 46, 1, Article 6 (March 2020), 28 pages. [https://dl.acm.org/doi/10.1145/3374916]