Optimization Method for Scheduling Length and the Number of Processors on Multiprocessor Systems

摘要

A high performance algorithm for scheduling of tasks aims to optimize the overall execution time of the program by properly allocating and arranging the execution order of the tasks on the multiprocessor systems such that the precedence constraints among the tasks are preserved. In this paper, we propose an algorithm to get the optimality of scheduling for large problem sizes and optimize the target system. The algorithm uses geometrical analysis based on an Artificial Intelligence (AI) technique to produce the optimal solution for the allocation/scheduling problem, also it uses pruning techniques to reduce the size of the search space and to minimize the number of processors that used. The viability and potential of the proposed algorithm is demonstrated by extensive experimental results (more than 180 random task graphs) to conclude that the proposed algorithm is an efficient scheme to obtain the optimality with hard and large problem of task graphs.