Search

We gathered the research community focused on compute scheduling in the new age of renewable power generation -- where variation in weather and solar radiation drives renewable generation, and thereby the carbon-intensity of power, and efforts to reduce environmental damage then create variation in compute capacity (opportunity). In this age, effective utilization of that opportunity is the key to sustainable computing. We report important findings on the attributes of future platforms, characterizing the power grid variation, reliability challenges, and two-way relationships between datacenters and grid that are emerging. Workloads are changing as well, with growing understanding of how computing can be malleable, delay flexible, or even acceptably approximate. Between these, we focus on how scheduling can meet these challenges, managing between flexible workloads and dynamically varying platforms – performing to new metrics that reflect both performance and non-performance attributes (e.g. carbon emissions). The concerns that underlie a shift to variable capacity derive from a broader societal concern about the sustainability of computing, and our last section addresses critical challenges in awareness, responsibilities, and action.The talks and position papers from attendees are available at https://people.cs.uchicago.edu/~aachien/workshops/varsched23/.

This work revisits I/O bandwidth-sharing strategies for HPC applications. When several applications postconcurrent I/O operations, well-known approaches include serializing these operations (First-Come First-Served) or fair-sharing the bandwidth across them (FairShare). Another recent approach, I/O-Sets, assigns priorities to the applications, which are classified into different sets based upon the average length of their iterations. We introduce several new bandwidth-sharing strategies, some of them simple greedy algorithms, and some of them more complicated to implement, and we compare them with existing ones. Our new strategies do not rely on any a-priori knowledge of the behavior of the applications, such as the length of work phases, the volume of I/O operations, or some expected periodicity. We introduce a rigorous framework, namely steady-state windows, which enables to derive bounds on the competitive ratio of all bandwidth-sharing strategies for three different objectives: minimum yield, platform utilization, and global efficiency. To the best of our knowledge, this work is the first to provide a quantitative assessment of the online competitiveness of any bandwidth-sharing strategy. This theory-oriented assessment is complemented by a comprehensive set of simulations, based upon both synthetic and realistic traces. The main conclusion is that two of our simple and low-complexity greedy strategies significantly outperform First-Come First-Served, FairShare and I/O-Sets, and we recommend that the I/O community implements them for further assessment.; Ce travail revisite les stratégies de partage de la bande passante d’entrée-sortie entre applications de calcul haute performance. Quand plusieurs applications postent simultanément des opérations d’entrée-sortie, les approches classiques incluent la sérialisation de ces opérations (FCFS) et le partage équitable de la bande passante (FairShare). Une approche récente, I/O-Sets, attribue des priorités aux applications, qui sont classées en différents ensembles basés sur la longueur moyenne de leurs itérations.Nous introduisons plusieurs stratégies nouvelles de partage de la bande passante, de simples heuristiques gloutonnes et des stratégies plus compliquées à implémenter, et nous les comparons aux solutions préexistantes. Nos stratégies n’utilisent aucune connaissance a priori du comportement des applications, telle que la longueur des phases de calcul, le volume des entrées-sorties, ou leur périodicité.Nous introduisons un cadre rigoureux, les fenêtres de régime permanent, qui permet de définir des bornes sur le facteur de compétitivité de toutes les stratégies de partage de la bande passante, et ce pour trois objectifs: le yield (rendement) minimal, l’utilisation de la plateforme, et l’efficacité globale. À notre connaissance, ce travail est le premier à proposer une évaluation quantitative du facteur de compétitivité de stratégies de partage de la bande passante. Cette évaluation théorique est complétée par un ensemble de simulations, utilisant des traces synthétiques et d’autres réalistes. La principale conclusion de ces simulations est que deux de nos simples heuristiques gloutonnes de faible complexité obtiennent de bien meilleures performances que FCFS, FairShare et I/O-Sets. Nous recommandons donc que la communauté les implémente afin de permettre leur évaluation en pratique.

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; The problem of scheduling moldable tasks has been widely studied, in particular when tasks have dependencies (i.e., task graphs), or when tasks are released on-the-fly (i.e., online). However, few study has focused on both (i.e., online scheduling of moldable task graphs). In this paper, we derive constant competitive ratios for this problem under several common yet realistic speedup models for the tasks (roofline, communication, Amdahl, and a combination of them). We also provide the first lower bound on the competitive ratio of any deterministic online algorithm for arbitrary speedup model, which is not constant but depends on the number of tasks in the longest path of the graph.

Directed acyclic graphs are commonly used to model scientific workflows, by expressing dependencies between tasks, as well as the resource requirements of the workflow. As a special case, rooted directed trees occur in several applications, for instance in sparse matrix computations. Since typical workflows are modeled by huge trees, it is crucial to schedule them efficiently, so that their execution time (or makespan) is minimized. Furthermore, it might be beneficial to distribute the execution on several compute nodes, hence increasing the available memory, and allowing us to parallelize parts of the execution. To exploit the heterogeneity of modern clusters in this context, we investigate the partitioning and mapping of tree-shaped workflows on target architectures where each processor can have a different memory size. Our three-step heuristic adapts and extends previous work for homogeneous clusters [Gou et al., TPDS 2020]. The changes we propose concern the assignment to processors (which considers the different memory sizes) and the availability of suitable processors when splitting or merging subtrees. We evaluate our approach with extensive simulations and demonstrate that exploiting the heterogeneity in the cluster reduces the makespan significantly compared to the state of the art for homogeneous memory.

International audience; The Young/Daly formula provides an approximation of the optimal checkpoint period for a parallel application executing on a supercomputing platform. The Young/Daly formula was originally designed for preemptible tightly-coupled applications. We provide some background and survey various application scenarios to assess the usefulness and limitations of the formula.

Les enjeux des 26èmes journées du longitudinal (JDL) étaient d’examiner les formes de la sélection, ainsi que leurs évolutions et leurs articulations, d’interroger l’expérience de celles et de ceux qui sont sélectionnés et de celles et de ceux qui sélectionnent et de distinguer les ressemblances et les dissemblances entre les deux univers scolaire et professionnel. L’approche longitudinale requise pour ces journées a permis d’analyser les sélections successives au fil des parcours, dans le système éducatif puis vers et sur le marché du travail, ceci notamment en examinant les déterminants qui conduisent à accéder ou non à telle ou telle position dans le système éducatif (niveau, filière, spécialité, etc.) ou sur le marché du travail (qualification, secteur, etc.). À cette fin, les contributions se sont appuyées sur des méthodes quantitatives, via des enquêtes nationales ou locales, ou qualitatives, par des entretiens biographiques et/ou des interrogations répétées. Ces journées ont été organisées par le centre associé au Céreq de Toulouse du Laboratoire CERTOP (UMR-CNRS et Université Jean-Jaurès), avec la participation des laboratoires EFTS (UMR Université Jean-Jaurès et ENSFEA) et LPS-DT (EA Université Jean-Jaurès). Elles se sont déroulées en visioconférences, les 12 et 13 novembre 2020, et ont bénéficié du soutien financier de l’Université Jean-Jaurès Toulouse 2, de l’Institut national de la jeunesse et de l’éducation populaire (INJEP), du Céreq et des trois laboratoires organisateurs. Depuis plus de 20 ans, les JDL sont organisées par le Céreq ou un de ses centres régionaux associés. Elles regroupent une centaine de chercheur·e·s autour d’une thématique inscrite dans une approche longitudinale de l’analyse de la relation formation-emploi. Les actes des rencontres sont édités tous les ans par le Céreq.