A dynamically constrained genetic algorithm for hardware-software partitioning

ABSTRACT

In this article, we describe the application of an enhanced genetic algorithm to the problem of hardware-software codesign. Starting from a source code written in a high level language our algorithm determines, using a dynamically-weighted fitness function, the most interesting code parts of the program to be implemented in hardware, given a limited amount of resources, in order to achieve the greatest overall execution speedup. The novelty of our approach resides in the tremendous reduction of the search space obtained by specific optimizations passes that are conducted on each generation. Moreover, by considering different granularities during the evolution process, very fast and effective convergence (in the order of a few seconds) can thus be attained. The partitioning obtained can then be used to build the different functional units of a processor well suited for a large customization, thanks to its architecture that uses only one instruction, Move.

REFERENCES

• 1: Marnix Arnold , Henk Corporaal, Designing domain-specific processors, Proceedings of the ninth international symposium on Hardware/software codesign, p.61-66, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371677]
• 2: Vincenzo Catania , Michele Malgeri , Marco Russo, Applying Fuzzy Logic to Codesign Partitioning, IEEE Micro, v.17 n.3, p.62-70, May 1997 [doi>10.1109/40.591657]
• 3: Henk Corporaal, Microprocessor Architectures: From VLIW to Tta, John Wiley & Sons, Inc., New York, NY, 1997
• 4: R. P. Dick and N. K. Jha. MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(10):920--935, October 1998.
• 5: P. Eles, K. Kuchcinski, Z. Peng, and A. Doboli. System level hardware/software partioning based on simulated annealing and tabu search. Design Automation for Embedded Systems, 2:5--32, 1997.
• 6: 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]
• 7: R. Gupta and G. D. Micheli. System-level synthesis using re-programmable components. In Proc. European Design Automation Conference, pages 2--7, August 1992.
• 8: J. Harkin, T. M. McGinnity, and L. Maguire. Genetic algorithm driven hardware-software partitioning for dynamically reconfigurable embedded systems. Microprocessors and Microsystems, 25(5):263--274, 2001.
• 9: J. Henkel and R. Ernst. High-level estimation techniques for usage in hardware/software co-design. In ASP-DAC, pages 353--360, 1998.
• 10: Jörg Henkel , Rolf Ernst, An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.2, p.273-290, April 2001 [doi>10.1109/92.924041]
• 11: Jan Hoogerbrugge , Henk Corporaal, Transport-Triggering versus Operation-Triggering, Proceedings of the 5th International Conference on Compiler Construction, p.435-449, April 07-09, 1994
• 12: 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
• 13: Marisa López-Vallejo , Juan Carlos López, On the hardware-software partitioning problem: System modeling and partitioning techniques, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.269-297, July 2003 [doi>10.1145/785411.785412]
• 14: Roman Lysecky , Frank Vahid, A Study of the Speedups and Competitiveness of FPGA Soft Processor Cores using Dynamic Hardware/Software Partitioning, Proceedings of the conference on Design, Automation and Test in Europe, p.18-23, March 07-11, 2005 [doi>10.1109/DATE.2005.38]
• 15: H. Oudghiri and B. Kaminska. Global weighted scheduling and allocation algorithms. In European Conference on Design Automation, pages 491--495, March 1992.
• 16: J.-M. Renders and H. Bersini. Hybridizing genetic algorithms with hill-climbing methods forglobal optimization: two possible ways. In Proc. of the First IEEE Conference on Evolutionary Computation, volume 1, pages 312--317, June 1994.
• 17: V. Srinivasan , S. Radhakrishnan , R. Vemuri, Hardware/software partitioning with integrated hardware design space exploration, Proceedings of the conference on Design, automation and test in Europe, p.28-35, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 18: Gianluca Tempesti , Pierre-Andre Mudry, A Move Processor for Bio-Inspired Systems, Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware, p.262-271, June 29-July 01, 2005 [doi>10.1109/EH.2005.3]
• 19: Frank Vahid , Daniel D. Gajski, Incremental hardware estimation during hardware/software functional partitioning, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.3, p.459-464, Sept. 1995 [doi>10.1109/92.407006]
• 20: Frank Vahid , Daniel D. Gajski , Jie Gong, A binary-constraint search algorithm for minimizing hardware during hardware/software partitioning, Proceedings of the conference on European design automation, p.214-219, September 19-23, 1994, Grenoble, France
• 21: T. Wiangtong. Hardware/Software Partitioning And Scheduling For Reconfigurable Systems. PhD thesis, Imperial College London, February 2004.
• 22: T. Wiangtong, P. Y. Cheung, and W. Luk. Comparing three heuristic search methods for functional partitioning in hardware-software codesign. Design Automation for Embedded Systems, 6(4):425--449, July 2002.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Systems specification methodology

General Terms:
Algorithms, Design

Keywords:
TTA processor, constrained hardware-software partitioning, genetic algorithm