General modeling and technology-mapping technique for LUT-based FPGAs

ABSTRACT

We present a general approach to the FPGA technology mapping problem that applies to any logic block composed of lookup tables (LUTs) and can yield optimal solutions. The connections between LUTs of a logic block are modeled by virtual switches, which define a set of multiple-LUT blocks (MLBs) called an MLB-basis. We identify the MLB-bases for various commercial logic blocks. Given a n MLB-basis, we formulate FPGA mapping as a mixed integer linear programming (MILP) problem to achieve both the generality and the optimality objectives. We solve the MILP models using a general-purpose MILP solver, and present the results of mapping some ISCAS.85 benchmark circuits with a variety of commercial FPGAs. Circuits of a few hundred gates can be mapped in reasonable time using the MILP approach directly. Larger circuits can be handled by partitioning them prior to technology mapping. We show that optimal or provably near-optimal solutions can be obtained for the large ISCAS.85 benchmark circuits using partitions defined by their high-level functions.

REFERENCES

• 1: Altera Inc. The Altera FPGA Data Book, Sunnyvale, CaliL, 1993.
• 2: AT&T Inc. The AT~4T FPGA Data Book, Allentown, Pa., 1995.
• 3: Peter Barth, Logic-based 0-1 constraint programming, Kluwer Academic Publishers, Norwell, MA, 1995
• 4: Amit Chowdhary , John P. Hayes, Technology mapping for field-programmable gate arrays using integer programming, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.346-352, November 05-09, 1995, San Jose, California, United States
• 5: J. Cong and Y. Ding. FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Trans. on CAD, 13(1):1-11, Jan. 1994.
• 6: CPLEX Optimization Inc. CPLEX documentation, 1990.
• 7: E. Detjens et ak Technology mapping in MIS. Proc. Int'l Conf. on CAD, pp. 116-119, 1987.
• 8: Robert J. Francis , Jonathan Rose , Kevin Chung, Chortle: a technology mapping program for lookup table-based field programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.613-619, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123418]
• 9: M. C. Hansen , J. P. Hayes, High-level test generation using physically-induced faults, Proceedings of the 13th IEEE VLSI Test Symposium (VTS'95), p.20, April 30-May 03, 1995
• 10: A. Sangiovanni-Vincentelli, A. El Carnal, and J. Rose. Synthesis methods for field programmable gate arrays. Proc. of IEEE, pp. 1057-1083, July 1993.
• 11: XiHnx Inc. The Programmable Logic Data Book, Santa Clara, Calif., 1994.

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.1 Design Styles
          Subjects: Logic arrays
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Performance