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.

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.

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 propose une solution logicielle au problème du développement et de l'exécution en temps réel d'applications de vision sur des machines de type cluster. Pour cela, avons développé deux bibliothèques utilisant des techniques d'évaluation partielle et de méta-programmation template qui permettent de programmer ces machines en s'attachant à rendre accessible les modèles de programmation parallèles à des développeurs issus de la communauté Vision pour qui ces problématiques ne sont pas triviales, tout en conservant des performances élevées. Ces deux bibliothèques : EVE, qui prend en charge la gestion du parallélisme SIMD, et QUAF, qui propose un modèle de programmation à base de squelettes algorithmiques pour la programmation sur machines MIMD, ont été validées par deux applications de vision de complexité réaliste, une reconstruction 3D et un suivi de piéton par filtrage particulaire, développées et exécutées sur un cluster dédié à la vision artificielle

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.

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. / This thesis aims to define a design methodology for high performance applications on future embedded processors. These architectures require an efficient usage of their different level of parallelism (fine-grain, coarse-grain), and a good handling of the inter-processor communications and memory accesses. In order to study this methodology, we have used a target processor which represents this type of emerging architectures, the Cell BE processor.We have also chosen a low level image processing application, the Harris points of interest detector, which is representative of a typical low level image processing application that is highly parallel. We have studied several parallelisation schemes of this application and we could establish different optimisation techniques by adapting the software to the specific SIMD units of the Cell processor. We have also developped a library named CELL MPI that allows efficient communication and synchronisation over the processing elements, using a simplified and implicit programming interface. This work allowed us to develop a methodology that simplifies the design of a parallel algorithm on the Cell processor.We have designed a parallel programming tool named SKELL BE which is based on algorithmic skeletons. This programming model providesan original solution of a meta-programming based code generator. Using SKELL BE, we can obtain very high performances applications that uses the Cell architecture efficiently when compared to other tools that exist on the market.

Les architectures parallèles sont désormais présentes dans tous les matériels informatiques, mais les programmeurs ne sont généralement pas formés à leur programmation dans les modèles explicites tels que MPI ou les Pthreads. Il y a un besoin important de modèles plus abstraits tels que les squelettes algorithmiques qui sont une approche structurée. Ceux-ci peuvent être vus comme des fonctions d’ordre supérieur synthétisant le comportement d’algorithmes parallèles récurrents que le développeur peut ensuite combiner pour créer ses programmes. Les développeurs souhaitent obtenir de meilleures performances grâce aux programmes parallèles, mais le temps de développement est également un facteur très important. Les approches par squelettes algorithmiques fournissent des résultats intéressants dans ces deux aspects. La bibliothèque Orléans Skeleton Library ou OSL fournit un ensemble de squelettes algorithmiques de parallélisme de données quasi-synchrones dans le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Nous avons amélioré OSL afin de lui apporter de meilleures performances et une plus grande expressivité. Nous avons voulu analyser le rapport entre les performances des programmes et l’effort de programmation nécessaire sur OSL et d’autres modèles de programmation parallèle. La comparaison rigoureuse entre des programmes parallèles dans OSL et leurs équivalents de bas niveau montre une bien meilleure productivité pour les modèles de haut niveau qui offrent une grande facilité d’utilisation tout en produisant des performances acceptables. / Parallel architectures have now reached every computing device, but software developers generally lackthe skills to program them through explicit models such as MPI or the Pthreads. There is a need for moreabstract models such as the algorithmic skeletons which are a structured approach. They can be viewed ashigher order functions that represent the behaviour of common parallel algorithms, and those are combinedby the programmer to generate parallel programs. Programmers want to obtain better performances through the usage of parallelism, but the development time implied is also an important factor. Algorithmic skeletons provide interesting results in both those fields. The Orléans Skeleton Library or OSL provides a set of algorithmic skeletons for data parallelism within the bulk synchronous parallel model for the C++ language. It uses advanced metaprogramming techniques to obtain good performances. We improved OSL in order to obtain better performances from its generated programs, and extended its expressivity. We wanted to analyze the ratio between the performance of programs and the development effort needed within OSL and other parallel programming models. The comparison between parallel programs written within OSL and their equivalents in low level parallel models shows a better productivity for high level models : they are easy to use for the programmers while providing decent performances.

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.