With the increase of demand for computing resources and the struggle to provide the necessary energy, power-aware resource management is becoming a major issue for the High-performance computing (HPC) community. Including reliable energy management to a supercomputer's resource and job management system (RJMS) is not an easy task. The energy consumption of jobs is rarely known in advance and the workload of every machine is unique and different from the others. We argue that the first step towards properly managing power is to deeply understand the power consumption of the workload, which involves predicting the workload power consumption and exploiting it by using smart power-aware scheduling algorithms. Crucial questions are (i) how sophisticated a prediction method needs to be to provide accurate workload power predictions, and (ii) to what point an accurate workload's power prediction translates into efficient power management. In this work, we proposed a method to predict and exploit HPC workloads power consumption with the objective of reducing the supercomputers power consumption, while maintaining the management (scheduling) performance of the RJMS. Our method exploits workload submission logs with power monitoring data, and relies on a mix of lightweight power prediction methods and a classical EASY Backfillling inspired heuristic. Then, we model and solve the power capping scheduling as a greedy knapsack algorithm. This algorithm improves the Quality of Service and avoids starvation while keeping the solution lightweight. We base this study on logs of Marconi 100, a 980-node supercomputer. We show using simulation that a lightweight history-based prediction method can provide accurate enough power prediction to improve the energy management of a large scale supercomputer compared to energy-unaware scheduling algorithms. These improvements have no significant negative impact on performance.

Information and Communications Technologies (ICT) are an increasingly important contributor to the environmental crisis. Computer scientists need tools for measuring the footprint of the code they produce and for optimizing it. Running Average Power Limit (RAPL) is a low-level interface designed by Intel that provides a measure of the energy consumption of a CPU (and more) without the need for additional hardware. Since 2017, it is available on most x86 processors, including AMD processors. More and more people are using RAPL for energy measurement, mostly like a black box without deep knowledge of its behavior. Unfortunately, this causes mistakes when implementing measurement tools. In this article, we propose to come back to the basic mechanisms that allow to use RAPL measurements and present a critical analysis of their operations. In addition to long-established mechanisms, we explore the suitability of the recent eBPF technology (formerly and abbreviation for extended Berkeley Packet Filter) for working with RAPL. We release an implementation in Rust that avoids the pitfalls we detected in existing tools, improving correctness, timing accuracy and performance, with desirable properties for monitoring and profiling parallel applications. We provide an experimental study with multiple benchmarks and processor models to evaluate the efficiency of the various mechanisms and their impact on parallel software. We show that no mechanism provides a significant performance advantage over the others. However, they differ significantly in terms of ease-of-use and resiliency. We believe that this work will help the community to develop correct, resilient and lightweight measurement tools.

With the increase of demand for computing resources and the struggle to provide the necessary energy, power-aware resource management is becoming a major issue for the High-performance computing (HPC) community. Including reliable energy management to a supercomputer’s resource and job management system (RJMS) is not an easy task. The energy consumption of jobs is rarely known in advance and the workload of every machine is unique and different from the others. We argue that the first step toward properly managing energy is to deeply understand the energy consumption of the workload, which involves predicting the workload’s power consumption and exploiting it by using smart power-aware scheduling algorithms. Crucial questions are (i) how sophisticated a prediction method needs to be to provide accurate workload power predictions, and (ii) to what point an accurate workload’s power prediction translates into efficient energy management. In this work, we propose a method to predict and exploit HPC workloads’ power consumption, with the objective of reducing the supercomputer’s power consumption while maintaining the management (scheduling) performance of the RJMS. Our method exploits workload submission logs with power monitoring data, and relies on a mix of light-weight power prediction methods and a classical EASY Backfillling inspired heuristic. We base this study on logs of Marconi 100, a 980 servers supercomputer. We show using simulation that a light-weight history-based prediction method can provide accurate enough power prediction to improve the energy management of a large scale supercomputer compared to energy-unaware scheduling algorithms. These improvements have no significant negative impact on performance.

EcoIndex has been proposed to evaluate the absolute environmental performance of a given URL using a score ranging from 0 to 100 (the higher, the better). In this article, we make a critical analysis of the initial approach and propose alternatives that no longer calculate a plain score but allow the query to be situated among other queries. The generalized critiques come with statistics and rely on extensive experiments (first contribution). Then, we move on to low-cost Machine Learning (ML) approaches (second contribution) and a transition before obtaining our final results (third contribution). Our research aims to extend the initial idea of analytical computation, i.e., a relation between three variables, in the direction of algorithmic ML computations. The fourth contribution corresponds to a discussion on our implementation, available on a GitHub repository. Along with the paper, we invite the reader to examine the question: What attributes make sense for our problem?, or equivalently, what is a relevant data policy for studying digital environmental impacts? Beyond computational questions, it is important for the scientific community to focus on this question in particular. We currently promote using well-established ML techniques because of their potential, which we discuss in the paper. However, we also question techniques for their frugality or otherwise. Our data science project is still at the data exploration stage. We also want to encourage synergy between technical expertise and business knowledge because this is fundamental for advancing the data project.

The cloud is extended towards the edge to form a computing continuum while managing resources' heterogeneity. The serverless technology simplified how to build cloud applications and use resources, becoming a driving force in consolidating the continuum with the deployment of small functions with short execution. However, the adaptation of serverless to the edge-cloud continuum brings new challenges mainly related to resource management and scheduling. Standard cloud scheduling policies are based on greedy algorithms that do not efficiently handle platforms' heterogeneity nor deal with problems such as cold start delays. This work introduces a new scheduling policy that tries to address these issues. It is based on multi-objective optimization for data transfers and makespan while considering heterogeneity. Using simulations that vary workloads, platforms, and heterogeneity levels, we study the system utilization, the trade-offs between the targets, and the impacts of considering platforms' heterogeneity. We perform comparisons with a baseline inspired by a Kubernetes-based policy, representing greedy algorithms. Our experiments show considerable gaps between the efficiency of a greedy-based scheduling policy and a multi-objective-based one. The last outperforms the baseline by reducing makespan, data transfers, and system utilization by up to two orders of magnitudes in relevant cases for the edge-cloud continuum.

The global energy demand for digital activities is constantly growing. Computing nodes and cloud services are at the heart of these activities. Understanding their energy consumption is an important step towards reducing it. On one hand, physical power meters are very accurate in measuring energy but they are expensive, difficult to deploy on a large scale, and are not able to provide measurements at the service level. On the other hand, power models and vendor-specific internal interfaces are already available or can be implemented on existing systems. Plenty of tools, called software-based power meters, have been developed around the concepts of power models and internal interfaces, in order to report the power consumption at levels ranging from the whole computing node to applications and services. However, we have found that it can be difficult to choose the right tool for a specific need. In this work, we qualitatively and experimentally compare several software-based power meters able to deal with CPU or GPU-based infrastructures. For this purpose, we evaluate them against high-precision physical power meters while executing various intensive workloads. We extend this empirical study to highlight the strengths and limitations of each software-based power meter.

EcoIndex has been proposed to evaluate the absolute environmental performance of a given URL using a score ranging from 0 to 100 (higher is better). In this article, we revisit the calculation method of the EcoIndex metric through low-cost Machine Learning (ML) approaches. Our research aims to extend the initial idea of analytical computation, i.e., a relation (equation) between three variables, in the direction of algorithmic Machine Learning (ML) computations, allowing to treat large numbers of data, which is not the case with the current computation. For a URL, our new calculation methods mimic the initial metric and return an environmental performance score but make fewer assumptions than the initial method. We develop several ML ways, either using learning techniques (Locality Sensitive Hashing, K Nearest Neighbor) or matrix computation constitutes the paper’s first contribution. We use standard methods to keep the solutions simple and understood by the public. The second contribution corresponds to a discussion on our implementations, available on a GitHub repository. As major findings or trends of our study, we also discuss the limits of the past and new approaches in a search for new metrics regarding the environmental performance of HTTP requests admissible by the most significant number of people. Our work refers to the uses of digital technology. Therefore, explaining the environmental footprint measures with few words seems important if we want to move towards greater digital sobriety. Otherwise, we run the risk of not being followed by civil society.

Predicting the performance of applications executed on GPUs is a great challenge and is essential for efficient job schedulers. There are different approaches to do this, namely analytical modeling and machine learning (ML) techniques. Machine learning requires large training sets and reliable features, nevertheless it can capture the interactions between architecture and software without manual intervention. In this paper, we compared a BSP-based analytical model to predict the time of execution of kernels executed over GPUs. The comparison was made using three different ML techniques. The analytical model is based on the number of computations and memory accesses of the GPU, with additional information on cache usage obtained from profiling. The ML techniques Linear Regression, Support Vector Machine, and Random Forest were evaluated over two scenarios: first, data input or features for ML techniques were the same as the analytical model and, second, using a process of feature extraction, which used correlation analysis and hierarchical clustering. Our experiments were conducted with 20 CUDA kernels, 11 of which belonged to 6 real-world applications of the Rodinia benchmark suite, and the other were classical matrix-vector applications commonly used for benchmarking. We collected data over 9 NVIDIA GPUs in different machines. We show that the analytical model performs better at predicting when applications scale regularly. For the analytical model a single parameter λ is capable of adjusting the predictions, minimizing the complex analysis in the applications. We show also that ML techniques obtained high accuracy when a process of feature extraction is implemented. Sets of 5 and 10 features were tested in two different ways, for unknown GPUs and for unknown Kernels. For ML experiments with a process of feature extractions, we got errors around 1.54% and 2.71%, for unknown GPUs and for unknown Kernels, respectively.

Predictive maintenance aims to anticipate indus-trial equipment failures in order to allow early scheduling of corrective actions. Such a maintenance approach is based on a detailed analysis that takes into account the technical and contextual characteristics of the target industrial equipment. However, this analysis requires a significant period of time to collect a representative quantity of data to learn a predictive model. Federated learning (FL in short) is a promising approach that allows several participants to build collaboratively a global predictive model. This approach has been widely explored in generic loT applications and large scale architectures. However, the implementation of FL in actual environments requires to consider several issues to adapt to existing loT architectures, including the management/orchestration of the federated tasks and handling the limitations of computational resources. Indeed, most of the current research focus on the aggregation of heavy deep learning algorithms. In this paper, we propose an architecture for FL in the context of loT based on the classical 3-layer architecture standardized by ETSI11https://www.etsi.org/. We consider new features for performing federated tasks (training, aggregation and man-agement of each participant). We also propose a stacking-based aggregation method to build the global model in a cost-efficient way. We evaluate finally the performance and effectiveness of this approach on real use-case scenarios. The comparison with other models trained in a centralized way highlights the benefit of our approach.

Federated learning (FL) is an approach that enables collaborative machine learning (ML) without sharing data over the network. Internet of Things (IoT) and Industry 4.0 are promising areas for FL adoption. Nevertheless, there are several challenges to overcome before the deployment of FL methods in existing large-scale IoT environments. In this paper, we present one step further toward the adoption of FL systems for IoT. More specifically, we developed a prototype that enables distributed ML model deployment, federated task orchestration, and monitoring of system state and model performance. We tested the prototype on a network that contains multiple Raspberry Pi for a use case of modeling the states of conveyors in an airport.

Maintaining Cloud data centers is a worrying challenge in terms of energy efficiency. This challenge leads to solutions such as deploying Edge nodes that operate inside buildings without massive cooling systems. Edge nodes can act as smart heaters by recycling their consumed energy to heat these buildings. We propose a novel technique to perform temperature forecasting for Edge Computing smart heater environments. Our approach uses time series algorithms to exploit historical air temperature data, smart heaters’ power consumption and temperature to create models to predict short-term ambient temperature over one hour horizon. We implemented our approach on top of Facebook's Prophet time series forecasting framework, and we used the real-time logs from Qarnot Computing as a use-case of a smart heater Edge platform. Our best trained model yields ambient temperature forecasts with less than 2.66% Mean Absolute Percentage Error.

Buildings in residential and commercial sites consume close to 40 per cent of the world’s total energy produced and is growing at a steady pace. The need to lower the energy footprint is a matter of sustainability and active research for the smart building community. Recent trends in machine learning have led to significant work on occupancy detection in spaces by training isolated or ex-situ models, but with no reliability of performance on unknown spaces. Model applicability becomes questionable when the sensor value distribution is different from training data and in a real-life this is usually the case. Furthermore, analyzing a space on a floor-plan in silo obscures the holistic view of interactivity between building elements. In this paper, we propose the design of a generic building management system that auto-learns occupancy patterns and leverages spatial organization to deliver actionable insights on energy savings. We combine the building information with sensor signals into a Spatio-temporal activity graph, whose edges are dynamically updated based on occupancy. We introduce human-space interaction models to infer the human transmission capacity of each edge and compute an Eigenvalue score for all the spaces to derive automated checkpoints on space-wise appliance monitoring.

Scheduling computational jobs with data-sets dependencies is an important challenge of edge computing infrastructures. Although several strategies have been proposed, they have been evaluated through ad-hoc simulator extensions that are, when available, usually not maintained. This is a critical problem because it prevents researchers to -easily- perform fair comparisons between different proposals. In this paper, we propose to address this limitation by presenting a simulation engine dedicated to the evaluation and comparison of scheduling and data movement policies for edge computing use-cases. Built upon the Batsim/SimGrid toolkit, our tool includes an injector that allows the simulator to replay a series of events captured in real infrastructures. It also includes a controller that supervises storage entities and data transfers during the simulation, and a plug-in system that allows researchers to add new models to cope with the diversity of edge computing devices. We demonstrate the relevance of such a simulation toolkit by studying two scheduling strategies with four data movement policies on top of a simulated version of the Qarnot Computing platform, a production edge infrastructure based on smart heaters. We chose this use-case as it illustrates the heterogeneity as well as the uncertainties of edge infrastructures. Our ultimate goal is to gather industry and academics around a common simulator so that efforts made by one group can be factorised by others.

High-Performance Computing (HPC) platforms are growing in size and complexity. In order to improve the quality of service of such platforms, researchers are devoting a great amount of effort to devise algorithms and techniques to improve different aspects of performance such as energy consumption, total usage of the platform, and fairness between users. In spite of this, system administrators are always reluctant to deploy state of the art scheduling methods and most of them revert to EASY-backfilling, also known as EASY-FCFS (EASY-First-Come-First-Served). Newer methods frequently are complex and obscure and the simplicity and transparency of EASY are too important to sacrifice. In this work, we used execution logs from five HPC platforms to compare four simple scheduling policies: FCFS, Shortest estimated Processing time First (SPF), Smallest Requested Resources First (SQF), and Smallest estimated Area First (SAF). Using simulations, we performed a thorough analysis of the cumulative results for up to 180 weeks and considered three scheduling objectives: waiting time, slowdown and per-processor slowdown. We also evaluated other effects, such as the relationship between job size and slowdown, the distribution of slowdown values, and the number of backfilled jobs, for each HPC platform and scheduling policy. We conclude that one can only gain by replacing EASY-backfilling with SAF with backfilling, as it offers improvements in performance by up to 80% in the slowdown metric while maintaining the simplicity and the transparency of FCFS. Moreover, SAF reduces the number of jobs with large slowdowns and the inclusion of a simple thresholding mechanism guarantees that no starvation occurs. Finally, we propose SAF as a new benchmark for future scheduling studies.

We consider the problem of scheduling jobs to minimize the maximum weighted flow-time on a set of related machines. When jobs can be preempted this problem is well-understood; for example, there exists a constant competitive algorithm using speed augmentation. When jobs must be scheduled non-preemptively, only hardness results are known. In this paper, we present the first online guarantees for the non-preemptive variant. We present the first constant competitive algorithm for minimizing the maximum weighted flow-time on related machines by relaxing the problem and assuming that the online algorithm can reject a small fraction of the total weight of jobs. This is essentially the best result possible given the strong lower bounds on the non-preemptive problem without rejection.

Despite the impressive growth and size of super-computers, the computational power they provide still cannot match the demand. Efficient and fair resource allocation is a critical task. Super-computers use Resource and Job Management Systems to schedule applications, which is generally done by relying on generic index policies such as First Come First Served and Shortest Processing time First in combination with Backfilling strategies. Unfortunately, such generic policies often fail to exploit specific characteristics of real workloads. In this work, we focus on improving the performance of online schedulers. We study mixed policies, which are created by combining multiple job characteristics in a weighted linear expression, as opposed to classical pure policies which use only a single characteristic. This larger class of scheduling policies aims at providing more flexibility and adaptability. We use space coverage and black-box optimization techniques to explore this new space of mixed policies and we study how can they adapt to the changes in the workload. We perform an extensive experimental campaign through which we show that (1) even the best pure policy is far from optimal and that (2) using a carefully tuned mixed policy would allow to significantly improve the performance of the system. (3) We also provide empirical evidence that there is no one size fits all policy, by showing that the rapid workload evolution seems to prevent classical online learning algorithms from being effective.

Summary We study the problem of executing an application represented by a precedence task graph on a parallel machine composed of standard computing cores and accelerators. Both off‐line and on‐line settings are addressed by proposing generic scheduling approaches. In the first case, we establish strong lower bounds on the worst‐case performance of a known approach based on Linear Programming and replace the greedy List Scheduling policy used in this approach by a better task ordering. Although this modification leads to the same approximability guarantees, it performs much better in practice. We also extend this algorithm to more types of computing units, achieving an approximation ratio which depends on the number of different types. In the on‐line case, tasks arrive in any order which respects the precedence relations and the scheduler has to take irrevocable decisions about their allocation and execution. We propose the first on‐line scheduling algorithm taking into account precedences, which is based on adequate rules for selecting the type of processor where to allocate the tasks. Finally, all the previous algorithms have been experimented on a large number of simulations built on actual libraries, assessing their good practical behavior with respect to the state‐of‐the‐art solutions and baseline algorithms.

In this paper, we consider the online problem of scheduling independent jobs non-preemptively so as to minimize the weighted flow-time on a set of unrelated machines. There has been a considerable amount of work on this problem in the preemptive setting where several competitive algorithms are known in the classical competitive model. However, the problem in the non-preemptive setting admits a strong lower bound. Recently, Lucarelli et al. presented an algorithm that achieves a O(1/epsilon^2)-competitive ratio when the algorithm is allowed to reject epsilon-fraction of total weight of jobs and has an epsilon-speed augmentation. They further showed that speed augmentation alone is insufficient to derive any competitive algorithm. An intriguing open question is whether there exists a scalable competitive algorithm that rejects a small fraction of total weights. In this paper, we affirmatively answer this question. Specifically, we show that there exists a O(1/epsilon^3)-competitive algorithm for minimizing weighted flow-time on a set of unrelated machine that rejects at most O(epsilon)-fraction of total weight of jobs. The design and analysis of the algorithm is based on the primal-dual technique. Our result asserts that alternative models beyond speed augmentation should be explored when designing online schedulers in the non-preemptive setting in an effort to find provably good algorithms.

When a computer system schedules jobs there is typically a significant cost associated with preempting a job during execution. This cost can be from the expensive task of saving the memory's state and loading data into and out of memory. There is a need for non-preemptive system schedulers to avoid the costs of preemption on desktops, servers and data centers. Despite this need, there is a gap between theory and practice. Indeed, few non-preemptive online schedulers are known to have strong foundational guarantees. This gap is likely due to strong lower bounds on any online algorithm for popular objectives. Indeed, typical worst case analysis approaches, and even resource augmented approaches such as speed augmentation, result in all algorithms having poor performance guarantees. This paper considers online non-preemptive scheduling problems in the worst-case model where the algorithm is allowed to reject a small fraction of jobs. By rejecting only few jobs, this paper shows that the strong lower bounds can be circumvented. This model can be used to discover scheduling policies with desirable worst-case guarantees. Specifically, the paper presents algorithms for minimizing the total flow-time and minimizing the total weighted flow-time plus energy under the speed-scaling mechanism. The algorithms have a small constant competitive ratio while rejecting only a constant fraction of jobs. Beyond specific results, the paper asserts that alternative models beyond speed augmentation should be explored to aid in the discovery of good schedulers in the face of the requirement of being online and non-preemptive.

Summary Job scheduling is an old topic in High‐Performance Computing (HPC), and it is more and more studied in data centers. Large data centers are often split into separate partitions for cloud computing and HPC; each partition normally has its specific scheduler. The possibility of migrating jobs from the HPC partition to the cloud one is a topic widely discussed in the literature. However, job migration from cloud to HPC is a much less explored topic. Nevertheless, such migration may be useful in many situations, in particular when the HPC platform has a low resource usage level, and the cloud usage level is high. A large number of jobs that could migrate from the cloud to the HPC partition may be observed in Google data center workloads. Job scheduling using overbooking strategy is seen as the main reason for the high resource usage level in clouds. However, overbooking can lead to a high rate of rescheduling and job dumping, which potentially causes response time violations. This work shows that HPC platforms can host and execute some cloud jobs with low interference in HPC jobs and a low number of response time violations. We introduce the definition of a cloud‐HPCconvergence areaand propose a job scheduling strategy for it, aiming at reducing the number of response time violations of cloud jobs without interfering with HPC jobs execution. Our proposal is formally defined and then evaluated in different execution scenarios, using theSimGridsimulation framework, with workload data from production HPC grid. The experimental results show that often, there is a large number of empty areas in the scheduling plan of HPC platforms, which makes it possible to allocate cloud jobs by backfilling. This is due to the sparse HPC job submission pattern and the low resource usage level in some HPC platforms. One performed simulation scenario considered a set of 11K parallel HPC jobs running on a 2560‐processor platform having an average resource usage level of 38.0%. The proposed convergence scheduler succeeded to inject around 267K cloud jobs in the HPC platform, with a response time violation rate under 0.00094% for such jobs, considering 80 processors in theconvergence areaand no effects on the HPC workload. This experiment considered cloud jobs based on job features of Google public cloud workloads, with a processing time slack factor of 1.25 (which is considered as high priority in the Google cloud SLA—Service Level Agreement). Usually, most cloud jobs show a slack factor higher than 1.25 (most cloud jobs are medium or low priority). The same simulation, repeated with a higher slack factor (4), showed no response time violations.

The EASY-FCFS heuristic is the basic building block of job scheduling policies in most parallel High Performance Computing platforms. Despite its simplicity, and the guarantee of no job starvation, it could still be improved on a per-system basis. Such tuning is difficult because of non-linearities in the scheduling process. The study conducted in this paper considers an online approach to the automatic tuning of the EASY heuristic for HPC platforms. More precisely, we consider the problem of selecting a reordering policy for the job queue under several feedback modes. We show via a comprehensive experimental validation on actual logs that periodic simulation of historical data can be used to recover existing in-hindsight results that allow to divide the average waiting time by almost 2. This results holds even when the simulator results are noisy. Moreover, we show that good performances can still be obtained without a simulator, under what is called bandit feedback - when we can only observe the performance of the algorithm that was picked on the live system. Indeed, a simple multi-armed bandit algorithm can reduce the average waiting time by 40 percent.

We present a new method for scheduling independent tasks on a parallel machine composed of identical processors. This problem has been studied extensively for a long time with many variants. We are interested here in designing a generic algorithm in the on-line non-preemptive setting whose performance is good for various objectives. The basic idea of this algorithm is to detect some problematic tasks that are responsible for the delay of other shorter tasks. Then the former tasks are redirected to be executed in a dedicated part of the machine. We show through an extensive experimental campaign that this method is effective and in most cases is closer to some standard lower bounds than the base-line method for the problem.

This special issue of Concurrency and Computation: Practice and Experience contains revised and extended versions of selected papers presented at the conference Euro-Par 2016.Euro-Par-the European Conference on Parallel Computing-is an annual series of international conferences dedicated to the promotion and advancement of all aspects of parallel and distributed computing.Euro-Par covers a wide spectrum of topics from algorithms and theory to software technology and hardware-related issues, with application areas ranging from scientific to mobile and cloud computing.The major part of the Euro-Par audience consists of researchers in academic institutions, government laboratories, and industrial organisations.Euro-Par 2016, the 22nd conference in the Euro-Par series, was held in Grenoble, France.It was organised by Inria, Université Grenoble-Alpes, and IUT 2 Grenoble.Twelve broad topics were defined and advertised, covering a large variety of aspects of parallel and distributed computing.The call for papers attracted a total of 176 submissions.The submitted papers were reviewed at least 3 and, in most cases, 4 or even more times (4 reviews on average).A total of 47 papers were finally accepted for publication.This makes a global acceptance rate of 26.7 %.The authors of accepted papers came from 20 countries, with the 4 main contributing countries-France, the United States, Germany, and Spain-accounting for a bit more than half of them.Compared to the conference version, this framework is enhanced further with the availability of customized CUDA kernels and a multiple-GPU implementation with almost linear scalability.The reviewers appreciated the high quality and scientific soundness of the treatise.Concluding this preface, we would like to thank Prof Geoffrey Fox, editor-in-chief of Concurrency and Computation: Practice and Experience, for his support of this special issue.We

We present a new approach for scheduling independent tasks on multiple CPUs and multiple GPUs. The tasks are assumed to be parallelizable on CPUs using the moldable model: the final number of cores allotted to a task can be decided and set by the scheduler. More precisely, we design an algorithm aiming at minimizing the makespan-the maximum completion time of all tasks-for this scheduling problem. The proposed algorithm combines a dual approximation scheme with a fast integer linear program (ILP). It determines both the partitioning of the tasks, i.e., whether a task should be mapped to CPUs or a GPU, and the number of CPUs allotted to a moldable task if mapped to the CPUs. A worst-case analysis shows that the algorithm has an approximation ratio of 3/2 + ε. Since the time complexity of the ILP-based algorithm could be non-polynomial, we also present a polynomial-time algorithm with an approximation ratio of 2 + ε. We complement the theoretical analysis of our two novel algorithms with a simulation study. In these simulations, we compare our algorithms to a modified version of the classical HEFT algorithm, which we adapted to handle moldable tasks. The simulation results show that our algorithm with the (3/2 + ε)-approximation ratio produces significantly shorter schedules than the modified HEFT for most of the instances. In addition, our results provide evidence that our ILP-based algorithm can solve larger problem instances in a reasonable amount of time.

Resource augmentation is a well-established model for analyzing algorithms, particularly in the online setting. It has been successfully used for providing theoretical evidence for several heuristics in scheduling with good performance in practice. According to this model, the algorithm is applied to a more powerful environment than that of the adversary. Several types of resource augmentation for scheduling problems have been proposed up to now, including speed augmentation, machine augmentation and more recently rejection. In this paper, we present a framework that unifies the various types of resource augmentation. Moreover, it allows generalize the notion of resource augmentation for other types of resources. Our framework is based on mathematical programming and it consists of extending the domain of feasible solutions for the algorithm with respect to the domain of the adversary. This, in turn allows the natural concept of duality for mathematical programming to be used as a tool for the analysis of the algorithm's performance. As an illustration of the above ideas, we apply this framework and we propose a primal-dual algorithm for the online scheduling problem of minimizing the total weighted flow time of jobs on unrelated machines when the preemption of jobs is not allowed. This is a well representative problem for which no online algorithm with performance guarantee is known. Specifically, a strong lower bound of Omega(sqrt{n}) exists even for the offline unweighted version of the problem on a single machine. In this paper, we first show a strong negative result even when speed augmentation is used in the online setting. Then, using the generalized framework for resource augmentation and by combining speed augmentation and rejection, we present an (1+epsilon_s)-speed O(1/(epsilon_s epsilon_r))-competitive algorithm if we are allowed to reject jobs whose total weight is an epsilon_r-fraction of the weights of all jobs, for any epsilon_s > 0 and epsilon_r in (0,1). Furthermore, we extend the idea for analysis of the above problem and we propose an (1+\epsilon_s)-speed epsilon_r-rejection O({k^{(k+3)/k}}/{epsilon_{r}^{1/k}*epsilon_{s}^{(k+2)/k}})-competitive algorithm for the more general objective of minimizing the weighted l_k-norm of the flow times of jobs.

Today, most high-performance computing (HPC) platforms have heterogeneous hardware resources (CPUs, GPUs, storage, etc.) A Graphics Processing Unit (GPU) is a parallel computing coprocessor specialized in accelerating vector operations. The prediction of application execution times over these devices is a great challenge and is essential for efficient job scheduling. There are different approaches to do this, such as analytical modeling and machine learning techniques. Analytic predictive models are useful, but require manual inclusion of interactions between architecture and software, and may not capture the complex interactions in GPU architectures. Machine learning techniques can learn to capture these interactions without manual intervention, but may require large training sets. In this paper, we compare three different machine learning approaches: linear regression, support vector machines and random forests with a BSP-based analytical model, to predict the execution time of GPU applications. As input to the machine learning algorithms, we use profiling information from 9 different applications executed over 9 different GPUs. We show that machine learning approaches provide reasonable predictions for different cases. Although the predictions were inferior to the analytical model, they required no detailed knowledge of application code, hardware characteristics or explicit modeling. Consequently, whenever a database with profile information is available or can be generated, machine learning techniques can be useful for deploying automated on-line performance prediction for scheduling applications on heterogeneous architectures containing GPUs.

Energy consumption has become one of the most important factors in High Performance Computing platforms. However, while there are various algorithmic and programming techniques to save energy, a user has currently no incentive to employ them, as they might result in worse performance. We propose to manage the energy budget of a supercomputer through EnergyFairShare (EFS), a FairShare-like scheduling algorithm. FairShare is a classic scheduling rule that prioritizes jobs belonging to users who were assigned small amount of CPU-second in the past. Similarly, EFS keeps track of users 'consumption of Watt-seconds and prioritizes those whom jobs consumed less energy. Therefore, EFS incentives users to optimize their code for energy efficiency. Having higher priority, jobs have smaller queuing times and, thus, smaller turn-around time. To validate this principle, we implemented EFS in a scheduling simulator and processed workloads from various HPC centers. The results show that, by reducing it energy consumption, auser will reduce it stretch (slowdown), compared to increasing it energy consumption. To validate the general feasibility odour approach, we also implemented EFS as an extension forSLURM, a popular HPC resource and job management system.We validated our plugin both by emulating a large scale platform, and by experiments upon a real cluster with monitored energy consumption. We observed smaller waiting times for energy efficient users.

We consider the classical First Come First Served / backfilling algorithm which is commonly used in actual batch schedulers. As HPC platforms grow in size and complexity, an interesting question is how to enhance this algorithm in order to improve global performance by reducing the overall amount of communications. In this direction, we are interested in studying the impact of contiguity and locality allocation constraints on the behavior of batch scheduler. We provide a theoretical analysis of the cost of enforcing contiguity and locality properties. More specifically, we show that both properties do not impose strong limit on achievable make span performance while comparing feasible optimal solutions under different settings, we describe here the existing results on this topic and complete them with all combinations of constraints. We also propose a range of different allocation algorithms for backfilling by choosing between a strict or a soft enforcing of locality and contiguity. Our approach is validated through an extensive series of simulations based on batch scheduler traces. Experiments show that our algorithms do not increase the make span in average when comparing to actual practices. Interestingly, we observe that enforcing contiguity efficiently improves locality.

The job management system is the HPC middleware responsible for distributing computing power to applications. While such systems generate an ever increasing amount of data, they are characterized by uncertainties on some parameters like the job running times. The question raised in this work is: To what extent is it possible/useful to take into account predictions on the job running times for improving the global scheduling?

Summary More and more computers use hybrid architectures combining multi‐core processors and hardware accelerators such as graphics processing units (GPUs). We present in this paper a new method for scheduling efficiently parallel applications with m CPUs and k GPUs, where each task of the application can be processed either on a core (CPU) or on a GPU. The objective is to minimize the maximum completion time (makespan). The corresponding scheduling problem is Non‐deterministic Polynomial (NP)‐time hard, Copyright © 2014 John Wiley & Sons, Ltd.

Summary On resource sharing platforms, the execution of the jobs submitted by users is usually controlled by a centralized global scheduler. It determines efficient schedules regarding some common objective function that all organizations agree with (for instance, maximizing the utilization of the entire platform). However, in practice, each organization is mostly interested in the performance obtained for its own jobs. We study the price that the collectivity must pay in order to allow independence to selfish, self‐governing organizations, so they can choose the best schedules for their own jobs. In other words, we are interested in analyzing the costs on the global performance inflicted by the decentralization of scheduling policies. We present a game‐theoretic model for the problem and the associated coordination mechanisms developed to reduce the cost of the decentralization of the decision‐making process. The main contribution is to show (in theory and practice) how to devise pure Nash equilibria configurations for every instance of the problem and to prove that the price paid by the collectivity depends on the local scheduling policy and on the characteristics of the workload executed on such platforms. Copyright © 2014 John Wiley & Sons, Ltd.

Uncertainties stemming from multiple sources affect distributed systems and jeopardize their efficient utilization. Desktop grids are especially concerned by this issue as volunteers lending their resources may have irregular and unpredictable behaviors. Efficiently exploiting the power of such systems raises theoretical issues that received little attention in the literature. In this paper, we assume that there exist predictions on the intervals during which machines are available. When these predictions have a limited estimation, it is possible to schedule a set of jobs such that the effective total execution time will not be higher than the predicted one. We formally prove that it is the case when scheduling jobs only in large intervals and when provisioning sufficient slacks to absorb uncertainties. We present multiple heuristics with various efficiencies and costs that are empirically assessed through simulations based on actual traces.

Today, many high performance computing platforms use hybrid architectures combining multi-core processors and hardware accelerators like GPUs (Graphic Processing Units). This paper presents a new method for scheduling tasks for biological sequence comparison applications with CPUs and GPUs. This strategy is called SWDUAL and is based on a dual approximation scheme for determining which tasks are most suitable to be executed on the GPUs. The objective is to obtain fast execution time and minimize the idle time on each PE (Processing Element). It is implemented using a master-slave model. Results obtained when sequences were compared to five public genomic databases show that this method allows to reduce the execution time on hybrid platforms when compared to other public available implementations.

We investigate a dynamic, adaptive resource allocation scheme with the aim of accelerating the convergence of multi-start population-based search heuristics (PSHs) running on multiple parallel processors. Given that each initialization of a PSH performs differently over time, we develop an exponential learning scheme which allocates computational resources (processors) to each variant in an online manner, based on the performance level attained by each initialization. For the well-known example of (mu+lambda)-evolution strategies, we show that the time required to reach the target quality level of a given optimization problem is significantly reduced and that the utilization of the parallel system is likewise optimized. Our learning approach is easily implementable with currently available batch management systems and provides notable performance improvements without modifying the employed PSH, so it is very well-suited to improve the performance of PSHs in large-scale parallel computing environments.

The parallel computing platforms available today are increasingly larger and thus, more and more subject to failures. Consequently it is necessary to develop efficient strategies providing safe and reliable completion for HPC parallel applications. Checkpointing is one of the most popular and efficient technique for developing fault-tolerant applications on such context. However, checkpoint operations are costly in terms of time, computation, and network communication. This will certainly affect the global performance of the application. In this work, we propose a performance model that expresses formally the checkpoint scheduling problem. This model exhibits the tradeoff between the impact of the checkpoints operations and the lost computation due to failures. Based on this model, we study the computational complexity of the problem of scheduling checkpoints with variable costs for general failure distributions. More precisely, we provide a new computational complexity analysis that explicits in depth the relations between the probabilistic failure model, the checkpoint cost, and the computational model. In particular, we prove that the checkpoint scheduling problem is NP-hard even in the simple case of uniform failure distribution. We also present a dynamic programming scheme for determining the optimal checkpointing times in all the variants of the problem.

Given multiple parallel heuristics solving the same problem, we are interested in combining them for taking advantage of their diversity. We propose to use the algorithm portfolio model of execution. In this model, we have multiple resources on which the candidate heuristics can be executed. An instance is solved through a concurrent execution of heuristics (each on a fraction of resources) that is stopped as soon as one of them completes its execution. The efficiency of this model depends among other things of the resource sharing adopted in a concurrent execution. In most algorithm portfolio studies, the resources fraction of a heuristic is fixed. In this paper, we consider malleable algorithm portfolio. In this portfolio model, the fraction of resources of a heuristic can be changed during its execution. We extend the computational model proposed in [1] to formalize the problem of resource sharing construction in malleable portfolio. We then propose an efficient algorithm based on the combination of two guaranteed approximation algorithms for solving it. Finally, we evaluate the proposed algorithm with multiple simulations on a database of SAT solvers. The obtained results show that even in considering that the resource allocation of a heuristic can just be changed once, malleable allocations in comparison to static ones lead to an improvement of the spent time for solving an instance in algorithm portfolio.time for solving an instance in algorithm portfolio.

We study the problem of scheduling in parallel systems with many users. We analyze scenarios with many submissions issued over time by several users. These submissions contain one or more jobs; the set of submissions are organized in successive campaigns. Jobs belonging to a single campaign are sequential and independent, but any job from a campaign cannot start until all the jobs from the previous campaign are completed. Each user's goal is to minimize the sum of flow times of his campaigns. We define a theoretical model for Campaign scheduling and show that, in the general case, it is NP-hard. For the single-user case, we show that an ρ-approximation scheduling algorithm for the (classic) parallel job scheduling problem is also an ρ-approximation for the Campaign scheduling problem. For the general case with k users, we establish a fairness criterion inspired by time sharing. We propose FAIRCAMP, a scheduling algorithm which uses campaign deadlines to achieve fairness among users between consecutive campaigns. We prove that FAIRCAMP increases the flow time of each user by a factor of at most kρcompared with a machine dedicated to the user. We also prove that FAIRCAMP is a ρ-approximation algorithm for the maximum stretch. By simulation, we compare FAIRCAMP to the First-Come-First-Served (FCFS). We show that, compared with FCFS, FAIRCAMP reduces the maximum stretch by up to 3.4 times. The difference is significant in systems used by many (k > 5) users. Our results show that, rather than just individual, independent jobs, campaigns of jobs can be handled by the scheduler efficiently and fairly.

Frequent resources failures are a major challenge for the rapid completion of batch jobs. Check pointing and migration is one approach to accelerate job completion avoiding deadlock. We study the problem of scheduling checkpoints of sequential jobs in the context of Desktop Grids, consisting of volunteered distributed resources. We craft a checkpoint scheduling algorithm that is provably optimal for discrete time when failures obey any general probability distribution. We show using simulations with parameters based on real-world systems that this optimal strategy scales and outperforms other strategies significantly in terms of check pointing costs and batch completion times.

We conduct a game theoretic analysis on the problem of scheduling jobs on computing platforms composed of several independent and selfish organizations, known as the Multi-Organization Scheduling Problem (MOSP). Each organization shares resources and jobs with others, expecting to decrease the makespan of its own jobs. We modeled MOSP as a non-cooperative game where each agent is responsible for assigning all jobs belonging to a particular organization to the available processors. The local scheduling of these jobs is defined by coordination mechanisms that first prioritize local jobs and then schedule the jobs from others according to some given priority. When different priorities are given individually to the jobs - like in classical scheduling algorithms such as LPT or SPT - then no pure e-approximate equilibrium is possible for values of e less than 2. We also prove that even deciding whether a given instance admits or not a pure Nash equilibrium is co-NP hard. When these priorities are given to entire organizations, we show the existence of an algorithm that always computes a pure ρ-approximate equilibrium using any ρ-approximation list scheduling algorithm. Finally, we prove that the price of anarchy of the MOSP game using this mechanism is asymptotically bounded by 2.

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.

In this work, we are interested in the problem of satisfying multiple concurrent requests submitted to a computing server. Informally, there are users each sending a sequence of requests to the server. The requests consist of tasks linked by precedence constraints. Tasks may occur several times in the same sequence as well as in a request sequence of another user. The computing server has to execute tasks with variable processing times. The server owns a cache of limited size where intermediate results of the processing may be stored. If an intermediate result for a task is stored into the cache, no processing cost has to be paid and the result can directly be fetched from the cache. The goal of this work is to determine a schedule of the tasks such that an optimization function is minimized (the only objective studied up to now is the make span). This problem is a variant of caching which considers only one sequence of requests. We then extend the study to the minimization of the mean completion time of the request sequences. Two models are considered. In the first model, caching is forced whereas in the second model caching is optional and one can choose whether an intermediate result is stored in the cache or not. All combinations turn out to be NP-hard for fixed cache sizes and we provide a formulation as dynamic program as well as bounds for in approximation. We propose polynomial time approximation algorithms for some variants and analyze their approximation ratios. Finally, we also devise some heuristics and present experimental results. Tasks may occur several times in the same sequence as well as in a request sequence of another user. The computing server has to execute tasks with variable processing times. The server owns a cache of limited size where intermediate results of the processing may be stored. If an intermediate result for a task is stored into the cache, no processing cost has to be paid and the result can directly be fetched from the cache. The goal of this work is to determine a schedule of the tasks such that an optimization function is minimized (the only objective studied up to now is the make span). This problem is a variant of caching which considers only one sequence of requests. We then extend the study to the minimization of the mean completion time of the request sequences. Two models are considered. In the first model, caching is forced whereas in the second model caching is optional and one can choose whether an intermediate result is stored in the cache or not. All combinations turn out to be NP-hard for fixed cache sizes and we provide a formulation as dynamic program as well as bounds for in approximation. We propose polynomial time approximation algorithms for some variants and analyze their approximation ratios. Finally, we also devise some heuristics and present experimental results.

SUMMARY In this paper we consider the problem of scheduling on computing platforms composed of several independent organizations, known as the Multi‐Organization Scheduling Problem (MOSP). Each organization provides both resources and jobs and follows its own objectives. We are interested in the best way to minimize the makespan on the entire platform when the organizations behave in a selfish way. We study the complexity of the MOSP problem with two different local objectives—makespan and average completion time—and show that MOSP is strongly NP‐Hard in both cases. We formally define a selfishness notion, by means of restrictions on the schedules. We prove that selfish behavior imposes a lower bound of 2 on the approximation ratio for the global makespan. We present various approximation algorithms of ratio 2 which validate selfishness restrictions. These algorithms are experimentally evaluated through simulation, exhibiting good average performances and presenting good fairness to organizations' local objectives. Copyright © 2011 John Wiley & Sons, Ltd.

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.

We are interested in this paper to study scheduling problems in systems where many users compete to perform their respective jobs on shared parallel resources. Each user has specific needs or wishes for computing his/her jobs expressed as a function to optimize (among maximum completion time, sum of completion times and sum of weighted completion times). Such problems have been mainly studied through game theory. In this work, we focus on solving the problem by optimizing simultaneously each user's objective function independently using classical combinatorial optimization techniques. Some results have already been proposed for two users on a single computing resource. However, no generic combinatorial method is known for many objectives. The analysis proposed in this paper concerns an arbitrarily fixed number of users and is not restricted to a single resource. We first derive inapproximability bounds; then we analyze several greedy heuristics whose approximation ratios are close to these bounds. However, they remain high since they are linear in the number of users. We provide a deeper analysis which shows that a slightly modified version of the algorithm is a constant approximation of a Pareto-optimal solution.

Abstract The distributed nature of the grid results in the problem of scheduling parallel jobs produced by several independent organizations that have partial control over the system. We consider systems in which each organization owns a cluster of processors. Each organization wants its tasks to be completed as soon as possible. In this paper, we model an off‐line system consisting of N identical clusters of m processors. We show that it is always possible to produce a collaborative solution that respects participants' selfish goals, at the same time improving the global performance of the system. We propose an algorithm (called MOLBA) with a guaranteed worst‐case performance ratio on the global makespan, equal to 4. Next, we show that a better bound (equal to 3) can be obtained in a specific case when the last completed job requires at most m / 2 processors. Then, we derive another algorithm (called ILBA) that in practice improves the proposed, guaranteed solution by further balancing the schedules. Finally, by an extensive evaluation by simulation, we show that the algorithms are efficient on typical instances. Copyright © 2008 John Wiley & Sons, Ltd.

In the past, efficient parallel algorithms have always been developed specifically for the successive generations of parallel systems (vector machines, shared-memory machines, distributed-memory machines, etc.). Today, due to many reasons, such as the inherent heterogeneity, the diversity, and the continuous evolution of the existing parallel execution supports, it is very hard to solve efficiently a target problem by using a single algorithm or to write portable programs that perform well on any computational supports. Toward this goal, we propose a generic framework based on communication models and adaptive approaches in order to adaptively model performances on grid computing environments. We apply this methodology on collective communication operations and show, by achieving experiments on a real platform, that the framework provides significant performances while determining the best combination model- algorithm depending on the problem and architecture parameters.

We study two problems directly resulting from organizational decentralization of the grid. Firstly, the problem of fair scheduling in systems in which the grid scheduler has complete control of processors' schedules. Secondly, the problem of fair and feasible scheduling in decentralized case, in which the grid scheduler can only suggest a schedule, which can be later modified by a processor's owner. Using game theory, we show that scheduling in decentralized case is analogous to the prisoner's dilemma game. Moreover, the Nash equilibrium results in significant performance drop. Therefore, a strong community control is required to achieve acceptable performance.

In this work, we analyze the problem of scheduling a set of independent jobs on a homogeneous parallel computer. This problem has been widely studied from both a theoretical perspective (complexity analysis, and predictability of scheduling algorithms) and practical side (schedulers in production systems). It is common for some processors of a cluster to become unavailable for a certain period of time corresponding to reservations. These reservations represent blocks of time and quantities of resources set assigned in advance for specific applications. We propose here to investigate the scheduling problem where there are restricted resource availabilities. Our main result is to provide a deep analysis for this problem (complexity, lower bounds and upper bounds) for several variants of list scheduling algorithms. More precisely, we show that the problem of scheduling with any reservations can not be approximated. This leads to the study of restricted versions of this problem where the amount of reservation is limited. Our analysis is based on an old bound of Graham for resource constraint list scheduling for which we propose a new simpler proof by considering the continuous version of this problem.

A malleable task is a computational unit that may be executed on any arbitrary number of processors, whose execution time depends on the amount of resources allotted to it. This paper presents a new approach for scheduling a set of independent malleable tasks which leads to a worst case guarantee of $\frac{3}{2}+\varepsilon$ for the minimization of the parallel execution time for any fixed $\varepsilon > 0$. The main idea of this approach is to focus on the determination of a good allotment and then to solve the resulting problem with a fixed number of processors by a simple scheduling algorithm. The first phase is based on a dual approximation technique where the allotment problem is expressed as a knapsack problem for partitioning the set of tasks into two shelves of respective heights 1 and $\frac{1}{2}$.

The problem of multiple sequence alignment is one of the most important problems in computational biology. In this paper we present a new method that simultaneously performs multiple sequence alignment and phylogenetic tree inference for large input data sets. We describe a parallel implementation of our method that utilises simulated annealing metaheuristic to find locally optimal phylogenetic trees in reasonable time. To validate the method, we perform a set of experiments with synthetic as well as real-life data

No abstract available.

The problem of optimal scheduling n independent malleable tasks in a parallel processor system is studied. It is assumed that an execution of any task can be preempted and the number of processors allocated to the same task can change during its execution. We present a rectangle packing algorithm, which converts an optimal solution for the relaxed problem, in which the number of processors allocated to a task is not required to be integer, into an optimal solution for the original problem in O(n) time.

Summary form only given. The major issue today on cluster and grid computing is the efficient resource management. The evaluation of scheduling strategies is hard because of the generation of jobs under realistic scenario. This is true for rigid jobs (where the number of processors is fixed) and even more for moldable ones. We present an approach to generate realistic workloads for this kind of jobs. The model we propose is based on the analysis of one year of utilization of the I-cluster, a 225 processors cluster. From this log we extract a typical load for this kind of parallel machines and introduce a way to generate synthetic realistic workloads in an automatic way. This work was done as a way to test scheduling strategies taking into account both rigid and moldable jobs so as the workload generator may handle moldable jobs.

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.

Summary form only given. There is today an increasing diversity of parallel execution supports. Solving a target problem by using a single algorithm is not always efficient on any computational support. We present here a polyalgorithmic approach for selecting the most suitable algorithm among various ones for given problem size and available resources. Our principal objective here is to illustrate such an approach on the well-known matrix multiplication problem which is one of the most important basic numerical kernels. More precisely, we propose a polyalgorithm which uses both advantages of standard and fast algorithms which is able to automatically choose the right and suitable algorithm for computing the matrix multiplication of any dimension on a particular parallel system. We target this approach on homogeneous clusters of PCs while providing some experiments.

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.

Scheduling is a central issue for implementing applications on parallel and distributed systems. This problem has been intensively studied for conventional parallel systems. Clusters of SMP (symmetric Multi-Processors) are a cost effective alternative to parallel supercomputers which are more and more popular. New characteristics are influencing the execution of parallel applications, like for instance the hierarchical structure and the heterogeneity of the processors. Communications between SMP usually need some important latencies that create large communication delays. Designing efficient software that take full advantage of such systems remains difficult. The model of malleable task (MT) was introduced some years ago and has been proved to be an efficient way for implementing parallel applications on conventional systems. Here, the target application is considered at a larger level of granularity than in other models (corresponding typically to numerical routines) where the tasks can themselves be executed in parallel. In this paper, we are interested in designing efficient lowcost scheduling algorithms for implementing parallel applications for clusters. We first discuss the problems that occur while scheduling an application on parallel systems and give a classification of applications leading to various scheduling problems. For each of these problems, we will use the same methodology for optimizing the resource utilization of parallel programs.

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.

A malleable task is a computational unit which may be executed on any arbitrary number of processors, its execution time depending on the amount of resources allotted to it.According to the standard behavior of parallel applications, we assume that the malleable tasks are monotonic, i.e. that the execution time is decreasing with the number of processors while the computational work increases.This paper presents a new approach for scheduling a set of independent malleable tasks which leads to a worst case guarantee of fi for the minimization of the parallel execution time, or makespan.It improves all other existing practical results including the two-phases method introduced by Turek et al.The main idea is to transfer the difficulty of a two phases method from the scheduling part to the allotment selection.We show how to formulate this last problem as a knapsack optimization problem.Then, the scheduling problem is solved by a dual-approximation which leads to a simple structure of two consecutive shelves.

The aim of this work is to show that scheduling a set of independent chains on a parallel machine under the BSP model is a difficult optimization problem which can be easily approximated in practice. BSP is a machine independent computational model which is becoming more and more popular. Finding the optimal solution when the number of processors is fixed is shown to be hard. Efficient heuristics including communications are proposed and analyzed. We particularly focus on the influence of synchronization between consecutive supersteps. Simulations of a large number of instances have been carried out to complement the theoretical worst case analysis. They confirm the very good behaviour of the algorithm on average.

This paper establishes the exact upper bound for Lawler's heuristic proving that its schedule of a UECT tree on m identical processors does not exceed an optimal solution by more than m/2 time units.

The approximate solution of the m-machine problem is addressed. The Lam–Sethi worst-case analysis of the Coffman–Graham algorithm is set up to be partly incorrect. A slightly different context is set up to correct and complete this analysis. It is shown that the makespan of a schedule computed by an extended Coffman–Graham algorithm is lower than or at worst equal to $({{2 - 2} / m})\omega _{{\text{opt}}} - {{(m - 3)} / m}$, where $\omega _{{\text{opt}}} $ is the minimal makespan of a schedule.