Who: Artem Shinkarov

Where: The Outhouse at 7pm

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.