Push-Pull: Deterministic Search-Based DAG Scheduling for Heterogeneous Cluster Systems

Authors: Sang Cheol Kim, Sunggu Lee and Jaegyoon Hahm - Korea

Complete Citation

• Sang Cheol Kim, Sunggu Lee and Jaegyoon Hahm. Push-Pull: Deterministic Search-Based DAG Scheduling for Heterogeneous Cluster Systems. IEEE Transactions on Parallel and Distributed Computing, 18(11), 2007.

Abstract

Consider directed acyclic graph (DAG) scheduling for a large heterogeneous system, which consists of processors with varying processing capabilities and network links with varying bandwidths. The search space of possible task schedules for this problem is immense. One possible approach for this optimization problem, which is NP-hard, is to start with the best task schedule found by a fast deterministic task scheduling algorithm and then iteratively attempt to improve the task schedule by employing a general random guided search method. However, such an approach can lead to extremely long search times, and the solutions found are sometimes not significantly better than those found by the original deterministic task scheduling algorithm. In this paper, we propose an alternative strategy, termed Push-Pull, which starts with the best task schedule found by a fast deterministic task scheduling algorithm and then iteratively attempts to improve the current best solution using a deterministic guided search method. Our simulation results show that given similar runtimes, the Push-Pull algorithm performs well, achieving results similar to or better than all of the other algorithms being compared.

Annotations

• Start with a cost program for workflow computations: each task in the workflow has a cost associated with each processor, and the output from that task may be transmitted to any other processor for an additional associated cost.
• Place all tasks on processors and minimize the makespan time.

• Employs an iterative Push-Pull approach to improve makespan time until convergence.
• Push operations increase parallelism where beneficial by pushing jobs to other processors.
• Pull operations reduce parallelism where beneficial by stacking jobs on the same processor, reducing transmission costs.
• Push-Pull is thus a deterministic, computationally simple scheduling algorithm.
• Uses simulation to compare the Push-Pull approach to 6 other algorithms.
• Push-pull results beat other algorithms by small margins.

Related Work

• HEFT

-- JustinWozniak - 31 Oct 2007