Automatic Code Generation with Mathematica

Kranc is a Mathematica package which generates Cactus thorns from equations. Starting from equations in Mathematica format, specifying a system of PDEs in abstract index notation, Kranc discretises the equations and generates a complete Cactus thorn that evaluates these equations. Kranc-generated thorns use all relevant Cactus APIs for initial data setup, analysis, time integration with MoL, and adaptive mesh refinement using Carpet. Kranc was originally developed by Sascha Husa, Ian Hinder, and Christiane Lechner.

We have updated our Kranc web site. This page is now outdated; please go on to kranccode.org for up-to-date information.

In the Alpaca project, we extend Kranc with additional capabilities to monitor and improve Kranc-generated code:

• Kranc-generated code can use LoopControl to automatically parallelise inner loops with OpenMP, combining both MPI and OpenMP for best performance on current multi-core systems.
• LoopControl also uses loop tiling (blocking) to optimise cache use on modern architectures with memory hierarchies.
• We are experimenting with generating hardware-specific code in Mathematica, e.g. based on Intel's SSE2 vector instructions, to improve the performance of the generated code. Such optimisations can be targetted to different hardware architectures while keeping the source code (the Mathematica script) generic.

---

Advantages of Automatic Code Generation

Code generation systems such as Kranc can take over part of the compiler's responsibility for generating optimal code. This requires that the code generation occurs automatically, without requiring human intervention (e.g. cut and paste, or declaring the used variables), so that the code can really be regenerated at will as part of the build setup. This makes it possible to generate different code on different systems, enabling hardware specific optimisations for different processor types and/or different system architectures.

Code generation systems can fill an important gap that exists in current compiler technology. The compiler never sees the actual discretised equations that are to be solved. Instead, these equations are broken down to a much lower level, namely the level or arrays, pointers, loops, temporary variables, and arithmetic operations on these. It is very difficult, if not impossible, for the compiler to obtain a "high level overview" that would enable it to perform substantial optimisations. A high level view contains concepts such as:

• grid points
• evaluating a right hand side
• discretisation stencil
• iterating over grid points

Current languages (C, C++, Fortran, ...) cannot express these concepts. One has to translate grid points to array elements, RHS evaluations into loads, stores, and sequences of arithmetic operations, iterations into loops, etc. These translations all lose information that the compiler then cannot use any more to optimise code. For example, evaluating a discretisation stencil makes use of neighbouring grid points, leading to data locality that needs to be harvested to achieve good performance on cache-based architectures. Many such properties that are immediately clear from the numerical algorithm are very difficult to describe to the compiler:

• LHS grid points are written to exactly once,
• RHS grid points may be used multiple times, by neighbouring LHS grid points, where "neighbourhood" is in terms of physical space, not memory locations,
• there is a layer of ghost points around the LHS grid points.

Kranc and other code generation systems do have this high level knowledge, and can thus apply corresponding optimisations much more easily. In addition, since Kranc operates only at the high level, it is easier to understand and modify, which substantially simplifies experimenting with new kinds of optimisations .