Volume 8 Number 1 (Jan. 2013)
Home > Archive > 2013 > Volume 8 Number 1 (Jan. 2013) >
JCP 2013 Vol.8(1): 61-68 ISSN: 1796-203X
doi: 10.4304/jcp.8.1.61-68

Efficient Algorithm for Hardware/Software Partitioning and Scheduling on MPSoC

Honglei Han, Wenju Liu, Wu Jigang, Guiyuan Jiang
 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.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Jul 19, 2019 News!

    Vol 14, No 7 has been published with online version   [Click]

  • Read more>>