La prolifération des architectures multi-coeurs est source d’unepression importante pour les developpeurs, qui doivent chercherà paralléliser leurs applications de manière à profiter au mieux deces plateformes. Malheureusement, les modèles de programmationde bas niveau amplifient les difficultés inhérentes à la conceptiond’applications complexes et parallèles. Il existe donc une attentepour des modèles de programmation de plus haut niveau, quipuissent simplifier la vie des programmeurs de manière significative,tout en proposant des abstractions suffisantes pour absorberl’hétérogénéité des architectures matérielles.Contrairement à une multitude de modèles de programmation parallèlequi introduisent de nouveaux langages, annotations ou étendentdes langages existants et requièrent donc des compilateurs spécialisés,nous exploitons ici le potentiel du language C++ standardet traditionnel. En particulier nous avons recours à ses capacitésen terme de meta-programmation, afin de fournir au programmeurune interface de programmation parallèle simple et directe. Cetteinterface autorise le programmeur à exprimer le parallélismede son application au prix d’une altération négligeable du codeséquentiel initial. Un runtime intelligent se charge d’extraire touteinformation relative aux dépendances de données entre tâches,ainsi que celles relatives à l’ordonnancement. Nous montronscomment ce runtime est à même d’exploiter ces informations dansle but de détecter et protéger les données partagées, puis réaliserun ordonnancement prenant en compte les particularités des caches.L’implémentation initiale de notre modèle de programmation est unelibrairie C++ pure appelée XPU. XPU est conÃ˘gue dans le but defaciliter l’explicitation, par le programmeur, du parallélisme applicatif.Une seconde réalisation appelée FATMA doit être considérée commeune extension d’XPU qui permet une détection automatique desdépendances dans une séquence de tâches : il s’agit donc de parallélisationautomatique, sans recours à quelque outil que se soit,excepté un compilateur C++ standard. Afin de démontrer le potentielde notre approche, nous utilisons ces deux outils –XPU et FATMA–pour paralléliser des problèmes populaires, ainsi que des applicationsindustrielles réelles. Nous montrons qu’en dépit de leur abstractionélevée, nos modèles de programmation présentent des performancescomparables à des modèles de programmation de basniveau,et offrent un meilleur compromis productivité-performance. / The continuous proliferation of multicore architectures has placeddevelopers under great pressure to parallelize their applicationsaccordingly with what such platforms can offer. Unfortunately,traditional low-level programming models exacerbate the difficultiesof building large and complex parallel applications. High-level parallelprogramming models are in high-demand as they reduce the burdenson programmers significantly and provide enough abstraction toaccommodate hardware heterogeneity. In this thesis, we proposea flexible parallelization methodology, and we introduce a newtask-based parallel programming model designed to provide highproductivity and expressiveness without sacrificing performance.Our programming model aims to ease expression of both sequentialexecution and several types of parallelism including task, data andpipeline parallelism at different granularity levels to form a structuredhomogeneous programming model.Contrary to many parallel programming models which introducenew languages, compiler annotations or extend existing languagesand thus require specialized compilers, extra-hardware or virtualmachines..., we exploit the potential of the traditional standardC++ language and particularly its meta-programming capabilities toprovide a light-weight and smart parallel programming interface. Thisprogramming interface enable programmer to express parallelismat the cost of a little amount of extra-code while reuse its legacysequential code almost without any alteration. An intelligent run-timesystem is able to extract transparently many information on task-datadependencies and ordering. We show how the run-time system canexploit these valuable information to detect and protect shared dataautomatically and perform cache-aware scheduling.The initial implementation of our programming model is a pure C++library named "XPU" and is designed for explicit parallelism specification.A second implementation named "FATMA" extends XPU andexploits the transparent task dependencies extraction feature to provideautomatic parallelization of a given sequence of tasks withoutneed to any specific tool apart a standard C++ compiler. In order todemonstrate the potential of our approach, we use both of the explicitand automatic parallel programming models to parallelize popularproblems as well as real industrial applications. We show thatdespite its high abstraction, our programming models provide comparableperformances to lower-level programming models and offersa better productivity-performance tradeoff.

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. <br> 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. <br> 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. <br> 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. <br> 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.

Nous nous intéressons à l'acquisition temps réel d'informations tridimensionnelles sur une scène à partir de plusieurs caméras dans le contexte des applications interactives. Nous proposons un système de vision complet allant de l'acquisition des images à la modélisation des formes et du mouvement de l'utilisateur. La distribution des tâches sur une grappe de PC, et en particulier la parallélisation de plusieurs algorithmes d'extraction de la géométrie de la scène, permet un fonctionnement temps-réel avec une faible latence. De nombreuses applications sont développées et valident la mise en oeuvre réalisée de ce système. Une approche nouvelle de la modélisation du mouvement est aussi proposée. Celle-ci permet de suivre et d'identifier les membres de l'utilisateur sans connaissance a priori sur la forme de ce dernier.

Les travaux présentés dans ce mémoire s'inscrivent dans la problématique dite d'adéquation algorithme architecture. Ils concernent la conception et le développement d'outils logiciels permettant de faire du prototypage rapide d'applications parallèles de vision artificielle sur des architectures de type MIMD à mémoire distribuée. De tels outils ont pour objectif de faciliter l'évaluation rapide d'un ensemble de solutions vis à vis d'un problème donné en diminuant de manière drastique les temps de cycle conception-implantation-validation des applications. L'outil SKiPPER développé dans le cadre de ces travaux est basé sur le concept des squelettes de parallélisation. Ceux-ci représentent des constructeurs génériques de haut niveau encapsulant des formes communes de parallélisme tout en dissimulant les détails relatifs à l'exploitation de ce parallélisme sur la plate-forme cible. Au niveau langage, la spécification des squelettes est réalisée au sein du langage fonctionnel Caml sous la forme de fonctions d'ordre supérieur. Ainsi, la spécification d'une application est un programme purement fonctionnel dans lequel l'expression du parallélisme est limitée au choix et à l'instanciation des squelettes choisis dans une base pré-définie. L'environnement de développement SKiPPER est organisé autour de trois modules réalisant respectivement l'expansion du code fonctionnel en un graphe flot de données (outil Dromadaire), le placement-ordonnancement de ce graphe sur l'architecture matérielle (outil SynDEx développé à l'INRIA) et la génération de code cible final pour l'architecture cible (la machine Transvision du LASMEA dans notre cas). L'applicabilité des concepts mis en \oe uvre dans SKiPPER et des outils développés conjointement est démontrée également dans les travaux présentés dans ce mémoire. Diverses applications de complexité réaliste (étiquetage en composantes connexes, détection et suivi de signalisation horizontale autoroutière) ont été parallélisées automatiquement par l'environnement SKiPPER validant ainsi l'objectif initial de prototypage rapide d'applications parallèles de vision artificielle à fortes contraintes temporelles sur architecture dédiée.

Les approches de parallélisme structuré sont un compromis entre la parallélisation automatique et la programmation concurrentes et réparties telle qu'offerte par MPI ou les Pthreads. Le parallélisme à squelettes est l'une de ces approches. Un squelette algorithmique peut être vu comme une fonction d'ordre supérieur qui capture un algorithme parallèle classique tel qu'un pipeline ou une réduction parallèle. Souvent la sémantique des squelettes est simple et correspondant à celle de fonctions d'ordre supérieur similaire dans les langages de programmation fonctionnels. L'utilisation combine les squelettes disponibles pour construire son application parallèle. Lorsqu'un programme parallèle est conçu, les performances sont bien sûr importantes. Il est ainsi très intéressant pour le programmeur de disposer d'un modèle de performance, simple mais réaliste. Le parallélisme quasi-synchrone (BSP) offre un tel modèle. Le parallélisme étant présent maintenant dans toutes les machines, du téléphone au super-calculateur, il est important que les modèles de programmation s'appuient sur des sémantiques formelles pour permettre la vérification de programmes. Les travaux menés on conduit à la conception et au développement de la bibliothèque Orléans Skeleton Library ou OSL. OSL fournit un ensemble de squelettes algorithmiques data-parallèles quasi-synchrones. OSL est une bibliothèque pour le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Les communications se basent sur la bibliothèque MPI. OSL étant basée sur le modèle BSP, il est possible non seulement de prévoir les performances des programmes OSL mais également de fournir une portabilité des performances. Le modèle de programmation d'OSL a été formalisé dans l'assistant de preuve Coq. L'utilisation de cette sémantique pour la preuve de programmes est illustrée par un exemple.

Les approches de parallélisme structuré sont un compromis entre la parallélisation automatique et la programmation concurrentes et réparties telle qu'offerte par MPI ou les Pthreads. Le parallélisme à squelettes est l'une de ces approches. Un squelette algorithmique peut être vu comme une fonction d'ordre supérieur qui capture un algorithme parallèle classique tel qu'un pipeline ou une réduction parallèle. Souvent la sémantique des squelettes est simple et correspondant à celle de fonctions d'ordre supérieur similaire dans les langages de programmation fonctionnels. L'utilisation combine les squelettes disponibles pour construire son application parallèle. Lorsqu'un programme parallèle est conçu, les performances sont bien sûr importantes. Il est ainsi très intéressant pour le programmeur de disposer d'un modèle de performance, simple mais réaliste. Le parallélisme quasi-synchrone (BSP) offre un tel modèle. Le parallélisme étant présent maintenant dans toutes les machines, du téléphone au super-calculateur, il est important que les modèles de programmation s'appuient sur des sémantiques formelles pour permettre la vérification de programmes. Les travaux menés on conduit à la conception et au développement de la bibliothèque Orléans Skeleton Library ou OSL. OSL fournit un ensemble de squelettes algorithmiques data-parallèles quasi-synchrones. OSL est une bibliothèque pour le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Les communications se basent sur la bibliothèque MPI. OSL étant basée sur le modèle BSP, il est possible non seulement de prévoir les performances des programmes OSL mais également de fournir une portabilité des performances. Le modèle de programmation d'OSL a été formalisé dans l'assistant de preuve Coq. L'utilisation de cette sémantique pour la preuve de programmes est illustrée par un exemple. / Structured parallelism approaches are a trade-off between automatic parallelisation and concurrent and distributed programming such as Pthreads and MPI. Skeletal parallelism is one of the structured approaches. An algorithmic skeleton can be seen as higher-order function that captures a pattern of a parallel algorithm such as a pipeline, a parallel reduction, etc. Often the sequential semantics of the skeleton is quite simple and corresponds to the usual semantics of similar higher-order functions in functional programming languages. The user constructs a parallel program by combined calls to the available skeletons. When one is designing a parallel program, the parallel performance is of course important. It is thus very interesting for the programmer to rely on a simple yet realistic parallel performance model. Bulk Synchronous Parallelism (BSP) offers such a model. As the parallelism can now be found everywhere from smart-phones to the super computers, it becomes critical for the parallel programming models to support the proof of correctness of the programs developed with them. . The outcome of this work is the Orléans Skeleton Library or OSL. OSL provides a set of data parallel skeletons which follow the BSP model of parallel computation. OSL is a library for C++ currently implemented on top of MPI and using advanced C++ techniques to offer good efficiency. With OSL being based over the BSP performance model, it is possible not only to predict the performances of the application but also provides the portability of performance. The programming model of OSL is formalized using the big-step semantics in the Coq proof assistant. Based on this formal model the correctness of an OSL example is proved.

Concevoir et implanter des programmes parallèles est une tâche complexe, sujette aux erreurs. La vérification des programmes parallèles est également plus difficile que celle des programmes séquentiels. Pour permettre le développement et la preuve de correction de programmes parallèles, nous proposons de combiner le langage parallèle fonctionnel quasi-synchrone BSML, les squelettes algorithmiques - qui sont des fonctions d’ordre supérieur sur des structures de données réparties offrant une abstraction du parallélisme – et l’assistant de preuve Coq, dont le langage de spécification est suffisamment riche pour écrire des programmes fonctionnels purs et leurs propriétés. Nous proposons un plongement des primitives BSML dans la logique de Coq sous une forme modulaire adaptée à l’extraction de programmes. Ainsi, nous pouvons écrire dans Coq des programmes BSML, raisonner dessus, puis les extraire et les exécuter en parallèle. Pour faciliter le raisonnement sur ceux-ci, nous formalisons le lien entre programmes parallèles, manipulant des structures de données distribuées, et les spécifications, manipulant des structures séquentielles. Nous prouvons ainsi la correction d’une implantation du squelette algorithmique BH, un squelette adapté au traitement de listes réparties dans le modèle de parallélisme quasi synchrone. Pour un ensemble d’applications partant d’une spécification d’un problème sous forme d’un programme séquentiel simple, nous dérivons une instance de nos squelettes, puis nous extrayons un programme BSML avant de l’exécuter sur des machines parallèles. / Parallel program design and implementation is a complex, error prone task. Verifying parallel programs is also harder than verifying sequential ones. To ease the development and the proof of correction of parallel programs, we propose to combine the functional bulk synchronous parallel language BSML; the algorithmic skeleton, that are higher order function on distributed data structures which offer an abstraction of the parallelism ; and the Coq proof assistant, who’s specification language is rich enough to write purely functional programs together with their properties. We propose an embedding of BSML primitives in the Coq logic in a modular form, adapted to program extraction. So we can write BSML programs in Coq, reason on them, extract them and then execute them in parallel. To ease the specification of these programs, we formalise the relation between parallel programs using distributed data structures and specification using sequential data structure. We prove the correctness of an implementation of the BH skeleton. This skeleton is devoted to the treatment of distributed lists in the BSP model. For a set of application, starting from a sequential specification of a problem, we derive an instance of our skeletons, then extract a BSML program which is executed on parallel machines.

Les grappes de PCs constituent des architectures distribuées dont l'adoption se répand à cause de leur faible coût mais aussi de leur extensibilité en termes de noeuds. Notamment, l'augmentation du nombre des noeuds est à l'origine d'un nombre croissant de pannes par arrêt qui mettent en péril l'exécution d'applications distribuées. L'absence de solutions efficaces et portables confine leur utilisation à des applications non critiques ou sans contraintes de temps. MoLOToF est un modèle de tolérance aux pannes de niveau applicatif et fondée sur la réalisation de sauvegardes. Pour faciliter l'ajout de la tolérance aux pannes, il propose une structuration de l'application selon des squelettes tolérants aux pannes, ainsi que des collaborations entre le programmeur et le système de tolérance des pannes pour gagner en efficacité. L'application de MoLOToF à des familles d'algorithmes parallèles SPMD et Maître-Travailleur a mené aux frameworks FT-GReLoSSS et ToMaWork respectivement. Chaque framework fournit des squelettes tolérants aux pannes adaptés aux familles d'algorithmes visées et une mise en oeuvre originale. FT-GReLoSSS est implanté en C++ au-dessus de MPI alors que ToMaWork est implanté en Java au-dessus d'un système de mémoire partagée virtuelle fourni par la technologie JavaSpaces. L'évaluation des frameworks montre un surcoût en temps de développement raisonnable et des surcoûts en temps d'exécution négligeables en l'absence de tolérance aux pannes. Les expériences menées jusqu'à 256 noeuds sur une grappe de PCs bi-coeurs, démontrent une meilleure efficacité de la solution de tolérance aux pannes de FT-GReLoSSS par rapport à des solutions existantes de niveau système (LAM/MPI et DMTCP).

Cette thèse vise à définir une méthodologie de mise en œuvre d'applications performantes sur les processeurs embarqués du futur. Ces architectures nécessitent notamment d'exploiter au mieux les différents niveaux de parallélisme (grain fin, gros grain) et de gérer les communications et les accès à la mémoire. Pour étudier cette méthodologie, nous avons utilisé un processeur cible représentatif de ces architectures émergentes, le processeur CELL. Le détecteurde points d'intérêt de Harris est un exemple de traitement régulier nécessitant des unités de calcul intensif. En étudiant plusieurs schémas de mise en oeuvre sur le processeur CELL, nous avons ainsi pu mettre en évidence des méthodes d'optimisation des calculs en adaptant les programmes aux unités spécifiques de traitement SIMD du processeur CELL. L'utilisation efficace de la mémoire nécessite par ailleurs, à la fois une bonne exploitation des transferts et un arrangement optimal des données en mémoire. Nous avons développé un outil d'abstraction permettant de simplifier et d'automatiser les transferts et la synchronisation, CELL MPI. Cette expertise nous a permis de développer une méthodologie permettant de simplifier la mise en oeuvre parallèle optimisée de ces algorithmes. Nous avons ainsi conçu un outil de programmation parallèle à base de squelettes algorithmiques : SKELL BE. Ce modèle de programmation propose une solution originale de génération d'applications à base de métaprogrammation. Il permet, de manière automatisée, d'obtenir de très bonnes performances et de permettre une utilisation efficace de l'architecture, comme le montre la comparaison pour un ensemble de programmes test avec plusieurs autres outils dédiés à ce processeur.

Cette thèse porte sur la segmentation supervisée de flux vidéo dans un contexte applicatif lié à la reconnaissance d'actions de la vie courante.La méthode de segmentation proposée est dérivée la méthode des modèles de formes implicites (Implicit Shape Model) et s'obtient en optimisant les votes présents dans cette méthode d'élection.Nous démontrons que cette optimisation (dans un contexte de fenêtre temporelle glissante) peut être exprimée de manière équivalente dans le formalisme des SVM en imposant une contrainte de cohérence temporelle à l'apprentissage, ou, en représentant la fenêtre glissante selon une décomposition pyramidale dense.Tout ce processus est validé expérimentalement sur un jeu de données de la littérature de segmentation supervisée.Il y surpasse les autres méthodes de type modèles de formes implicites et le SVM linéaire standard.La méthode proposée est ensuite mise en œuvre dans le cadre de la segmentation supervisée d'actions.Pour cela, des primitives dédiées sont extraites des données squelette de la personne d'intérêt obtenues grâce à des logiciels standards.Ces primitives sont ensuite quantifiées puis utilisées par la méthode d'élection.Ce système de segmentation d'actions obtient les meilleurs scores de l'état de l'art sur un jeu de données de la littérature de reconnaissance d'actions, ce qui valide cette combinaison des primitives et de la méthode d'élection. / This thesis focuses on the supervised segmentation of video streams within the application context of daily action recognition.A segmentation algorithm is obtained from Implicit Shape Model by optimising the votes existing in this polling method.We prove that this optimisation can be linked to the sliding windows plus SVM framework and more precisely is equivalent with a standard training by adding temporal constraint, or, by encoding the data through a dense pyramidal decomposition. This algorithm is evaluated on a public database of segmentation where it outperforms other Implicit Shape Model like methods and the standard linear SVM.This algorithm is then integrated into a action segmentation system.Specific features are extracted from skeleton obtained from the video by standard software.These features are then clustered and given to the polling method.This system, combining our feature and our algorithm, obtains the best published performance on a human daily action segmentation dataset.