With the increasing scale of High-Performance Computing (HPC) systems and a new awareness of the environmental impact of HPC, new strategies are required to improve the efficiency of resource usage on these systems. One such strategy is Dynamic Resource Management (DRM), which allows changing the resources assigned to a job dynamically during its execution. This increased flexibility in resource allocation and job scheduling can lead to improvements in several system efficiency metrics. Despite these benefits, DRM has not yet been established as a ready-to-use technology for production HPC systems. This is caused by the significant changes required in all the layers of the HPC system software stack, which are only achievable with an extensive and holistic co-design process between resource management software and applications. In this work, we demonstrate the applicability of a recently introduced, generic design approach for dynamic resources called Dynamic Processes with PSets (DPP), to enable DRM in realworld systems. To this end, we developed an exemplary, dynamic system software stack implementation following the DPP design principles throughout all layers. Based on this, we assess the applicability and performance of our approach using both synthetic benchmarks and job mixes consisting of several dynamic, real-world applications. On up to$\mathbf{1 0 0}$nodes, we measure moderate overheads for process reconfiguration in applications while significantly improving the system throughput and average job turnaround time compared to static scheduling in crowded system scenarios.

Scheduling task graphs with communication delay is a widely studied NP-hard problem. Many heuristics have been proposed, but there is no constant approximation algorithm for this classic model. In this paper, we focus on the scheduling of the important class of fork-join task graphs (describing many types of common computations) on homogeneous processors. For this sub-case, we propose a guaranteed algorithm with a $\left( {1 + \frac{m}{{m - 1}}} \right)$-approximation factor, where m is the number of processors. The algorithm is not only the first constant approximation for an important sub-domain of the classic scheduling problem, it is also a practical algorithm that can obtain shorter makespans than known heuristics. To demonstrate this, we propose adaptations of known scheduling heuristic for the specific fork-join structure. In an extensive evaluation, we then implemented these algorithms and scheduled many fork-join graphs with up to thousands of tasks and various computation time distributions on up to hundreds of processors. Comparing the obtained results demonstrates the competitive nature of the proposed approximation algorithm.

Energy consumption has become one of the mostcritical issues in the evolution of High Performance Computingsystems (HPC). Controlling the energy consumption of HPCplatforms is not only a way to control the cost but also a stepforward on the road towards exaflops. Powercapping is a widelystudied technique that guarantees that the platform will notexceed a certain power threshold instantaneously but it givesno flexibility to adapt job scheduling to a longer term energybudget control. We propose a job scheduling mechanism that extends thebackfilling algorithm to become energy-aware. Simultaneously, we adapt resource management with a node shutdown technique to minimize energy consumption whenever needed. Thiscombination enables an efficient energy consumption budgetcontrol on a cluster during a period of time. The technique isexperimented, validated and compared with various alternativesthrough extensive simulations. Experimentation results show highsystem utilization and limited bounded slowdown along withinteresting outcomes in energy efficiency while respecting anenergy budget during a particular time period.

The goal of this paper is to study how limited cooperation can impact the quality of the schedule obtained by multiple independent organizations in a typical grid computing platform. This relaxed version of the problem known as the Multi-Organization Scheduling Problem (MOSP) models an environment where organizations providing both resources and jobs tolerate a bounded degradation on the make span of their own jobs in order to minimize the make span over the entire platform. More precisely, the technical contributions are the following. First, we improve the existing in approximation bounds for this problem proving that what was previously though as not polynomially approximable ({\it unless $P=NP$}) is actually not approximable at all. We achieve this using two families of instances whose Pareto optimal solutions are on par with the previous in aproximability bounds. Then, we present two algorithms that solve the problem with approximation ratios of (2, 3/2) and (3, 4/3) respectively. This means that when using the first (second) algorithm, if an organization tolerates that the completion time of its last job cannot exceed twice (three times) the time it would have obtained by itself, then the algorithm provides a solution that is a 3/2-approximation (4/3-approximation) for the optimal global make span. Both algorithms are efficient since their performance ratio correspond to the Pareto optimal solutions of the previously defined instances.

The distributed nature of new computing platforms results in the problem of scheduling parallel jobs produced by several independent organizations that have each their own rules. They have no direct control over the whole system; thus, it is necessary to revisit classical scheduling with locality constraints. In this work, we consider distributed computing systems in which each organization has its own resources. Each organization aims at minimizing the execution times of its own jobs. We introduce a global centralized mechanism for designing a collaborative solution that improves the global performance of the system while respecting organizations' selfish objectives. The proposed algorithm is proved to have an approximation ratio equal to 3 over the global optimal makespan and this bound is shown to be asymptotically tight (when the number of organizations is large). Several variants of this problem are also studied. Then, we derive another algorithm that improves in practice these solutions by further balancing the schedules. Finally, we provide some experiments based on simulations that demonstrate a very good efficiency of this last algorithm on typical instances.

In this work we study the portfolio problem which is to find a good combination of multiple heuristics to solve given instances on parallel resources in minimum time. The resources are assumed to be discrete, it is not possible to allocate a resource to more than one heuristic. Our goal is to minimize the average completion time of the set of instances, given a set of heuristics on homogeneous discrete resources. This problem has been studied in the continuous case in [T. Sayag et al., 2006]. We first show that the problem is hard and that there is no constant ratio polynomial approximation unlessP=NPin the general case. Then, we design several approximation schemes for a restricted version of the problem where each heuristic must be used at least once. These results are obtained by using oracle with several guesses, leading to various tradeoff between the size of required information and the approximation ratio. Some additional results based on simulations are finally reported using a benchmark of instances on SAT solvers.

Applications structured as parallel task graphs exhibit both data and task parallelism and arise in many domains. Scheduling these applications efficiently on parallel platforms has been a long-standing challenge. In the case of a single homogeneous platform, such as a cluster, results have been obtained both in theory, i.e., guaranteed algorithms, and, in practice, i.e., pragmatic heuristics. Due to task parallelism, these applications are well suited for execution on distributed platforms that span multiple clusters possibly in multiple institutions. However, the only available results in this context are nonguaranteed heuristics. In this paper, we develop a scheduling algorithm, MCGAS, which is applicable to multicluster platforms that are almost homogeneous. Such platforms are often found as large subsets of multicluster platforms. Our novel contribution is that MCGAS computes task allocations so that a (tunable) performance guarantee is provided. Since a performance guarantee does not necessarily imply good average performance in practice, we also compare MCGAS with a recently proposed nonguaranteed algorithm. Using simulation over a wide range of experimental scenarios, we find that MCGAS leads to better average application makespans than its competitor.

Cumulative memory occupation is a quite intuitive but not so studied constraint in scheduling. The interest in such a constraint is present in multi-System-on-Chip, embedded systems for storing instruction code, or in scientific computation for storing results. Memory occupation seen as a constraint is impossible to solve with approximation algorithms. We believe that transforming the constraint into a second objective to optimize helps to deal with such constraints. The problem addressed in this paper is to schedule tasks on identical processors in order to minimize both maximum completion time and maximum cumulative memory occupation. For independent tasks, a family of algorithms with good approximation ratios based on a PTAS is given. Several approximation ratios are proved to be impossible to achieve with any schedule. The precedence constrained case is then studied and a family of performance guaranteed algorithms based on List Scheduling is proposed. Finally, optimizing the mean completion time as a third objective is also studied and a tri-objective algorithm is given.

Summary form only given. In recent years, there was a huge development of low cost large scale parallel systems. The design of efficient parallel algorithms has to be reconsidered to take into account new parameters of such execution platforms which are characterized by a larger number of heterogeneous processors, often organized as hierarchical subsystems. Alternative computational models have been designed to take into account these new characteristics. Parallel tasks model /spl times/ PT in short - is a promising alternative for scheduling parallel applications. Another way of looking at the problem (which is somehow a dual view) is the divisible load model (DL) where an application is considered as a collection of a large number of elementary - sequential - computing units. These two new views of the problem allow us to consider communications implicitly or to mask them, leading to more tractable problems. This paper, first, presents some approximation algorithms for the PT model with a special emphasis on new execution platforms. We show how to mix these results with the DL model to manage the resources of an actual computational grid of 600 processors.

We describe in this paper a new method for building an efficient algorithm for scheduling jobs in a cluster. Jobs are considered as parallel tasks (PT) which can be scheduled on any number of processors. The main feature is to consider two criteria that are optimized together. These criteria are the makespan and the weighted minimal average completion time (minsum). They are chosen for their complementarity, to be able to represent both user-oriented objectives and system administrator objectives.We propose an algorithm based on a batch policy with increasing batch sizes, with a smart selection of jobs in each batch. This algorithm is assessed by intensive simulation results, compared to a new lower bound (obtained by a relaxation of ILP) of the optimal schedules for both criteria separately. It is currently implemented in an actual real-size cluster platform.

The model of malleable task (MT) was introduced some years ago and has been proved to be an efficient way for implementing parallel applications. It considers a target application at a larger level of granularity than in other models (corresponding typically to numerical routines) where the tasks can themselves be executed in parallel.