Architectural improvements for field programmable counter arrays: enabling efficient synthesis of fast compressor trees on FPGAs

ABSTRACT

The Field Programmable Counter Array (FPCA) was introduced to improve FPGA performance for arithmetic circuits. An FPCA is a reconfigurable IP core that can be integrated into an FPGA. To exploit the FPCA, a circuit is transformed by merging disparate addition and multiplication operations into large multi-input addition operations, which are synthesized as compressor trees on the FPCA; the remaining portion of the circuit is synthesized on the FPGA. This paper presents a series of architectural improvements to the FPCA that reduce routing delay, increase flexibility and component utilization, and simplify the integration process. Using an FPGA containing six FPCAs, we observed average and maximum speedups of 1.60x and 2.40x on a set of arithmetic benchmarks

REFERENCES

• 1: Altera Corporation, Stratix II Device Handbook, vol. 1 and 2, available online: http://www.altera.com/
• 2: Altera Corporation, Stratix II vs. Virtex-4 Performance Comparison, available online: http://www.altera.com/
• 3: Altera Corporation, Stratix III Device Handbook, vol. 1 and 2, available online: http://www.altera.com/
• 4: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 5: Philip Brisk , Ajay K. Verma , Paolo Ienne , Hadi Parandeh-Afshar, Enhancing FPGA performance for arithmetic circuits, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278565]
• 6: Chen, C.-Y., Chien, S.-Y., Huang, Y.-W., Chen, T.-C., Wang, T.-C., and Chen, L.-G. Analysis and architecture design of variable block-size motion estimation for H.264/AVC, IEEE Trans. Circuits and Systems-I, vol. 53, no. 2, February, 2006, 578--593.
• 7: Cherepacha, D., and Lewis, D. DP-FPGA: an FPGA architecture optimized for datapaths. VLSI Design, vol. 4, no. 4, 1996, 329--343.
• 8: Dadda, L., Some schemes for parallel multipliers, Alta Frequenza, vol. 34, May, 1965, 349--356.
• 9: Frederick, M.T., and Somani, A.K. Multi-bit carry chains for high-performance reconfigurable fabrics. Int. Conf. Field Prog. Logic and Applications (FPL'06) (Madrid, Spain, August 28-30, 2006) 1--6.
• 10: Scott Hauck , Thomas W. Fry , Matthew M. Hosler, High-performance carry chains for FPGA's, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.2, p.138-147, April 2000 [doi>10.1109/92.831434]
• 11: R. Kastner , A. Kaplan , S. Ogrenci Memik , E. Bozorgzadeh, Instruction generation for hybrid reconfigurable systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.605-627, October 2002 [doi>10.1145/605440.605446]
• 12: Kaviani, A., Vranseic, D., and Brown, S. Computational field programmable architecture, IEEE Custom Integrated Circuits, Conf. (CICC'98) (Santa Clara, CA, USA, May 11-14, 1998) 261--264.
• 13: Kuon, I., and Rose, J. Measuring the gap between FPGAs and ASICs. IEEE Trans. Computer-Aided Design, vol. 26, no. 2, February, 2007, 203--215.
• 14: Katarzyna Leijten-Nowak , Jef L. van Meerbergen, An FPGA architecture with enhanced datapath functionality, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611846]
• 15: Mirzaei, S., Hosangadi, A., and Kastner, R. High speed FIR filter implementation using add and shift method, Int. Conf. Computer Design (ICCD'06) (San Jose, CA, USA, October 1-4, 2006).
• 16: Hadi Parandeh-Afshar , Philip Brisk , Paolo Ienne, Efficient synthesis of compressor trees on FPGAs, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
• 17: Juri Põldre , Kalle Tammemäe, Reconfigurable Multiplier for Virtex FPGA Family, Proceedings of the 9th International Workshop on Field-Programmable Logic and Applications, p.359-364, August 30-September 01, 1999
• 18: Sriram, S., Brown, K., Defosseux, R., Moerman, F., Paviot, O., Sundararajan, V., and Gatherer, A. A 64 channel programmable receiver chip for 3G wireless infrastructure, IEEE Custom Integrated Circuits Conf. (CICC'05) (San Jose, CA, USA, September 18-21, 2005) 59--62.
• 19: Paul F. Stelling , Charles U. Martel , Vojin G. Oklobdzija , R. Ravi, Optimal Circuits for Parallel Multipliers, IEEE Transactions on Computers, v.47 n.3, p.273-285, March 1998 [doi>10.1109/12.660163]
• 20: W. J. Stenzel , W. J. Kubitz , G. H. Garcia, A Compact High-Speed Parallel Multiplication Scheme, IEEE Transactions on Computers, v.26 n.10, p.948-957, October 1977 [doi>10.1109/TC.1977.1674730]
• 21: Ajay K. Verma , Paolo Ienne, Automatic synthesis of compressor trees: reevaluating large counters, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 22: A. K. Verma , P. Ienne, Improved use of the carry-save representation for the synthesis of complex arithmetic circuits, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.791-798, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382683]
• 23: Wallace, C.S. A suggestion for a fast multiplier, IEEE Trans. Elec. Computers, vol. 13, February, 1964, 14--17.
• 24: Wang, G., Sivaswamy, S., Ababei, C., Bazargan, K., Kastner, R., and Bozorgzadeh, E. Statistical analysis and design of HARP FPGAs, IEEE Trans. Computer-Aided Design, vol. 25, no. 10, 2006, 2088--2102.
• 25: Weinberger, A. 4:2 carry-save adder module, IBM Technical Disclosure Bulletin, vol. 23, Jan. 1981.
• 26: Xilinx Corporation, Virtex-4 User Guide, available online: http://www.xilinx.com/
• 27: Xilinx Corporation, Virtex-5 User Guide, available online: http://www.xilinx.com/
• 28: Paul S. Zuchowski , Christopher B. Reynolds , Richard J. Grupp , Shelly G. Davis , Brendan Cremen , Bill Troxel, A hybrid ASIC and FPGA architecture, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.187-194, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774600]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

General Terms:
Design, Performance

Keywords:
FPGA, field programmable counter array (FPCA)