Field Programmable Compressor Trees: Acceleration of Multi-Input Addition on FPGAs

ABSTRACT

Multi-input addition occurs in a variety of arithmetically intensive signal processing applications. The DSP blocks embedded in high-performance FPGAs perform fixed bitwidth parallel multiplication and Multiply-ACcumulate (MAC) operations. In theory, the compressor trees contained within the multipliers could implement multi-input addition; however, they are not exposed to the programmer. To improve FPGA performance for these applications, this article introduces the Field Programmable Compressor Tree (FPCT) as an alternative to the DSP blocks. By providing just a compressor tree, the FPCT can perform multi-input addition along with parallel multiplication and MAC in conjunction with a small amount of FPGA general logic. Furthermore, the user can configure the FPCT to precisely match the bitwidths of the operands being summed. Although an FPCT cannot beat the performance of a well-designed ASIC compressor tree of fixed bitwidth, for example, 9×9 and 18×18-bit multipliers/MACs in DSP blocks, its configurable bitwidth and ability to perform multi-input addition is ideal for reconfigurable devices that are used across a variety of applications.

REFERENCES

• 1: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 2: Altera Corporation. 2006. Stratix II performance and logic efficiency analysis. White paper. September. http://www.altera.com/.
• 3: Altera Corporation. 2008a. Stratix II device handbook. http://www.altera.com/.
• 4: Altera Corporation. 2008b. Stratix III device handbook. http://www.altera.com/.
• 5: Altera Corporation. 2008c. Stratix IV device handbook. http://www.altera.com/.
• 6: Jean-Luc Beuchat , Arnaud Tisserand, Small Multiplier-Based Multiplication and Division Operators for Virtex-II Devices, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.513-522, September 02-04, 2002
• 7: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 8: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 9: Philip Brisk , Ajay K. Verma , Paolo Ienne , Hadi Parandeh-Afshar, Enhancing FPGA performance for arithmetic circuits, Proceedings of the 44th annual Design Automation Conference, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278565]
• 10: Alessandro Cevrero , Panagiotis Athanasopoulos , Hadi Parandeh-Afshar , Ajay K. Verma , Philip Brisk , Frank K. Gurkaynak , Yusuf Leblebici , Paolo Ienne, Architectural improvements for field programmable counter arrays: enabling efficient synthesis of fast compressor trees on FPGAs, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA [doi>10.1145/1344671.1344699]
• 11: Chen, C.-Y., Chien, S.-Y., Huang, Y.-W., Chen, T.-C., Wang, T.-C., and Chen, L.-G. 2006. Analysis and architecture design of variable block-size motion estimation for H.264/AVC. IEEE Trans. Circ. Syst.-I 53, 578--593.
• 12: Cherepacha, D. and Lewis, D. 1996. DP-FPGA: An FPGA architecture optimizated for datapaths. VLSI Des. 4, 329--343.
• 13: Cosoroaba, A. and Rivoallon, F. 2006. Achieving higher system performance with the Virtex-5 family of FPGAs. White paper: Xilinx Corporation. July. http://www.xilinx.com/.
• 14: Dadda, L. 1965. Some schemes for parallel multipliers. Alta Frequenza 34, 349--356.
• 15: Frederick, M. T. and Somani, A. K. 2006. Multi-bit carry chains for high performance reconfigurable fabrics. In Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--6.
• 16: 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]
• 17: C. H. Ho , P. H. W. Leong , W. Luk , S. J. E. Wilton , S. Lopez-Buedo, Virtual Embedded Blocks: A Methodology for Evaluating Embedded Elements in FPGAs, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.35-44, April 24-26, 2006 [doi>10.1109/FCCM.2006.71]
• 18: Kaviani, A., Vranisec, D., and Brown, S. 1998. Computational field programmable architecture. In Proceedings of the IEEE Custom Integrated Circuits Conference. 261--264.
• 19: Kuon, I. and Rose, J. 2007. Measuring the gap between FPGAs and ASICs. IEEE Trans. Comput.-Aided Des. 26, 203--215.
• 20: 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
• 21: 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]
• 22: Mirzaei, S., Hosangadi, A., and Kastner, R. 2006. FPGA implementation of high speed FIR filters using add and shift method. In Proceedings of the International Conference on Computer Design. 308--313.
• 23: Vojin G. Oklobdzija , David Villeger, Improving multiplier design by using improved column compression tree and optimized final adder in CMOS technology, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.2, p.292-301, June 1995 [doi>10.1109/92.386228]
• 24: Hadi Parandeh-Afshar , Philip Brisk , Paolo Ienne, A novel FPGA logic block for improved arithmetic performance, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA [doi>10.1145/1344671.1344698]
• 25: Hadi Parandeh-Afshar , Philip Brisk , Paolo Ienne, Efficient synthesis of compressor trees on FPGAs, Proceedings of the 2008 Asia and South Pacific Design Automation Conference, January 21-24, 2008, Seoul, Korea
• 26: Hadi Parandeh-Afshar , Philip Brisk , Paolo Ienne, Improving synthesis of compressor trees on FPGAs via integer linear programming, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany [doi>10.1145/1403375.1403680]
• 27: Parandeh-Afshar, H., Brisk, P., and Ienne, P. 2009. Scalable and low cost design approach for variable block size motion estimation. In Proceedings of the International Symposium on VLSI Design Automation and Test.
• 28: 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
• 29: Sriram, S., Brown, K., Defosseux, R., Moerman, F., Paviot, O., Sundararajan, V., and Gatherer, A. 2005. A 64 channel programmable receiver chip for 3G wireless infrastructure. In Proceedings of the IEEE Custom Integrated Circuits Conference. 59--62.
• 30: Paul F. Stelling , Vojin G. Oklobdzija, Design strategies for optimal hybrid final adders in a parallel multiplier, Journal of VLSI Signal Processing Systems, v.14 n.3, p.321-331, Dec. 1996 [doi>10.1007/BF00929625]
• 31: 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]
• 32: Verma, A. K., Brisk, P., and Ienne, P. 2008. Data-Flow transformations to maximize the use of carry-save representation in arithmetic circuits. IEEE Trans. Comput.-Aided Des. 27, 1761--1774.
• 33: Wallace, C. S. 1964. A suggestion for a fast multiplier. IEEE Trans. Elec. Comput. 13, 14--17.
• 34: Xilinx Corporation. 2008a. Virtex-5 FPGA XtremeDSP design considerations. http://www.xilinx.com/.
• 35: Xilinx Corporation. 2008b. Virtex-5 user guide. http://www.xilinx.com/.
• 36: 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.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

General Terms:
Algorithms, Performance

Keywords:
Field Programmable Compressor Tree (FPCT), Field Programmable Gate Array (FPGA), compressor tree