摘要：软硬件划分与调度是软硬件协同设计的关键环节，是经典的组合优化问题。本文针对调度与软硬件划分问题提出一种高效的启发式算法。调度算法根据任务的出度及软件计算时间对任务赋予不同的优先级，出度越大，优先级越高，出度相同的情况下，软件计算时间越大，优先级越高。划分算法首先寻找关键路径，然后将关键路径上具有最高受益面积比的任务交由硬件去实现。每次迭代更新当前关键路径的调度长度及剩余硬件面积。继续循环，直到剩余的硬件面积不再满足关键路径上的任何一个软件任务所需的硬件面积的要求为止，这样使得硬件面积的使用率比较高。实验表明，该算法对已有算法的改进可达到38％。

关键词：多处理器片上系统 调度 软硬件划分 嵌入式系统 

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