Nous presentons une methode generale de planification : L'algorithme Fil d'Ariane. Cette methode est appliquee au probleme de la planification automatique de trajectoires. L'originalite de la methode reside dans son adaptation automatique a la complexite du probleme pose. La planification automatique de trajectoires est transformee en un probleme d'optimisation d'une fonctionnelle de<br />l'espace des plans dans $R^+$. Cette optimisation permet d'explorer<br />les positions accessibles a partir d'une configuration initiale. La<br />methode ne construit pas l'espace des configurations; par contre, a<br />mesure que le temps passe, une approximation de plus en plus fine de<br />l'espace accessible est construite. Cette approximation est faite par<br />un premier algorithme appele l'algorithme $EXPLORE$ qui garantit la<br />completude pour une resolution donnee de la methode. D'autre part,<br />un deuxieme algorithme, l'algorithme $SEARCH$, permet d'accelerer<br />la recherche d'un chemin et d'atteindre la configuration finale. En<br />resume, la methode proposee permet de construire un planificateur<br />complet pour une resolution donnee qui exploite d'une maniere<br />efficace l'espace des plans pour explorer l'espace des configurations.<br />Nous avons implante deux planificateurs bases sur l'algorithme Fil<br />d'Ariane : le premier est un planificateur de trajectoires pour un<br />robot mobile holonome, et le deuxieme, notre experimentation<br />principale, un planificateur de trajectoires pour un bras manipulateur<br />a six degres de liberte. Pour ce dernier, nous avons realise une<br />implantation de notre algorithme sur une machine massivement<br />parallele et planifie les mouvements d'un bras a 6 degres de<br />liberte.<br />Pour optimiser les fonctions des algorithmes EXPLORE et SEARCH nous<br />avons utilise les algorithmes genetiques. Ces algorithmes<br />sont des methodes d'optimisation stochastiques facilement<br />parallelisables.

Cette these contribue a l'etude des semantiques pour la specification et la verification des systemes reactifs. Plus precisement, nous comparons des semantiques comportementales, basees sur la bisimulation avec celles induites par des logiques modales du temps arborescent. Dans la premiere partie, nous considerons les modeles d'entrelacement pour les systemes sequentiels non-deterministes. Plusieurs travaux recents ont montre que dans le cadre des systemes a branchement infini (c-a-d. non-determinisme infini), l'equivalence de bisimulation (forte), reconnue comme l'equivalence semantique de base pour le temps arborescent, est strictement plus fine que celles induites par les logiques du temps arborescent (nous savons depuis longtemps qu'elles coincident sous l'hypothese de branchement fini). Nous utilisons les Processus Ordinaux de Klop, et, en derivant une notion de pouvoir de distinction d'une equivalence semantique, nous montrons dans un cadre parfaitement unifie que la bisimulation est plus fine que les logiques du temps arborescent, mais aussi que pour une large classe de combinateurs, les congruences engendrees par les logiques restent strictement plus faibles que la bisimulation. Dans la deuxieme partie de la these, nous considerons les modeles d'ordre partiel pour les systemes paralleles, dans lesquels on dispose d'une definition satisfaisante de l'operation de raffinement de programme (cette notion est liee a la methode classique de conception hierarchique des programmes). Parmi les equivalences semantiques de la litterature, la history preserving bisimulation est particulierement interessante car c'est une congruence pour l'operation de raffinement quand les systemes n'ont pas d'action invisible. En utilisant une caracterisation de cette equivalence en termes d'une bisimulation avant-arriere, nous exhibons deux caracterisations logiques, ainsi qu'un algorithme de traduction entre ces deux logiques. Nous etudions aussi plusieurs variantes de cette bisimulation avant-arriere. Enfin, nous elargissons le champ de travail en considerant les modeles d'ordre partiel avec actions invisibles. Nous montrons que la bisimulation avant-arriere susmentionnee, adaptee a ce cadre, coincide avec la branching bisimulation sur les arbres causaux, mais aussi avec deux nouvelles equivalences~: l'equivalence de mixed-ordering branching et la history preserving branching bisimulation, que nous etudions.

La demande croissante de puissance de calcul est telle que des ordinateurs de plus en plus performants sont fabriques. Afin que ces machines puissent etre facilement exploitees, les lacunes actuelles en terme d'environnements de programmation doivent etre comblees. Le but a atteindre est de trouver un compromis entre recherche de performances et portabilite. Cette these s'interesse plus particulierement au placement statique de graphes de taches sur architectures paralleles a memoire distribuee. Ce travail s'inscrit dans le cadre du projet INRIA-IMAG APACHE et du projet europeen SEPP-COPERNICUS (Software Engineering for Parallel Processing). Le graphe de taches sans precedence est le modele de representation de programmes paralleles utilise dans cette these. Un tour d'horizon des solutions apportees dans la litterature au probleme de l'ordonnancement et du placement est fourni. La possibilite d'utilisation des algorithmes de placement sur des graphes de precedence, apres une phase de regroupement, est soulignee. Une solution originale est proposee, cette solution est interfacee avec un environnement de programmation complet. Trois types d'algorithmes (gloutons, iteratifs et exacts) ont ete concus et implementes. Parmi ceux-ci, on retrouve plus particulierement un recuit simule et une recherche tabu. Ces algorithmes optimisent differentes fonctions objectives (des plus simples et universelles aux plus complexes et ciblees). Les differents parametres caracterisant le graphe de taches peuvent etre affines suite a un releve de traces. Des outils de prise de traces permettent de valider les differentes fonctions de cout et les differents algorithmes d'optimisation. Un jeu de tests est defini et utilise. Les tests sont effectue sur le Meganode (machine a 128 transputers), en utilisant comme routeur VCR de l'universite de Southampton, les outils de generation de graphes synthetiques ANDES du projet ALPES (developpe par l'equipe d'evaluation de performances du LGI-IMAG) et l'algorithme de regroupement DSC (Dominant Sequence Clustering) de PYRROS (developpe par Tao Yang et Apostolos Gerasoulis). Mapping task graphs on distributed memory parallel computers

Le but de cette these est d'etudier et developper des methodes pour la parallelisation efficace des applications scientifiques sur machines paralleles a memoire distribuee. Dans une premiere partie nous presentons deux bibliotheques de fonctions de communication PVM ((\it Parallel Virtual Machine)) et MPI ((\it Message Passing Interface)). Ces dernieres fournissent une portabilite des programmes sur la grande majorite des machines paralleles, mais aussi sur des reseaux d'ordinateurs heterogenes. Cette partie illustre le probleme de la mesure des performances pour des reseaux de processeurs heterogenes. Ceci nous a amene a adapter le calcul du facteur d'acceleration et de l'efficacite afin de pouvoir evaluer les performances d'un algorithme sur un reseau de processeurs heterogenes. La deuxieme partie est consacree a l'etude de bibliotheques numeriques paralleles, comme ScaLAPACK, et au developpement d'une methode etudiee de maniere theorique, mais peu utilisee en pratique pour augmenter les performances des fonctions de ces bibliotheques : le recouvrement calcul/communication. L'idee generale consiste a anticiper les communications, notamment en pipelinant l'envoi des messages. Des resultats experimentaux sur machines Cray T3D et IBM SP1, permettent de valider les etudes theoriques effectuees sur des algorithmes de base de ces bibliotheques.

Les travaux de cette thèse s’inscrivent dans le domaine des systèmes complexes et s’intéressent plus particulièrement à l’exécution efficace et reproductible de simulations multi-agents de grande taille dans un contexte parallèle et distribué de haute performance de type cluster (HPC). Dans ce contexte, nous nous intéressons plus particulièrement à la conception des modèles pour faciliter leur distribution, à la synchronisation des composants distribués et à la communication entre agents. La première contribution de cette thèse est la comparaison qualitative et quantitative des principales plateformes multi-agents parallèles et distribués qui ciblent les simulations à large échelle dans un environnement haute performance.Ce travail a permis d’identifier les limites ou manques des plateformes existantes, majoritairement la communication entre les agents, la synchronisation ainsi que la distribution de la charge peu flexible. Pour offrir plus de flexibilité à la distribution des simulations, nous proposons un formalisme de modélisation à base de graphes imbriqués qui nous permet de tirer parti de librairies performantes pour décomposer et distribuer les simulations. Nous avons ensuite effectué une étude sur l’impact de la synchronisation dans les PDMAS, en proposant trois politiques de synchronisation différentes afin de fournir aux modélisateurs un niveau de résolution adapté aux différents problèmes de synchronisation. Pour finir, nous définissons un schéma de communication entre toutes les entités qui composent une simulation indépendamment du processus sur lequel les entités s’exécutent. Ces propositions sont réunies au sein d’une plateforme multi-agents parallèle appelée FractalPMAS. Cette plateforme est une preuve de concept qui nous a permis de mettre en œuvre nos différentes contributions afin d’observer et de comparer les comportements de nos algorithmes. Pour valider ce travail trois modèles agents reconnus, le modèle proie-prédateur, le modèle Flocking et un modèle de contamination, ont été utilisés. Nous avons réalisé des simulations utilisant jusqu’à 512 cœurs et les résultats obtenus, en termes de performances et d’extensibilité, s’avèrent prometteurs. / Contributions of this PHD take place on computer science research on complex systems, specifically in efficient andreproducible execution of large multi-agent simulations in a parallel and distributed high performance cluster type of context(HPC) systems. We are particularly interested in the design of models to facilitate their distribution, synchronization ofdistributed components and communication between agents. In this context, we are particularly interested in the designof models to facilitate their distribution, synchronization of distributed components and communication between agents.The first contribution of this thesis is the qualitative and quantitative comparison of the main parallel and distributedmulti-agent platforms targeting large scale simulations in a high performance environment. This work identified limitationsof existing platforms, mainly communication between agents, synchronization and the distribution of the load which isinflexible. To offer more flexibility in the distribution of simulations, we propose a modeling formalism based nested graphsallowing us to decompose and distributed simulations using powerful libraries. We then conducted a study on the impactof synchronization in PDMAS, proposing three different synchronization policies to provide modelers a level of resolutionadapted to the various synchronization problems. Finally, we define a communication schema between all entities thatmake up a simulation regardless of the process on which entities are running.These contributions are combined in a parallel multi-agent platform called FractalPMAS. This platform is a proof of conceptand allowed us to implement our different contributions to observe and compare the behavior of our algorithms. To validatethis work three recognized agents model, the predator-prey model, the Flocking model and contamination model wereused. We performed simulations using up to 512 cores and the results obtained, in terms of performance and scalabilityare promising.

Le travail presente dans cette these consiste a definir les fonctionnalites d'une machine virtuelle ParObj, supportant la notion d'objets concurrents et adaptee aux exigences du parallelisme massifs. Cette these s'inscrit dans le cadre du projet PARX de l'equipe "SYstemes Massivement PAralleles" du LGI qui vise a specifier et a realiser un systeme d'exploitation pour machines paralleles. A travers l'analyse de quelques Systemes Distribues a Objets connus, nous degageons les mecanismes de base que doit supporter ParObj. Nous avons arrete notre etude sur les aspects suivants : structures des entites, gestion des entites, gestion des interactions entre entites, et gestion des ressources. Dans notre approche, nous offrons dans ParObj un support parallele pour des objets passifs et actifs qui peuvent etre a la fois a gros grains (fichier, processus, etc.), et a grains intermediaires (liste chainee, thread, etc.). Pour une gestion encore plus fine du parallelisme, nous supportons aussi la notion d'objet fragmente. Un objet fragmente est un objet qui est decoupe en plusieurs sous-objets independants (fragments de l'objet) de taille quelconque, et qui peuvent etre accedes individuellement, de maniere concurrente.En revanche, nous avons decide de laisser aux compilateurs le soin de gerer les objets a grains fins. De plus, pour eliminer les conflits d'acces aux donnees, nous offrons un mecanisme de synchronisation des objets. L'architecture generale de ParObj est basee sur le modele original a trois niveaux de processus de PARX : le thread (qui est un flot de controle sequentiel a l'interieur d'une tache), la tache (qui est un contexte d'execution), et la Ptache (qui represente un programme parallele a l'execution). Une Ptache definit un domaine de communication et de protection, et assure la correction semantique du programme parallele (synchronisation des taches, controle des protocoles d'echanges, etc.). Au sein d'une Ptache, la protection des objets est assuree grace a des capacites. La localisation d'une entite (qui depend de sa visibilite et de sa reference) est realise grace a un mecanisme original de designation. Les experimentations que nous avons realisees montrent que ce mecanisme est parfaitement adapte a la gestion du parallelisme massif.

La simulation physique interactive est une composante clé pour les environnements virtuels. Toutefois, la quantité de calcul ainsi que la complexité du code augmente rapidement avec la variété, le nombre et la taille des objets simulés. Au cours de cette thèse nous avons étudié les différents moyens d'améliorer l'interactivité, et en même temps de minimiser l'impact sur le code de simulation. En premier lieu nous avons développé une nouvelle approche de détection de collisions pour les objets déformables qui est rapide et plus robuste que les approches traditionnelles de détection par proximité. Pour tirer profit des machines multi-core, nous proposons une approche de parallélisation qui repose sur un parallélisme des tâches. Avant l'éxecution d'un pas de temps nous extrayons un graphe de dépendance de tâche qui est partitionné pour définir la répartition des tâches entre les processeurs. Cette approche a un faible impact sur les algorithmes de simulation physique étant donné que le parallélisme est obtenu en changeant uniquement le code d'orchestration du lancement des tâches. Finalement, nous avons étendu nos travaux aux architectures multi-CPU et multi-GPU. L'utilisation de ces ressources de manière efficace et transparente est un enjeu de taille. Nous proposons un schéma de parallélisation pour l'équilibrage dynamique de charge entre plusieurs CPUs et GPUs. Nous nous appuyons sur une approche à deux niveaux associant un partitionement du graphe de tâches et l'équilibrage de charge par l'utilisation du vol de travail guidé par des critères d'affinité entre processeurs. Ces critères visent à limiter les migrations de taches entre les unités de calcul, et de favoriser l' association de petites tâches sur les processeurs et des grandes sur les GPU pour tirer parti de l'hétérogénéité.

Les applications temps réel durs sont celles qui doivent exécuter en respectant des contraintes temporelles. L'ordonnancement temps réel a bien été étudié sur mono-processeurs depuis plusieurs années. Récemment, l'utilisation d'architectures multiprocesseurs a augmenté dans les applications industrielles et des architectures parallèles sont proposées pour que le logiciel devienne compatible avec ces plateformes. L'ordonnancement multiprocesseurs de tâches parallèles dépendantes n'est pas une simple généralisation du cas mono-processeur et la problématique d'ordonnancement devient plus complexe et difficile.
Dans cette thèse, nous étudions le problème d'ordonnancement temps réel de graphes de tâches parallèles acycliques sur des plateformes multiprocesseurs. Dans ce modèle, un graphe est composé d'un ensemble de sous-tâches dépendantes sous contraintes de précédence qui expriment les relations de précédences entre les sous-tâches. L'ordre d'exécution des sous-tâches est dynamique, c'est-à-dire que les sous-tâches peuvent s'exécuter en parallèle ou séquentiellement par rapport aux décisions de l'ordonnanceur temps réel. Pour traiter les contraintes de précédence, nous proposons deux méthodes pour l'ordonnancement des graphes : par transformation du modèle de graphe de sous tâches parallèles en un modèle de tâches séquentielles indépendantes, plus simple à ordonnancer et par ordonnancement direct des graphes en prenant en compte les relations de dépendance entre les sous-tâches. Nous proposons un ordonnancement des graphes en prenant directement en compte les paramètres temporels des graphes et un ordonnancement au niveau des sous-tâches, par rapport à des paramètres temporels attribués aux sous-tâches par un algorithme spécifique.
Enfin, nous prouvons que les deux méthodes d'ordonnancement de graphes ne sont pas comparables. Nous fournissons alors des résultats de simulation pour comparer ces méthodes en utilisant les algorithmes d'ordonnancement globaux EDF et DM. Nous avons développé un logiciel nommé YARTISS pour générer des graphes aléatoires et réaliser les simulations / The interest for multiprocessor systems has recently been increased in industrial applications, and parallel programming API's have been introduced to benefit from new processing capabilities. The use of multiprocessors for real-time systems, whose execution is performed based on certain temporal constraints is now investigated by the industry. Real-time scheduling problem becomes more complex and challenging in that context. In multiprocessor systems, a hard real-time scheduler is responsible for allocating ready jobs to available processors of the systems while respecting their timing parameters.
In this thesis, we study the problem of real-time scheduling of parallel Directed Acyclic Graph (DAG) tasks on homogeneous multiprocessor systems. In this model, a DAG task consists of a set of subtasks that execute under precedence constraints. At all times, the real-time scheduler is responsible for determining how subtasks execute, either sequentially or in parallel, based on the available processors of the system. We propose two DAG scheduling approaches to determine the execution form of DAG tasks. The first approach is the DAG Stretching algorithm, from the Model Transformation approach, which forces DAG tasks to execute as sequentially as possible. The second approach is the Direct Scheduling, which aims at scheduling DAG tasks while respecting their internal dependencies. We provide real-time schedulability analyses for Direct Scheduling at DAG-Level and at Subtask-Level.
Due to the incomparability of DAG scheduling approaches, we use extensive simulations to compare performance of global EDF with global DM scheduling using our simulation tool YARTISS

Les grammaires attribuées offrent un formalisme très adapté à la détection du parallélisme et à la parallélisation. Les graphes de dépendances associés à chaque production correspondent en effet à des graphes de flot de contrôle. Grâce aux grammaires attribuées (\it l)-ordonnées, il est possible de calculer statiquement un ordre total sur les attributs des non-terminaux qui soit compatible avec l'ordre partiel induit par les graphes de dépendances, ce qui évite grand nombre de synchronisations dynamiques. Toutefois, il apparaît que le parallélisme inhérent à ces graphes est beaucoup trop important en pratique pour supporter une parallélisation complète. Notre but a été de montrer qu'il est possible de sélectionner le parallélisme pour obtenir une parallélisation efficace en pratique. Pour cela, l'évaluateur parallèle a été implanté dans un système réel de traitement des grammaires attribuées qu'est le système (\sc FNC-2) et porté sur plusieurs plateformes (KSR1, Multimax et Sequent). Plusieurs types d'implantations ont été effectués afin d'étudier l'influence de la méthode d'évaluation sur la parallélisation. Les méthodes que nous avons utilisées s'appliquent à des architectures à mémoire partagée. Sur les machines testées, les résultats obtenus sont très encourageants malgré l'absence d'utilisation de caractéristiques propres à chaque machine. Un deuxième problème soulevé par le parallélisme est l'explosion mémoire qui a lieu pendant l'évaluation. En séquentiel, cette consommation a été largement limitée par l'utilisation d'un optimiseur mémoire qui permet le partage des instances d'attributs en dehors de l'arbre. Deux structures sont utilisées\,: la variable globale et la pile. Nous avons proposé une méthode pour étendre cette optimisation mémoire au cas parallèle ce qui permet d'une part de sortir les attributs de l'arbre même en parallèle et d'autre part d'éliminer de nombreuses règles de copie.

La complexité croissante des systèmes d'acquisition et de traitement en temps réel (TDAQ) pour les expériences de physique des hautes énergies appelle à une évolution ad hoc des outils de développement. Dans cet ouvrage, nous traitons de l'articulation entre la spécification de principe des systèmes TDAQ et leur conception/réalisation sur une plateforme matérielle et logicielle concrète. Notre travail repose sur la définition d'une méthodologie de développement des systèmes TDAQ qui réponde aux problématiques de développements particulières à ces systèmes. Il en résulte la spécification détaillée d'un « canevas méthodologique » basé sur le langage UML, destiné à encadrer un processus de développement. L'usage de ce canevas méthodologique UML doit permettre la mise en place progressive d'un canevas « maison », c'est-à-dire un atelier de développement comprenant des composants réutilisables et des éléments d'architecture génériques adaptés aux applications TDAQ. L'ouvrage s'articule autour de 4 sections principales. La section II est dévolue à la caractérisation et à l'évolution des systèmes TDAQ. En section III, nous nous intéressons aux technologies pertinentes pour notre problématique, notamment les techniques de réutilisation logicielle telles les motifs récurrents (design patterns) et les canevas (frameworks), avec une orientation en faveur des domaines du temps réel et de l'embarqué. Notre apport conceptuel spécifique est exposé en section IV, où nous procédons notamment à la spécification détaillée, formalisée et exemples à l'appui, de notre modèle de développement. Enfin, nous terminons notre propos en section V en évoquant le projet de R&D MORDICUS de mise en œuvre concrète de notre canevas méthodologique UML, ainsi que les développements récents de l'OMG (Object Management Group) sur l'architecture orientée modèles (Model Driven Architecture), particulièrement en résonance avec notre travail.