TechTalks from event: IEEE IPDPS 2011

Note 1: Only plenary sessions (keynotes, panels, and best papers) are accessible without requiring log-in. For other talks, you will need to log-in using the email you registered for IPDPS 2011. Note 2: Many of the talks (those without a thumbnail next to the their description below) are yet to be uploaded. Some of them were not recorded because of technical problems. We are working with the corresponding authors to upload the self-recorded versions here. We sincerely thank all authors for their efforts in making their videos available.

SESSION 26: Scheduling

  • Efficient Parallel Scheduling of Malleable Tasks Authors: Peter Sanders (University of Karlsruhe, Germany); Jochen Speck (KIT, Germany)
    We give an O(n + minfn; mg log m) work algorithm for scheduling n tasks with ?exible amount of parallelism on m processors, provided the speedup functions of the tasks are concave. We give ef?cient parallelizations of the algorithm that run in polylogarithmic time. Previous algorithms were sequential and required quadratic work. This is in some sense a best-possible result since the problem is NP-hard for more general speedup functions.
  • Offline Scheduling of Multi-threaded Request Streams on a Caching Server Authors: Veronika Rehn-Sonigo (University of Franche-Comté, France); Denis Trystram (University of Grenoble, France); Fréd&
    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 makespan). 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 ?rst 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 ?xed cache sizes and we provide a formulation as dynamic program as well as bounds for inapproximation. We propose polynomial time approximation algorithms for some variants and analyze their approximation ratios. Finally, we also devise some heuristics and present experimental results.
  • Tight Analysis of Relaxed Multi-Organization Scheduling Algorithms Authors: Daniel Cordeiro (Grenoble University, France); Pierre-François Dutot (Grenoble University, France); Gregory Mounié
    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 MultiOrganization Scheduling Problem (MOSP) models an environment where organizations providing both resources and jobs tolerate a bounded degradation on the makespan of their own jobs in order to minimize the makespan over the entire platform. More precisely, the technical contributions are the following. First, we improve the existing inapproximation bounds for this problem proving that what was previously though as not polynomially approximable (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 inaproximability 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 ?rst (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 makespan. Both algorithms are ef?cient since their performance ratio correspond to the Pareto optimal solutions of the previously de?ned instances.
  • Scheduling Functional Heterogeneous Systems with Utilization Balancing Authors: Yuxiong He (Microsoft Research, USA); Jie Liu (Microsoft Research, USA); Hongyang Sun (Nanyang Technological University, Singap
    Heterogeneous systems become popular in both client and cloud. A parallel program can incur operations on multiple processing resources such as CPU, GPU, and vector processor units. This paper investigates scheduling problems on functionally heterogeneous systems with the objective of minimizing the completion time of parallel jobs. We ?rst present performance bounds of online scheduling and show that any online algorithm is at best around (K + 1)-competitive with respect to job completion time, where K is the total number of resource types. There exist ”bad” jobs that prevent any online algorithms from obtaining good interleaving of heterogeneous tasks. This lower bound suggests that the relative performance of online algorithms versus an of?ine optimal could degrade linearly as types of heterogeneous resources increase. The limitation of online scheduling motivates our study of how additional of?ine or lookahead information can help improve scheduling performance. We propose a Multi-Queue Balancing algorithm (MQB) that effectively transforms the problem of minimizing completion time to one of maximizing utilization of heterogeneous resources. It promotes interleaving of heterogeneous tasks through balancing the task queues of different types. Our simulation results suggest that MQB reduces the execution time of online greedy algorithms up to 40% over various workloads and outperforms other of?ine schemes in most cases. Furthermore, MQB can use limited and approximated of?ine information to improve scheduling decisions.