Research On HW/SW Partitioning For Heterogeneous MPSoC Based On Greedy And Simulated Annealing Algorithm

The heterogeneous MPSoC integrates the advantages of different processor cores,and it is considered as the future development trend of embedded computing platform.The design of embedded systems includes hardware (HW) design and software (SW)design. So for, the most popular design method is designing the hardware andsoftware at the same time. According to some recent researches, HW/SW partitioningis the most important step in the design process. Therefore, how to design the HW/SWpartitioning algorithm with high performance is becoming the focus.Greedy algorithm and Simulated Annealing (SA) algorithm are two effectivemethods for HW/SW partitioning. The greedy algorithm has low computationalcomplexity, but it can only get local optimal solution. The SA algorithm can searchthe global optimal solution. However, its computational complexity is higher.According to the characteristics of the hardware/software bi-model and taking thealgorithm of the0/1knapsack problem as a reference, this paper proposes ahardware/software partitioning algorithm which combined the greedy algorithm andthe simulated annealing algorithm to accelerate the convergence speed and improvethe quality of partition solution. The contents are as follows:Aiming at the low quality of partitioning caused by ignoring the communicationcost in the greedy algorithm, this paper proposes an improved greedy algorithm basedon analyzing the communication among tasks and the0-1knapsack problem. First, theinitial solution is calculated by traditional pre-partitioning algorithm. Then, thecommunication cost is brought in the HW/SW partitioning system model. Based onthe initial solution and the ratio of the change of value with change of space, theproposed method does another move. Comparing to the traditional algorithms, theexperimental results show that this method can improve the quality of the partitioningsolution without increasing the computational complexity.To address the problem of slow speed of convergence in the SA algorithm whenit is in the process of global optimization, the paper proposes an improved SAalgorithm after analyzing the convergence conditions and the two cycles of thealgorithm. One of the improvements is improving the movement model to increase theprobability of the movement range in2and3. This improvement can reduce theruntime of outer cycle effectively. The other improvement is designing a new costfunction to improve the efficiency of searching the global optimal solution and reduce the times of inner cycle.In order to verify the above algorithms, the paper programs the algorithms usingthe TGFF tool and C++program description language and does some comparativeanalysis of the algorithm runtime and system time after partitioning which arerestrained by hardware resource. The experimental results show that the proposedalgorithms are better than the algorithms compared. In addition, the advantage is moredistinct in the harsh condition.