ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 Push-Pull: Deterministic Search-Based DAG Scheduling for Heterogeneous Cluster Systems
Cited 42 time in scopus Download 3 time Share share facebook twitter linkedin kakaostory
저자
김상철, 이승구, 함재균
발행일
200711
출처
IEEE Transactions on Parallel and Distributed Systems, v.18 no.11, pp.1489-1502
ISSN
1045-9219
출판사
IEEE
DOI
https://dx.doi.org/10.1109/TPDS.2007.1106
협약과제
07MW2400, 자동차 센서노드용 초소형 운영체제 개발, 마평수
초록
Consider 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 running times, the Push-Pull algorithm performs well, achieving similar or better results than all of the other algorithms being compared. © 2007 IEEE.
KSP 제안 키워드
DAG scheduling, Heterogeneous cluster systems, NP-hard, Optimization problem, PULL algorithm, Search Space, Search-based, Task scheduling algorithm, heterogeneous systems, push-pull, search method