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

摘要： 针对嵌入式系统中的单处理器和单ASIC体系结构，将软硬件划分问题抽象为MKP模型，通过扩展其边界的维数，引入二维的贪婪算法来解决软硬件划分问题。算法旨在满足硬件面积约束、功耗约束和存储空间需求约束的前提下使系统的运行时间最优，算法的时间复杂度降低到O（log n·log n）。算法基于代表功能块粒度的控制数据流图（CFG），摒弃了传统的面向软件或硬件的方法，给出了一种新的选择初始状态的方法，该方法将关键节点映射到软件，其余的用硬件实现，因缩小了算法的搜索空间，从而进一步提高了算法的运行速度。最后进行对比实验，实验结果证明该算法在运行时间和稳定性方面均优于遗传算法和模拟算法。

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