Hierarchical decomposition algorithm for hardware/software partitioning

ABSTRACT

This paper proposes a novel fast technique for partitioning a system into hardware and software components and scheduling the resulting components for execution. The technique maps hierarchical task graphs onto a heterogeneous architecture containing a single sequential processing engine for executing software components and programmable logic for implementing hardware components. The technique uses an iterative improvement algorithm to evaluate placement of components in the hardware and software partitions. It also uses a decomposition phase to alter the number and granularity of tasks evaluated. By doing so, the algorithm can perform early evaluations on fewer, coarse grained tasks and only evaluate smaller granularities as needed to achieve the desired execution time of the task system. The suitability of this technique in finding a solution which meets a given timing constraint on the system is evaluated by comparing it to a iterative improvement algorithm on a typical non-hierarchical task graph where the task granularities are fixed. To show robustness of the approach, the comparison is done for a large number of synthetic task graphs and the results are normalized so that statistical analysis can be performed on the large sample set.

REFERENCES

• 1: K. Chatha and R. Vemuri, "An Iterative Algorithm for Hardware-Software Partitioning, Hardware Design Space Exploration and Scheduling," Design Automation for Embedded Systems, vol. 5, pp. 281--193, 2000.
• 2: P. Eles, Z. Peng, K. Kuchcinski, and A. Dobolo, "System level hardware/software partitioning based on simulated annealing and tabu search," Design Automation for Embedded Systems, vol. 2, pp. 5--32, 1997.
• 3: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 4: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 5: R. Dick, Multiobjective Synthesis of Low-Power Real-Time Distributed Embedded Systems, PhD. Dissertation, Princeton University, 2002.
• 6: Sin Ming Loo , B. Earl Wells, Static scheduling in a reconfigurable hardware environment, 2003
• 7: Yana E. Krasteva , Ana B. Jimeno , Eduardo de la Torre , Teresa Riesgo, Straight Method for Reallocation of Complex Cores by Dynamic Reconfiguration in Virtex II FPGAs, Proceedings of the 16th IEEE International Workshop on Rapid System Prototyping (RSP'05), p.77-83, June 08-10, 2005 [doi>10.1109/RSP.2005.45]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
hardware software codesign, hierarchical task graph, partitioning