Proposition de stages de recherche (niveau Master 2)
Performances d'algorithmes précis
Performances réelles des algorithmes numériques précis
Prérequis :
--
Lieu :
Equipe DALI, Université de Perpignan. Laboratoire LIRMM, UMR 5506 - CNRS - U. Montpellier 2.
Encadrant :
Philippe LANGLOIS, David PARELLO
Thématique, domaines scientifiques, mots-clés :
mesure de performance, interaction processeur-compilateur-algorithme, simulation de processeur, algorithmes numériques, codes de calcul
Motivation générale :
Un des critères de comparaison entre algorithmes est sa complexité effective en temps, c'est-à-dire celle qui se traduit par des mesures de temps de calcul. Il est classique que les publications de nouveaux algorithmes illustrent ceci par des tableaux de mesures selon les très nombreux paramètres qui conditionnent de telles mesures : processeurs, unités spécialisées, mémoires, compilateurs, ... Pourtant ces tableaux ne sont au mieux qu'une photographie, la plupart du temps floue, des performances d'un algorithme. Leur lisibilité a une très courte durée de vie et, surtout, la reproductibilité des résultats publiés relève de la fiction.
En matière d'algorithme numérique, en calcul scientifique en particulier, le décompte (manuel) du nombre d'opérations flottantes est aussi un incontournable classique. Pourtant la corrélation entre ce décompte et les mesures effectives est de moins en moins possible. Le code executé par les unités de calcul actuelles est bien loin de l'algorithme écrit sur le papier.
Comment faire confiance quand un auteur écrit que son algorithme va plus vite que les autres ?
Objectif du stage :
L'exécution de l'algorithme sur le processeur idéal de Hennessy et Patterson permet d'obtenir une mesure du potentiel de performance d'un algorithme exprimée en terme l'ILP (parallélisme d'instructions). Nous avons récemment développé (deux versions prototypes) de simulateur de ce processeur idéal. Ainsi l'ILP est obtenus automatiquement, de façon reproductible et portable. Les premiers résultats sont prometteurs.
L'objectif général du projet dans lequel ce stage s'inscrit est de rapidement proposer une plateforme de référence pour la mesure de codes à forte composante de calcul et écrits en langage de "haut niveau". Ainsi le développeur ou le concepteur d'algorithmes pourra réaliser une analyse fine du potentiel de performance de son/ses code/s, indépendamment du choix a priori d'environnement de calcul. L'ambition de ce projet est de pouvoir disposer d'une analyse de performance validée.
Dans ce cadre plusieurs directions de travail font l'objet de stages de recherche (niveau Master 1 ou 2). L'instrumentation doit être étendue pour permettre une analyse approfondie des propriétés de l'algorithme qui conditionnent sa performance maximale. L'approche proposée doit être confrontée aux démarches actuelles (statistiques et expérimentations) pour différents codes de différentes tailles représentatives (de l'algorithme de quelques dizaines de lignes aux grands codes de simulation numérique). La mesure de ces grands codes impose d'optimiser les performances du simulateur. La large diffusion de l'outil, qui participe aussi à sa validation, nécessite d'améliorer son ergonomie.
Premiers éléments de bibliographie :
B. Goossens, Ph. Langlois, D. Parello. Processor simulation: a new way for the performance analysis of numerical algorithms. Dagstuhl Seminar "Computer-assisted Proofs -- tools, methods and applications", 16-20 Nov. 2009, Dagstuhl, Germany. 
J. Hennessy, D. Patterson. Computer architecture. A quantitative approach. 2003.