Improvements to technology mapping for LUT-based FPGAs

ABSTRACT

The paper presents several improvements to state-of-the-art in FPGA technology mapping exemplified by a recent advanced technology mapper DAOmap [Chen and Cong, ICCAD '04]. Improved cut enumeration computes all K-feasible cuts without pruning for up to 7 inputs for the largest MCNC benchmarks. A new technique for on-the-fly cut dropping reduces by orders of magnitude memory needed to represent cuts for large designs. Improved area recovery leads to mappings with area on average 7% smaller than DAOmap, while preserving delay optimality when starting from the same optimized netlists. Applying mapping with structural choices derived by a synthesis flow on average reduces delay by 7% and area by 14%, compared to DAOmap.

REFERENCES

• 1: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 2: D. Chen , J. Cong, DAOmap: a depth-optimal area optimization mapping algorithm for FPGA designs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.752-759, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382677]
• 3: S. Chatterjee, A. Mishchenko, R. Brayton, X. Wang, and T. Kam, "Reducing structural bias in technology mapping", Proc. ICCAD '05, pp. 519--526. http://www.eecs.berkeley.edu/~alanmi/ publications/2005/iccad05_map.pdf
• 4: 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]
• 5: J. Cong and Y. Ding, "FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs", IEEE Trans. CAD, Vol.13(1), Jan. 1994, pp. 1--12.
• 6: J. Cong and Y. Ding, "On area/depth trade-off in LUT-based FPGA technology mapping," IEEE Trans. VLSI, Vol 2(2), Jun. 1994, pp 137--148.
• 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: J. Cong et al, RASP: FPGA/CPLD Technology Mapping and Synthesis Package. http://ballade.cs.ucla.edu/software_release/rasp/htdocs/
• 9: N. Eén, A. Biere "Effective preprocessing in SAT through variable and clause elimination," Proc. SAT'05.
• 10: A. Farrahi and M. Sarrafzadeh, "Complexity of lookup-table minimization problem for FPGA technology mapping," IEEE Trans. CAD, vol. 13 (11), 1994, pp. 1319--1332.
• 11: IWLS 2005 Benchmarks. http://iwls.org/iwls2005/benchmarks.html
• 12: Chi-Chou Kao , Yen-Tai Lai, An efficient algorithm for finding the minimal-area FPGA technology mapping, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.168-186, January 2005 [doi>10.1145/1044111.1044121]
• 13: A. Kuehlmann, V. Paruthi, F. Krohm, and M. K. Ganai, "Robust boolean reasoning for equivalence checking and functional property verification," IEEE Trans. CAD, Vol. 21(12), 2002, pp. 1377--1394.
• 14: E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, "Logic decomposition during technology mapping," IEEE Trans. CAD, vol. 16(8), 1997, pp. 813--833.
• 15: Feng Lu , Li-C. Wang , K.-T. (Tim) Cheng , John Moondanos , Ziyad Hanna, A signal correlation guided ATPG solver and its applications for solving difficult industrial cases, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775947]
• 16: V. Manohara-rajah, S. D. Brown, Z. G. Vranesic, "Heuristics for area minimization in LUT-based FPGA technology mapping," Proc. IWLS'04, pp. 14--21.
• 17: A. Mishchenko, S. Chatterjee, R. Jiang, R. Brayton, "FRAIGs: A unifying representation for logic synthesis and verification," ERL Technical Report, EECS Dept., UC Berkeley, March 2005.
• 18: A. Mishchenko, S. Chatterjee, R. Brayton, and M. Ciesielski, "An integrated technology mapping environment," Proc. IWLS'05, pp. 383--390. http://www.eecs.berkeley.edu/~alanmi/publications/2005/ iwls05_env.pdf
• 19: A. Mishchenko, S. Chatterjee, R. Brayton, and P. Pan, "Integrating logic synthesis, technology mapping, and retiming", Proc. IWLS'05, pp. 383--390. Also, submitted to DAC '06. http://www.eecs.berkeley. edu/~alanmi/publications/2006/dac06_int.pdf
• 20: MVSIS Group. MVSIS: Multi-Valued Logic Synthesis System. UC Berkeley. http://www?cad.eecs.berkeley.edu/mvsis/
• 21: Berkeley Logic Synthesis and Verification Group, ABC: A System for Sequential Synthesis and Verification, Release 50905. http://www.eecs.berkeley.edu/~alanmi/abc/
• 22: Peichen Pan , Chih-Chang Lin, A new retiming-based technology mapping algorithm for LUT-based FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.35-42, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275118]
• 23: M. Teslenko , E. Dubrova, Hermes: LUT FPGA technology mapping algorithm for area minimization with optimum depth, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.748-751, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382676]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

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

General Terms:
Algorithms

Keywords:
FPGA, area recovery, cut enumeration, lossless synthesis, technology mapping