Search

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.; 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.; 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.

Scientific workflows are frequently modeled as Directed Acyclic Graphs (DAG) oftasks, which represent computational modules and their dependencies, in the form of dataproduced by a task and used by another one. This formulation allows the use of runtime sys-tems which dynamically allocate tasks onto the resources of increasingly complex and hetero-geneous computing platforms. However, for some workflows, such a dynamic schedule mayrun out of memory by exposing too much parallelism. This paper focuses on the problem oftransforming such a DAG to prevent memory shortage, and concentrates on shared memoryplatforms. We first propose a simple model of DAG which is expressive enough to emulate com-plex memory behaviors. We then exhibit a polynomial-time algorithm that computes the max-imum peak memory of a DAG, that is, the maximum memory needed by any parallel schedule.We consider the problem of reducing this maximum peak memory to make it smaller than agiven bound by adding new fictitious edges, while trying to minimize the critical path of thegraph. After proving this problem NP-complete, we provide an ILP solution as well as severalheuristic strategies that are thoroughly compared by simulation on synthetic DAGs modelingactual computational workflows. We show that on most instances, we are able to decrease themaximum peak memory at the cost of a small increase in the critical path, thus with little im-pact on quality of the final parallel schedule.; Les applications de calcul scientifique sont souvent modélisées pardes graphes de tâches orientés acycliques (DAG), qui représentent les tâchesde calcul et leurs dépendances, sous la forme de données produites par unetâche et utilisées par une autre. Cette formulation permet l’utilisation d’APIqui allouent dynamiquement les tâches sur les ressources de plateformes decalcul hétérogènes de plus en plus complexes. Cependant, pour certaines ap-plications, un tel ordonnancement dynamique peut manquer de mémoire enexploitant trop de parallélisme. Cet article porte sur le problème consistant àtransformer un tel DAG pour empêcher toute pénurie de mémoire, en se con-centrant sur les plateformes à mémoire partagée. On propose tout d’abord unmodèle simple de graphe qui est assez expressif pour émuler des comporte-ments mémoires complexes. On expose ensuite un algorithme polynomial quicalcule le pic mémoire maximum d’un DAG, qui représente la mémoire maxi-male requise par tout ordonnancement parallèle. On considère ensuite le prob-lème consistant à réduire ce pic mémoire maximal pour qu’il devienne plus pe-tit qu’une borne donnée en rajoutant des arêtes fictives, tout en essayant deminimiser le chemin critique du graphe. Après avoir prouvé ce problème NP-complet, on fournit un programme linéaire en nombres entiers le résolvant,ainsi que plusieurs stratégies heuristiques qui sont minitieusement comparées-sur des graphes synthétiques modélisant des applications de calcul réelles. Onmontre que sur la plupart des instances, on arrive à diminuer le pic mémoiremaximal, au prix d’une légère augmentation du chemin critique, et donc avecpeu d’impact sur la qualité de l’ordonnancement parallèle final.

Scientific workflows are frequently modeled as Directed Acyclic Graphs (DAG) oftasks, which represent computational modules and their dependencies, in the form of dataproduced by a task and used by another one. This formulation allows the use of runtime sys-tems which dynamically allocate tasks onto the resources of increasingly complex and hetero-geneous computing platforms. However, for some workflows, such a dynamic schedule mayrun out of memory by exposing too much parallelism. This paper focuses on the problem oftransforming such a DAG to prevent memory shortage, and concentrates on shared memoryplatforms. We first propose a simple model of DAG which is expressive enough to emulate com-plex memory behaviors. We then exhibit a polynomial-time algorithm that computes the max-imum peak memory of a DAG, that is, the maximum memory needed by any parallel schedule.We consider the problem of reducing this maximum peak memory to make it smaller than agiven bound by adding new fictitious edges, while trying to minimize the critical path of thegraph. After proving this problem NP-complete, we provide an ILP solution as well as severalheuristic strategies that are thoroughly compared by simulation on synthetic DAGs modelingactual computational workflows. We show that on most instances, we are able to decrease themaximum peak memory at the cost of a small increase in the critical path, thus with little im-pact on quality of the final parallel schedule.; Les applications de calcul scientifique sont souvent modélisées pardes graphes de tâches orientés acycliques (DAG), qui représentent les tâchesde calcul et leurs dépendances, sous la forme de données produites par unetâche et utilisées par une autre. Cette formulation permet l’utilisation d’APIqui allouent dynamiquement les tâches sur les ressources de plateformes decalcul hétérogènes de plus en plus complexes. Cependant, pour certaines ap-plications, un tel ordonnancement dynamique peut manquer de mémoire enexploitant trop de parallélisme. Cet article porte sur le problème consistant àtransformer un tel DAG pour empêcher toute pénurie de mémoire, en se con-centrant sur les plateformes à mémoire partagée. On propose tout d’abord unmodèle simple de graphe qui est assez expressif pour émuler des comporte-ments mémoires complexes. On expose ensuite un algorithme polynomial quicalcule le pic mémoire maximum d’un DAG, qui représente la mémoire maxi-male requise par tout ordonnancement parallèle. On considère ensuite le prob-lème consistant à réduire ce pic mémoire maximal pour qu’il devienne plus pe-tit qu’une borne donnée en rajoutant des arêtes fictives, tout en essayant deminimiser le chemin critique du graphe. Après avoir prouvé ce problème NP-complet, on fournit un programme linéaire en nombres entiers le résolvant,ainsi que plusieurs stratégies heuristiques qui sont minitieusement comparées-sur des graphes synthétiques modélisant des applications de calcul réelles. Onmontre que sur la plupart des instances, on arrive à diminuer le pic mémoiremaximal, au prix d’une légère augmentation du chemin critique, et donc avecpeu d’impact sur la qualité de l’ordonnancement parallèle final.

We are interested to an optimization problem on graphs (the Vertex Cover) in a very specific context: the huge instances of data. We defined a treatment model based on constraints linked to the limited amount of memory, model for which properties comes from several existing models in the litterature (online, streaming...). We studied several algorithms suitable to this model: we analyzed, first theoretically, the quality of their solutions and their complexities (in worst and average case). We then conducted an experimental study on very large graphs., Nous nous sommes intéressés à un problème d'optimisation sur des graphes (le Vertex Cover) dans un contexte de traitement bien particulier : celui des grandes instances de données. Nous avons défini pour cela un modèle de traitement basé sur des contraintes liées principalement à la quantité de mémoire limitée, modèle qui reprenait des propriétés issues de plusieurs modèles existants dans la littérature (online, streaming...). Nous avons étudié plusieurs algorithmes adaptés à ce modèle : nous avons analysé, tout d'abord de façon théorique, la qualité de leurs solutions ainsi que leurs complexités (en pire cas et en moyenne). Nous avons ensuite mené une étude expérimentale sur de très gros graphes.

We are interested to an optimization problem on graphs (the Vertex Cover) in a very specific context: the huge instances of data. We defined a treatment model based on constraints linked to the limited amount of memory, model for which properties comes from several existing models in the litterature (online, streaming...). We studied several algorithms suitable to this model: we analyzed, first theoretically, the quality of their solutions and their complexities (in worst and average case). We then conducted an experimental study on very large graphs.; Nous nous sommes intéressés à un problème d'optimisation sur des graphes (le Vertex Cover) dans un contexte de traitement bien particulier : celui des grandes instances de données. Nous avons défini pour cela un modèle de traitement basé sur des contraintes liées principalement à la quantité de mémoire limitée, modèle qui reprenait des propriétés issues de plusieurs modèles existants dans la littérature (online, streaming...). Nous avons étudié plusieurs algorithmes adaptés à ce modèle : nous avons analysé, tout d'abord de façon théorique, la qualité de leurs solutions ainsi que leurs complexités (en pire cas et en moyenne). Nous avons ensuite mené une étude expérimentale sur de très gros graphes.