A fast predictive algorithm with idle reduction for heterogeneous system scheduling

作者：Niyom Anan^*; Sophatsathit Peraphon; Lursinsap Chidchanok

来源：Simulation Modelling Practice and Theory, 2016, 63: 83-103.

DOI：10.1016/j.simpat.2016.02.006

• Task graph
• Heterogeneous systems
• Algorithm running time
• Schedule length

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.

• 出版日期2016-4