Data layout types : a type-based approach to automatic data layout transformations for improved SIMD vectorisation
Abstract
The increasing complexity of modern hardware requires sophisticated programming
techniques for programs to run efficiently. At the same time, increased power of
modern hardware enables more advanced analyses to be included in compilers. This
thesis focuses on one particular optimisation technique that improves utilisation
of vector units. The foundation of this technique is the ability to chose memory
mappings for data structures of a given program.
Usually programming languages use a fixed layout for logical data structures
in physical memory. Such a static mapping often has a negative effect on usability
of vector units. In this thesis we consider a compiler for a programming language
that allows every data structure in a program to have its own data layout. We
make sure that data layouts across the program are sound, and most importantly
we solve a problem of automatic data layout reconstruction. To consistently do this,
we formulate this as a type inference problem, where type encodes a data layout
for a given structure as well as implied program transformations. We prove that
type-implied transformations preserve semantics of the original programs and we
demonstrate significant performance improvements when targeting SIMD-capable
architectures.