HW/SW partitioning techniques for multi-mode multi-task embedded applications

ABSTRACT

An embedded system is called a multi-mode embedded system if it performs multiple applications by dynamically reconfiguring the system functionality. Further, the embedded system is called a multi-mode multi-task embedded system if it additionally supports multiple tasks to be executed in a mode. In this paper, we address an important HW/SW partitioning problem, that is, HW/SW partitioning of multi-mode multi-task embedded applications with timing constraints of tasks. The objective of the optimization problem is to find a minimal total system cost of allocation/mapping of processing resources to functional modules in tasks together with a schedule that satisfies the timing constraints. The key success of solving the problem is closely related to the degree of the amount of utilization of the potential parallelism among the executions of modules. However, due to an inherently excessively large search space of the parallelism, and to make the task of schedulabilty analysis easy, the prior HW/SW partitioning methods have not been able to fully exploit the potential parallel execution of modules. To overcome the limitation, we propose a set of comprehensive HW/SW partitioning techniques which solve the three subproblems of the partitioning problem simultaneously: (1) allocation of processing resources,(2) mapping the processing resources to the modules in tasks, and (3) determining an execution schedule of modules. Specifically, based on a precise measurement on the parallel execution and schedulability of modules, we develop a stepwise refinement partitioning technique for single-mode multi-task applications, which aims to solve the subproblems 1, 2 and 3 effectively in an integrated fashion. The proposed techniques is then extended to solve the HW/SW partitioning problem of multi-mode multi-task applications (i.e., to find a globally optimized allocation/mapping of processing resources with feasible execution schedule of modules).

REFERENCES

• 1: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 2: N. Audsley, A. Burns, M. Richardsons, and W. Wellings, "Hard Real-time Scheduling: The Deadline-monotonic Approach," Proc. IEEE Workshop on Real-time Operating Systems and Software, 1991.
• 3: Sudarshan Banerjee , Nikil Dutt, Efficient Search Space Exploration for HW-SW Partitioning, Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'04), p.122-127, September 08-10, 2004 [doi>10.1109/CODES+ISSS.2004.23]
• 4: F. Vahid and T. D. Le, "Extending the Kernighan-Lin Heuristic for Hardware and Software Functional Partitioning," Journal of Design Automation for Embedded Systems, Vol. 2 1997.
• 5: Junwei Hou , Wayne Wolf, Process Partitioning for Distributed Embedded Systems, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.70, March 18-20, 1996
• 6: R. P. Dick and N. K. Jha, "MOGAC: A Multiobjective Genetic Algorithm for Hardware-Software Cosynthesis of Distributed Embedded Systems," IEEE TCAD, Vol. 17, No. 10, Oct. 1998.
• 7: Youngsoo Shin , Daehong Kim , Kiyoung Choi, Schedulability-driven performance analysis of multiple mode embedded real-time systems, Proceedings of the 37th conference on Design automation, p.495-500, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337556]
• 8: Hyunok Oh , Soonhoi Ha, Hardware-software cosynthesis of multi-mode multi-task embedded systems with real-time constraints, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774817]
• 9: M. T. Schmitz, B. M. Al-Hashimi and P. Eles, "Cosynthesis of Energy-Efficient Multimode Embedded Systems With Consideration of Mode-Execution Probabilities," IEEE TCAD, vol. 24, no. 2, Feb. 2005.
• 10: A. Kalavade and P.A. Subrahmanyam, "Hardware/Software Partitioning for Multifunction Systems," IEEE TCAD, vol. 9, no.9, Sep. 1998.
• 11: Sudarshan Banerjee , Elaheh Bozorgzadeh , Nikil Dutt, Physically-aware HW-SW partitioning for reconfigurable architectures with partial dynamic reconfiguration, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065667]
• 12: B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Tech. Journal, 1970.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design

Keywords:
allocation, binding, co-design, scheduling