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

Abstract

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

HAN Honglei,LIU Wenju,WU Jigang,LI Hui. An Efficient Algorithm of Hardware/Software Partitioning and Scheduling on MPSoC[J]. J4, 2011, 33(9): 57-62.

References

［1］Abdelhalim M B,Habib S ED. An Integrated HighLevel Hardware/Software Partitioning Methodology［J］. Des Autom Embed Syst,2011，15(1):1950.
［2］Wolf W, Fellow. Multiprocessor SystemonChip (MPSoC) Technology［J］. IEEE Transaction on ComputerAided Design of Integrated Circuits And Systems，2008,27(10):17011713.
［3］Boeres C, Rebello V E F. Towards Optimal Static Task Scheduling for Realistic Machine Models: Theory and Practice［J］.The International Journal of High Performance Computing Applications, 2003,17(2):173189.
［4］Kwok Yukwong, Ahmad I. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors［J］.ACM Computing Surveys, 1999, 31(4):406471.
［5］Wu Jigang,Srikanthan T. LowComplex Dynamic Programming Algorithm for Hardware/Software Partitioning［J］. Information Processing Letters，2006,98(2):4146.
［6］Wu Jigang, Srikanthan T, Member S, at al. Algorithmic Aspects of Hardware/Software Partitioning: 1D Search Algorithms［J］. IEEE Transactions on Computers，2010,59(4):532544.
［7］Aviral S,Mohit K,Sanjiv K,et al. Optimal Hardware/Software Partitioning for Concurrent Specification Using Dynamic Programming［C］∥Proc of the IEEE Int’l Conf on VLSI Design, 2000:110113.
［8］Niemann R, Marwedel P. An Algorithm for Hardware/software Partitioning Using Mixed Integer Linear Programming［J］.Partitioning Methods for Embedded Systems, Design Automation for Embedded Systems, 1997,2(2):165193.
［9］Chatha K S,Vemuri R. HardwareSoftware Partitioning and Pipelined Scheduling of Transformative Applications［J］. IEEE Trans on Very Large Scale Integration Systems, 2002,10(3):193208.
［10］Zou Yi,Zhuang Zhenquan, Chen Huanhuan. HWSW Partitioning Based on Genetic Algorithm［C］∥Proc of CEC’04,2004:628633.
［11］Henkel J, Ernst R . An Approach to Automated Hardware/software Partitioning Using a Flexible Granularity That is Driven by HighLevel Estimation Techniques［J］. IEEE Trans on Very Large Scale Integr (VLSI) System, 2001, 9(2):273289.
［12］Karam S C, Ranga V. HardwareSoftware Partitioning and Pipelined Scheduling of Transformative Applications［J］.IEEE Trans on Very Large Scale Integr (VLSI) System, 2002,10(3):193208.
［13］Wiangtong T, Cheung P Y K, Luk W. Comparing Three Heuristic Search Methods for Functional Partitioning in Hardwaresoftware Codesign［J］. Design Automation for Embedded Systems, 2002，6(4):425449.
［14］Chatha K S,Vemuri R. Magellan: Multiway HardwareSoftware Partitioning and Scheduling for Latency Minimization of Hierarchical ControlDataflow Task Graphs［C］∥Proc of the Ninth Int’l Symp Hardware/Software Codesign, 2001:4247.
［15］Wu Jigang, Srikanthan T, Tao Jiao. Algorithmic Aspects for Functional Partitioning and Scheduling in Hardware/Software CoDesign［J］. Design Automation Embedded System, 2008，12(4): 345375.
［16］Youness H, Hassan M, Sakanushi K, et al. A High Performance Algorithm for Scheduling and HardwareSoftware Partitioning on MPSoCs［C］∥Proc of the 4th Int’l Conf on Design & Technology of Integrated Systems in Nanoscal Era, 2009:7176.
［17］Kwok YuKwong, Ahmad I. Benchmarking and Comparison of the Task Graph Scheduling Algorithms［J］.Journal of Parallel and Distributed Computing, 1999,59(3):381422.
［18］Banerjee S, Bozorgzadeh E,Dutt N. PhysicallyAware HWSW Partitioning for Reconfigurable Architectures with Partial Dynamic Reconfiguration［C］∥Proc of the 42nd DAC’05, 2005:335340.