Shannon meets Cray – SxC

Knowledge about handcrafted vectorization algorithms is scattered among various fields, system architectures, programming languages paradigms and industrial pieces of codes. The main objective of the project is to bring structure to this knowledge through novel conceptual and practical tools. The end goal is to facilitate the writing of SIMD programs and to pave the way to future auto-vectorization methods for stream processing. The main difficulty to achieve these goals is to understand the interplay of sequentiality and bit-level parallelism. Circuit complexity, as introduced by Shannon in the early years of computer science, offers a powerful framework to study such notion of paralelism. In this multidisciplinary project, we bring together methodologies from the fields of circuit complexity of automata, and programming language design for parallel architectures, with motivations from data processing and bioinformatics applications.

The project's results will be implemented into a compilation tool-chain. At the
highest level, we will design and develop a domain specific language, dubbed
Vectoid. Its goal is to allow more programmers to harness SIMD instructions.
Vectoid will be compiled to a Vectorial Intermediate Representation (VIR)
dedicated to stream processing. In turn VIR will be compiled to low level code
for various SIMD architectures. The design of this compilation tool-chain will
be informed by a theoretical investigation on the expressivity of vectorical
circuits. It will be evaluated on data processing and bioinformatics benchmarks.