Authors: Shaikhah AlEbrahim Imtiaz Ahmad
Publish Date: 2016/11/09
Volume: 73, Issue: 6, Pages: 2313-2338
Abstract
Efficient scheduling of tasks in heterogeneous computing systems is of primary importance for highperformance execution of programs The programs are to be considered as multiple sequences of tasks that are presented as directed acyclic graphs DAG Each task has its own execution timeline that incorporates into multiple processors Moreover each edge on the graph represents constraints between the sequenced tasks In this paper we propose a new list–scheduling algorithm that schedules the tasks represented in the DAG to the processor that best minimizes the total execution time by taking into consideration the restriction of crossover between processors This objective will be achieved in two major phases a computing priorities of each task that will be executed and b selecting the processor that will handle each task The first phase priorities computation focuses on finding the best execution sequence that minimizes the makespan of the overall execution In listscheduling algorithm the quality of the solution is very sensitive to the priority assigned to the tasks Therefore in this paper we include an enhanced calculation of weight that is used in the ranking equation for determining the priority of tasks The second phase processor selection primarily focuses on allocating a processor that is a best fit for each task to be executed In this paper we enhance the processor selection by introducing a randomized decision mechanism based on a threshold which decides whether the task be assigned to the processor with the lowest execution time or to the processor that produces the lowest finish time This mechanism considers a balanced combination of the local and global optimal results to explore the search space efficiently to optimize the overall makespan The proposed algorithm is evaluated on different randomly generated DAGs and results are compared with the wellknown existing approaches to show the effectiveness of the proposed algorithm in reducing the makespan of execution The experiment’s results show improvement in the makespan that reaches up to 6–7
Keywords: