Resource sharing in pipelined CDFG synthesis

ABSTRACT

Efficient use of limited available resources on an FPGA remains a crucial problem for synthesizing pipelined designs. Resource sharing addresses this challenge. In this paper, we propose resource sharing techniques that can be incorporated into an automated synthesis flow to generate pipelined designs. Given a synthesized pipelined design, we create a direct relationship between available time slack on modules and the multiplexing overhead due to sharing. This flexibility is maximally exploited without violating any throughput constraints. We propose different techniques to address resource sharing problems of varying restrictions. Specifically, we propose an optimal algorithm for Constant-Slack Resource Sharing and a heuristic for the general Intra-Pipeline Stage Resource Sharing. On an average the demand on arithmetic functional units can be reduced by 39.5% for a set of benchmarks from the multimedia domain using our resource sharing technique.

REFERENCES

• 1: Adam Kaplan , Philip Brisk , Ryan Kastner, Data communication estimation and reduction for reconfigurable systems, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775987]
• 2: Heidi Ziegler , Byoungro So , Mary Hall , Pedro C. Diniz, Coarse-Grain Pipelining on Multiple FPGA Architectures, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.77, September 22-24, 2002
• 3: Seda Ogrenci Memik , Gokhan Memik , Roozbeh Jafari , Eren Kursun, Global resource sharing for synthesis of control data flow graphs on FPGAs, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775985]
• 4: Wakabayashi, K. and T. Yoshimura. A Resource Sharing and Control Synthesis Method for Conditional Branches. in IEEE International Conference on Computer Aided Design. 1989.
• 5: Kim, T., et al., A Scheduling Algorithm for Conditional Resource Sharing - A Hierarchical Reduction Approach. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 1994. 13(4): p. 425--438.
• 6: 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
• 7: Jason Cong , Yiping Fan , Guoling Han , Xun Yang , Zhiru Zhang, Architectural Synthesis Integrated with Global Placement for Multi-Cycle Communication, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.536, November 09-13, 2003 [doi>10.1109/ICCAD.2003.35]
• 8: Deming Chen , Jason Cong , Yiping Fan, Low-power high-level synthesis for FPGA architectures, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871541]
• 9: Sumit Gupta , Nikil Dutt , Rajesh Gupta , Alex Nicolau, SPARK: A High-Lev l Synthesis Framework For Applying Parallelizing Compiler Transformations, Proceedings of the 16th International Conference on VLSI Design, p.461, January 04-08, 2003
• 10: Mei, B., et al. DRESC: A Retargetable Compiler for Coarse-Grained Reconfigurable Architectures. in International Symposium on Field Programmable Logic. 2002.
• 11: 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