关键词: 软硬件划分, 二维增强贪婪算法, 启发式搜索, 关键路径

Abstract: According to the single processor and single ASIC structure in the embedded system，abstract the software-hardware partitioning problem into the MKP（Multiple Knapsack Problem） one.Bring in the two-dimension greedy algorithm to solve the software-hardware problem through the border dimension extending.The algorithm is aiming to minimize the system running time under the satisfaction of the hardware area constraint，power restrict and memory space limit.The complexity of the algorithm is reduced to O（log n·log n）.The algorithm is based on the control data flow diagram（CFG） which is represent the function granularity，abandons the traditional software or hardware oriented method，puts forward a novel initial state selecting method，this method maps the critical nodes to software，others are implemented with hardware，because the searching space is narrowed down，so the running speed of algorithm can be improved more.The experimental results indicate the algorithm is superior to the genetic algorithm and simulating annealing algorithm in running time and stability.

Key words: hardware/software partitioning, two-dimension enhanced greedy algorithm, heuristic search algorithm, critical vertices