An efficient lightweight algorithm for scheduling tasks onto dynamically reconfigurable hardware using graph-oriented simulated annealing

Scheduling complex applications as task graphs on finite computational resources assuring task interdependencies is a well-known NP-complete optimization problem. This problem is well-addressed for microprocessor systems but for Dynamically Reconfigurable Hardware (DRHW) systems in which, in addition to tasks, the reconfiguration time and complexity also have to be scheduled; this problem is more complicated. DRHW reconfiguration overhead is considerable and can be crucial for real-world applications. To deal with this overhead, in this paper, a meta-heuristic method named Graph-Oriented Simulated Annealing (GOSA) is proposed. By introducing an innovative graph and solution structures called schedule graphs, and also some controlling functions which are inherited from the nature of the problem, the proposed method adapts itself to the characteristics of the problem. This helps the algorithm to adjust its exploration and exploitation speed and accuracy according to the requirements of the given problem and consequently find high-quality solutions quickly. 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. The method is comprehensively evaluated by performing numerous experiments in terms of execution time, makespan, scalability, and reliability. The results of the experiments on benchmarks show that in terms of the quality of the solutions, GOSA outperforms BGA, HPSO-GA, and FATS by 17%, 13%, and 5%, respectively, and its execution time is considerably less than all competing algorithms. Moreover, according to the experiments done on synthetic graphs, the makespan of the solutions generated by GOSA, Genetic Algorithm (GA), and the Gxhaustive Search over the List Scheduler are improved on average by 7.2%, 8.1%, and 19.1%, respectively. The most significant achievement of the proposed method is its execution time which is 31 times faster than GA. Finally, the results confirm that the proposed method is scalable for large task graphs, and its reliability is superior.

Automated summary

In this paper, a meta-heuristic method called GOSA is proposed to address the scheduling problem in DRHW systems. By introducing innovative graph and solution structures, along with controlling functions inherited from the nature of the problem, the proposed method is able to quickly find high-quality solutions. Experimental results show that GOSA outperforms other algorithms in terms of solution quality and execution time.