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

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 opti...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2007-11, Vol.18 (11), p.1489-1502
Main Authors: Sang Cheol Kim, Sunggu Lee, Hahm, J.
Format: Article
Language:English
Subjects:
Algorithms
Bandwidth
Cluster Systems
Clustering algorithms
Costs
Heterogeneous Systems
Heuristic algorithms
Iterative algorithms
Optimization
Optimization methods
Processor scheduling
Schedules
Scheduling
Scheduling algorithm
Search methods
Searching
Strategy
Studies
Task Scheduling
Tasks
Wide area networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2007.1106