.png){kind=icon}
.png){kind=icon}
Return
A fast predictive algorithm with idle reduction for heterogeneous system scheduling
.png){kind=icon}
PRE
AI
DOI：10.1016/j.simpat.2016.02.006.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A heterogeneous task scheduling algorithm called Predict and Arrange Task Scheduling (PATS) algorithm was proposed to achieve a lower bound time complexity with minimum schedule length. Two major steps were introduced, i.e. earliest finish time with level-based task scheduling and idle slot reduction. In the first step, tasks are scheduled according to their predicted earliest finish time from the candidate task list and their dependencies. Scheduling is performed one level at a time starting from top level and transcend downward. In the second step, the idle time slots in each processing unit are minimized. Two sets of experiments were designed to evaluate the merits of proposed algorithm. The first experiment involved the task graphs used by other methods. These graphs are all synthesized. The second experiment concerned the task graphs derived from real world applications such as montage work flow, molecular dynamic code. The experimental results showed that the PATS algorithm yielded better average schedule length ratio, running time, and efficiency than the compared algorithms. (C) 2016 Elsevier B.V. All rights reserved.
Keywords:
Task graph
Heterogeneous systems
Algorithm running time
Schedule length
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.6
Papers:
2.6K
Citations:
4.8K