Research On HW/SW Partitioning For Reconfigurable Computing System Based On Simulated Annealing Algorithm

Reconfigurable computing system is typically composed of general purposeprocessors and programmable devices, and it has limited hardware resource andsoftware resource. Tasks can be implemented in software resource or hardwareresource, but task execution time and power consumption may be significantdifference. To take full advantage of hardware resource and to meet the demandscenarios, Hardware/software partitioning is required. Hardware/software partitioningis a key step and research focus in the design of reconfigurable computing system.Hardware/software partitioning is a combinatorial optimization problem, whichhas been proved to be NP-hard, the present study usually uses the heuristic algorithmto solve this problem, and the study focuses on improving the algorithm’sconvergence rate and solution quality. This paper presents improved heuristicalgorithm to improving convergence rate and solution quality for two type sets oftasks.In the case of small and medium size set of tasks, this paper uses SimulatedAnnealing(SA) algorithm to solve hardware/software partitioning problem, which is aused heuristic algorithm, but SA has slow convergence speed and poor solutionquality. So this paper uses an improved disturbance model and annealing schedule toimprove its convergence speed. For algorithm’s poor solution quality, this paper givesa new cost function. The new cost function guide the algorithm’s search in thesolution space, which avoid the blindness of the search, so the method can quicklyfind near optimal solutions and improve the solution quality.In the case of large size set of tasks, this paper combines both the improvedgreedy algorithm and SA to solve the hardware/software partitioning. In a large taskset, the method which simply uses a heuristic algorithm to slove partitioning problemwill lead to increased running time and poor solution. For these problems, firstly,thispaper uses the improved greedy algorithm to initialize the task set. Greedy algorithmtime complexity is low and easy to implement, and algorithm’s solution can be closeto the global approximate optimal solution region. Secondly, the SA is be used tocontinue the search. SA algorithm has global search ability, and can finally get theglobal approximate optimal solution.To validate the algorithm, this paper uses a common tool--TGFF to generaterandom test task set, and achieve the proposed algorithm and comparison algorithms in the same platform. Experiments show that the proposed algorithm has less runningtime than the comparison algorithms, and has improved solution quality in this smalland middle scale of the task. In a large task set, the running time of the proposedalgorithm, although has longer than the greedy algorithm, but has better solutionquality; and the proposed algorithm produces better solutions and reduces the runningtime when compared to the SA.