Open Tech Calendar

Title: Automatic data layout transformations enabling SIMD vectorisation.

Abstract:
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 the talk we will consider a compiler for a
programming language that allows every data structure in a program to have its
own data layout.

Such an approach comes with a number of challenges. First, the number of
theoretically possible data layout configurations per program is very large.
We need to choose the one that will lead to the best program
vectorisation. Secondly, we have to make sure that the chosen configuration
is sound. Finally, the code we generate has to encode desired vectorisation
preferably in a portable way.

Our solution lies in using types to encode data layouts. We
use a type system to verify data layout consistency in programs. Type
inference techniques allow us to solve a data layout reconstruction problem.
We prove that type-implied transformations preserve semantics
of the original programs and we demonstrate significant performance improvements
when targeting SIMD-capable architectures.