Optimization procedure for algorithms of task scheduling in high performance heterogeneous distributed computing systems

AbstractIn distributed computing, the schedule by which tasks are assigned to processors is critical to minimizing the execution time of the application. However, the problem of discovering the schedule that gives the minimum execution time is NP-complete. In this paper, a new task scheduling algorithm called Sorted Nodes in Leveled DAG Division (SNLDD) is introduced and developed for HeDCSs with consider a bounded number of processors. The main principle of the developed algorithm is to divide the Directed Acyclic Graph (DAG) into levels and sort the tasks in each level according to their computation size in descending order. To evaluate the performance of the developed SNLDD algorithm, a comparative study has been done between the developed SNLDD algorithm and the Longest Dynamic Critical Path (LDCP) algorithm which is considered the most efficient existing algorithm. According to the comparative results, it is found that the performance of the developed algorithm provides better performance than the LDCP algorithm in terms of speedup, efficiency, complexity, and quality. Also, a new procedure called Superior Performance Optimization Procedure (SPOP) has been introduced and implemented in the developed SNLDD algorithm and the LDCP algorithm to minimize the sleek time of the processors in the system. Again, the performance of the SNLDD algorithm outperforms the existing LDCP algorithm after adding the SPOP procedure