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.

International audience; Scheduling independent tasks on a parallel platform is a widely-studied problem, in particular when the goal is to minimize the total execution time, or makespan (P||C_max problem in Graham's notations). Also, many applications do not consist of sequential tasks, but rather of parallel moldable tasks that can decide their degree of parallelism at execution (i.e., on how many processors they are executed). Furthermore, since the energy consumption of data centers is a growing concern, both from an environmental and economical point of view, minimizing the energy consumption of a schedule is a main challenge to be addressed. One should decide, for each task, on how many processors it is executed, and at which speed the processors are operated, with the goal to minimize the total energy consumption. We further focus on co-schedules, where tasks are partitioned into shelves, and we prove that the problem of minimizing the energy consumption remains NP-complete when static energy is consumed during the whole duration of the application. We are however able to provide an optimal algorithm for the schedule within one shelf, i.e., for a set of tasks that start at the same time. Several approximation results are derived, and simulations are performed to show the performance of the proposed algorithms.; L’ordonnancement de tâches indépendantes sur une plateforme parallèle est un problème vastement étudié, en particulier lorsque le but est de minimiser le temps d’exécution total, ou makespan (P||C_max en utilisant la notation de Graham). De nombreuses applications ne sont pas séquentielles, et sont plutôt des tâches parallélisables moldables, dont le degré de parallélisation peut être choisi à l’exécution (i.e., sur combien de processeurs elles sont exécutées). De plus, étant donné que la consommation énergétique des centres de données devient un sujet de plus en plus important, que ce soit d’un point de vue environnemental ou économique, la minimisation de la consommation d’énergie est un défi majeur à relever. La décision algorithmique à prendre concerne, pour l’exécution de chaque tâche, le nombre de processeurs ainsi que la vitesse des dits processeurs, dans le but de minimiser la consommation totale d’énergie. Nous nous intéressons plus précisément aux co-ordonnancements, dans lesquels les tâches sont partitionnées en étagères, et nous prouvons que la minimisation de la consommation d’énergie est un problème NP-complet lorsque l’énergie statique est consommée pendant la totalité de l’exécution de l’application. Nous fournissons tout de même un algorithme optimal dans le cas d’un ordonnancement sur une seule étagère, i.e., pour un ensemble de tâches commençant simultanément. Plusieurs résultats d’approximation sont prouvés, et des simulations sont effectuées pour exhiber la performance des algorithmes proposés