A novel FPGA logic block for improved arithmetic performance

ABSTRACT

To improve FPGA performance for arithmetic circuits, this paper proposes a new architecture for FPGA logic cells that includes a 6:2 compressor. The new cell features additional fast carry-chains that concatenate adjacent compressors and can be routed locally without the global routing network. Unlike previous carry-chains for binary and ternary addition, the carry chain used by the new cell only spans 2 logic blocks, which significantly improves the delay of multi-input addition operations mapped onto the FPGA. The delay and area overhead that arises from augmenting a traditional FPGA logic cell with the new compressor structure is minimal. Using this new cell, we observed an average speedup in combinational delay of 1.41x compared to adder trees synthesized using ternary adders

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, 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
• 5: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 6: 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]
• 7: 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.
• 8: Cherepacha, D., and Lewis, D. DP-FPGA: an FPGA architecture optimized for datapaths. VLSI Design, vol. 4, no. 4, 1996, 329--343.
• 9: Jason Cong , Hui Huang , Xin Yuan, Technology mapping and architecture evalution for k/m-macrocell-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.3-23, January 2005 [doi>10.1145/1044111.1044113]
• 10: Dadda, L., Some schemes for parallel multipliers, Alta Frequenza, vol. 34, May, 1965, 349--356.
• 11: Fadavi-Ardekani, J. M x N Booth encoded multiplier generator using optimized Wallace trees. IEEE Trans. VLSI Systems, vol. 1., no. 2, June, 1993, 120--125.
• 12: 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.
• 13: Radhika S. Grover , Weijia Shang , Qiang Li, A faster distributed arithmetic architecture for FPGAs, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503054]
• 14: 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]
• 15: Hu, Y., and He, L. Private communication. June 8, 2007.
• 16: Yu Hu , Satyaki Das , Steve Trimberger , Lei He, Design, synthesis and evaluation of heterogeneous FPGA with mixed LUTs and macro-gates, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 17: 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]
• 18: 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.
• 19: 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.
• 20: Ohsang Kwon , Kevin Nowka , Earl E. Swartzlander, Jr., A 16-Bit by 16-Bit MAC Design Using Fast 5: 3 Compressor Cells, Journal of VLSI Signal Processing Systems, v.31 n.2, p.77-89, June 2002 [doi>10.1023/A:1015333103608]
• 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. High speed FIR filter implementation using add and shift method, Int. Conf. Computer Design (ICCD '06) (San Jose, CA, USA, October 1-4, 2006).
• 23: H. Mora Mora , J. Mora Pascual , J. L. Sanchez Romero , F. Pujol Loopez, Partial Product Reduction Based on Look-Up Tables, Proceedings of the 19th International Conference on VLSI Design held jointly with 5th International Conference on Embedded Systems Design, p.399-404, January 03-07, 2006 [doi>10.1109/VLSID.2006.130]
• 24: 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
• 25: Parandeh-Afshar, H., Brisk, P., and Ienne, P. Improving Synthesis of Compressor Trees on FPGAs via Integer Linear Programming, to appear: Design, Automation and Test in Europe Conference and Exhibition (DATE'08) (Munich, Germany, March 10-14, 2008).
• 26: 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
• 27: Santoro, M., and Horowitz, M. A pipelined 64x64b iterative array multiplier, IEEE Int. Solid-State Circuits Conf. (ISSCC'88) (February 17-19, 1988) 36--37, 290.
• 28: Song, P., and De Micheli, G. Circuit and architecture trade-offs for high speed multiplication, IEEE Journal of Solid-State Circuits, vol. 26, no. 9, September, 1991, 1184--1198.
• 29: 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.
• 30: 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]
• 31: 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]
• 32: 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]
• 33: E. E. Swartzlander, Parallel Counters, IEEE Transactions on Computers, v.22 n.11, p.1021-1024, November 1973 [doi>10.1109/T-C.1973.223639]
• 34: Junhyung Um , Taewhan Kim, Layout-aware synthesis of arithmetic circuits, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513971]
• 35: 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
• 36: 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]
• 37: A. K. Verma , P. Ienne, Improving XOR-Dominated Circuits by Exploiting Dependencies between Operands, Proceedings of the 2007 conference on Asia South Pacific design automation, p.601-608, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.358052]
• 38: Wallace, C.S. A suggestion for a fast multiplier, IEEE Trans. Elec. Computers, vol. 13, February, 1964, 14--17.
• 39: Weinberger, A. 4:2 carry-save adder module, IBM Technical Disclosure Bulletin, vol. 23, Jan. 1981.
• 40: Xilinx Corporation, Virtex-4 User Guide, available online: http://www.xilinx.com/
• 41: Xilinx Corporation, Virtex-5 User Guide, available online: http://www.xilinx.com/
• 42: 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

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic

General Terms:
Design, Performance

Keywords:
6.2 compressor, FPGA, arithmetic circuits, carry-chain, compressor tree, multi-operand addition