A general approach to solving hardware and software partitioning problem based on evolutionary algorithms*

Hardware/software partitioning (HW/SW) is a significant problem in hardware-software co-design, and it is also an NP-hard problem. In order to solve the HW/SW quickly and effectively by evolutionary algorithms, the HW/ SW is firstly regarded as a variant of knapsack problem. Based on a new greedy strategy, a greedy repair and optimization algorithm GROM is proposed to eliminate the infeasible solutions. Subsequently, a general algorithm framework based on discrete evolutionary algorithm for HW/SW problem is proposed. On the basis of the above algorithm framework, genetic algorithm (GA), binary particle swarm optimization (BPSO), binary differential evolution algorithm with hybrid encoding (HBDE) and group theory-based optimization algorithm (GTOA) are used to solve large-scale HW/SW instances. The feasibility and effectiveness of the algorithm framework proposed in the paper are verified by comparing the good and bad of the calculation results of above algorithms, and pointed out that the performance of GTOA and BPSO is better than that of HBDE and GA, they are more suitable for solving large-scale HW/SW problem.