Arnold Rosenberg

IC-Optimal Schedules that Accommodate Heterogeneous Clients

Abstract:   Initial results are presented concerning the problem of clustering the tasks of computation-dags so as to accommodate the heterogeneity of remote clients in Internet-based computing. Earlier work has developed the underpinnings of IC-Scheduling theory, an algorithmic framework for scheduling computations having intertask dependencies for Internet-based computing (IC, for short). The goal of the schedules produced by the Theory is to render tasks eligible for execution at the maximum possible rate, with the dual aim of: (a) utilizing remote clients' computational resources well, by enhancing the likelihood of having work to allocate to an available client; (b) lessening the likelihood of a computation's stalling for lack of tasks that are eligible for execution. The current paper addresses the problem of enhancing IC-Scheduling theory so that it can accommodate the varying computational resources of different remote clients. The techniques developed here accomplish this goal by clustering a computation's tasks so as to render the computation multi-granular. After a few ad hoc examples, several task-clustering strategies are developed which exploit the structure of the computation being performed. These strategies range from one that works for any dag, to ones that build increasingly on the explicit structure of the dag being scheduled.

 slides (pdf)

Jon Weinberg

Symbiotic Space-Sharing: Mitigating Resource Contention on SMP Systems

Abstract:   Symbiotic space-sharing is a technique that can improve system throughput by executing parallel applications in combinations and configurations that alleviate pressure on shared resources. In this talk, we explore the opportunity for symbiotic schedulers and discuss initial findings and prototype implementations. We show that such schedulers can improve throughput by 20\% over conventional space-sharing when resource bottlenecks are known. We then discuss approaches for exposing these bottlenecks to the scheduler, including through user-provided job script hints as well as fine-grained, memory signatures extracted from applications. Lastly, we discuss additional studies and components necessary to realize symbiotic scheduling in HPC environments.

 slides (ppt) slides (pdf)

Cynthia Lee

Studies of the User-Scheduler Relationship.

Abstract:   An important prerequisite to effective resource management is productive interaction between the user and scheduler. Unfortunately, relatively little scheduling research directly studies the users themselves. This talk will cover user survey-based studies we have conducted, which probe several aspects of the user-scheduler relationship, and propose solutions to three of the most vexing barriers between the two. First, users' monetary valuation of compute time and schedule turnaround time is examined in terms of a utility function. Second, responsiveness of the scheduler to users' varied valuations is optimized via a genetic algorithm heuristic, creating a controlled market for computation. Finally, the chronic problem of inaccurate user runtime requests, and its implications for scheduler performance, is examined, along with mitigation techniques.

 slides (ppt)

Emmanuel Jeannot

Handling collusion in desktop grid

Abstract:   By exploiting idle time on volunteer's machines, desktop grids provide a way to execute large sets of computational tasks while requiring negligible maintenance and extra cost. Although, it constitutes a valuable resource for low-budget projects, relying on external resources can be hazardous and ensuring the validity of the obtained results is mandatory. We will present a taxonomy of existing and possible risks by considering several aspects of workers faultiness (maliciousness, collusion, dynamicity). Then, we propose a general framework for scheduling tasks in order to obtain reliable results. Our final solution contains mechanisms for the scheduling and answer selection processes which use both a trust-based system that characterizes workers previous behaviors. Joint work with Louis-Claude Canon and Jon Weissman.

 slides (pdf)

Jack Dongarra

Multicore Scheduling and Programming

 slides (pdf)

Denis Trystram

Multi-users, multi-organizations, multi-objectives : a single perspective.

Abstract:   The new computing platforms, like grids composed of multiple clusters, are characterized by new features that force to revisit the scheduling problem. Classical scheduling algorithms are mostly centralized. This centralized character allows to design more efficient algorithms (consider for instance the PTAS of Shmoys for the basic P||cmax problem). However, the platforms are intrinsically distributed. Each cluster is under the administration of a separate « organization » that has its own rules. Moreover, the resources (processors) are shared between several users that have also their own selfish goals. In this talk, we will first discuss the limitations of the existing scheduling algorithms. Then, the concept of cooperation is introduced both between organizations and users. On the first hand, we propose an approximation algorithm for the global makespan without disturbing the local objectives. On the second hand, we study the problem of optimizing simultaneously the objectives of many users within the same organization. Inapproximability results show that we can not expect too much in such a case. Finally, the mixed case of multi-user competing for resources for several organizations is addressed.

 slides (ppt) slides (pdf)

Kunal Agrawal

Adaptive Scheduling with Parallelism Feedback

Abstract:   Multiprocessor scheduling in a shared multiprogramming environment is often structured as two-level scheduling, where a kernel-level job scheduler allots processors to jobs and a user-level task scheduler schedules the work of a job on the allotted processors. In this context, the number of processors allotted to a particular job may vary during the job's execution, and the task scheduler must adapt to these changes in processor resources. For overall system efficiency, the task scheduler should also provide parallelism feedback to the job scheduler to avoid the situation where a job is allotted processors that it cannot use productively. We present an adaptive task scheduler for multitasked jobs with dependencies that provides continual parallelism feedback to the job scheduler in the form of requests for processors. Our scheduler guarantees that a job completes near optimally while utilizing at least a constant fraction of the allotted processor cycles. Our scheduler can be applied to schedule data-parallel programs, such as those written in High Performance Fortran (HPF), *Lisp, C*, NESL, and ZPL. Our analysis models the job scheduler as the task scheduler's adversary, challenging the task scheduler to be robust to the system environment and the job scheduler's administrative policies. For example, the job scheduler can make available a huge number of processors exactly when the job has little use for them. To analyze the performance of our adaptive task scheduler under this stringent adversarial assumption, we introduce a new technique called ``trim analysis,'' which allows us to prove that our task scheduler performs poorly on at most a small number of time steps, exhibiting near-optimal behavior on the vast majority. To be precise, suppose that a job has work $T_1$ and critical-path length $T_infty$ and is running on a machine with $P$ processors. Using trim analysis, we prove that our scheduler completes the job in $O(T_1/Padj + T_infty + L lg P)$ time steps, where $L$ is the length of a scheduling quantum and $Padj$ denotes the $O(T_infty + L lg P)$-trimmed availability. This quantity is the average of the processor availability over all time steps excluding the $O(T_infty + L lg P)$ time steps with the highest processor availability. When $T_1/T_infty gg Padj$ (the job's parallelism dominates the $O(T_infty + L lg P)$-trimmed availability), the job achieves nearly perfect linear speedup. Conversely, when $T_1/T_infty ll Padj$, the asymptotic running time of the job is nearly the length of its critical path.

 slides (pdf)

Olivier Beaumont

Scheduling Divisible Workloads on Heterogeneous Platforms under Bounded Multi-Port Model

Abstract:   In this talk, we discuss complexity issues for scheduling divisible workloads on heterogeneous systems under the bounded multi-port model. To our best knowledge, this paper is the first attempt to consider divisible load scheduling under a realistic communication model, where the master node can communicate simultaneously to several slaves, provided that bandwidth constraints are not exceeded. We concentrate on one round distribution schemes, where a given node starts its processing only once all data has been received. Our main contributions are (i) the proof that processors start working immediately after receiving their work (ii) the study of the optimal schedule in the case of 2 processors and (iii) the proof that scheduling divisible load under the bounded multi-port model is NP-complete. This last result strongly differs from divisible load literature and represents the first NP-completeness result when latencies are not taken into account.

 slides (pdf)

Paulo Detti

Scheduling unreliable jobs on parallel machines

Abstract:   An allocation and sequencing problem is considered in which a set of independent jobs have to be processed by a set of machines. Each job is characterized by a certain success probability and a reward, which is obtained if the job is successfully carried out. When a job fails during processing, the machine is blocked and the jobs subsequently scheduled on that machine are blocked until the end of the unsupervised period. The problem is to assign and sequence the jobs on the machines so that the expected total reward is maximized. Connections with other problems, complexity and algorithmic results are presented. In particular, we propose a polyhedral characterization for the single machine case, a connection to other scheduling problems implying that the problem we consider is strongly NP-hard even with 2 machines, approximation results and an effective upper bound.

 slides (pdf)

Loris Marchal

Offline and online scheduling of concurrent bags-of-tasks on heterogeneous platforms

Abstract:   Scheduling problems are already difficult on traditional parallel machines. They become extremely challenging on heterogeneous clusters, even when embarrassingly parallel applications are considered. In this paper we deal with the problem of scheduling multiple applications, made of collections of independent and identical tasks, on a heterogeneous master-worker platform. The applications are submitted online, which means that there is no a priori (static) knowledge of the workload distribution at the beginning of the execution. The objective is to minimize the maximum stretch, i.e. the maximum ratio between the actual time an application has spent in the system and the time this application would have spent if executed alone. On the theoretical side, we design an optimal algorithm for the offline version of the problem (when all release dates and application characteristics are known before-hand). We also introduce several heuristics for the general case of online applications. On the practical side, we have conducted extensive simulations and MPI experiments, showing that we are able to deal with very large problem instances in a few seconds. Also, the solution that we compute totally outperforms classical heuristics from the literature, thereby fully assessing the usefulness of our approach.

 slides (pdf)

Bruno Gaujal

From Sturmian words to Balanced trees

Abstract:   Many Scheduling problems with frequency constraints are solved optimally by Sturmian words. Sturmian words are binary infinite words with many equivalent definitions: they are aperiodic sequences with complexity n+1, balanced sequences and mechanical words. For problems with a recursive nature, one rather need to consider Sturmian trees. The first natural definition of Sturmian trees is to consider planar trees of complexity n+1 but in doing so, one looses the other two properties. In this talk, we will consider non-ordered trees. In this case, we show that strongly balanced trees are exactly mechanical trees. Moreover we will see that they are also aperiodic trees of minimal complexity, so that the three equivalent definitions of Sturmian words are almost preserved in that case.

 slides (pdf)

Arnaud Legrand

Toward a Fully Decentralized Algorithm for Multiple Bag-of-tasks Application Scheduling on Grids

Abstract:   In this talk, we present a fully decentralized algorithm for fair resource sharing between multiple bag-of-tasks applications in a grid environment. This algorithm is inspired from related work on multi-path routing in communication network. An interesting feature of this algorithm is that it allows the choice of wide variety of fairness criteria and achieves both optimal path selection and flow control. In addition, this algorithm only requires local information at each slave computing tasks and at each buffer of the network links while minimal computation is done by the schedulers. A naive adaptation is unstable and inefficient though. Fortunately, a simple and effective scaling mechanism is sufficient to circumvent this issue. This scaling mechanism is motivated by a careful study of the subtle differences with the classical multi-path routing problem. We prove its efficiency through a detailed analysis of a simple simulation.

 slides (pdf)

Jean-Marc Nicod

Batch Scheduling for Identical Multi-Tasks Jobs on Heterogeneous Platforms

Abstract:   We consider the scheduling of one batch of identical jobs on a grid of heterogeneous computers. Each job of the batch is an application described by a Directed Acyclic Graph (DAG) of tasks without forks(in-tree) and executed independently from the others jobs. Each job is an instance of the same DAG and the tasks of the DAG are typed, i.e. there may be two identical tasks in one job and a task of one type can only be executed on the computers where the corresponding program is installed. The execution resources are distributed and each resource can carry out a set of task types, the installed programs, so several hosts may be able to carry out the same task. The objective function of our problem is to minimize the makespan of the batch execution. An example that matches these definitions is a workflow to process a set of data in several steps on a grid where the softwares installed on the hosts differs: each step could be a filter applied to one or more images and only some filters are available on each host. In this context, we consider the optimization of the schedule depending on the size, from small to large sized batches, on the characteristics of the batches, etc. Different scheduling techniques could be used to schedule such applications: off-line or online, flow oriented, etc. Classical off-line scheduling techniques for DAGs are heuristics, as there is no direct optimal solution to this problem.They just take one job into account so that multiple jobs will be scheduled as if they were just one application, without benefiting from the knowledge that there are several identical jobs nor of the structure of the jobs. Moreover, if the size of the batch is large,some heuristics may become very costly. On-line techniques are usually simple but they do not either take benefit of the identical structure of the jobs. Steady state oriented scheduling techniques provides an optimal solution in this case but for an infinite number of jobs. We compare three scheduling techniques: a simple on-line scheduler, a steady-state scheduling technique and a genetic heuristic based algorithm. The on-line algorithm just schedule the tasks as soon as they are free of their dependencies. The genetic based algorithm start from a list-scheduling solution and improve it by selecting the best individuals from the makespan of their schedule. The steady-state technique generates a periodic schedule from the result of a linear program, built with the constraints that characterize the problem. By using an experimental evaluation based on simulation, we show that the platform architecture and the DAG structure affect the performances of the schedule differently depending on the used algorithm. Then, we propose some adaptations to these scheduling algorithms to improve their performances on the execution of the batch.

 slides (pdf)

Anthony T. Chronopoulos

Game theory based load balanced job allocation in distributed systems

Abstract:   The main goal of our work is to provide fairness to the users and the users' jobs , i.e. all the users and their jobs should experience approximately equal expected response time (expected queuing delay + processing time + any communication time) or be charged approximately equal price for their execution independent of the computers allocated, and we will show that game theory provides a suitable framework for characterizing such schemes. For distributed systems in which all the jobs belong to a single user (single-class), we use a cooperative game to model the load balancing problem which takes the average system information into account (static load balancing). Our solution is based on the Nash Bargaining Solution which provides a Pareto optimal solution for the distributed system and is also a fair solution. We then extend the system model to include jobs from various users (multi-user/multi-class job distributed system) and include pricing to model a Grid system. We use the concept of Nash equilibrium as the solution of our non-cooperative games and derive distributed algorithms for computing it. We also derive a dynamic scheme tries to minimize the expected response time of the entire system and the other tries to minimize the expected response time of the individual users to provide a fair solution.

 slides (pdf)

Henri Casanova

Scheduling Mixed-Parallel Applications with Advance Reservations

Abstract:   In this talk we discuss the scheduling of mixed-parallel applications, which exhibit both task and data parallelism, in advance reservations settings. Both the problem of minimizing application turn-around time and that of meeting a deadline are studied. For each several scheduling algorithms are proposed, some of which borrow ideas from previously published work in non-reservation settings. Algorithms are compared in simulation over a wide range of application and reservation scenarios. The main finding is that schedules computed using the previously published CPA algorithm can be adapted to advance reservation settings, notably resulting in low resource consumption and thus high efficiency.

 slides (ppt)

Florina M. Ciorba

Enhancing self-scheduling algorithms via synchronization and weighting

Abstract:   Existing dynamic self-scheduling algorithms, used to schedule independent tasks on heterogeneous clusters, cannot handle tasks with dependencies because they lack the support for internode communication. In this talk a synchronization mechanism that provides inter-processor communication, is presented to compensate for the above mentioned deficiency. This mechanism enables self-scheduling algorithms to efficiently handle nested loops with dependencies. A weighting mechanism is presented also that significantly improves the performance of dynamic self-scheduling algorithms. Traditionally, the self-scheduling algorithms divide the total number of tasks into chunks and assign them to processors. The weighting mechanism adapts the chunk sizes to the computing power and current run-queue state of the processors. The synchronization and weighting mechanisms are orthogonal, in the sense that they can simultaneously be applied to loops with dependencies. Thus, they broaden the application spectrum of dynamic self-scheduling algorithms and improve their performance. Extensive tests confirm the efficiency of the synchronization and weighting mechanisms and the significant improvement of the synchronized-weighted versions of the algorithms over the synchronized-only versions.

 slides (pdf)

Kiminori Matsuzaki

An Efficient Implementation of Data-Parallel Skeletons on Multicore Processors

Abstract:   Recently, multicore processors are getting widely available. Developing programs that run efficiently on multicore processors is a hard task since the programs should run in parallel. Furthermore, cache memory shared among CPU cores makes the development much more difficult.

 slides (pdf)

Anne Benoit

Mapping skeleton workflows onto heterogeneous platforms to optimize throughput, latency and reliability

Abstract:   Mapping workflow applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline graphs. Several antagonist criteria should be optimized, such as throughput, latency, reliability (or a combination). Typical applications include digital image processing, where images are processed in steady-state mode. In this talk, we study the complexity of various multi-criteria mapping problems for pipeline graphs. For some NP-hard instances of the problem, polynomial bi-criteria heuristics are presented and their relative performance is evaluated through extensive simulations.

 slides (pdf)

Umit V. Catalyurek

Multi-Objective Scheduling of Streaming Workflows

Abstract:   Scheduling, in many application domains, involves the optimization of multiple performance metrics. In this talk, I will present a novel algorithm framework for the multi-objective scheduling of workflows that act on a stream of input data. Our framework focuses on the two performance metrics: latency and throughput, and minimizes the latency of workflows while satisfying strict throughput requirements. We leverage pipelined, task and data parallelism in a coordinated manner to meet these objectives and investigate the benefit of task duplication in alleviating communication overheads in the pipelined schedule for different workflow characteristics. Evaluation using synthetic benchmarks as well as those derived from real applications shows that our algorithm consistently produces lower-latency schedules and meets throughput requirements, even when previously proposed schemes fail.

 slides (ppt)

Larry Carter

Scheduling: Today and Tomorrow

 slides (ppt) slides (pdf)