SMAP: heterogeneous technology mapping for area reduction in FPGAs with embedded memory arrays

ABSTRACT

It has become clear that large embedded configurable memory arrays will be essential in future FPGAs. Embedded arrays provide high-density high-speed implementations of the storage parts of circuits. Unfortunately, they require the FPGA vendor to partition the device into memory and logic resources at manufacture-time. This leads to a waste of chip area for customers that do not use all of the storage provided. This chip area need not be wasted, and can in fact be used very efficiently, if the arrays are configured as large multi-output ROMs, and used to implement logic. In order to efficiently use the embedded arrays in this way, a technology mapping algorithm that identifies parts of circuits that can be efficiently mapped to an embedded array is required. In this paper, we describe such an algorithm. The new tool, called SMAP, packs as much circuit information as possible into the available memory arrays, and maps the rest of the circuit into four-input lookup-tables. On a set of 29 sequential and combinational benchmarks, the tool is able to map, on average, 60 4-LUTs into a single 2-Kbit memory array. If there are 16 arrays available, it can map, on average, 358 4-LUTs to the 16 arrays.

REFERENCES

• 1: XiUnx, Inc., XG~O00 Series (E/L/EX/XL) Field Programmable Gate Arrays vl.0~, Setpember 1996.
• 2: Altera Corporation, Da~abook, June 1996.
• 3: Actel Corporation, Datasheet: 3~OODX Field. Programmable Gate Arrays, 1995.
• 4: Actel Corporation, Actel's Reprogrammable SPGAs, 1996.
• 5: Lattice Semiconductor Corporation, Datasheet: ispLSI and pLSI 6192 High Density Programmable Logic with Dedicated Memory and Register/Counter Modules, July 1996.
• 6: Steven J. E. Wilton , Jonathan Rose , Zvonko G. Vranesic, Architecture of centralized field-configurable memory, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.97-103, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201326]
• 7: S. 3. E. Wilton, J. Rose, and Z. G. Vranesic, "Merecry/logic interconnect flexibility in FPGAs with large embedded memory arrays," in Proceedings of the IEEE 1996 Custom Integrated Circuits Conference, pp. 144- 147, May 1996.
• 8: Steven J. E. Wilton , Jonathan Rose , Zvonko G. Vranesic, Memory-to-memory connection structures in FPGAs with embedded memory arrays, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.10-16, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258307]
• 9: T. Ngai, 3. Rose, and S. J. E. Wilton, "An SRAM- Programmable field-configurable memory," in Proceedings of the IEEE 1995 Custom Integrated Circuits Conference, pp. 499--502, May 1995.
• 10: Michael Hutton , J. P. Grossman , Jonathan Rose , Derek Corneil, Characterization and parameterized random generation of digital circuits, Proceedings of the 33rd annual conference on Design automation, p.94-99, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240537]
• 11: Rajeev Murgai , Masahiro Fujita , Fumiyasu Hirose, Logic synthesis for a single large look-up table, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.415, October 02-04, 1995
• 12: J. He and J. Rose, "Technology mapping for heretogeneous FPGAs,' in Proceedings o.f the A CM Internetional Workshop on Field Programmable Gate Arrays, Feb 1994.
• 13: David Filo , Jerry Chih-Yuan Yang , Frédéric Mailhot , Giovanni De Micheli, Technology mapping for a two-output RAM-based field programmable gate array, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 14: Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127670]
• 15: Rajeev Murgai , Yoshihito Nishizaki , Narendra Shenoy , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic synthesis for programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.620-625, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123421]
• 16: G. D. Micheli and M. Santomauro, "Smile: A computer program for partitioning of programmed logic arrays," Computer-Aided Design, vol. 15, no. 2, pp. 89-97, 1983.
• 17: M. Ciesielski and S. Yang, "Plade: A two-stage PLA decomposition," IEEE Transactions on Computer-Aided Design, vol. 11, no. 8, pp. 943-954, 1992.
• 18: Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996 [doi>10.1145/233539.233540]
• 19: 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.
• 20: E. Sentovich, "SIS: A system for sequential circuit analysis," Tech. Rep. UCB/ERL M92/41, Electronics Research Laboratory, University of California, Berkeley, May 1992.
• 21: Steven Joseph Edward Wilton , Jonathan Rose , Zvenko Vranesic, Architectures and algorithms for field-programmable gate arrays with embedded memory, 1997

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.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout; Placement and routing
  B.8 Performance and Reliability

General Terms:
Algorithms, Design, Performance