Improving synthesis of compressor trees on FPGAs via integer linear programming

ABSTRACT

Multi-input addition is an important operation for many DSP and video processing applications. On FPGAs, multi-input addition has traditionally been implemented using trees of carry-propagate adders. This approach has been used because the traditional lookup table (LUT) structure of FPGAs is not amenable to compressor trees, which are used to implement multi-input addition and parallel multiplication in ASIC technology. In prior work, we developed a greedy heuristic method to map compressor trees onto the general logic of an FPGA using a component called generalized parallel counter (GPC). Although this technique reduced the combinational delay of our circuits, when synthesized onto Altera Stratix-II FPGAs, by 27% on average; however, the area was increased by an average 11%. To further reduce the delay and limit the increase in area, we have developed a new solution to the mapping problem based on integer linear programming. This new approach reduced the delay of the compressor tree by 32% on average and reduced the area by 3% compared to an adder tree.

REFERENCES

• 1: Shahnam Mirzaei , Anup Hosangadi , Ryan Kastner, High speed FIR filter implementation using add and shift method, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117251]
• 2: S. Sriram, K. Brown, R. Defosseux, F. Moerman, O. Paviot, V. Sundararajan, and A. Gatherer, "A 64 channel programmable receiver chip for 3G wireless infrastructure," IEEE Custom Integrated Circuits Conf., San Jose, CA, USA, pp. 59--62, Sept. 18--21, 2005.
• 3: C. Y. Chen, S-Y. Chien, Y-W. Huang, T-C. Chen, T-C. Wang, and L-G. Chen, "Analysis and architecture design of variable block-size motion estimation for H.264/AVC," IEEE Trans. Circuits and Systems-I, Vol. 53, No. 2, pp. 578--593, Feb., 2006.
• 4: L. Dadda, "Some schemes for parallel multipliers," Alta Frequenza, Vol. 34, pp. 349--356, May, 1965.
• 5: 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]
• 6: 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]
• 7: 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
• 8: 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]
• 9: 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]
• 10: 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
• 11: C. S. Wallace, "A suggestion for a fast multiplier," IEEE Trans. Electronic Computers, Vol. 13, pp. 14--17, Feb., 1964.
• 12: 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]
• 13: 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
• 14: Altera, Corp. "The Stratix II device handbook, vol. 1 and 2," available online from http://www.altera.com/.
• 15: Xilinx Corp. "Virtex-4 user guide," available online from http://www.xilinx.com.
• 16: Altera, Corp. "Stratix II vs. Virtex-4 performance comparison," available online from http://www.altera.com/.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.1 Design Styles

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays
      B.7.2 Design Aids

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Adaptable architectures

General Terms:
Design, Performance