Hardware/software partitioning with multi-version implementation exploration

ABSTRACT

Hardware/software partitioning is an increasingly common technique that maps critical regions of a software application into custom hardware to achieve application speedup. Most previous partitioning approaches assume that each application region has only a single hardware implementation. However, code regions typically can be implemented as many different versions that tradeoff performance and area, as in the case of a loop that can be unrolled by different amounts. We introduce a new formulation of hardware/software partitioning that integrates multiple versions of region implementations, improving performance by more than 27% on average compared to partitioning with a single implementation. We present an optimal ILP solution, and introduce an efficient heuristic that achieves solutions within 0% to 8% of the optimal while running in less than one second for large problem sizes.

REFERENCES

• 1: Chatha, K. and Vemuri, R. 2000. An iterative algorithm for partitioning, hardware design space exploration and scheduling of hardware-software systems. Design Automation for Embedded Systems Journal, No. 5, August 2000, pp 281--293,.
• 2: Karam S. Chatha , Ranga Vemuri, MAGELLAN: multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs, Proceedings of the ninth international symposium on Hardware/software codesign, p.42-47, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371671]
• 3: CriticalBlue. http://www.criticalblue.com.
• 4: EEMBC. http://www.eembc.org.
• 5: Eles, P., Peng, Z., Kuchchinski, K., and Doboli, A. 1997. System level hardware/software partitioning based on simulated annealing and tabu search. Journal on Design Automation for Embedded Systems, Vol. 2, No. 1, pp. 5--32.
• 6: Ernst, R. and Henkel, J. 1992. Hardware-software codesign of embedded controllers based on hardware extraction. In Proceedings of the International Workshop on Hardware/Software Codesign (CODES).
• 7: J. Grode , P. V. Knudsen , J. Madsen, Hardware resource allocation for hardware/software partitioning in the LYCOS system, Proceedings of the conference on Design, automation and test in Europe, p.22-27, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 8: Gupta, R. and De Micheli, G. 1992. System-level synthesis using reprogrammable components. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pp. 2--7.
• 9: C. Haubelt , J. Teich , K. Richter , R. Ernst, System Design for Flexibility, Proceedings of the conference on Design, automation and test in Europe, p.854, March 04-08, 2002
• 10: Jörg Henkel, A low power hardware/software partitioning approach for core-based embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.122-127, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309896]
• 11: ILOG CPLEX. http://www.ilog.com/products/cplex/
• 12: Asawaree Kalavade , Edward A. Lee, A global criticality/local phase driven algorithm for the constrained hardware/software partitioning problem, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 13: Asawaree Kalavade , P. A. Subrahmanyam, Hardware/software partitioning for multi-function systems, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.516-521, November 09-13, 1997, San Jose, California, United States
• 14: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 15: 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]
• 16: Emre Ozre , Andy P. Nisbet , David Gregg, Fine-Tuning Loop-Level Parallelism for Increasing Performance of DSP Applications on FPGAs, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.273-274, April 20-23, 2004
• 17: Pellerin, D. and Thibault, S. 2006. Evaluating hardware acceleration strategies using C-to-hardware tools. XCell Journal, Issue 58, pp. 16--18.
• 18: Yanbing Li , Tim Callahan , Ervan Darnell , Randolph Harr , Uday Kurkure , Jon Stockwood, Hardware-software co-design of embedded reconfigurable architectures, Proceedings of the 37th conference on Design automation, p.507-512, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337559]
• 19: Byoungro So , Mary W. Hall , Pedro C. Diniz, A compiler approach to fast hardware design space exploration in FPGA-based systems, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 20: 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
• 21: Stitt, G. 2008. Hardware/software partitioning with multi-version implementation exploration. Technical Report, February 2008. University of Florida.
• 22: Greg Stitt , Roman Lysecky , Frank Vahid, Dynamic hardware/software partitioning: a first approach, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775896]
• 23: Greg Stitt , Frank Vahid , Gordon McGregor , Brian Einloth, Hardware/software partitioning of software binaries: a case study of H.264 decode, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084905]
• 24: 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]
• 25: XPRES Compiler. http://www.tensilica.com/html/xpres.html.
• 26: Yamada, T., Kataoka, S., and Watanabe, K. 2002. Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Information Processing Society of Japan Journal, Vol. 43, No. 9, pp. 2864--2870.

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
fpga, hardware/software codesign, hardware/software partitioning, synthesis