An efficient ACO-based algorithm for scheduling tasks onto dynamically reconfigurable hardware using TSP-likened construction graph

摘要

Any complex application can be realized as a graph of dependent tasks, and scheduling these tasks onto a limited number of computational resources while satisfying their dependencies is a well-known NP-complete optimization problem. For microprocessor systems, several algorithms have been proposed that can efficiently find suboptimal schedules. A solution for dynamically reconfigurable hardware (DRHW), however, is more complicated, as the time and complexity of reconfiguration has to be scheduled as well. The reconfiguration overhead in these systems is significant, and quickly becomes a crucial factor in real-world applications. In this paper, a meta-heuristic method known as Feasibility Assured TSP-likened Scheduling (FATS) is proposed in which the scheduling problem is translated into a construction graph, similar to Travelling Sales Person (TSP) problem, such that it would be able to benefit from the advantages of Ant Colony Optimization (ACO) algorithm. Moreover, by exploiting such a construction graph, precedence constraints and system limitations are satisfied beforehand, the feasibility of solutions is assured, while avoiding the costly solution repair operations. To demonstrate the performance of the proposed method, it was tested on several synthetic and real-world benchmark task graphs and the results were compared with a selection of classic and state-of-the-art algorithms. A comprehensive set of experiments was performed to evaluate the method in terms of efficiency, execution time, scalability and reliability. In brief, the results of experiments on benchmarks showed that on average FATS outperforms HPSO-GA and BGA by 8.4 % and 12.2 % respectively in terms of the quality of the solutions, and its run-time is far less than the state-of-the-art algorithms. Also, on synthetic graphs the makespan improvements of the solutions generated by FATS and GA over the List scheduler are on average 11.2 % and 6.8 % better respectively; and from the execution-time point of view, our method is 27.37 % faster than GA. Moreover, the results confirm that the proposed method is scalable for large task graphs and its reliability is superior to other compared algorithms.