摘要：软硬件划分是软硬件协同设计的关键环节，划分的结果直接影响目标系统的设计质量。因此，对于一个给定的应用程序，为了使得目标系统快速执行且成本低廉，合理的划分策略十分重要。由于单个任务具有多种不同的硬件实现方式，与传统的单一硬件实现方式的软硬件划分问题相比，多选择的软硬件划分更能客观地反映现实应用。这导致问题的求解更具挑战性，它们已被证明是NP完全问题。基于多核处理器片上系统并针对任务图为二叉树的应用，建立了多选择软硬件划分问题的计算模型，并提出了解决该问题的动态规划算法。实验结果表明，当问题规模适中时，所提动态规划算法能够有效地获得精确解，并展示了算法的计算能力与硬件面积限制之间的关系。

关键词：多选择软硬件划分 多核处理器片上系统 二叉树 动态规划算法 

单位：天津工业大学计算机科学与软件学院 天津300387 中国科学院软件所计算机科学国家重点实验室 北京100190 天津大学计算机科学与技术学院 天津300072