Chortle: a technology mapping program for lookup table-based field programmable gate arrays

ABSTRACT

Field Programmable Gate Arrays are new devices that combine the versatility of a Gate Array with the user-programmability of a PAL. This paper describes an algorithm for technology mapping of combinational logic into Field Programmable Gate Arrays that use lookup table memories to realize combinational functions. It is difficult to map into lookup tables using previous techniques because a single lookup table can perform a large number of logic functions, and prior approaches require each function to be instantiated separately in a library. The new algorithm, implemented in a program called Chortle uses the fact that a K-input lookup table can implement any Boolean function of K-inputs, and so does not require a library-based approach. Chortle takes advantage of this complete functionality to evaluate all possible decompositions of the input Boolean network nodes. It can determine the optimal (in area) mapping for fanout-free trees of combinational logic. In comparisons with the MIS II technology mapper, on MCNC-89 Logic Synthesis benchmarks Chortle achieves superior results in significantly less time. 1

REFERENCES

• Bake90: S. Baker,"AMD: Mach CMOS PLD a 'breakthrough'", Electronic Engineering Times, No. 581, March 12 1990 p. 8.
• Berg88: Ft.A. Bergamaschi, "Automatic Synthesis and Technology Mapping of Combinational Logic," Proc. ICCAD 88, Nov 1988, pp.466-469.
• Berk88: M. Berkelaar, J. Jess , "Technology Mapping for Standard Cell Generators", Proc. ICCAD 88, Nov 1988, pp. 470-473.
• Detj87: E.Detjens et. al, "Technology Mapping in MIS", Proc. ICCAD 87, Nov 1987, pp. 116-119.
• ElGa89: A. E1 Carnal, et. ed, "An Architecture for Electrically Corrfigurable Gate Arrays," IEEE JSSC Vol. 24, No. 2, April 1989, pp. 394-398.
• Fran91: Ft. J. Francis, "Ph.D. Thesis in preparation," University of Toronto, Department of Electrical Engineering.
• Hsie88: H. Hsleh, et. al "A 9000-Gate User-Programmable Gate Array," Proc. 1988 CICC, May 1988, pp. 15.3.1 - 15.3.7.
• Keut87: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• Lisa87: Ft. Lisaa~ke, F. Brglez, G. Kedem, "McMAP: A Fast Technology Mapping Procedure for Multi-Level Logic Synthesis," Proc. ICCD, pp. 252-256, October 1988.
• Marr89: C. Marr, "Logic Array Beats Development Time Blues," Electronic System Design Magazine, Nov. 1989, pp. 38-42.
• Ples89: Plessey Semiconductor ERA60100 preliminary data sheet.
• Rose89: J.S. Ftose, R.J. Francis, P. Chow, and D. Lewis, "The Effect of Logic Block Complexity on Area of Programmable Gate Arrays," Proc. 1989 CICC, May 1989, pp. 5.3.1-5.:3.5.
• Wong89: S.C. Wong, et. al, "A ~;000-Gate CMOS EPLD with Multiple Logic and Interconnect Arrays," Proc. 1989 CICC, May 1989, pp. 5.8.1 - 5.8.4.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design