Composition de squelettes algorithmiques : application au prototypage rapide d'applications de vision

Jury de soutenance : DR, DHOME Michel, President PR, MIGUET Serge, Rapporteur MCF-HDR, HOUZET Dominique, Rapporteur PR, QUILLIOT Alain, Examinateur PR, PAINDAVOINE Michel, Examinateur PR, DERUTIN Jean-Pierre, Directeur de these MCF-HDR, SEROT Jocelyn, Co-directeur de theseOur work deals with parallel programming environments which are developed in order to help the user of ''Multiple Instruction stream Multiple Data stream - Distributed Memory'' (MIMD-DM) computers to easily program such a machine. Image processing is our target application field. The SKiPPER (SKeleton-based Parallel Programming EnviRonment) toolset was developed for this purpose. It is designed to address the problem of rapid prototyping of image processing applications, and to get a fully operational application in a very short time with a few stages within the design process. The methodology used in SKiPPER is based on algorithmic skeletons. Algorithmic skeletons are higher-order program constructs encapsulating common and recurrent forms of parallelism to make them readily available for the application programmer. More precisely our work concerns the composition problem of algorithmic skeletons. Our goal is to increase the number of image processing applications which can be written with this methodology and therefore the SKiPPER tool. The version of SKiPPER described here was specifically designed to support arbitrary nesting of skeletons, which is the hardest form of composition we have to deal with. This version relies on a fully dynamic execution model whereas the previous versions relied on mostly static execution models. The main idea was to design a generic new skeleton which is able to dynamically emulate any skeleton of the SKiPPER's library. In this way the new version of the SKiPPER's kernel is able to manage the skeleton composition ''on the fly''. In order to evaluate our approach, some benchmark programs with a real case study of a face-tracking algorithm are given. The interest of this example is to cast a light on the need for skeleton nesting in realistic image processing applications.Le travail présenté s'inscrit dans le cadre de la recherche sur des outils d'aide à la programmation parallèle de machines MIMD-DM. Notre champ applicatif est celui de la programmation d'applications de vision artificielle. Ces recherches ont abouti au développement de l'outil SKiPPER (SKeleton-based Parallel Programming EnviRonment) qui est un outil d'aide à la programmation parallèle pour le prototypage rapide d'applications de vision artificielle. Il a été conçu pour obtenir une application opérationnelle dans un délai très court et avec le minimum d'étapes intermédiaires dans le processus de réalisation. La méthodologie retenue pour Sa mise en oeuvre est fondée sur l'emploi de squelettes algorithmiques. Ces structures de programmation paramétrables encapsulent des formes communément utilisées de parallélisme pour les rendre facilement exploitables. Dans le cadre de ce projet nous nous intéressons aux aspects compositionnels de ces squelettes afin d'augmenter le potentiel d'applications de vision artificielle qui peuvent être spécifiées avec notre outil. Le séquencement de squelettes étant un cas trivial de composition déjà pris en charge dans les premiers développements de SKiPPER, nous nous intéressons ici au cas plus difficile de l'imbrication de plusieurs squelettes, homogène et hétérogène, c'est-à-dire entre squelettes identiques ou non. Nous proposons une approche dynamique de la composition des squelettes de parallélisation en établissant une formulation générique de tous les squelettes de la bibliothèque de l'environnement et un modèle d'exécution capable de gérer dynamiquement à l'exécution les problèmes qui lui sont lies. Afin de valider l'approche, un certain nombre de programmes tests sont évalues ainsi qu'une application réelle de traitement d'images faisant apparaître la nécessite de disposer dans certains cas de figure de la souplesse et du potentiel offert par la composition de squelettes dans l'expression du parallélisme potentiel