ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

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

상세정보

학술지 Task Scheduling Algorithm using Minimized Duplications in Homogeneous Systems
Cited 43 time in scopus Download 1 time Share share facebook twitter linkedin kakaostory
저자
신광식, 차명진, 장문석, 정진하, 윤오완, 최상방
발행일
200808
출처
Journal of Parallel and Distributed Computing, v.68 no.8, pp.1146-1156
ISSN
0743-7315
출판사
Elsevier
DOI
https://dx.doi.org/10.1016/j.jpdc.2008.04.001
협약과제
08MS1700, 멀티코아 CPU 및 MPU기반 크롯플랫폼 게임기술 개발, 양광호
초록
For fine grain task graphs, duplication-based scheduling algorithms are generally more efficient than list and cluster-based algorithms. However, most duplication-based heuristics try to duplicate all possible ancestor nodes of a given join node, in order to reduce the earliest start time (EST) of the join node, even though these ancestor nodes have already been allocated in previous steps. Thus, these duplication heuristics inevitably induce redundant duplications, which lead to the superfluous consumption of resources and generally deteriorate the scheduling result in the case of a bounded number of processors. When scheduling algorithms are used on an unbounded number of processors, the required number of processors grows excessively with the size of the task graph, thereby limiting the practicality of these algorithms for large task graphs. In this paper, we propose a novel algorithm designed to allocate join nodes without redundant duplications. In the proposed algorithm, if the ancestor nodes of a join node are duplicated when scheduling the join node, the original allocations of these ancestor nodes are removed using a very efficient method. The performance of the proposed algorithm, in terms of its normalized schedule length and efficiency, is compared with that of some of the recently proposed algorithms. The proposed algorithm generates better or comparable schedules with minimized duplication. Specifically, the simulation results show that it is most useful on a bounded number of processors. © 2008 Elsevier Ltd. All rights reserved.
키워드
Distributed architectures, Load balancing and task assignment, Parallel processors, Scheduling and task partitioning
KSP 제안 키워드
Distributed architecture, Load balancing, Novel algorithm, Parallel processor, Scheduling and task partitioning, Task scheduling algorithm, cluster-based, duplication-based scheduling, fine grain, homogeneous systems, normalized schedule length