SxC - De Shannon à Cray

Coordinateur : Charles Paperman, Inria, CRIStAL

Équipe : D-DAL du Groupe Thématique : SISE

Dates : 2025 - 2030

Résumé :

L’art d’écrire des algorithmes vectorisés est disséminé dans de nombreuses communautés : architecture et système, langages de programmation, codes industriels. Le premier objectif du projet est d’organiser ces connaissances à l’aide d’outils mathématiques et pratiques. L’objectif final est alors de faciliter l’écriture de programmes SIMD et d’initier la conception d’auto-vectorisation pour les traitements en flot. La principale difficulté réside dans la compréhension des interactions entre séquentialité et parallélisme au niveau du bit d’information. La complexité de circuit, introduite pas Shannon à l’aube de l’informatique, offre un cadre puissant à l’étude de cette notion de parallélisme. Ce projet multi-disciplinaire propose d’assembler des méthodes de complexité de circuits liés aux automates et de conception de langages de programmation pour les architectures parallèles. Il tire ses motivations d’applications au traitement des données et à la bio-informatique.

Les résultats du projet seront assemblés dans une chaîne de compilation. Nous concevrons et développerons un langage dédié que nous appellerons Vectoid. Il permettra aux programmeurs d’utiliser efficacement et simplement les instructions SIMD. Vectoid sera compilé vers une Représentation Vectorielle Intermédiaire qui sera à son tour compilé vers du code de bas niveau de diverses architectures SIMD. La conception de cette chaîne de compilation se basera sur l’étude de l’expressivité des circuits vectoriels. Elle sera également évaluée sur des tâches de traitement de données et de bio-informatique.

Abstract :

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 pratical 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 nation 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 Representaion (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 vectorial circuits. It will be evaluated on data processing and bioinformatics benchmarks.