School of Computer Science and Software Engineering, Tianjin Polytechnic University, China

---

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 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. Task with higher out-degree possesses higher priority. For the tasks with the same outdegree, 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 a software task lying 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.

Index Terms—Hardware/software partitioning, task scheduling, algorithm, MPSoC

[PDF]

Cite: Honglei Han, Wenju Liu, Wu Jigang, Guiyuan Jiang, " Efficient Algorithm for Hardware/Software Partitioning and Scheduling on MPSoC," Journal of Computers vol. 8, no. 1, pp. 61-68, 2013.