翟庆雷，朱晓斌

(1. 河北地质大学 信息工程学院，河北 石家庄 050031；2. 石家庄文化传媒学校，河北，石家庄 050000)

0 引言

随着嵌入式系统的广泛应用，软硬件协同设计已成为一个重要的研究问题。硬件部分执行速度快，但是成本费用较高，花费的资源较多；软件部分虽然执行速度较慢，但成本花费较低，操作相对灵活。合理地把嵌入式系统中的组件根据需求进行软、硬件协同划分执行，对整个系统的性能将有很大的提升，因此软硬件划分（hardware/software partitioning，HW/SW）已成为软硬件协同设计中的一个重要问题。

近年来，基于启发式算法求解大规模HW/SW问题逐渐成为了一个研究热点。例如Arato等人[1]提出了一个求解HW/SW问题的2D搜索启发式算法，该算法利用了HW/SW问题特点，因而能够快速地找到高质量的解。Wu等人[2]将HW/SW问题看成带有通信成本的扩展 0-1背包问题，提出了求解该问题的一个 1D搜索启发式算法。该方法不仅提高了算法的性能，而且降低了算法的时间复杂度。Wang等人[3]提出了HEUR算法，并利用它给出了求解HW/SW问题的一种新方法。该方法首先忽略通信成本，将HW/SW问题看作是一个标准 0-1背包问题，求得其解作为原问题的一个潜在解；然后，再根据通信成本对潜在解进行调整，从而得到HW/SW的一个满足约束条件的可行解。虽然HEUR算法比1D搜索启发式算法[2]在解的质量上得到了很大提升，但是利用禁忌搜索对解作进一步的优化处理，在求解大规模HW/SW 实例时也是非常耗时的。正是由于HW/SW 的重要性和困难性，如何快速高效地求解该问题是一个值得研究与探讨的重要问题。……