Search

Scheduling n independent tasks onto m identical processors in order to minimize the makespan has been widely studied. As an alternative to classical heuristics, the SLACK algorithm groups tasks by packs of m tasks of similar execution times, and schedules first the packs with the largest differences. It turns out to be very performant in practice, but only few studies have been conducted on its theoretical properties. We derive novel analytical results for SLACK, and in particular, we study the performance of this algorithm from an asymptotical point of view, under the assumption that the execution times of the tasks follow a given probability distribution. The study is building on a comparison of the most heavily loaded machine compared to the least loaded one. Furthermore, we extend the results when the objective is to minimize the energy consumption rather than the makespan, since reducing the energy consumption of the computing centers is an ever-growing concern for economical and ecological reasons. Finally, we perform extensive simulations to empirically assess the performance of the algorithms with both synthetic and realistic execution time distributions.; Ordonnancer n tâches indépendantes sur m processeurs identiques afin de minimiser le temps total d’exécution est un problème qui a été largement étudié. Comme alternative aux heuristiques classiques, l’algorithme SLACK groupe les tâches en paquets de m tâches avec un temps similaire, et ordonnance d’abord les paquets avec les plus grandes différences de temps. Cette approche est très efficace en pratique, mais peu d'études se sont intéressées à son étude théorique. Nous proposons de nouveaux résultats analytiques pour SLACK. En particulier, nous étudions la performance de l’algorithme d’un point de vue asymptotique, en supposant que le temps d’exécution des tâches suit une distribution de probabilités connue. L’étude se base sur une comparaison entre le processeur le plus chargé et celui qui l’est le moins. De plus, nous étendons ces résultats à une fonction objective différente: la minimisation de la consommation énergétique. En effet, réduire la consommation énergétique descentres de calcul est un des défis majeurs actuels, à la fois d’un point de vue économique, mais aussi et surtout écologique. Finalement, nous effectuons de nombreuses simulations pour étudier de façon empirique la performance des algorithmes, avec des distributions de temps d’exécution synthétiques d’une part, et réalistes d’autre part.

Scientific applications are commonly modeled as the processing of directed acyclicgraphs of tasks, and for some of them, the graph takes the special form of a rooted tree. Thistree expresses both the computational dependencies between tasks and their storage requirements.The problem of scheduling/traversing such a tree on a single processor to minimize its memoryfootprint has already been widely studied. Hence, we move to parallel processing and study howto partition the tree for a homogeneous multiprocessor platform, where each processor is equippedwith its own memory. We formally state the problem of partitioning the tree into subtrees suchthat each subtree can be processed on a single processor and the total resulting processing time isminimized. We prove that the problem is NP-complete, and we design polynomial-time heuristicsto address it. An extensive set of simulations demonstrates the usefulness of these heuristics.; Les applications scientifiques sont couramment modélisées par des graphes de tâches. Pour certaines d'entre elles, le graphe prend la forme particulière d'un arbre enraciné". Cet arbre détermine à la fois les dépendance entre tâches de calcul et les besoins en stockage. Le problème d'ordonnancer (ou parcourir) un tel arbre sur un seul processeur pour réduire son empreinte mémoire a déjà largement été étudié. Dans ce rapport, nous considérons le traitement parallèle d'un tel arbre et étudions comment le partitionner pour une plate-forme decalcul formée de processeurs homogènes disposant chacun de sa propre mémoire.Nous formalisons le problème du partitionnement de l'arbre en sous-arbres de telle sorte que chaque sous-arbre puisse être traité sur un seul processeur et que le temps de calcul total soit minimal. Nous montrons que ce problème est NP-complet et proposons des heuristiques polynomiales. Un ensemble exhaustif,de simulations permet de montrer l'utilité de ces heuristiques.

This work presents a realistic performance model to execute scientific workflows on high-bandwidth memory architectures such as the Intel Knights Landing. We provide a detailed analysis of the execution time on such platforms, taking into account transfers from both fast and slow memory and their overlap with computations. We discussseveral scheduling and mapping strategies: not only tasks must be assigned to computing resources, but also one has to decide which fraction of input and output data will reside in fast memory, and which will have to stay in slow memory. Extensive simulations allow us to assess the impact of the mapping strategies on performance. We also conduct actualexperiments for a simple 1D Gauss-Seidel kernel, which assess the accuracy of the model and further demonstrate the importance of a tuned memory management. Altogether, our model and results lay the foundations for further studies and experiments on dual-memory systems.; Ce travail présente un modèle de performance réaliste pour exécuter des workflows scientifiques sur des architectures ayant des mémoires à bande passante élevée, comme par exemple Intel Knights Landing. Nous fournissons une analyse détaillée du temps d'exécution sur ces plates-formes, en tenant compte des transferts depuis deux mémoires (rapide et lente), et leur recouvrement avec les calculs. Nous introduisons plusieurs stratégiesd'ordonnancement et de placement mémoire: non seulement les tâches doivent être assignées aux ressources de calcul, mais il faut aussi décider quelle fraction des données d'entrée et de sortie va résider en mémoire rapide, alorsque le reste sera en mémoire lente. Des simulations approfondies nous permettentd'évaluer l'impact des stratégies de placement sur la performance. Nous menons également des expériences réelles pour un noyau de Gauss-Seidel 1D simple, afin d'évaluer la précision du modèle. Nous démontrons ainsi l'importance d'une gestion fine de la mémoire sur les systèmes avec double mémoire.

Multi-Processor System-on-Chip (MPSoC) has emerged as a promising embedded architecture to meet the increasing performance demand of embedded applications. However, due to limited energy budget, it is hard to guarantee that applications on MPSoC can be accomplished on time with a required throughput. The situation becomes even worse for applications with high reliability requirements, since extra energy will be inevitably consumed by task re-executions or duplicated tasks. Based on Dynamic Voltage and Frequency Scaling (DVFS) and task duplication techniques, this paper presents a novel energy-efficient scheduling model, which aims at minimizing the overall energy consumption of MPSoC applications under both throughput and reliability constraints. The problem is shown to be NP-complete, and several polynomial-time heuristics are proposed to tackle this problem. Comprehensive simulations on both synthetic and real application graphs show that our proposed heuristics can meet all the given constraints, while reducing the energy consumption.; Le système multiprocesseur sur puce (MPSoC) est une architecture prometteuse pour répondre à la demande de performance croissante des applications embarquées. Cependant, en raison de leur budget énergétique limité, il est difficile de garantir que les applications sur MPSoC peuvent être accomplies à temps avec un débit requis. La situation devient encore pire pour les applications présentant des exigences de fiabilité élevées, car une énergie supplémentaire sera inévitablement consommée par des ré-exécutions de tâches ou des tâches dupliquées. Basé sur le DVFS (Dynamic Voltage and Frequency Scaling) et la duplication de tâches, cet article présente un nouveau modèle d'ordonnancement, qui vise à minimiser la consommation d'énergie globale des applications MPSoC sous des contraintes de débit et de fiabilité. Le problème est montré NP-complet, et plusieurs heuristiques en temps polynomial sont proposées pour résoudre ce problème. Des simulations complètes sur des graphes d'application tant synthétiques que réels montrentque nos heuristiques peuvent répondre à toutes les contraintes données, tout en réduisant la consommation d'énergie.

In this paper, we consider the problem of scheduling an application on a parallel computational platform. The application is a particular task graph, either a linear chain of tasks, or a set of independent tasks. The platform is made of identical processors, whose speed can be dynamically modified. It is also subject to failures: if a processor is slowed down to decrease the energy consumption, it has a higher chance to fail. Therefore, the scheduling problem requires to re-execute or replicate tasks (i.e., execute twice a same task, either on the same processor, or on two distinct processors), in order to increase the reliability. It is a tri-criteria problem: the goal is to minimize the energy consumption, while enforcing a bound on the total execution time (the makespan), and a constraint on the reliability of each task. Our main contribution is to propose approximation algorithms for these particular classes of task graphs. For linear chains, we design a fully polynomial time approximation scheme. However, we show that there exists no constant factor approximation algorithm for independent tasks, unless P=NP, and we are able in this case to propose an approximation algorithm with a relaxation on the makespan constraint.; Dans ce papier, nous considérons le problème d'ordonnancement d'une application sur une plateforme parallèle de calcul. L'application est un graphe de tâches particulier: soit une chaîne de tâche, soit un ensemble de tâches indépendantes. La plateforme est constituée de processeurs identiques, dont la vitesse peut être modifiée dynamiquement. Cette plateforme est aussi sujette à des fautes: lorsque l'on réduit la vitesse d'exécution d'un processeur pour diminuer la consommation d'énergie, ce processeur a une plus grande chance de faillir. C'est pourquoi, pour augmenter la fiabilité du processus, l'ordonnanceur va devoir choisir de re-exécuter ou répliquer certaines tâches (les exécuter deux fois, soit sur le même processeur, soit sur deux processeurs distincts). Le problème est donc tri-critère: nous cherchons à minimiser la consommation d'énergie, tout en préservant une limite sur le temps d'exécution, ainsi qu'une borne sur la fiabilité de chaque tâche. Nos contributions résident en l'écriture d'algorithmes d'approximation efficaces pour les deux classes de graphes étudiées. Dans le cas des chaînes linéaires, nous proposons un schéma d'approximation entièrement polynomial (FPTAS). Puis nous prouvons qu'il n'existe pas d'algorithmes d'approximation à facteur constant dans le cas des tâches indépendantes, sauf si P=NP, mais nous sommes cependant capable d'exhiber un algorithme d'approximation lorsque l'on autorise une relaxation de la contrainte sur le temps d'exécution.

This paper investigates co-scheduling algorithms for processing a set of parallel applications. Instead of executing each application one by one, using a maximum degree of parallelism for each of them, we aim at scheduling several applications concurrently. We partition the original application set into a series of packs, which are executed one by one. A pack comprises several applications, each of them with an assigned number of processors, with the constraint that the total number of processors assigned within a pack does not exceed the maximum number of available processors. The objective is to determine a partition into packs, and an assignment of processors to applications, that minimize the sum of the execution times of the packs. We thoroughly study the complexity of this optimization problem, and propose several heuristics that exhibit very good performance on a variety of workloads, whose application execution times model profiles of parallel scientific codes. We show that co-scheduling leads to to faster workload completion time and to faster response times on average (hence increasing system throughput and saving energy), for significant benefits over traditional scheduling from both the user and system perspectives.; Nous étudions des algorithmes d'ordonnancement par lots pour un ensemble de tâches parallélisables. Plutôt que d'ordonnancer les tâches séquentiellement en utilisant le degré maximum de parallélisme pour chacune d'entre elles, nous cherchons à ordonnancer plusieurs tâches de manière concurrente. L'idée est de partitionner l'ensemble des tâches en une série de lots, qui seront exécutés les uns après les autres. Un lot est composé de plusieurs tâches, et un certain nombre de processeurs est alloué à chacune de ces tâches, sous la contrainte que le nombre total de processeurs alloués à un lot ne dépasse pas le nombre maximum de processeurs disponibles. L'objectif est de trouver une partition de l'ensemble des tâches en lots, et une allocation de processeurs optimale pour la minimisation de la somme des temps d'exécution de chaque lot. Nous étudions la complexité de ce problème d'optimisation, et proposons plusieurs heuristiques qui obtiennent d'excellentes performances sur plusieurs ensembles de tâches représentatifs des calculs parallèles scientifiques. Notre technique d'ordon\-nancement par lots permet non seulement d'obtenir un gain sur le temps d'exécution total, mais obtient également d'excellents résultats pour le temps de réponse moyen.

We consider a task graph to be executed on a set of processors. We assume that the mapping is given, say by an ordered list of tasks to execute on each processor, and we aim at optimizing the energy consumption while enforcing a prescribed bound on the execution time. While it is not possible to change the allocation of a task, it is possible to change its speed. Rather than using a local approach such as backfilling, we consider the problem as a whole and study the impact of several speed variation models on its complexity. For continuous speeds, we give a closed-form formula for trees and series-parallel graphs, and we cast the problem into a geometric programming problem for general directed acyclic graphs. We show that the classical dynamic voltage and frequency scaling (DVFS) model with discrete modes leads to a NP-complete problem, even if the modes are regularly distributed (an important particular case in practice, which we analyze as the incremental model). On the contrary, the VDD-hopping model leads to a polynomial solution. Finally, we provide an approximation algorithm for the incremental model, which we extend for the general DVFS model.

One has a large workload that is "divisible''---its constituent work's granularity can be adjusted arbitrarily---and one has access to $p$ remote computers that can assist in computing the workload. How can one best utilize these computers? Complicating this question is the fact that each remote computer is subject to interruptions (of known likelihood) that kill all work in progress on it. One wishes to orchestrate sharing the workload with the remote computers in a way that maximizes the expected amount of work completed. Strategies are presented for achieving this goal, by balancing the desire to checkpoint often---thereby decreasing the amount of vulnerable work at any point---vs.~the desire to avoid the context-switching required to checkpoint. The current study demonstrates the accessibility of strategies that provably maximize the expected amount of work when there is only one remote computer (the case p=1) and, at least in an asymptotic sense, when there are two remote computers (the case p=2); but the study strongly suggests the intractability of exact maximization for p >= 2 computers. This study responds to that challenge by developing efficient heuristics that employ both checkpointing and work replication as mechanisms for decreasing the impact of work-killing interruptions. The quality of these heuristics, in expected amount of work completed, is assessed through exhaustive simulations that use both idealized models and actual trace data.

In this document, I explore the problem of scheduling pipelined applications onto large-scale distributed platforms, in order to optimize several criteria. A particular attention is given to throughput maximization (i.e., the number of data sets that can be processed every time unit), latency minimization (i.e., the time required to process one data set entirely), and failure probability minimization. First, I accurately define the models and the scheduling problems, and exhibit surprising results, such as the difficulty to compute the optimal throughput and/or latency that can be obtained given a mapping. In particular, I detail the importance of the communication models, which induce quite different levels of difficulty. Second, I give an overview of complexity results for various cases, both for mono-criterion and for bi-criteria optimization problems. I illustrate the impact of the models on the problem complexity. Finally, I show some extensions of this work to different applicative contexts and to dynamic platforms.

In this paper, we explore the problem of mapping filtering web services on large-scale heterogeneous platforms. Two important optimization criteria should be considered in such a framework. The period, which is the inverse of the throughput, measuresthe rate at which data sets can enter the system. The latency measures the responsetime of the system in order to process one single data set entirely. Both criteria areantagonistic. For homogeneous platforms, the complexity of period minimization isalready known [14]; we derive an algorithm to solve the latency minimization problem,and we provide a bi-criteria algorithm which minimizes latency without exceeding aprescribed value for the period. However, when adding heterogeneity to the platform,we prove that minimizing the period or the latency becomes NP-hard. We provide aninteger linear program to solve both problems in the heterogeneous case.For period minimization on heterogeneous platforms, we design some efficient polynomial time heuristics and we assess their relative and absolute performance througha set of experiments. For small problem instances, the results are very close to theoptimal solution returned by the integer linear program.