An iterative area/performance trade-off algorithm for LUT-based FPGA technology mapping

ABSTRACT

In this paper, we propose an iterative area/performance trade-off algorithm for LUT-based FPGA technology mapping. First, it finds an area-optimized performance-considered initial network by a modified area optimization technique. Then, an iterative algorithm consisting of several resynthesizing techniques is applied to trade the area for the performance in the network gracefully. Experimental results show that this approach can provide a complete set of mapping solutions from the area-optimized one to the performance-optimized one for the given design. Furthermore, these two extreme solutions, the area-optimized one and the performance-optimized one, produced by our algorithm outperform the results of most existing algorithms. Therefore, our algorithm is very useful for the timing driven FPGA synthesis.

REFERENCES

• 1: The Programmable Logic Data Book, Xilinx Inc., San Jose, 1993.
• 2: R. Murgai, N. Shenoy, R. K. Brayton, and A. Sangiovanni- Vincentelli, "Improved logic synthesis algorithms for table look up architectures," in Proc. Int. Conf. Computer-Aided Design, pp. 564-567, Nov. 1991.
• 3: 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]
• 4: 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]
• 5: 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]
• 6: 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
• 7: R.J. Francis, J. Rose, and Z. Vranesic, "Technology mapping of look-up table-based FPGAs for performance," in Proc. Int. Conf. Computer-Aided Design, pp. 568-571, Nov. 1991.
• 8: R. Murgai, N. Shenoy, R. K. Brayton, and A. Sangiovanni- Vincentelli, "Performance directed synthesis for table lookup programmable gate arrays," in Proc. Int. Conf. Computer-Aided Design, pp. 572-575, Nov. 1991.
• 9: Prashant Sawkar , Donald Thomas, Performance directed technology mapping for look-up table based FPGAs, Proceedings of the 30th international conference on Design automation, p.208-212, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164672]
• 10: Jason Cong , Yuzheng Ding, Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.110-114, November 07-11, 1993, Santa Clara, California, United States
• 11: J. Cong, and Y. Ding, "FlowMap: an optimal technology mapping algorithm for delay optimization in lookup-table based F PGA designs," in IEEE Trans. on Computer-Aided Design, vol. 13, no. 1, pp. 1-12, Jan. 1994.
• 12: Christian Legl , Bernd Wurth , Klaus Eckl, A Boolean approach to performance-directed technology mapping for LUT-based FPGA designs, Proceedings of the 33rd annual conference on Design automation, p.730-733, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240657]
• 13: J. Cong, and Y. Ding, "On area/depth trade-off in LUT-based FPGA technology mapping," in IEEE Trans. on VLSI Systems, vol. 2, no. 2, pp. 137-148, June 1994.
• 14: R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. R. Wang, "MIS : a multi-level logic optimization system," in IEEE Trans. on Computer-Aided Design, vol. 6, no. 11, pp. 1062-1081, Nov. 1987.

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

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
LUT-Based FPGA Technology Mapping, Area/Performance Trade-Off, and Timing Driven FPGA Synthesis