Algorithmes Hybrides et Adaptatifs

Combiner plusieurs algorithmes différents résolvant le même problème mais chacun optimisant un critère de performance spécifique est une technique algorithmique classique. Cependant, on assiste actuellement à un regain d'intérêt, illustré par de nouveaux résultats théoriques et le succès des logiciels de calcul numérique ATLAS et FFTW. Cet intérêt est motivé par la construction d'algorithmes qui s'adaptent automatiquement au contexte d'exécution (données et architecture), ainsi à même d'exploiter des plateformes hétérogènes.

L'objectif de ce projet est d'améliorer la portabilité et les performances des applications grâce à l'utilisation d'algorithmes hybrides adaptatifs. Ces travaux seront appliqués au calcul fiable (bibliothèques FFLAS, LinBox et MPFI de la distribution Roxane), à l'optimisation combinatoire (en particulier ordonnancement et affectation) et aux problèmes inverses de vision artificielle (multi-caméras et temps-réel). L'une des actions phare du projet sera de résoudre des problèmes challenges en conception de réseaux pour le transport public urbain (ville modélisée par un graphe avec quelques milliers de sommets) qui nécessitent l'agrégation de milliers de processeurs. Répondre à ces challenges nécessite la mise en place d'algorithmes capables de s'adapter dynamiquement pour tirer parti de ressources de calcul hétérogènes et volatiles.

L'application des algorithmes adaptatifs théoriques à des librairies applicatives sur des plateformes hétérogènes est innovant. Elle est motivée par la maturité des technologies permettant l'exploitation de ressources distribuées, de l'agglomération des ressources disponibles localement au sein d'une équipe ou d'un laboratoire aux architectures à plus grande échelle. En particulier, le projet mènera des expérimentations sur la plateforme de réalité virtuelle Grimage, la grille régionale CIMENT et la grille nationale GRID'5000.

Ce projet relève des axes stratégiques de l'IMAG: modélisation et calcul, logiciels et systèmes. Il fédère des équipes spécialistes de la composition d'algorithmes dans des domaines complémentaires: programmation et ordonnancement sur ressources distribuées (MOAIS, ID-IMAG) ; calcul fiable (LMC-IMAG et projet ARENAIRE) ; optimisation combinatoire (GILCO) ; vision et interaction (MOVI, GRAVIR-IMAG).

Mots clés : Algorithmes adaptatifs, parallélisme, calcul fiable, optimisation, vision, ordonnancement.