Global resource sharing for synthesis of control data flow graphs on FPGAs

ABSTRACT

In this paper we discuss the global resource sharing problem during synthesis of control data flow graphs for FPGAs. We first define the Global Resource Sharing (GRS) problem. Then, we introduce the Global Inter Basic Block Resource Sharing (GIBBS) technique to solve the GRS problem. We developed five heuristics to solve the GRS problem. The first tries to minimize the number of connections between modules, the second considers the area gain, the third uses the criticality of operations assigned to resources as a measure for deciding on merging any given pair of resources, the fourth tries to capture common resource chains and overlap those to minimize both area and delay, and the fifth is the combination of these heuristics. While applying resource sharing, we also consider the execution frequency of the basic blocks. Using our techniques we synthesized several CDFGs representing applications from MediaBench suite. Our results show that, we can reduce the total area requirement by 44% on average (up to 59%) while increasing the execution time by 6% on average.

REFERENCES

• 1: M. R. Garey and D. S. Johnson. Computers and Intractability. W.H. Freeman and Company, 1999.
• 2: Maya B. Gokhale , Janice M. Stone, NAPA C: Compiling for a Hybrid RISC/FPGA Architecture, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.126, April 15-17, 1998
• 3: Malay Haldar , Anshuman Nayak , Alok Choudhary , Prith Banerjee, A system for synthesizing optimized FPGA hardware from MATLAB, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 4: Jeff Hammes , Bob Rinker , Wim Bohm , Walid Najjar , Bruce Draper , Ross Beveridge, Cameron: High Level Language Compilation for Reconfigurable Systems, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.236, October 12-16, 1999
• 5: T. Kim, N. Yonezawa, J.W.S. Liu, and C.L. Liu. A scheduling algorithm for conditional resource sharing - a hierarchical reduction approach. TCAD, 13(4):425--438, 1994.
• 6: Scott A. Mahlke , David C. Lin , William Y. Chen , Richard E. Hank , Roger A. Bringmann, Effective compiler support for predicated execution using the hyperblock, Proceedings of the 25th annual international symposium on Microarchitecture, p.45-54, December 01-04, 1992, Portland, Oregon, United States
• 7: P. Moisset, J. Park, and P. Diniz. Very high-level synthesis of control and datapath structure for reconfigurable logic devices, October 1999. Workshop on Compiler and Architecture Support for Embedded Systems.
• 8: S. Raje , R. A. Bergamaschi, Generalized resource sharing, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.326-332, November 09-13, 1997, San Jose, California, United States
• 9: 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
• 10: M. Wazlowski, L. Agarwal, T. Lee, A. Smith, E. Lam, P. Athanas, H. Silverman, and S. Gosh. Prism-ii compiler and architecture, 1993. IEEE Workshop on FPGAs for Custom Computing Machines.
• 11: Zhi Alex Ye , Andreas Moshovos , Scott Hauck , Prithviraj Banerjee, CHIMAERA: a high-performance architecture with a tightly-coupled reconfigurable functional unit, Proceedings of the 27th annual international symposium on Computer architecture, p.225-235, June 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.0 General

Keywords:
FPGA, control data flow graph, resource sharing