多核片上系统的调度与软硬件划分算法

摘要

软硬件协同设计已经成为嵌入式系统开发的主流技术，推动着嵌入式系统向着更高集成度和更高计算能力的方向发展。评价MPSoC性能的指标有很多，如执行时间、硬件面积、功耗等，而诸多性能指标之间都是相互制约的，因此很难得到完全意义上的最优解。虽然每种算法在自己相应的环境中都可以很好地运行，并得到较高的性能，但是由于基准的缺乏，使得不同算法之间很难进行比较。选择其中一个指标作为目标函数，其它指标作为约束条件，这样就可以将问题转化为在约束条件下求目标函数最优解的问题。
　　 软硬件划分与调度是软硬件协同设计的关键环节，是经典的组合优化问题。针对调度与软硬件划分问题提出一种高效的启发式算法。
　　 调度算法根据任务的出度及软件计算时间对任务赋予不同的优先级，出度越大，优先级越高，出度相同的情况下，软件计算时间越大，优先级越高。通过对同一层中的任务赋予不同的优先级，可以使得出度较大或软件计算时间较长的关键任务优先被调度执行，从而降低后续任务的等待时间，最终达到缩短总的执行时间的目的。
　　 划分算法首先寻找关键路径，然后将关键路径上具有最高受益面积比的任务交由硬件去实现。每次迭代更新当前关键路径的调度长度及剩余硬件面积。继续循环，直到剩余的硬件面积不再满足关键路径上的任何一个软件任务所需的硬件面积的要求为止，这样使得硬件面积的使用率比较高。通过改进后的调度算法与软硬件划分算法与已有算法相比，执行时间大约改进38％。