Auswahl der wissenschaftlichen Literatur zum Thema „Lots de graphes de tâches“

Au croisement des tâches « cohérence » et « formation des enseignants » de l’ANR ECalm, cette contribution porte sur la cohérence de textes d’élèves d’école primaire et de début de collège. Elle met en regard des annotations discursives prenant appui sur une extension de la SDRT (Segmented Discourse Representation Theory) permettant l’annotation de points d’incohérence et des jugements de cohérence formulés par des enseignant.e.s du premier degré dans le cadre d’une session de formation continue. La cohérence est envisagée comme une propriété de la représentation de discours que se construit celui qui interprète le texte tout au long de sa lecture. Le corpus analysé est issu du corpus RESOLCO, l’un des corpus de textes scolaires collectés, transcrits et annotés dans le cadre de l’ANR E-Calm. Ce corpus est constitué de textes en réponse à une même consigne d’écriture : une tâche-problème demandant aux élèves la rédaction d’un texte narratif impliquant la résolution d’anaphores de divers types. Cette analyse comparative vise tout d’abord à mettre à l’épreuve le modèle d’annotation discursive. Les incohérences visualisées dans les représentations sémantiques issues de l’analyse linguistique sous forme de graphes sont également perçues par les enseignant.e.s confronté.e.s à la lecture de ces mêmes textes, ce qui permet de valider le modèle. L’analyse des échanges à l’intérieur d’un groupe d’enseignants fait apparaitre que l’un des deux dispositifs proposés favorise la mise en place chez les enseignants d’une posture de lecteur à la recherche de la construction de la cohérence et non d’évaluateur en référence à une norme linguistique et leur permet d’interroger les calculs interprétatifs permettant de formuler des jugements de cohérence. La présentation des graphes aux enseignant.e.s les aide ensuite à objectiver leurs intuitions linguistiques et leurs jugements de cohérence.

La pandémie et le manque de main-d’œuvre qui affecte les entreprises et les organisations ne sont pas sans impact sur le milieu de travail. Ces deux conjonctures perturbent l’organisation du travail et l’attribution de tâches aux employés. De la même façon, les bouleversements engendrés par les fusions, défusions et réformes qui surviennent chaque décennie dans le réseau de la santé et des services sociaux du Québec entraînent leurs lots de changements. Chacun d’entre eux amène les gestionnaires, mais aussi les employés, à s’adapter. Au cœur de ces perturbations, le contrat psychologique (CP) se voit mis à l’épreuve alors qu’il émane de la relation d’emploi. Il se voit à risque de rupture alors qu’une telle rupture entraîne des coûts pour une organisation. Il est donc à propos de se demander : les pratiques de gestion peuvent-elles minimiser l’impact des bouleversements organisationnels sur le contrat psychologique? Par le recours à une méthode mixte (mixed method), l’étude présentée ici a permis de constater les effets favorables et défavorables de certaines pratiques de gestion liées à l’organisation du travail et aux pratiques d’attribution de tâches sur le contrat psychologique lors d’un bouleversement organisationnel. Offrant des bases à de nouvelles recherches sur les pratiques de gestion tout comme sur le contrat psychologique, les résultats permettent à des gestionnaires de prendre conscience de leur impact sur le contrat psychologique, et d’identifier des pratiques de gestion de l’organisation du travail et de tâches favorables au contrat psychologique afin d’en tirer profit dans le contexte actuel.

Cet article traite des processus d’écriture d’apprenants universitaires de français langue étrangère (L2/L3). Ces écritures ont été recueillies à l’aide du programme GenoGraphiX-Log qui est construit sur les exigences de la génétique textuelle et de la théorie mathématique des graphes. Notre corpus consiste en 44 écritures produites en français par des locuteurs ayant comme L1 soit l’anglais, soit le mandarin soit le finnois. Le premier objectif est de mieux décrire, en fonction des L1 des participants, les opérations d’écriture mises en oeuvre en français lors de la réalisation d’une même tâche. Le second objectif est d’évaluer comment la visualisation, basée sur la théorie des graphes et sur des méthodes statistiques inductives, soutient cette analyse des processus d’écriture. Les résultats se basent sur deux analyses issues des graphes : une analyse en composantes principales (ACP) et la visualisation des écritures exemplaires (les plus proches des centres de gravité de chaque groupe). Ces deux analyses complémentaires nous permettent de mesurer les spécificités des trois groupes et d’approfondir qualitativement l’analyse de signatures scripturales. Notre corpus et nos analyses montrent l’intérêt de l’utilisation des méthodes mixtes dans l’analyse des processus complexes d’écriture à l’aide d’outils de visualisation.

International audience This work proposes a scheduling strategy, based on re-indexing transformations, for task graphs associated with a linear timing function. This scheduling strategy is used to execute a cubical task graph, for which all the tasks have the sane execution time and inter-tasks communication delays are neglected, on a two-dimensional array of processors which is asymptotically space-optimal with respect to the timing function. Cet article présente une stratégie d'ordonnancement des graphes de tâches associés à une fonction de temps linéaire dans le contexte de la programmation parallèle. Cette stratégie d'ordonnancement est utilisée pour exécuter un graphe cubique de tâches, dont les tâches ont la même durée d'exécution et les temps de communications inter-tâches sont négligés, sur un réseau de processeurs bi-dimensionnel et asymptotiquement optimal par rapport à la fonction de temps. Ce résultat améliore la meilleure borne précédemment connue.

Cette thèse porte sur trois thématiques principales liées à l'ordonnancement de graphes de tâches sur des plates-formes de calcul modernes. Un graphe de tâches est une modélisation classique d'un programme à exécuter, par exemple une application de calcul scientifique. La décomposition d'une application en différentes tâches permet d'exploiter le parallélisme potentiel de cette application sans adapter le programme à la plate-forme de calcul visée. Le graphe décrit ces tâches ainsi que leurs dépendances, certaines tâches ne pouvant être exécutées avant que d'autres ne soient terminées. L'exécution d'une application est alors déterminée par un ordonnancement du graphe, calculé par un logiciel dédié, qui décrit entre autres quelles ressources sont allouées à chaque tâche et à quel moment. Les trois thèmes étudiés sont les suivants: exploiter le parallélisme intrinsèque des tâches, utiliser des accélérateurs tels que des GPU, et prendre en compte une mémoire limitée.Certaines applications présentent deux types de parallélisme que l'on peut exploiter: plusieurs tâches peuvent être exécutées simultanément, et chaque tâche peut être exécutée sur plusieurs processeurs afin de réduire son temps de calcul. Nous proposons et étudions deux modèles permettant de régir ce temps de calcul, afin d'exploiter ces deux types de parallélisme.Nous étudions ensuite comment utiliser efficacement des accélérateurs de calcul tels que des GPU, dans un contexte dynamique où les futures tâches à ordonnancer ne sont pas connues. La difficulté principale consiste à décider si une tâche doit être exécutée sur l'un des rares accélérateurs disponibles ou sur l'un des nombreux processeurs classiques. La dernière thématique abordée concerne le problème d'une mémoire principale limitée, et le recours à des transferts de données coûteux. Nous avons traité ce problème via deux scénarios. S'il est possible d'éviter de tels transferts, nous avons proposé de modifier le graphe afin de garantir que toute exécution ne dépasse pas la mémoire disponible, ce qui permet d'ordonnancemer les tâches dynamiquement au moment de l'exécution. Si tout ordonnancement nécessite des transferts, nous avons étudié le problème consistant à minimiser leur quantité.L'étude de ces trois thèmes a permis de mieux comprendre la complexité de ces problèmes. Les solutions proposées dans le cadre d'étude théorique pourront influencer de futures implémentations logicielles
This thesis deals with three main themes linked to task graph scheduling on modern computing platforms. A graph of tasks is a classical model of a program to be executed, for instance a scientific application. The decomposition of an application into several tasks allows to exploit the potential parallelism of this application without adaptating the program to the computing platform. The graph describes the tasks as well as their dependences, some tasks cannot be initiated before others are completed. The execution of an application is then determined by a schedule of the graph, computed by a dedicated software, which in particular describes which resources should be allocated to each task at which time. The three studied themes are the following: exploit inner task parallelism, use accelerators such as GPUs, and cope with a limited memory.For some applications, two types of parallelism can be exploited: several tasks can be executed concurrently, and each task may be executed on several processors, which reduces its processing time. We propose and study two models allowing to describe this processing time acceleration, in order to efficiently exploit both types of parallelism.We then study how to efficiently use accelerators such as GPUs, in a dynamic context in which the future tasks to schedule are unknown. The main difficulty consists in deciding whether a task should be executed on one of the rare available accelerators or on one of the many classical processors. The last theme covered in this thesis deals with a available main memory of limited size, and the resort to expensive data transfers. We focused on two scenarios. If it is possible to avoid such transfers, we propose to modify the graph in order to guarantee that any execution fits in memory, which allows to dynamically schedule the graph at runtime. If every schedule needs transfers, we studied how to minimize their quantity.The work on these three themes has led to a better understanding of the underlying complexities. The proposed theoretical solutions will influence future software implementations

L'objet de cette these est de creer un lien entre les techniques d'ordonnancement basees sur les graphes de taches acycliques a gros grain, et celles utilisees en parallelisation automatique. Dans une premiere partie une etude des techniques existantes est proposee. La seconde partie presente differents algorithmes de generation de code et de comptage d'iteration. Une methode permettant de generer des bornes de boucles efficaces est proposee. La troisieme partie presente un modele de calcul parallele, le graphe de taches parametre, qui est une representation independante de la taille du probleme, de graphes de taches acycliques frequemment utilises. Differentes techniques qui permettent d'automatiser la construction du graphe de taches parametre : partir d'un programme sequentiel a controle de flot statique annote par l'utilisateur sont ensuite proposees. Nous montrons comment des informations necessaires a l'ordonnancement peuvent etre derivees. Une annexe presente pluspyr, un outil d'aide au developpement d'applications paralleles integrant les differentes techniques exposees dans cette these

Ce travail de thèse de doctorat est dédié à l'étude d'un problème de placement de tâches dans le domaine de la compilation d'applications pour des architectures massivement parallèles. Ce problème vient en réponse à certains besoins industriels tels que l'économie d'énergie, la demande de performances pour les applications de type flots de données synchrones. Ce problème de placement doit être résolu dans le respect de trois critères: les algorithmes doivent être capable de traiter des applications de tailles variables, ils doivent répondre aux contraintes de capacités des processeurs et prendre en compte la topologie des architectures cibles. Dans cette thèse, les tâches sont organisées en réseaux de communication, modélisés sous forme de graphes. Pour évaluer la qualité des solutions produites par les algorithmes, les placements obtenus sont comparés avec un placement aléatoire. Cette comparaison sert de métrique d'évaluation des placements des différentes méthodes proposées. Afin de résoudre à ce problème, deux algorithmes de placement de réseaux de tâches de grande taille sur des architectures clusterisées de processeurs de type many-coeurs ont été développés. Ils s'appliquent dans des cas où les poids des tâches et des arêtes sont unitaires. Le premier algorithme, nommé Task-wise Placement, place les tâches une par une en se servant d'une notion d'affinité entre les tâches. Le second, intitulé Subgraph-wise Placement, rassemble les tâches en groupes puis place les groupes de tâches sur les processeurs en se servant d'une relation d'affinité entre les groupes et les tâches déjà affectées. Ces algorithmes ont été testés sur des graphes, représentants des applications, possédant des topologies de types grilles ou de réseaux de portes logiques. Les résultats des placements sont comparés avec un algorithme de placement, présent dans la littérature qui place des graphes de tailles modérée et ce à l'aide de la métrique définie précédemment. Les cas d'application des algorithmes de placement sont ensuite orientés vers des graphes dans lesquels les poids des tâches et des arêtes sont variables similairement aux valeurs qu'on peut retrouver dans des cas industriels. Une heuristique de construction progressive basée sur la théorie des jeux a été développée. Cet algorithme, nommé Regret Based Approach, place les tâches une par une. Le coût de placement de chaque tâche en fonction des autres tâches déjà placées est calculée. La phase de sélection de la tâche se base sur une notion de regret présente dans la théorie des jeux. La tâche qu'on regrettera le plus de ne pas avoir placée est déterminée et placée en priorité. Afin de vérifier la robustesse de l'algorithme, différents types de graphes de tâches (grilles, logic gate networks, series-parallèles, aléatoires, matrices creuses) de tailles variables ont été générés. Les poids des tâches et des arêtes ont été générés aléatoirement en utilisant une loi bimodale paramétrée de manière à obtenir des valeurs similaires à celles des applications industrielles. Les résultats de l'algorithme ont également été comparés avec l'algorithme Task-Wise Placement, qui a été spécialement adapté pour les valeurs non unitaires. Les résultats sont également évalués en utilisant la métrique de placement aléatoire
This Ph.D thesis is devoted to the study of the mapping problem related to massively parallel embedded architectures. This problem arises from industrial needs like energy savings, performance demands for synchronous dataflow applications. This problem has to be solved considering three criteria: heuristics should be able to deal with applications with various sizes, they must meet the constraints of capacities of processors and they have to take into account the target architecture topologies. In this thesis, tasks are organized in communication networks, modeled as graphs. In order to determine a way of evaluating the efficiency of the developed heuristics, mappings, obtained by the heuristics, are compared to a random mapping. This comparison is used as an evaluation metric throughout this thesis. The existence of this metric is motivated by the fact that no comparative heuristics can be found in the literature at the time of writing of this thesis. In order to address this problem, two heuristics are proposed. They are able to solve a dataflow process network mapping problem, where a network of communicating tasks is placed into a set of processors with limited resource capacities, while minimizing the overall communication bandwidth between processors. They are applied on task graphs where weights of tasks and edges are unitary set. The first heuristic, denoted as Task-wise Placement, places tasks one after another using a notion of task affinities. The second algorithm, named Subgraph-wise Placement, gathers tasks in small groups then place the different groups on processors using a notion of affinities between groups and processors. These algorithms are tested on tasks graphs with grid or logic gates network topologies. Obtained results are then compared to an algorithm present in the literature. This algorithm maps task graphs with moderated size on massively parallel architectures. In addition, the random based mapping metric is used in order to evaluate results of both heuristics. Then, in a will to address problems that can be found in industrial cases, application cases are widen to tasks graphs with tasks and edges weights values similar to those that can be found in the industry. A progressive construction heuristic named Regret Based Approach, based on game theory, is proposed. This heuristic maps tasks one after another. The costs of mapping tasks according to already mapped tasks are computed. The process of task selection is based on a notion of regret, present in game theory. The task with the highest value of regret for not placing it, is pointed out and is placed in priority. In order to check the strength of the algorithm, many types of task graphs (grids, logic gates networks, series-parallel, random, sparse matrices) with various size are generated. Tasks and edges weights are randomly chosen using a bimodal law parameterized in order to have similar values than industrial applications. Obtained results are compared to the Task Wise placement, especially adapted for non-unitary values. Moreover, results are evaluated using the metric defined above

Cette thèse traite du problème odits : ordonnancement distribué temps réel sérialisable. Son objectif est d'établir la faisabilité d'un jeu de tâches sporadiques distribuées soumises a des contraintes temps réel et partageant des objets modifiables persistants. Un jeu de tâches odits est dit faisable ssi il existe un ordonnancement satisfaisant les contraintes de cohérence des objets et les contraintes temps réel. Le problème est d'autant plus difficile que les tâches ont une structure en graphe. Cette thèse propose une approche générale de résolution du problème odits. Cette approche consiste, d'abord, a concevoir un ordonnancement en-ligne imposant une exécution sérialisable des tâches. Elle consiste, ensuite, a établir hors-ligne les conditions de faisabilité d'un jeu de tâches donné pour cet ordonnancement. Pour ce faire, cette thèse préconise une méthode novatrice basée sur (i) la caractérisation de l'ensemble des scénarios pires cas possibles et (ii) la modélisation de l'exécution de ces scénarios sous forme d'un graphe orienté value. Les temps de réponse pires cas sont obtenus par le calcul des plus longs chemins dans ce graphe. Les conditions de faisabilité en découlent. Deux solutions particulières sont dérivées de cette approche : l'une basée sur un ordonnancement périodique selon une séquence prédéfinie et l'autre basée sur un ordonnancement fifo. Pour chacune de ces solutions, les conditions de faisabilité nécessaires et suffisantes du jeu de tâches considéré sont établies. La complexité de ces conditions de faisabilité étant élevée, nous proposons des conditions de faisabilité de moindre complexité qui ne sont généralement que suffisantes. Cette thèse permet également d'aider le concepteur dans son choix du meilleur ordonnancement pour un jeu de tâches donné. Les résultats établis sont concrétisés par la réalisation de l'outil oodits qui se prononce sur la faisabilité d'un jeu de tâches pour les deux ordonnancements étudiés.

Les solutions proposées pour utiliser la puissance de calcul des ressources sous-utilisées ou inutilisées, concernent habituellement les applications multi-paramétrées. Les systèmes qui gèrent les dépendances entre les tâches le font généralement en interfaçant un système de calcul traditionnel. Il en résulte de nombreux et coûteux va-et-vient des résultats intermédiaires entre le client et les serveurs de calcul. A partir de ces constatations, nous avons spécifié la plate-forme HiPoP (Highly Distributed Platform of Computing) qui permet d'une part de proposer des applications spécifiques et d'autre part de les modéliser à l'aide de DAG. Nous avons également travaillé sur des caractéristiques fondamentales de la plate-forme telles que la tolérance aux fautes, que nous avons gérée en recourant aux duplicatas de tâches, et la sécurité des ressources des utilisateurs que nous confinons dans HDS (HiPoP Dynamic Sandbox). Un autre aspect sur lequel nous avons fortement mis l'accent est la facilité d'utilisation du système. En effet, bon nombre de systèmes offrent des fonctionnalités très intéressantes mais ne sont employés que par des utilisateurs avancés à cause de la complexité du système : installation du système et des dépendances logicielles, configuration, utilisation. Malgré une simplicité apparente de notre plate-forme dépourvue de matchmaker et d'ordonnanceur optimum, HiPoP a montré, comparativement à d'autres plates-formes gérant les dépendances entre les tâches, de très bonnes aptitudes à gérer les DAG comportant de nombreuses dépendances et ayant des tâches d'une durée pouvant aller de quelques secondes à une heure
A lot of resources are still under-used or unused for a long period of time whereas number of users needs computational power. The suggested solutions in order to use these resources usually concern multiparameter-applications where all users download and perform the same application on different data partitions. The systems which take in charge the dependences between tasks usually do it interfacing a traditional computing system. The outcome is some large and costly comings and goings of intermediary results between the client, servers and workers. From these observations, we have specified the HiPoP (Highly Distributed Platform of Computing) platform which, on the one hand, permits to submit its own specific applications and on the other hand to model them with DAG. We have also worked on fundamental characteristics of the platform such as fault tolerance that we managed resorting to task duplicates, and the users' resource security that we put in HDS (HiPoP Dynamic Sandbox). Another aspect we have strongly stressed is the system ease of use. Indeed, numbers of systems provide interesting functionalities but are only used by advanced users because of the system complexity: installation of the system and of its software dependences, configuration and utilization. Although our platform, which is devoid of matchmaker and of optimum scheduler, is very straightforward, HiPoP has shown, comparatively to other platforms managing dependences between tasks, some great aptitudes to manage DAG having a lot of dependences and having tasks from several seconds to one hour length

Depuis le milieu des années 1990, les bibliothèques de transmission de messages sont les technologies les plus utilisées pour développer des applications parallèles et distribuées. Des modèles de programmation basés sur des tâches peuvent être utilisés, par exemple, pour éviter les communications collectives sur toutes les ressources comme les réductions, les diffusions ou les rassemblements en les transformant en multiples opérations avec des tâches. Ensuite, ces opérations peuvent être planifiées par l'ordonnanceur pour placer les données et les calculs de manière à optimiser et réduire les communications de données.L'objectif principal de cette thèse est d'étudier ce que doit être la programmation basée sur des tâches pour des applications scientifiques et de proposer une spécification de cette programmation distribuée et parallèle, en expérimentant avec plusieurs représentations simplifiées d'applications scientifiques importantes pour TOTAL, et de méthodes linéaire classique dense et creuses. Au cours de la thèse, plusieurs langages de programmation et paradigmes sont étudiés. Des méthodes linéaires denses pour résoudre des systèmes linéaires, des séquences de produit matrice vecteur creux et la migration sismique en profondeur pré-empilement de Kirchhoff sont étudiées et implémentées en tant qu'applications basées sur des tâches.Une taxonomie, basée sur plusieurs de ces langages et paradigmes est proposée. Des logiciels ont été développés en utilisant ces modèles de programmation pour chaque application simplifiée. À la suite de ces recherches, une méthodologie pour la programmation de tâches parallèles est proposée, optimisant les mouvements de données en général et, en particulier, pour des applications scientifiques ciblées
Since the middle of the 1990s, message passing libraries are the most used technology to implement parallel and distributed applications. However, they may not be a solution efficient enough on exascale machines since scalability issues will appear due to the increase in computing resources. Task-based programming models can be used, for example, to avoid collective communications along all the resources like reductions, broadcast or gather by transforming them into multiple operations on tasks. Then, these operations can be scheduled by the scheduler to place the data and computations in a way that optimize and reduce the data communications. The main objective of this thesis is to study what must be task-based programming for scientific applications and to propose a specification of such distributed and parallel programming, by experimenting for several simplified representations of important scientific applications for TOTAL, and classical dense and sparse linear methods.During the dissertation, several programming languages and paradigms are studied. Dense linear methods to solve linear systems, sequences of sparse matrix vector product and the Kirchhoff seismic pre-stack depth migration are studied and implemented as task-based applications. A taxonomy, based on several of these languages and paradigms is proposed.Software were developed using these programming models for each simplified application. As a result of these researches, a methodology for parallel task programming is proposed, optimizing data movements, in general, and for targeted scientific applications, in particular

Le contexte général de ces travaux de recherche est celui des robots mobiles autonomes appelés à évoluer dans des environnements structurés et partiellement cartographiés en 2D. Ce document porte sur la synthèse de tâches sûres par prise en compte explicite des incertitudes de localisation, de contrôle, et de modélisation. La prise en compte de ces différentes incertitudes rend possible la génération de chemin sûrs, ayant de fortes chances d'être exécutés correctement. Afin de modéliser correctement les différentes incertitudes inhérentes au problème, il nous est apparu essentiel de mettre en avant les imbrications fortes existant entre planification et contrôle d'exécution. C'est pourquoi, au début du manuscrit, nous présentons une technique statistique d'estimation d'état classiquement utilisée en navigation : le filtre de Kalman étendu. Celui-ci sera utilisé dès la phase de planification, à partir de mesures simulées, afin d'estimer les incertitudes en configuration qui apparaitront lors de la navigation. A partir de ces incertitudes, nous indiquerons alors de quelle façon il est possible de calculer de manière formelle l'imprécision sur le contrôle. Cette dernière permet la définition d'un couloir au sein duquel le robot est assuré de rester lors de la navigation. Nous montrons alors de quelle manière des chemins sûrs peuvent être générés, à l'aide de l'imprécision sur le contrôle et d'un algorithme de parcours de graphe. L'imprécision sur le modèle de l'environnement est alors gérée de manière implicite par le planificateur à l'aide du concept de cartes locales. La méthode proposée, ainsi que les divers algorithmes développés, ont été validés en simulation ainsi que sur la plateforme mobile Robuter du laboratoire Heudiasyc.

L'objectif de cette thèse est de concevoir un système automatique constitué d'une ou plusieurs caméras capables de détecter en trois dimensions un amalgame d'objets stockés dans un conteneur. Pour ceci, il est nécessaire de modéliser, de reconnaître et de localiser des formes dans une image. Dans un premier temps, Nous proposons une solution d'optimisation du calibrage de caméras. C'est une tâche essentielle pour récupérer des informations quantitatives sur les images capturées. Cette méthode nécessite des compétences spécifiques en matière de traitement d'image, ce qui n'est pas toujours le cas dans l'industrie. Nous proposons d'automatiser et d'optimiser le système d'étalonnage en éliminant la sélection des images par l'opérateur. Ensuite, nous proposons d'améliorer les systèmes de détection d'objets fins et sans motif. Enfin, nous proposons d'adapter des algorithmes évolutionnaires dans le but d'optimiser les temps de recherche
The aim of this thesis is to design an automatic system involving one or several cameras capable of detecting in three dimensions a set of abjects placed in a bin. To do this, we must model, recognize and locate shapes in an image. First, we propose a solution to optimize the camera calibration system. This is an essential task for the retrieval of quantitative information about the captured images. However, the current methods require specific skills in image processing, which are not always available in industry. We propose to automate and optimize the calibration system by eliminating the selection of images by the operator. Second, we propose to improve the detection systems for thin and featureless abjects. Finally, we propose to adapt evolutionary algorithms to optimize search times

Cette thèse comprend deux parties. La première concerne les réseaux d'interconnexion et en particulier leur résistance aux pannes. Le premier chapitre traite d'extension de réseaux; on construit des réseaux de connexité et de degré maximum donnés en ajoutant des sommets p par p par p ceci avec un nombre minimum de remaillages. Dans le second chapitre on étudie la vulnérabilité des réseaux par bus ce qui nous conduit à étudier diverses notions de connexité dans les hypergraphes uniformes. La deuxième partie est consacrée à l'algorithme, distribuée et particulièrement à tout ce qui concerne les problèmes de messagerie (diffusion, routage). Le chapitre 3 traite de la diffusion d'information ou de requêtes dans un réseau distribué. On définit un nouvel algorithme : permettant de construire un arbre couvrant et on l'applique au problème de l'on mutuelle. Nous utilisons des méthodes de contrôle des transferts de connaissance ainsi que des techniques de synchronisation et de filtrage. Le chapitre 4 présente un «méta-algorithme» distribué basé sur la notion de phases. De plus on précise le rôle et l’importance de la topologie du réseau dans l'algorithmique distribuée. Dans ces deux derniers chapitres on détermine la complexité en nombre de messages et en temps des algorithmes. Enfin nous donnons en annexe un algorithme d'ordonnancement pour le calcul parallèle qui est optimal si le graphe de précédence des tâches est de type "2-steps' (élimination de Gauss dans une matrice dense)
This thesis contains two parts. Ln the first one we study interconnection networks and in particular their fault tolerance. The first chapter deals with the extensions of networks. We construct networks with given connectivity and maximum degree by adding the vertices p by p. In such a way that the minimum number possible of links is deleted. Ln chapter 2 we study the vulnerability of bus networks; this leads us to study various notions of connectivity in uniform hypergraphs. The second part concerns distributed algorithms, in particular problems of broadcasting and routing. Chapter 3 deals with the problem of broadcasting information or requests in a distributed net­ work. We give a new algorithm to construct a spanning tree and apply it to the problem of mutual exclusion. We use methods of control knowledge transfers and also synchronization and filtering methods. Ln chapter 4 we present a "meta-algorithm" based on the notion of phases. Furthermore we specify the use and the importance of the network topology in the distributed computing. Ln these two chapters we determine the complexity in number or messages and time of the proposed algorithms. Finally we give in the appendix a scheduling algorithm for parallel computing which is optimal for the 2-sceps precedence graph (Gaussian elimination in dense matrices)

La puissance de calcul des plus grands calculateurs ne fait qu'augmenter: de quelques centaines de cœurs de calculs dans les années 1990, on en est maintenant à plusieurs millions! Leur infrastructure évolue aussi: elle n'est plus linéaire, mais complètement hiérarchique. Les applications de calcul intensif, largement utilisées par la communauté scientifique, doivent donc se munir d'outils permettant d'utiliser pleinement l'ensemble de ces ressources de manière efficace. La simulation numérique repose bien souvent sur d'importants calculs dont le coût, en termes de temps et d'accès mémoire, peut fortement varier au cours du temps: on parle de charge de calcul variable. Dans cette Thèse, on se propose d'étudier les outils actuels de répartition des données et des calculs, afin de voir les raisons qui font que de tels outils ne sont pas pleinement adaptés aux fortes variations de charge ainsi qu'à la hiérarchie toujours plus importante des nouveaux calculateurs. Nous proposerons alors un nouveau modèle d'ordonnancement et de partitionnement, basé sur des interactions physiques, particulièrement adapté aux applications basées sur des maillages réguliers et présentant de fortes variations de charge au cours du temps. Nous validerons alors ce modèle en le comparant à des outils de partitionnement de graphes reconnus et largement utilisés, et verrons les raisons qui le rendent plus performant pour des applications aussi bien parallèles que distribuées. Enfin, nous proposerons une interface nous permettant d'utiliser cette méthode d'ordonnancement dans des calculateurs toujours plus hiérarchiques
Computing capability of largest computing centers is still increasing: from a few hundred of cores in the90's, they can now exceed several million of cores! Their infrastructure also evolves: it is no longerlinear, but fully hierarchical.High Performance applications, well used by the scientific community, require on tools that allow themto efficiently and fully use computing resources.Numerical simulations mostly rely on large computations chains for which the cost (computing load), either acomputing time or a memory access time, can strongly vary over time: it is referred to as dynamic computing loadevolution.In this thesis, we propose to study actual data partitioning and computing scheduling tools, and to explore theirlimitations with regards to strong and repetitive load variation as well as the still increasing cluster hierarchy.We will then propose a new scheduling and partitioning model, based on physical interactions, particularlysuitable to regular mesh based applications that produce strong computing load variations over time.We will then compare our model against well-known and widely used graph partitioning tools and we will see thereasons that make this model more reliable for such parallel and distributed applications.Lastly, we will propose a multi-level scheduling interface that is specially designed to allow to use ourmodel in even more hierarchical clusters