Description du sujet de thèse

Considérons le type le plus simple de problèmes numériques que l'on peut construire sur un processeur en utilisant une séquence d'opérations arithmétiques sur des nombres à virgule flottante et sans aucune structure de contrôle non triviale. Nous les appelons programmes en ligne droite ou SLP. Plus généralement, on peut considérer tout ensemble fini d'opérations « de base » (au lieu des opérations arithmétiques) sur un type de données « de base » (au lieu des nombres à virgule flottante de la machine).

Par exemple, le SLP suivant peut être utilisé pour calculer la fonction x^2 + 2 (y - 3 z)^4 :

v_4 ≔ 3 × v_3
v_4 ≔ v_2 - v_4
v_4 ≔ v_4 × v_4
v_4 ≔ v_4 × v_4
v_4 ≔ 2 × v_4
v_5 ≔ v_1 × v_1
v_4 ≔ v_4 + v_5.

Ici, v_1,...,v_5 sont un nombre fini de « registres » que nous utilisons pour contenir nos données (nombres à virgule flottante). Certains de ces registres correspondent à l'entrée de notre SLP (à savoir v_1=x, v_2=y, et v_3=z) et d'autres à la sortie (à savoir v_4). Les arguments des instructions sont soit des registres, soit des constantes (telles que 2 et 3).

D'une part, les SLP peuvent naturellement être considérés comme un type de données. Par exemple, le programme ci-dessus est une représentation possible du polynôme x^2 + 2 (y - 3 z)^4 et il est naturel de prendre en charge cette représentation dans les bibliothèques dédiées aux calculs avec des polynômes multivariés. D'autre part, les SLP peuvent être considérés comme des programmes. Par conséquent, nous pouvons utiliser les techniques des compilateurs pour effectuer des tâches de base sur les SLP, telles que l'élimination des sous-expressions communes, l'allocation des registres, ou la génération de bytecode qui peut être directement exécuté sur le CPU.

L'objectif principal de cette thèse est de développer et d'implémenter des algorithmes extrêmement efficaces pour de nombreux calculs avec des SLP, en exploitant leurs avantages spécifiques :

- Contrairement aux programmes d'usage général, les SLP peuvent être représentés de manière simple et adaptée à des manipulations efficaces.

- L'absence de structures de contrôle non triviales permet également de spécialiser les techniques de compilation à usage général afin d'obtenir des gains d'efficacité supplémentaires.

- Bien que le formalisme des SLP soit limité et fortement contraint par sa conception, il permet des ensembles arbitraires d'opérations de base et des types de données de base arbitraires. Pour plusieurs types de données de base intéressants, cela permet de développer des optimisations mathématiques spécifiques qui seraient difficiles à réaliser pour des programmes d'usage général.

- La simplicité du formalisme nous invite à étudier et à prendre en charge des types de matériel plus exotiques, tels que les GPU, les coprocesseurs matriciels ou les grands réseaux.

- Malgré leur simplicité, les SLP admettent de nombreuses applications intéressantes. En particulier, nous explorerons l'intégration d'équations différentielles ordinaires, la continuation de l'homotopie et l'interpolation éparse. Les SLP se rencontrent aussi naturellement dans les applications générales lorsqu'il est possible de dérouler toutes les boucles et tous les appels de fonction.

Contexte de travail

Le projet sera financé par l'ERC ODELIX. L'étudiant travaillera au sein de l'équipe MAX de calcul formel, disposera de matériel informatique adéquat, et sera incité de participer régulièrement à des manifestations scientifiques.

Informations complémentaires

Le projet sera financé par l'ERC ODELIX qui démarre le 1er octobre 2024.