Techniques for Static and Dynamic Compilation of Array Expressions
Mark Florisson · 2012
This thesis evaluates compiler techniques to efficiently evaluate local array expressions such as those found in APL, Fortran 90 and many other languages. We show that merely eliminating temporary arrays is not enough, and we contribute a reusable open source compiler called minivect that generates code which can outperform commercial Fortran compilers for even moderate data sizes in several test-cases, while retaining full runtime generality such as broadcasting as found in NumPy (similar to Fortran’s SPREAD intrinsic) and arbitrarily strided arrays. In extreme cases we measure speedups up to 9x compared to GNU Fortran, and up to 1.7x for Intel Fortran. We show how these speedups may be further increased through SIMD vector-sized transposes for certain array expressions, and by computing tile sizes at runtime. We furthermore provide insights and a working implementation of in-memory Abstract Syntax Tree (AST) remapping from an original AST and type system to a foreign AST and type system, enabling efficient full or partial mappings, allowing reuse of external compiler technology. We provide a working implementation of this for array expressions in the Cython language. We also contribute a minimal library that uses lazy evaluation combined with runtime compilation to generate efficient code. We also show how a compiler may be designed to facilitate adding new code generators with minimal effort without the need for an explicit intermediate representation. We finally show how we can circumvent temporary arrays by proving data independence using traditional dependence tests in various situations for arbitrary runtime arrays (as opposed to compile-time aliases). In case of possible dependence we construct distance and direction vectors at runtime in order to use wellknown compile-time optimizations, which we implement at runtime by adapting the array view on memory.