An efficient algorithm for finding the minimal-area FPGA technology mapping

ABSTRACT

Minimum area is one of the important objectives in technology mapping for lookup table-based field-progrmmable gate arrays (FPGAs). Although there is an algorithm that can find an optimal solution in polynomial time for the minimal-area FPGA technology mapping problem without gate duplication, its time complexity can grow exponentially with the number of inputs of the lookup-tables. This article proposes an algorithm with approximate to the area-optimal solution and lower time complexity. The time complexity of this algorithm is proven theoretically to be bounded by O(n³), where n is the total number of gates in the given circuit. It is shown that except for some cases the proposed algorithm can find an optimal solution of a given problem. We have combined the proposed algorithm with the existing postprocessing procedures which are used to find the gates that can be duplicated on a set of benchmark examples. The experimental results demonstrate the effectiveness of our algorithm.

REFERENCES

• 1: 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
• 2: Gang Chen , Jason Cong, Simultaneous logic decomposition with technology mapping in FPGA designs, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.48-55, February 2001, Monterey, California, United States [doi>10.1145/360276.360298]
• 3: Cong, J. and Ding, Y. 1994a. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. Comput.-Aided Des. of Integr. Circ. Syst. 13, 1 (Jan.), 1--11.
• 4: Cong, J. and Ding, Y. 1994b. On area/depth trade-off in LUT-Based FPGA technology mapping. IEEE Trans. VLSI Syst. 2, 2 (June), 137--148.
• 5: Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar , Kuang-Chien Chen, An Improved Graph-Based FPGA Techology Mapping Algorithm For Delay Optimization, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.154-158, October 11-14, 1992
• 7: Jason Cong , Chang Wu , Yuzheng Ding, Cut ranking and pruning: enabling a general and efficient FPGA mapping solution, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.29-35, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296425]
• 8: Farrahi, H. and Sarrafzadeh, M. 1994. Complexity of the lookup-table minimization problem for FPGA technology mapping. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 13, 11(Nov.), 1319--1332.
• 9: 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]
• 10: 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]
• 11: Juinn-Dar Huang , Jing-Yang Jou , Wen-Zen Shen, Compatible class encoding in Roth-Karp decomposition for two-output LUT architecture, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.359-363, November 05-09, 1995, San Jose, California, United States
• 12: Hwang, T. T., Owens, R. M., and Irwin, M. J. 1994. Logic synthesis for field-programmable gate arrays. IEEE Trans. Comput.-Aided Des. 13, 10(Oct.), 1280--1287.
• 13: Karp, R. M. and Roth, J. P. 1962. Minimization over Boolean graphs. IBM J. Res. Develop. April, 227--238.
• 14: Kevin Karplus, Xmap: A technology mapper for table-lookup field-programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.240-243, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127672]
• 15: Yung-Te Lai , Kuo-Rueih Ricky Pan , Massoud Pedram, FPGA Synthesis Using Function Decomposition, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.30-35, October 10-12, 1994
• 16: Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, BDD based decomposition of logic functions with application to FPGA synthesis, Proceedings of the 30th international conference on Design automation, p.642-647, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165078]
• 17: Lehman, E., Watanabe, Y., Grodstein, J., and Harkness, H. 1997. Logic decomposition during technology Mapping. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 16, 8(Aug.), 813--834.
• 18: 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]
• 19: Murgai, R., Shenoy, N., Brayton, R. K., and Sangiovanni-Vincentelli, A. 1991. Improved logic synthesis algorithms for table look up architectures. In Proceedings of the IEEE International Conference on Computer-Aided Design. 564--567.
• 20: Hiroshi Sawada , Takayuki Suyama , Akira Nagoya, Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.353-358, November 05-09, 1995, San Jose, California, United States
• 21: P. Sawkar , D. Thomas, Area and delay mapping for table-look-up based field programmable gate arrays, Proceedings of the 29th ACM/IEEE conference on Design automation, p.368-373, June 08-12, 1992, Anaheim, California, United States
• 22: Sentovich, E., Singh, K., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P., Brayton, R., and Sangiovanni-Vincentelli, A. 1992. SIS: A system for sequential circuit synthesis. Tech. rep. UCB/ERL M92/41. University of California, Berkeley, Berkeley, CA.
• 23: Wen-Zen Shen , Juinn-Dar Huang , Shih-Min Chao, Lambda set selection in Roth-Karp decomposition for LUT-based FPGA technology mapping, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.65-69, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217508]
• 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: Bernd Wurth , Klaus Eckl , Kurt Antreich, Functional multiple-output decomposition: theory and an implicit algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.54-59, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217506]
• 26: Zhang, S., Miller, D. M., and Muzio, J. C. 1996. Notes on complexity of the lookup-table minimization problem for FPGA technology mapping. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 15, 12(Dec.), 1588--1590.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis; Optimization

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Logic synthesis, greedy method, partition, technology mapping