A pipelined binary tree as a case study on designing efficient circuits for an FPGA in a bram aware design

ABSTRACT

Designing circuits for FPGAs involves challenges often distinct from designing circuits for ASICs. We describe efforts to convert a pattern counting circuit architecture, based on a pipelined binary tree and originally designed for ASIC implementation, into a circuit suitable for FPGAs. The original architecture, when mapped to a Spartan 3e FPGA, could process 10 million patterns per second and handle up to 4,096 patterns. The modified architecture could instead process 100 million patterns per second and handle up to 32,768 patterns, representing a 10x performance improvement and a 4x efficiency improvement. The redesign involved partitioning large memories into smaller ones at the expense of redundant control logic. Through this and other case studies, design patterns may emerge that aid designers in building high-performance efficient circuits for FPGAs

REFERENCES

• 1: Anderson, J., F. Najm. Active Leakage Power Optimization for FPGAs. IEEE Transactions on Computer-Aided Design of Integrated Cirucits and Systems, Vol 25. No 3. 2006.
• 2: Michael J. Beauchamp , Scott Hauck , Keith D. Underwood , K. Scott Hemmert, Embedded floating-point units in FPGAs, 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.1117204]
• 3: Giancarlo Beraudo , John Lillis, Timing optimization of FPGA placements by logic replication, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775885]
• 4: Jason Cong , Yean-Yow Hwang, Simultaneous depth and area minimization in LUT-based FPGA mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.68-74, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201322]
• 5: DeHon DeHon , Joshua Adams , Michael DeLorimier , Nachiket Kapre , Yuki Matsuda , Helia Naeimi , Michael Vanier , Michael Wrighton, Design Patterns for Reconfigurable Computing, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.13-23, April 20-23, 2004
• 6: Ken Eguro , Scott Hauck, Armada: timing-driven pipeline-aware routing for FPGAs, 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.1117227]
• 7: Li H., W. Mak, S. Katkoori. LUT-Based FPGA Technology Mapping for Power Minization with Optimal Depth. Proceedings of the International ACM Symposium on Field-Programmable Gate Arrays (FPGA) 2001.
• 8: Roman Lysecky , Susan Cotterell , Frank Vahid, A fast on-chip profiler memory, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513928]
• 9: Amit Singh , Malgorzata Marek-Sadowska, Efficient circuit clustering for area and power reduction in 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.503058]
• 10: Deshanand P. Singh , Stephen D. Brown, Integrated retiming and placement for field programmable gate arrays, 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.503059]
• 11: Welson Sun , Michael J. Wirthlin , Stephen Neuendorffer, Combining module selection and resource sharing for efficient FPGA pipeline synthesis, 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.1117228]
• 12: Russell Tessier , Vaughn Betz , David Neto , Thiagaraja Gopalsamy, Power-aware RAM mapping for FPGA embedded memory blocks, 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.1117229]
• 13: Xilinx, Inc. Spartan 3e 1600. http://www.xilinx.com/, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Performance

Keywords:
FPGA