• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

J4 ›› 2011, Vol. 33 ›› Issue (9): 57-62.

• 论文 • Previous Articles     Next Articles

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

HAN Honglei,LIU Wenju,WU Jigang,LI Hui   

  1. (1.School of Computer Science and Software,Tianjin Polytechnic University,Tianjin 300387;
    2.State Key Laboratory of Computer Science,Institute of Software,
    Chinese Academy of Sciences,Beijing 100190,China)
  • Received:2011-05-20 Revised:2011-07-26 Online:2011-09-25 Published:2011-09-25

Abstract:

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 execution time, the proposed algorithm assigns different priorities to different tasks according to their outdegree 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.

Key words: MPSoC;task scheduling;hardware/software partitioning;embedded system