Mapping arbitrary logic functions into synchronous embedded memories for area reduction on FPGAs

ABSTRACT

This work describes a new mapping technique, RAM-MAP, that identifies parts of circuits that can be efficiently mapped into the synchronous embedded memories found on field programmable gate arrays (FPGAs). Previous techniques developed for mapping into asynchronous embedded memories cannot be used because modern FPGAs do not have asynchronous embedded memories. After technology mapping, an area-prediction cost function is used to guide the selection of logic cones to be placed in embedded memories. Extra logic is added to compensate for missing asynchronous functionality on the synchronous memories. Experiments conducted on Altera's Stratix device family indicate that this embedded memory mapping technique can provide an average area reduction of 6.2% and up to 32.5% on a large set of industrial designs. A small architecture change that increases the size of the FPGA fabric by 0.05% can increase the average area reduction to 14.1% and up to 59.1% on the same design set.

REFERENCES

• 1: Altera Corporation, Altera Product Catalog, May 2005.
• 2: Xilinx Corporation, Virtex Series FPGAs Product Matrix, May 2005.
• 3: Steven J. E. Wilton, SMAP: heterogeneous technology mapping for area reduction in FPGAs with embedded memory arrays, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.171-178, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275137]
• 4: S. J. E. Wilton, "Heterogeneous technology mapping for area reduction in FPGAs with embedded memory arrays," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 19, pp. 56--68, January 2000.
• 5: Jason Cong , Songjie Xu, Technology mapping for FPGAs with embedded memory blocks, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.179-188, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275138]
• 6: Manoj A. Kumar , Jayaram Bobba , V Kamakoti, MemMap: Technology Mapping Algorithm for Area Reduction in FPGAs with Embedded Memory Arrays Using Reconvergence Analysis, Proceedings of the conference on Design, automation and test in Europe, p.20922, February 16-20, 2004
• 7: Frank Heile , Andrew Leaver, Hybrid product term and LUT based architectures using embedded memory blocks, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.13-16, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296415]
• 8: R. Hitchcock, G. Smith, and D. Cheng, "Timing analysis of computer-hardware," IBM Journal of Research and Development, pp. 100--105, January 1983.
• 9: C. Leiserson, F. Rose, and J. Saxe, Optimizing Synchronous Circuitry, 1983.
• 10: C. Leiserson and J. Saxe, Retiming Synchronous Circuitry, 1991.
• 11: J. Cong and Y. Ding, "Flowmap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, pp. 1--12, January 1994.
• 12: D. Singh, V. Manohararajah, and S. Brown, "Two-stage physical synthesis for FPGAs," Custom Integrated Circuits Conference (CICC), September 2005. To appear.
• 13: Altera Corporation, Stratix Device Handbook (Complete Two-Volume Set), July 2005.
• 14: Valavan Manohararajah , Gordon R. Chiu , Deshanand P. Singh , Stephen D. Brown, Difficulty of predicting interconnect delay in a timing driven FPGA CAD flow, Proceedings of the 2006 international workshop on System-level interconnect prediction, March 04-05, 2006, Munich, Germany [doi>10.1145/1117278.1117280]
• 15: Altera Corporation, Application Note 210: Converting Memory from Asynchronous to Synchronous for Stratix and Stratix GX Designs, November 2002.
• 16: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies
      B.7.2 Design Aids
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance