Research On Static Task Scheduling Problem For Multicore Systems

Multicore processor emerges as the time require since the performance improvement of the single-core processor has reached the bottleneck. As an important part of the Multi-core technique, the task-scheduling problem which is proved to be NPC (Non-deterministic Polynomial Complete) receives much concern from research community.The Simple List Scheduling (SLS) algorithm is incapable to get desirable schedule solution for scheduling tasks on multi-core processor. This paper will make a deep analysis on the undesirable performance of the SLS algorithm and point out that this algorithm only considers the task priority list for list scheduling and ignores all other graph topological orders which may lead to a better schedule solution. Take the basic idea of taking more graph topological orders into consideration, this paper gives the concepts of macroblock and macroblock topological order, based on which this paper will propose two advanced algorithms with a general designation of the Iterative List Scheduling (ILS) algorithm. One of the ILS algorithms enlarges the graph topological order search space by traversing the macroblock topological orders, the other one gets new graph topological order by swapping two random tasks of the current best graph topological order. In order to get smaller schedule length, the ILS algorithms repeatedly do list scheduling and selects the best schedule solution in the principle of schedule length minimization. Combine the basic thought of the PSO algorithm, the ILS-PSO algorithms are proposed to get smaller schedule length with the cost of higher time complexity. The ILS-PSO algorithms takes several graph topological orders as the initial best solution to avoid trapping in local optimal solution.According to theoretical analysis, it is impossible for the ILS algorithm to get bigger schedule-length than SLS algorithm, as the ILS algorithm considers more graph-topological-order for the procedure of list-scheduling including the task-priority-list. By contrast, the SLS algorithm only considers the task-priority-list.In order to verify the performance improvement from the ILS algorithms to the SLS algorithm, a plenty of sample task graphs with four common structures are generated to draw a comparison between scheduling algorithms. This paper takes the relative size of schedule length as the measurement of the performance these algorithms. Experimental results shows that the ILS algorithms significantly outperforms the SLS algorithm by a considerable margin, the average accelerate ratio exceeds 14.6% and the maximal accelerate ratio reaches 102.8% when communication to computation ratio exceeds 1. Statistical data indicates that the ILS algorithms gets higher performance than the ALS (Advanced List Scheduling) algorithm and the CPOP (Critical Path on Processor) algorithm.