Un modèle d'interprétation parallèle de Prolog basé sur la notion de processus est défini. En introduisant un type d'architecture nommée "architecture orientée processus" l'exécution du modèle dans un environnement multiprocesseurs est étudiée. Une expérimentation par simulation en langage parallèle Occam, en vue de valider le modèle et son exécution dans une architecture multiprocesseurs, est décrite. Finalement, un système Prolog avec la capacité de manipuler des clauses extérieures à la mémoire centrale est présenté.

Les technologies actuelles permettent l'intégration de systèmes de plus en plus complexes sur une seule puce. L'augmentation de la complexité induit un accroissement du temps de conception alors que paradoxalement, le concurrence économique impose des temps de mise sur le marché de plus en plus courts. Pour tenter de limiter ce décalage et d'accroître la productivité, l'industrie fait de plus en plus appel à la réutilisation de composants logiciels et matériels pour concevoir leurs systèmes.<br />L'un des problèmes de ce type de conception est celui de la réalisation de la communication entre composants. Cette thèse traite de la communication entre processeurs réalisée par des interfaces mixtes logicielles/matérielles. Leur difficulté de conception et l'impact du choix de partitionnement entre parties logicielles et matérielles nécessitent le développement de méthodes de génération automatique d'interfaces logicielles/matérielles pour l'exploration du partitionnement des services de communication.<br />La contribution de cette thèse consiste en une formalisation des problèmes liés à l'implémentation mixte logicielle/matérielle des services de communication et une proposition de flot pour la génération automatique d'interfaces. Des expériences de réalisations de primitives MPI ont permis d'appréhender le problème et de proposer un flot de génération automatique.

Dans le domaine de l'électronique pour la consommation de masse, les concepteurs sont tenus de fournir des systèmes embarqués qui doivent satisfaire des exigences de performance, de consommation, de co?t et de temps de mise sur le marché. Pour satisfaire toutes ces exigences, nous nous concentrons sur les systèmes sur puce multi-processeurs (MPSoCs) avec des processeurs configurables et des architectures hétérogènes. Comparés aux processeurs généralistes et aux circuits spécifiques à une application (ASICs), les processeurs configurables peuvent être utilisés pour équilibrer le rapport performance/nombre de transistors et la flexibilité. Dans cette thèse, les architectures hétérogènes sont définies comme un groupe de processeurs qui sont basées sur le même jeu d'instructions avec des extensions différentes. Cette thèse tente de résoudre les difficultés causées par les processeurs configurables et les architectures hétérogènes. En raison des processeurs configurables et de l'hétérogénéité, le champ des solutions d'implémentation devient extrêmement large et inclue des aussi bien des optimisations logicielles que des optimisationsmatérielles. C'est pourquoi nous présentons 4 niveaux d'abstraction différents avec des niveaux de détail et des vitesses de simulation différentes pour faciliter l'exploration des solutions d'implémentation. La méthode de simulation hybride est également intégrées à ces niveaux d'abstraction pour éviter les efforts d'adaption du logiciel dépendant du matériel (HdS pour Hardware dependant Software). En utilisant ces niveaux d'abstraction appliqués à ce genre de plateformes hétérogènes et configurables, nous avons construit un flot basé sur une exploration de l'ensemble des solutions d'implémentations sur des critères de budget. Réaliser une interface matériel/logiciel bien équilibrée est une tache complexe. Pour résoudre ce problème, nous utilisons le concept de graphe de dépendance des services (GdS) pour modéliser l'interface matériel/logiciel. Pour que l'implémentation choisie soit hautement performante et flexible, nous proposons un schéma de migration de taches dans lequel une tache peut être exécutée sur plusieurs processeurs compatibles avec différentes extensions d'instructions. Une application décodeur Motion-JPEG a été utilisée pour valider tous ces travaux.

Le travail présenté dans ce mémoire étudie et propose des modèles de calcul parallèles de type cellulaire pour traiter différents problèmes d’optimisation NP-durs définis dans l’espace euclidien, et leur implantation sur des processeurs graphiques multi-fonction (Graphics Processing Unit; GPU). Le but est de pouvoir traiter des problèmes de grande taille tout en permettant des facteurs d’accélération substantiels à l’aide du parallélisme massif. Les champs d’application visés concernent les systèmes embarqués pour la stéréovision de même que les problèmes de transports définis dans le plan, tels que les problèmes de tournées de véhicules. La principale caractéristique du modèle cellulaire est qu’il est fondé sur une décomposition du plan en un nombre approprié de cellules, chacune comportant une part constante de la donnée, et chacune correspondant à une unité de calcul (processus). Ainsi, le nombre de processus parallèles et la taille mémoire nécessaire sont en relation linéaire avec la taille du problème d’optimisation, ce qui permet de traiter des instances de très grandes tailles.L’efficacité des modèles cellulaires proposés a été testée sur plateforme parallèle GPU sur quatre applications. La première application est un problème d’appariement d’images stéréo. Elle concerne la stéréovision couleur. L’entrée du problème est une paire d’images stéréo, et la sortie une carte de disparités représentant les profondeurs dans la scène 3D. Le but est de comparer des méthodes d’appariement local selon l’approche winner-takes-all et appliquées à des paires d’images CFA (color filter array). La deuxième application concerne la recherche d’améliorations de l’implantation GPU permettant de réaliser un calcul quasi temps-réel de l’appariement. Les troisième et quatrième applications ont trait à l’implantation cellulaire GPU des réseaux neuronaux de type carte auto-organisatrice dans le plan. La troisième application concerne la génération de maillages structurés appliquée aux cartes de disparité afin de produire des représentations compressées des surfaces 3D. Enfin, la quatrième application concerne le traitement d’instances de grandes tailles du problème du voyageur de commerce euclidien comportant jusqu’à 33708 villes.Pour chacune des applications, les implantations GPU permettent une accélération substantielle du calcul par rapport aux versions CPU, pour des tailles croissantes des problèmes et pour une qualité de résultat obtenue similaire ou supérieure. Le facteur d’accélération GPU par rapport à la version CPU est d’environ 20 fois plus vite pour la version GPU sur le traitement des images CFA, cependant que le temps de traitement GPU est d’environ de 0,2s pour une paire d’images de petites tailles de la base Middlebury. L’algorithme amélioré quasi temps-réel nécessite environ 0,017s pour traiter une paire d’images de petites tailles, ce qui correspond aux temps d’exécution parmi les plus rapides de la base Middlebury pour une qualité de résultat modérée. La génération de maillages structurés est évaluée sur la base Middlebury afin de déterminer les facteurs d’accélération et qualité de résultats obtenus. Le facteur d’accélération obtenu pour l’implantation parallèle des cartes auto-organisatrices appliquée au problème du voyageur de commerce et pour l’instance avec 33708 villes est de 30 pour la version parallèle. / The work presented in this PhD studies and proposes cellular computation parallel models able to address different types of NP-hard optimization problems defined in the Euclidean space, and their implementation on the Graphics Processing Unit (GPU) platform. The goal is to allow both dealing with large size problems and provide substantial acceleration factors by massive parallelism. The field of applications concerns vehicle embedded systems for stereovision as well as transportation problems in the plane, as vehicle routing problems. The main characteristic of the cellular model is that it decomposes the plane into an appropriate number of cellular units, each responsible of a constant part of the input data, and such that each cell corresponds to a single processing unit. Hence, the number of processing units and required memory are with linear increasing relationship to the optimization problem size, which makes the model able to deal with very large size problems.The effectiveness of the proposed cellular models has been tested on the GPU parallel platform on four applications. The first application is a stereo-matching problem. It concerns color stereovision. The problem input is a stereo image pair, and the output a disparity map that represents depths in the 3D scene. The goal is to implement and compare GPU/CPU winner-takes-all local dense stereo-matching methods dealing with CFA (color filter array) image pairs. The second application focuses on the possible GPU improvements able to reach near real-time stereo-matching computation. The third and fourth applications deal with a cellular GPU implementation of the self-organizing map neural network in the plane. The third application concerns structured mesh generation according to the disparity map to allow 3D surface compressed representation. Then, the fourth application is to address large size Euclidean traveling salesman problems (TSP) with up to 33708 cities.In all applications, GPU implementations allow substantial acceleration factors over CPU versions, as the problem size increases and for similar or higher quality results. The GPU speedup factor over CPU was of 20 times faster for the CFA image pairs, but GPU computation time is about 0.2s for a small image pair from Middlebury database. The near real-time stereovision algorithm takes about 0.017s for a small image pair, which is one of the fastest records in the Middlebury benchmark with moderate quality. The structured mesh generation is evaluated on Middlebury data set to gauge the GPU acceleration factor and quality obtained. The acceleration factor for the GPU parallel self-organizing map over the CPU version, on the largest TSP problem with 33708 cities, is of 30 times faster.

Je présente dans ce document mes résultats de recherche sur la conception sûre de systèmes embarqués sûrs. La première partie concerne la répartition automatique de programmes synchrones. Le caractère automatique de la répartition apporte un réel degré de sûreté dans la conception de systèmes répartis car c'est la partie la plus délicate de la spécification qui est automatisée. Grâce à cela, l'absence d'inter-blocage et l'équivalence fonctionnelle entre le programme source centralisé et le programme final réparti peuvent être formellement démontrées. La deuxième partie traite le sujet de l'ordonnancement et de la répartition de graphes de tâches flots-de-données sur des architectures à mémoire répartie, avec contraintes de tolérance aux fautes et de fiabilité. Je présente principalement des heuristiques d'ordonnancement statique multiprocesseur avec pour but la tolérance aux fautes et la fiabilité des systèmes, mais également l'utilisation de méthodes formelles telles que la synthèse de contrôleurs discrets ou les transformations automatiques de programmes. Enfin, la troisième partie concerne les autoroutes automatisées, avec deux volets : la commande longitudinale de véhicules autonomes et les stratégies d'insertion dans les autoroutes automatisées.