download0 view133
twitter facebook

공공누리This item is licensed Korea Open Government License

Title
Push-Pull: Deterministic Search-Based DAG Scheduling for Heterogeneous Cluster Systems
Author(s)
김상철이승구함재균
Publication Year
2007-11-01
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.
Keyword
Task scheduling; optimization; heterogeneous systems; cluster systems
Journal Title
IEEE transactions on parallel and distributed systems
Citation Volume
18
ISSN
1045-9219
Files in This Item:
There are no files associated with this item.
Appears in Collections:
7. KISTI 연구성과 > 학술지 발표논문
URI
https://repository.kisti.re.kr/handle/10580/13653
http://www.ndsl.kr/ndsl/search/detail/article/articleSearchResultDetail.do?cn=NART56027940
Export
RIS (EndNote)
XLS (Excel)
XML

Browse