Sujet: Estimation statique de complexité pour l'optimisation manuelle de code

Les applications réelles sont trop complexes pour être uniformément optimisées manuellement. La technique usuelle consiste à réaliser un ou des profils d'exécution en instrumentant le code et en le faisant tourner sur quelques cas de jeux de données particuliers. Les jeux de données doivent être adaptés afin que les exécutions soient assez rapides. Le processus est itératif puisque chaque optimisation peut faire apparaître un nouveau goulot d'étranglement à l'exécution suivante.

Le but de cette thèse est de voir si une estimation statique et symbolique des poids de chaque module et de chaque instruction de chaque module est possible. Une solution exacte n'est pas calculable en général, mais il est possible de trouver des solutions approchées, surtout pour les codes scientifiques auxquels nous nous intéressons. La grosse difficulté du travail provient de la nécessité de faire des approximations. Quelles approximations faut-il faire? Quand faut-il faire une approximation? Peut-on obtenir un encadrement significatif? De quelles informations, statiques ou dynamiques, faut-il disposer? Telles sont certaines des questions auxquelles il faudra répondre.

Si les évaluations statiques des complexités des calculs s'avèrent intéressantes, elles devraient être étendues aux problèmes des volumes mémoire alloués et des volumes de données communiqués dans le cas de programmes parallèles.

Une première estimation statique de complexité a déjà été réalisée dans notre laboratoire, avec un objectif différent: essayer de comparer les complexités de deux versions d'un même code. Elle devrait permettre de faire des essais rapidement sans avoir à procéder à un gros travail d'implémentation.

Contact: François Irigoin - 01 64 69 48 48 - irigoin@cri.ensmp.fr


Voir aussi la description du projet PIPS.


Retour à la page de présentation du CRI