Le contexte de ce travail est l'assistance à la conception de systèmes embarqués, et particulièrement de Systems on Chip (SoC). Les domaines d'application concernés sont variés: avionique, téléphones portables, automobile. La complexité de ces systèmes, et leur interaction forte avec leur environnement, posent des problème de maîtrise de la conception (pour éviter les détections d'erreurs tardives, les diagnostics et réparations coûteux en moyens, mais aussi en temps de mise sur le marché), et de validation ou certification pour les systèmes à sûreté critique (qui doivent être vérifiés avant leur mise en service). Il s'en suit un fort besoin de méthodes et d'outils pour assister la conception sûre de ces systèmes, qui prennent la forme de méthodologies et de modèles à base de composants, de langages de spécification de haut niveau, d'outils de transformation et compilation, d'analyse et de vérification, de synthèse et génération de code. Dans ce contexte, une contribution est une proposition d'un modèle intermédiaire entre les systèmes de calculs dans le cadre du parallélisme de données intensif et les langages formels. Ce modèle intermédiaire permet la génération du code en langages formel à partir de ces systèmes dans le cadre ingénierie dirigé par les modèles. La validation formelle et l'analyse statique est donc possible sur la base du code généré. Une autre contribution est une proposition de mécanismes de contrôle dans le même cadre, sous forme de constructeurs de langage de haut-niveau et de leur sémantique. On veut les définir pour leur exploitation dans la vérification, synthèse et génération de code. Il s'agit de déterminer un niveau d'abstraction de représentation des systèmes où soit extraite la partie contrôle, et de la modéliser sous forme d'automates à états finis. Ceci permet de spécifier et implémenter des changements de modes calculs, qui se distinguent par exemple par les ressources utilisées, la qualité du service fourni, le choix d'algorithme remplissant une fonctionnalité. Cette abstraction est alors favorable à l'application d'outils d'analyse et vérification (de type model checking). On s'intéressera aussi à l'utilisation de techniques de synthèse de contrôleurs discrets, qui peut assurer la correction de façon constructive: à partir d'une spécification partielle du contrôle, elle calcule la partie manquante pour que les propriétés soient satisfaites. L'avantage pour le développement de la partie contrôle est dans la simplification de la spécification, et la correction par construction du résultat. Ce travail se fera en articulation avec des travaux déjà commencés sur la proposition d'une méthodologie de séparation contrôle/donnée! de mécanismes de contrôle, et leur intégration dans l'environnement de conception de systèmes à parallélisme de données intensif Gaspard. On travaillera dans le cadre des modèles de systèmes réactifs proposés par l'approche synchrone, de ses langages de programmation à base d'automates, et de ses outils académiques et commerciaux. En étude de cas, on s'intéressera à des applications en systèmes embarqués téléphone portable multimédia. / The work presented in this dissertation is carried out in the context of System-on-Chip (SoC) and embedded system design, particularly dedicated to data-parallel intensive processing applications (DIAs). Examples of such applications are found in multimedia processing and signal processing. On the one hand, safe design of DIAs is considered to be important due to the need of Quality of Service, safety criticality, etc., in these applications. However, the complexity of current embedded systems makes it difficult to meet this requirement. On the other hand, high-Ievel safe control, is highly demanded in order to ensure the correctness and strengthen the flexibility and adaptivity of DIAs. As an answer to this issue, we propose to take advantage of synchronous languages to assist safe DIAs design. First, a synchronous modeling bridges the gap between the Gaspard2 framework, which is dedicated to SoC design for DIAs, and synchronous languages that act as a model of computation enabling formal validation. The latter, together with their tools, enable high-Ievel validation of Gaspard2 specifications. Secondly, a reactive extension to a previous control proposition in Gaspard2, is also addressed. This extension is based on mode automata and contributes to conferring safe and verifiable features onto the previous proposition. As a result, model checking and discret controller synthesis can be applied for the purpose of correctness verification. Finally, a Model-Driven Engineering (MDE) approach is adopted in order to implement and validate our proposition, as well as benefit fron the advantages of MDE to address system complexity and productivity issues. Synchronous modeling, MARTE-based (the UML profile fo Modeling and Analysis of Real-Time and Embedded system) control modeling, and model transformations, including code generation, are dealt with in the implementation.

De nombreux travaux portent sur les réseaux de neurones artificiels appliqués à des systèmes fortement contraints (systèmes ambulatoires, systèmes autonomes, systèmes adaptatifs, etc), pour lesquels le caractère élémentaire et massivement distribué des calculs neuronaux s'avère un atout. De façon plus large, ce caractère définit la nature même des calculs connexionnistes : une puissance de calcul et une robustesse fondées sur un parallélisme massif à grain très fin où les unités de calcul s'insèrent dans un flux d'informations très dense. Il est donc indispensable de pouvoir pleinement exploiter ce parallélisme connexionniste, à la fois en termes de potentiel de calcul et en termes de perspectives d'implantations embarquées efficaces. Une partie de ces travaux s'attache à définir différentes approches d'implantation massivement parallèle de réseaux neuronaux. Une approche globale de la pratique de calcul connexionniste ne peut pas faire l'économie d'une réflexion sur les fondements de la conception des architectures connexionnistes susceptibles de résoudre un problème donné. L'essentiel des travaux sur les réseaux de neurones s'est concentré sur la définition de familles de modèles neuronaux dont l'apprentissage permet de traiter des tâches telles que classification, régression, discrimination, auto-régression, etc. Ces modèles restent d'actualité, ne serait-ce que par la variété des applications dans lesquelles ils jouent encore un rôle central, et les travaux rapportés dans ce manuscrit portent en partie sur ces modèles. Néanmoins, ils n'apparaissent le plus souvent que comme des outils de traitement statistique de données, au même titre que de nombreux autres modèles. Ils se heurtent ainsi à une barrière de complexité dans les problèmes qu'ils sont susceptibles de résoudre. Franchir "à l'aveuglette" cette barrière, c'est à dire proposer ex nihilo des architectures connexionnistes capables de réaliser des tâches cognitives complexes, ne semble pas raisonnable. De nombreux chercheurs suggèrent alors de prendre appui sur des exemples naturels de systèmes distribués capables de réaliser ces tâches. Les neurosciences sont une orientation possible. C'est cette inspiration sur la base des mécanismes observés dans le cerveau qui est proposée dans une partie des travaux rapportés dans ce manuscrit. L'objet de ces travaux n'est pas de faire le tour de l'apport possible des neurosciences pour la conception des modèles connexionnistes, mais de montrer que même dans le cas de modèles d'inspiration corticale, la défense du parallélisme connexionniste passe par une étude focalisée sur les mécanismes locaux de gestion du flux d'informations sous-jacent à ces modèles.

Les simulations paralllèles sont devenues des outils indispensables dans de nombreux domaines scientifiques. Pour simuler des phénomènes complexes, ces simulations sont exécutées sur de grandes machines parallèles. La puissance de calcul de ces machines n'a cessé de monter permettant ainsi le traitement de simulations de plus en plus imposantes. En revanche, les systèmes d'I/O nécessaires à la sauvegarde des données produites par les simulations ont suivit une croissance beaucoup plus faible. Actuellement déjà, il est difficile pour les scientifiques de sauvegarder l'ensemble des données désirées et d'avoir suffisament de puissance de calcul pour les analyser par la suite. A l'ère de l'Exascale, on estime que moins de 1% des données produites par une simulation pourronts être sauvegardées. Ces données sont pourtant une des clés vers des découvertes scientifiques majeures. Les traitements in-situ sont une solution prometteuse à ce problème. Le principe est d'effectuer des analyses alors que la simulation est en cours d'exécution et que les données sont encore en mémoire. Cette approche permet d'une part d'éviter le goulot d'étranglement au niveau des I/O mais aussi de profiter de la puissance de calcul offerte par les machines parallèles pour effectuer des traitements lourds en calcul. Dans cette thèse, nous proposons d'utiliser le paradigme du dataflow pour permettre la construction d'applications in-situ complexes. Pour cela, nous utilisons l'intergiciel FlowVR permettant de coupler des codes parallèles hétérogènes en créant des canaux de communication entre eux afin de former un graphe. FlowVR dispose de suffisament de flexibilité pour permettre plusieurs stratégies de placement des processus d'analyses que cela soit sur les nœuds de la simulation, sur des cœurs dédiés ou des nœuds dédiés. De plus, les traitements in-situ peuvent être exécutés de manière asynchrone permettant ainsi un faible impact sur les performances de la simulation. Pour démontrer la flexibilité de notre approche, nous nous sommes intéressés au cas à la dynamique moléculaire et plus particulièrement Gromacs, un code de simulation de dynamique moléculaire couramment utilisé par les biologistes pouvant passer à l'échelle sur plusieurs milliers de coeurs. En étroite collaboration avec des experts du domaine biologique, nous avons contruit plusieurs applications. Notre première application consiste à permettre à un utilisateur de guider une simulation de dynamique moléculaire vers une configuration souhaitée. Pour cela, nous avons couplé Gromacs à un visualiseur et un bras haptique. Grâce à l'intégration de forces émises par l'utilisateur, celui ci peut guider des systèmes moléculaires de plus d'un million d'atomes. Notre deuxième application se concentre sur les simulations longues sur les grandes machines parallèles. Nous proposons de remplacer la méthode native d'écriture de Gromacs et de la déporter dans notre infrastructure en utilisant deux méthodes distinctes. Nous proposons également un algorithme de rendu parallèle pouvant s'adapter à différentes configurations de placements. Notre troisième application vise à étudier les usages que peuvent avoir les biologistes avec les applications in-situ. Nous avons développé une infrastructure unifiée permettant d'effectuer des traitements aussi bien sur des simulations intéractives, des simulations longues et en post-mortem. / Parallel simulations have become a powerwul tool in several scientific areas. To simulate complex phenomena, these simulations are running on large parallel machines. The computational power available on those machines has increased a lot in the last years allowing to simulate very large models. Unfortunately, the I/O capabilities necessary to save the data produced by simulation has not grown at the same pace. Nowadays, it is already difficult to save all the needed data and to have enough computational power to analyse them afterwards. At the exascale time frame, it is expected that less than 1% of the total data produced by simulations will be saved. Yet, these data may lead to major discoveries. In-situ analytics are a promising solution to this problem. The idea is to treat the data while the simulation is still running and the data are in memory. This way, the I/O bottleneck is avoided and the computational power avaible on parallel machines can be used as well for analytics. In this thesis, we propose to use the dataflow paradigm to enable the construction of complex in-situ applications. We rely on the FlowVR middleware which is designed to couple parallel heterogeneous codes by creating communication channels between them to form a graph. FlowVR is flexible enough to allow several placement strategies on simulation nodes, dedicated cores or dedicated nodes. Moreover, in-situ analytics are executed asynchronously leading to a low impact on the simulation performances. To demonstrate the flexibility of our approach, we used Gromacs, a commonly used parallel molecular dynamic simulation package, as application target. With the help of biology experts, we have built several realistic applications. The first one is allowing a user to steer a molecular simulation toward a desired state. To do so, we have couple Gromacs with a live viewer and an haptic device. The user can then apply forces to drive molecular systems of more than 1 million atoms. Our second application focus on long simulation running in batch mode on supercomputers. We replace the native writing method of Gromacs by two methods in our infrastructure. We also propose a implemented a flexible rendering algorithm able to able to various placement strategies. Finally, we study the possible usage o biologists with our infrastructure. We propose a unifed framework able to run treatments on interactive simulation, long simulations and in post-process.

Mes recherches concernent les outils de développement pour le calcul intensif. Une application sera dite intensive s'il faut fortement l'optimiser pour obtenir la puissance de calcul requise pour répondre aux contraintes, d'une part, de temps d'exécution et, d'autre part, de ressources de la plateforme d'exécution. De telles applications se retrouvent aussi bien dans le domaine du calcul scientifique que dans le domaine du traitement de signal intensif (télécommunications, traitement multimédia). Les difficultés de développement de telles applications sont principalement l'exploitation du parallélisme des architectures d'exécution (des supercalculateurs aux systèmes sur silicium en passant par les grappes de stations de travail), l'hétérogénéité de ces mêmes architectures et le respect des contraintes de temps et de ressources. Le but de mes recherches est de proposer des outils permettant la programmation efficace des applications de calcul intensif. Ceux-ci peuvent être des compilateurs, des paralléliseurs ou des environnements de spécification. Mes travaux ont commencé par les compilateurs paralléliseurs et s'orientent de plus en plus vers les environnements de spécification. Ces environnements comportent des compilateurs paralléliseurs. Cette évolution consiste donc à remplacer le langage de programmation et la phase d'analyse des programmes par une spécification des algorithmes de plus haut niveau et facilitant la phase d'analyse de dépendances. En effet, le but de cette analyse est de retrouver l'essence de l'algorithme codé par le programme analysé. La spécification de l'algorithme par les seules dépendances de données permet d'éliminer l'analyse de dépendances et d'avoir toute l'information nécessaire pour les optimisations du compilateur paralléliseur. Quatre principes dirigent mes recherches : 1. Programmer au plus haut niveau possible. Il ne devrait pas être de la responsabilité du programmeur de gérer les détails de l'exécution de son application. Idéalement, il devrait exprimer son algorithme et les compilateurs devraient générer le code le plus efficace possible sur l'architecture visée. 2. Promouvoir le parallélisme de données. Ce paradigme de programmation permet justement une programmation de haut niveau dans bien des cas. Il est bien adapté au calcul intensif où les traitements sont souvent réguliers et la quantité de données manipulées importante. 3. Optimiser au plus tôt dans la chaîne de développement. Je suis convaincu que plus les informations de performances et les optimisations sont faites tôt dans le développement d'une application, plus ce développement sera rapide et l'application efficace. L'environnement de conception doit donc faire apparaître ces informations si elles sont disponibles, y compris avant compilation de l'application. 4. Restreindre le domaine d'application. Il est très difficile d'optimiser tous les programmes en général. Le domaine du calcul intensif lui-même est déjà ambitieux. En se focalisant sur un domaine d'application précis, on peut espérer réduire la variété des applications et ainsi proposer des optimisations adaptées. C'est la voie que j'ai suivie dans mes recherches les plus récentes en restreignant le domaine d'application au traitement de signal intensif.

Cette thèse présente l'étude de l'implantation d'un système Prolog parallèle sur une architecture sans mémoire commune dans le cadre du projet PLoSys (Parallel Logic System). L'exécution exploite le parallélisme de manière implicite. Le système repose sur un modèle OU multiséquentiel. Le partage de l'état d'exécution est assuré par copie des données. Le langage Prolog supporté est complet, et intègre les effets de bord classiques du langage. La gestion parallèle fait l'objet d'une étude complète pour préserver la compatibilité avec l'exécution séquentielle du langage Prolog. En particulier, une méthode originale est présentée pour la gestion parallèle des effets de bord. Enfin, ce document présente la réalisation d'un prototype portable, ainsi que l'analyse des résultats obtenus

Malgré sa complexité de résolution, le problème de SATisfaisabilité est une excellente et compétitive approche pour résoudre un large éventail de problèmes. Cela génère une forte demande pour une résolution de SAT haute performance de la part des industriels. Au fil du temps, de nombreuses approches et optimisations différentes ont été développées pour résoudre le problème plus efficacement. Ces innovations ont été faites sans prendre en compte le développement des micro processeurs actuels qui voient le nombre de leur cœurs de calcul augmenter. Cette thèse présente un nouveau type d'algorithme parallèle basé sur une forte collaboration où un processus riche est en charge de l'évaluation de l'arbre de recherche et où des processus pauvres fournissent des informations partielles ou globales, heuristiques ou logiques afin de simplifier la tâche du riche. Pour concrétiser ce solveur et le rendre efficace, nous avons étendu la notion de chemin de guidage à celle d'arbre de guidage. L'arbre de recherche est totalement partagé en mémoire centrale et tous les processeurs peuvent y travailler en même temps. Ce nouveau solveur est appelé MTSS pour Multi-Threaded SAT Solver. De plus, nous avons implémenté une tâche pour les processus riche et pauvres qui leur permet d'exécuter un solveur SAT externe, et cela, avec ou sans échange de lemmes afin de paralléliser tous types de solveurs (dédiés aux formules industrielles ou aléatoires). Ce nouvel environnement facilite la parallélisation des futures implémentations pour SAT. Quelques exemples et expérimentations, avec ou sans échange de lemmes, de parallélisation de solveurs externes sont présentées, mais aussi des résultats sur les performances de MTSS. Il est intéressant de noter que certaines accélérations sont super linéaires.

Pour permettre une plus grande capacité de calcul les concepteurs de systèmes embarqués se tournent aujourd'hui vers les MPSoC. Malheureusement, ces systèmes sont difficiles à programmer. Un des problèmes durs est l'expression et l'optimisation des réorganisations de données au sein d'un programme. Dans cette thèse nous souhaitons proposer une chaîne de compilation qui : 1) propose une syntaxe simple et haut-niveau pour exprimer le découpage et la réorganisation des données d'un programme parallèle ; 2) définisse une exécution déterministe du programme (critique dans le cadre des systèmes embarqués) ; 3) optimise et adapte les programmes aux contraintes de l'architecture. Pour répondre au point 1) nous proposons un langage haut-niveau, SLICES, qui permet de décrire les réorganisation de données à travers des découpages multidimensionnels. Pour répondre au point 2) nous montrons qu'il est possible de compiler SLICES vers un langage de flots de données, SJD, qui s'inscrit dans le modèle des Cyclostatic Data-Flow et donc admet une exécution déterministe. Pour répondre au point 3) nous définissons un ensemble de transformations qui préservent la sémantique des programmes SJD. Nous montrons qu'il existe un sous-ensemble de ces transformations qui génère un espace de programmes équivalents fini. Nous proposons une heuristique pour explorer cet espace de manière à choisir la variante la plus adaptée à notre architecture. Enfin nous évaluons cette méthode sur deux problèmes classiques : la réduction de la mémoire consommée et la réduction des communications d'une application parallèle.

Les volumes de données multimédia ont fortement crus ces dernières années. Facebook stocke plus de 100 milliards d'images, 200 millions sont ajoutées chaque jour. Cela oblige les systèmes de recherche d'images par le contenu à s'adapter pour fonctionner à ces échelles. Les travaux présentés dans ce manuscrit vont dans cette direction. Deux observations essentielles cadrent nos travaux. Premièrement, la taille des collections d'images est telle, plusieurs téraoctets, qu'il nous faut obligatoirement prendre en compte les contraintes du stockage secondaire. Cet aspect est central. Deuxièmement, tous les processeurs sont maintenant multi-cœurs et les grilles de calcul largement disponibles. Du coup, profiter de parallélisme et de distribution semble naturel pour accélérer tant la construction de la base que le débit des recherches par lots. Cette thèse décrit une technique d'indexation multidimensionnelle s'appelant eCP. Sa conception prend en compte les contraintes issues de l'usage de disques et d'architectures parallèles et distribuées. eCP se fonde sur la technique de quantification vectorielle non structurée et non itérative. eCP s'appuie sur une technique de l'état de l'art qui est toutefois orientée mémoire centrale. Notre première contribution se compose d'extensions destinées à permettre de traiter de très larges collections de données en réduisant fortement le coût de l'indexation et en utilisant les disques au mieux. La seconde contribution tire profit des architectures multi-cœurs et détaille comment paralléliser l'indexation et la recherche. Nous évaluons cet apport sur près de 25 millions d'images, soit près de 8 milliards de descripteurs SIFT. La troisième contribution aborde l'aspect distribué. Nous adaptons eCP au paradigme Map-Reduce et nous utilisons Hadoop pour en évaluer les performances. Là, nous montrons la capacité de eCP à traiter de grandes bases en indexant plus de 100 millions d'images, soit 30 milliards de SIFT. Nous montrons aussi la capacité de eCP à utiliser plusieurs centaines de cœurs. / The scale of multimedia collections has grown very fast over the last few years. Facebook stores more than 100 billion images, 200 million are added every day. In order to cope with this growth, methods for content-based image retrieval must adapt gracefully. The work presented in this thesis goes in this direction. Two observations drove the design of the high-dimensional indexing technique presented here. Firstly, the collections are so huge, typically several terabytes, that they must be kept on secondary storage. Addressing disk related issues is thus central to our work. Secondly, all CPUs are now multi-core and clusters of machines are a commonplace. Parallelism and distribution are both key for fast indexing and high-throughput batch-oriented searching. We describe in this manuscript a high-dimensional indexing technique called eCP. Its design includes the constraints associated to using disks, parallelism and distribution. At its core is an non-iterative unstructured vectorial quantization scheme. eCP builds on an existing indexing scheme that is main memory oriented. Our first contribution is a set of extensions for processing very large data collections, reducing indexing costs and best using disks. The second contribution proposes multi-threaded algorithms for both building and searching, harnessing the power of multi-core processors. Datasets for evaluation contain about 25 million images or over 8 billion SIFT descriptors. The third contribution addresses distributed computing. We adapt eCP to the MapReduce programming model and use the Hadoop framework and HDFS for our experiments. This time we evaluate eCP's ability to scale-up with a collection of 100 million images, more than 30 billion SIFT descriptors, and its ability to scale-out by running experiments on more than 100 machines.

Le traitement des systèmes pleins issus de modélisation d'interactions de type particulaires est un problème lourd que les méthodes multipôles proposent d'optimiser grâce à des approximations hiérarchiques basées sur la régularité des potentiels sous-jacents. Cette thèse offre des développements sur une nouvelle méthode multipôle pour l'électromagnétisme à la fois en terme d'un traitement unifié de l'ensemble des fréquences et informatique dans le cadre du paralléélisme et d'optimisations algorithmiques telles que le partitionnement par graphes et le recouvrement des communications par des calculs.

Les travaux menés dans cette thèse concernent les problèmes d'ordonnancement sur des plates-formes de calcul dynamiques et hétérogènes et s'appuient sur le modèle de communication "multi-port" pour les communications. Nous avons considéré le problème de l'ordonnancement des tâches indépendantes sur des plates-formes maîtres-esclaves, dans les contextes statique et dynamique. Nous nous sommes également intéressé au problème de la redistribution de fichiers répliqués dans le cadre de l'équilibrage de charge. Enfin, nous avons étudié l'importance des mécanismes de partage de bande passante pour obtenir une meilleure efficacité du système.