General technology mapping for field-programmable gate arrays based on lookup tables

ABSTRACT

We present a general technology-mapping methodology (TULIP) for field-programmable gate arrays (FPGAs) that can yield optimal results, and is applicable to any FPGA with a logic block composed of lookup tables (LUTs). We introduce the concept of a virtual switch to model the internal connections of a logic block with multiple LUTs; each configuration of virtual switches is called a multiple-LUT block (MLB). A logic block can be precisely defined by a small but complete set of representative configurations called an MLB basis. The MLB bases for various commercial FPGA families are demonstrated. Given a logic block represented by its MLB basis, technology mapping is precisely formulated as a graph-covering problem, which is transformed into a mixed integer-linear programming (MILP) optimization problem in order to achieve our optimality and generality objectives. The MILP model is solved using a general-purpose MILP solver tool. The results of using TULIP for mapping some ISCAS-85 benchmark circuits to a variety of logic blocks are presented. Circuits of a few hundred gates can be mapped directly in a few minutes. To map larger circuits to complex logic blocks, some approximation techniques are proposed based on partitioning the input circuit and simplifying the MLB basis. We show that these approximations result in close-to-optimal mappings of the benchmark circuits.

REFERENCES

• 1: Actel Inc. 1993. The Actel FPGA Data Book. Actel Inc., Sunnyvale, CA.
• 2: Altera Inc. 1993. The Altera FPGA Data Book. Altera Inc., Sunnyvale, CA.
• 3: Peter Barth, Logic-based 0-1 constraint programming, Kluwer Academic Publishers, Norwell, MA, 1995
• 4: BRAYTON, R. K., RUDELL, R., SANGIOVANNI-VINCENTELLI, A., AND WANG, A. R. 1987. Mis: A multiplelevel logic optimization system. IEEE Trans. CAD 6, Nov., 1062-1081.
• 5: Amit Chowdhary, Technology mapping for field-programmable gate arrays, University of Michigan, Ann Arbor, MI, 1997
• 6: 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
• 7: Amit Chowdhary , John P. Hayes, General modeling and technology-mapping technique for LUT-based FPGAs, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.43-49, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258311]
• 8: CONG, J. AND DING, Y. 1994. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. CAD 13, Jan., 1-11.
• 9: 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]
• 10: Jason Cong , Yean-Yow Hwang, Partially-dependent functional decomposition with applications in FPGA synthesis and mapping, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.35-42, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258310]
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: Cplex Corp. 1990. cplex documentation. Cplex Corp.
• 13: 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]
• 14: 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
• 15: HARARY, F. 1969. Graph Theory. Addison-Wesley, Reading, MA.
• 16: HE, J. AND ROSE, J. 1994. Technology mapping for heterogeneous FPGAs. In Proceedings of the International Symposium on Field-Programmable Gate Arrays (Feb. 1994).
• 17: IBM Corp. 1990. Optimization Subroutine Library. IBM Corp.
• 18: Madhukar R. Korupolu , K. K. Lee , D. F. Wong, Exact tree-based FPGA technology mapping for logic blocks with independent LUTs, Proceedings of the 35th annual conference on Design automation, p.708-711, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277222]
• 19: LAI, Y.-T., PAN, K.-R. R., PEDRAM, M., AND VRUDHULA, S. 1993. FGMap: A technology mapping algorithm for lookup table type FPGAs based on function graphs. In Proceedings of the International Workshop on Logic Synthesis (May 1993). 9b.1-9b.4.
• 20: Lucent Microelectronics. 1995. The Lucent FPGA Data Book. Lucent Microelectronics, allentown, PA.
• 21: 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]
• 22: MURGAI, R., SHENOY, N., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1991. Improved logic synthesis algorithms for table lookup architectures. In Proceedings of the International on CAD (Nov. 1991). 564-567.
• 23: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 24: Nam-Sung Woo, A heuristic method for FPGA technology mapping based on the edge visibility, Proceedings of the 28th conference on ACM/IEEE design automation, p.248-251, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127675]
• 25: Xilinx Inc. 1994. The Xilinx FPGA Data Book. Xilinx Inc., Santa Clara, CA.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Algorithms, Design, Theory

Keywords:
Basis, circuit partitioning, field-programmable gate arrays, lookup tables (LUTs), mapping, multiple-LUT blocks, nonrooted trees, rooted trees, synthesis