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

An Efficient Algorithm of Hardware/Software Partitioning and Scheduling on MPSoC

作　　者：韩红蕾[1,2] 刘文菊[1,2] 武继刚[1,2] 李慧[1,2] 

机构地区：[1]天津工业大学计算机科学与软件学院,天津300387 [2]中国科学院软件所计算机科学国家重点实验室,北京100190

出　　处：《计算机工程与科学》2011年第9期57-62,共6页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60970016)

摘　　要：软硬件划分与调度是软硬件协同设计的关键环节,是经典的组合优化问题。本文针对调度与软硬件划分问题提出一种高效的启发式算法。调度算法根据任务的出度及软件计算时间对任务赋予不同的优先级,出度越大,优先级越高,出度相同的情况下,软件计算时间越大,优先级越高。划分算法首先寻找关键路径,然后将关键路径上具有最高受益面积比的任务交由硬件去实现。每次迭代更新当前关键路径的调度长度及剩余硬件面积。继续循环,直到剩余的硬件面积不再满足关键路径上的任何一个软件任务所需的硬件面积的要求为止,这样使得硬件面积的使用率比较高。实验表明,该算法对已有算法的改进可达到38%。Hardware/software （HW/SW） partitioning and task scheduling are the crucial steps of HW/SW co-design. It is very difficult to achieve the optimal solution as both scheduling and partitioning are combinatorial optimization problems. In this paper a heuristic solution is proposed for scheduling and partitioning on the multi-processor system on chips （MPSOC）. In order to minimize the overall execu- tion time, the proposed algorithm assigns different priorities to different tasks according to their out-de- gree and the software execution time. The higher the out-degree, the higher the priority. For the tasks with the same out-degree, the higher the software execution time, the higher the priority. The proposed algorithm initially searches for the critical path in the task graph, and then assigns the task with the highest benefit-to-area ratio to hardware implementation. The critical path and the available hardware area are updated during the iteration. The whole calculation process works until the available hardware area is not enough to implement any software task in the critical path. As a result, the hardware area is utilized as many as possible. Simulation results show that, the proposed algorithm can reduce the overall execution time up to by 38% in comparison to the latest work.

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

分 类 号：TP302[自动化与计算机技术—计算机系统结构]