Ordonnancement de programmes à structures de données complexes – CODAS

L'avènement du parallélisme dans les super-ordinateurs, les systèmes embarqués, ou encore dans les classiques ordinateurs de bureau, cause une demande toujours plus forte d'optimisations de code de haut niveau, et de compilateurs toujours plus sophistiqués. Un des grands challenges actuels de la communauté de compilation est de prendre en compte cette complexité croissante des logiciels et des matériels.

La feuille de route Hipeac (http://www.hipeac.net/system/files/hipeac_roadmap1_0.pdf) cite parmi les thématiques de recherche les plus importantes à développer le problème d'exposition du parallélisme dans les applications, ainsi que son optimisation à la compilation et à l'exécution. Il y a donc une demande croissante de solutions d'ordonnancements pour toutes sortes de programmes, en particulier ceux qui manipulent de gros volumes de données.

L'objectif de notre projet à long terme est de développer une manière unifiée et générique de raisonner sur et de manipuler des programmes. Ces programmes auront un flot de contrôle quelconque, et manipuleront des structures de données plus complexes que des tableaux. Nous choisissons de construire nos recherches à partir du modèle polyédrique. Nous voulons étendre ce modèle de raisonnement à la fois de manière théorique et algorithmique, de façon à traiter des programmes plus généraux qu'actuellement.

Dans ce projet CoDaS, nous proposons d'étudier l'ordonnancement de programmes qui contiennent des structures de données complexes spécifiques, comme des listes ou des arbres. Nous proposons de garder le modèle polyédrique comme modèle de base pour représenter les dépendances de données et formaliser la notion d'ordonnancement. Nous désirons utiliser les travaux existants dans les communautés d'interprétation abstraite et de réécriture, afin de raisonner sur le contrôle approximé et les structures de données complexes. L'objectif est de trouver une façon compacte de représenter les données et les
calculs de manière unifiée, et de fournir des algorithmes permettant d'ordonnancer des programmes à partir de cette représentation.

Les recherches seront menées par une boucle expérimentale, des exemples de la littérature vers la théorie, suivis d'une évaluation empirique. Cette évaluation prendra la forme d'une « preuve de concept » ; application de la méthode à la preuve de terminaison, et la démonstration via un prototype de générateur de code de l'applicabilité de la méthode sur des exemples simples.