Design space exploration for field programmable compressor trees

ABSTRACT

The Field Programmable Compressor Tree (FPCT) is a programmable compressor tree (e.g., a Wallace or Dadda Tree) intended for integration in an FPGA or other reconfigurable device. This paper presents a design space exploration (DSE) method that can be used to identify the best FPCT architecture for a given set of arithmetic benchmark circuits; in practice, an FPGA vendor can use the design space exploration to tailor the FPCT to meet the needs of the most important benchmark circuits of the vendor's largest-volume clients. One novel feature of the DSE is the introduction of a metric called I/O utilization; we found that I/O utilization has a strong correlation with both the critical path delay and area of the benchmark circuits under study. Pruning the search space using I/O utilization allowed us to reduce significantly the number of FPCTs that must be synthesized and evaluated during the DSE, while giving high confidence that the best architectures are still explored. The DSE was applied to seven small-to-medium range benchmark circuits; one FPCT architecture was found that was 30% faster than the second best in terms of critical path delay, and only 3.34% larger than the smallest.

REFERENCES

• 1: Ahmed, E., and Rose, J. The effect of LUT and cluster size on deep-submicron FPGA performance and density. IEEE Trans. VLSI, vol. 12, no. 3, March, 2004, 288--298.
• 2: Altera Corporation. Stratix II vs. Virtex-4 Performance Comparison. Available online: http://www.altera.com/
• 3: Ansaloni, G., Bonzini, P., and Pozzi, L. Design and architectural exploration of expression-grained reconfigurable arrays, IEEE Symposium on Application-Specific Processors, Anaheim, CA, USA, June 8-9, 2008.
• 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: 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]
• 8: Chen, C-Y., et al.. 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.
• 9: Dadda, L., Some schemes for parallel multipliers, Alta Frequenza, vol. 34, May, 1965, 349--356.
• 10: Scott Hauck , Thomas W. Fry , Matthew M. Hosler , Jeffrey P. Kao, The chimaera reconfigurable functional unit, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.2, p.206-217, February 2004 [doi>10.1109/TVLSI.2003.821545]
• 11: Ian Kuon , Jonathan Rose, Area and delay trade-offs in the circuit and architecture design of 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.1344695]
• 12: 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.
• 13: David Lewis , Elias Ahmed , Gregg Baeckler , Vaughn Betz , Mark Bourgeault , David Cashman , David Galloway , Mike Hutton , Chris Lane , Andy Lee , Paul Leventis , Sandy Marquardt , Cameron McClintock , Ketan Padalia , Bruce Pedersen , Giles Powell , Boris Ratchev , Srinivas Reddy , Jay Schleicher , Kevin Stevens , Richard Yuan , Richard Cliff , Jonathan Rose, The Stratix II logic and routing architecture, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046195]
• 14: Mirzaei, S., Hosangadi, A., and Kastner, R. High speed FIR filter implementation using add and shift method, Int. Conf. Computer Design, San Jose, CA, USA, October 1-4, 2006.
• 15: 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
• 16: 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]
• 17: 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., San Jose, CA, USA, September 18-21, 2005, 59--62.
• 18: 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]
• 19: 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
• 20: 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]
• 21: Wallace, C. S. A suggestion for a fast multiplier, IEEE Trans. Elec. Computers, vol. 13, February, 1964, 14--17.
• 22: Xilinx Corporation. Virtex-5 user guide. Available online: http://www.xilinx.com/
• 23: Ye, A. G., and Rose, J. Using bus-based connections to improve field-programmable gate array density for implementing datapath circuits. IEEE Trans. VLSI, vol. 14, no. 5, May, 2006, 462--473.
• 24: Sami Yehia , Nathan Clark , Scott Mahlke , Krisztiàn Flautner, Exploring the design space of LUT-based transparent accelerators, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086301]

INDEX TERMS

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

General Terms:
Performance

Keywords:
design space exploration (dse), field programmable compressor tree (fpct)