Hardware-software bipartitioning for dynamically reconfigurable systems

ABSTRACT

The main unique feature of dynamically reconfigurable systems is the ability to time-share the same reconfigurable hardware resources. However, the energy-delay cost associated with reconfiguration must be accounted for during hardware-software partitioning. We propose a method for mapping nodes of an application control flow graph either to software or reconfigurable hardware, explicitly targeting minimization of the energy-delay cost due to both computation and configuration. The addressed problems are energy-delay product minimization, delay-constrained energy minimization, and energy-constrained delay minimization. We show how these problems can be tackled by using network flow techniques, after transforming the original control flow graph into an equivalent network. If there are no constraints, as in the case of the energy-delay product minimization, we are able to generate an optimal solution in polynomial time.

REFERENCES

• 1: C. Cheng and T. Hu, "Maximum concurrent flows and minimum cuts," Algorithmica, vol. 8, 1992.
• 2: Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
• 3: S. Hauck and G. Borriello, "An evaluation of bipartitioning techniques," IEEE Trans. CAD, vol. 18, 1997.
• 4: Huiqun Liu , D. F. Wong, Network flow based circuit partitioning for time-multiplexed FPGAs, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.497-504, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289077]
• 5: Robert P. Dick , Niraj K. Jha, CORDS: hardware-software co-synthesis of reconfigurable real-time distributed embedded systems, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.62-67, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288561]
• 6: Bharat P. Dave, CRUSADE: hardware/software co-synthesis of dynamically reconfigurable heterogeneous real-time distributed embedded systems, Proceedings of the conference on Design, automation and test in Europe, p.22-es, January 1999, Munich, Germany [doi>10.1145/307418.307461]
• 8: Marlene Wan , Hui Zhang , Varghese George , Martin Benes , Arthur Abnous , Vandana Prabhu , Jan Rabaey, Design Methodology of a Low-Energy Reconfigurable Single-Chip DSP System, Journal of VLSI Signal Processing Systems, v.28 n.1-2, p.47-61, May-June 2001 [doi>10.1023/A:1008159121620]
• 9: S. Ogrenci Memik , E. Bozorgzadeh , R. Kastner , M. Sarrafzadeh, A super-scheduler for embedded reconfigurable systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 10: Karam S. Chatha , Ranga Vemuri, Hardware-Software Codesign for Dynamically Reconfigurable Architectures, Proceedings of the 9th International Workshop on Field-Programmable Logic and Applications, p.175-184, August 30-September 01, 1999
• 11: Peter Voigt Knudsen , Jan Madsen, PACE: A Dynamic Programming Algorithm for Hardware/Software Partitioning, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.85, March 18-20, 1996
• 12: Frank Vahid, Modifying Min-Cut for Hardware and Software Functional Partitioning, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.43, March 24-26, 1997
• 13: 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]
• 14: DJPEG Call Graph, http://www.aisee.com/split/index.htm, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Performance

Keywords:
hardware-software partitioning, network flows, reconfigurable systems