FPGA area reduction by multi-output function based sequential resynthesis

ABSTRACT

We propose a new resynthesis algorithm for FPGA area reduction. In contrast to existing resynthesis techniques, which consider only single-output Boolean functions and the combinational portion of a circuit, we consider multi-output functions and retiming, and develop effective algorithms that incorporate recent improvements to SAT-based Boolean matching. Our experimental results show that with the optimal logic depth, the resynthesis considering multi-output functions reduces area by up to 0.4% compared to the one considering single-output functions, and the sequential resynthesis reduces area by up to 10% compared to combinational resynthesis when both consider multi-output functions. Furthermore, our proposed resynthesis algorithm reduces area by up to 16% compared to the best existing academic technology mapper, Berkeley ABC.

REFERENCES

• 1: A. Farrahi and M. Sarrafzadeh, "Complexity of the lookup-table minimization problem for fpga technology mapping," TCAD, 1994.
• 2: Jason Cong , Yuzheng Ding, On area/depth trade-off in LUT-based FPGA technology mapping, Proceedings of the 30th international conference on Design automation, p.213-218, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164675]
• 3: Jason Cong , Yean-Yow Hwang, Simultaneous depth and area minimization in LUT-based FPGA mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.68-74, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201322]
• 4: V. Manohararajah, S. D. Brown, and Z. G. Vranesic, "Heuristics for area minimization in lut-based fpga technology mapping," IWLS, 2004.
• 5: 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]
• 6: "Abc: A system for sequential synthesis and verification," in http://www.eecs.berkeley.edu/alumni/abc/.
• 7: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, Improvements to technology mapping for LUT-based FPGAs, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117208]
• 8: K. Minkovich and J. Cong, "Optimality study of logic synthesis for lut-based fpgas," FPGA, 2006.
• 9: G. D. Micheli, "Synchronous logic synthesis: algorithms for cycle-time minimization," TCAD, 1991.
• 10: A. Mishchenko, S. Chatterjee, and R. Brayton, "Dag-aware aig rewriting," DAC, 2005.
• 11: S. Malik, E. Sentovich, R. Brayton, and A. Sangiovanni-Vincentelli, "Retiming and resynthesis: Optimizing sequential networks with combinational techniques," TCAD, 1991.
• 12: R. Brayton and A. Mishchenko, "Sequential rewriting," IWLS, 2007.
• 13: Eric Lehman , Yosinori Watanabe , Joel Grodstein , Heather Harkness, Logic decomposition during technology mapping, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.264-271, November 05-09, 1995, San Jose, California, United States
• 14: Alan Mishchenko , Xinning Wang , Timothy Kam, A new enhanced constructive decomposition and mapping algorithm, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775871]
• 15: Andrew Ling , Deshanand P. Singh , Stephen D. Brown, FPGA technology mapping: a study of optimality, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065693]
• 16: Jason Cong , Kirill Minkovich, Improved SAT-based Boolean matching using implicants for LUT-based FPGAs, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216944]
• 17: Luca Benini , Giovanni De Micheli, A survey of Boolean matching techniques for library binding, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.193-226, July 1997 [doi>10.1145/264995.264996]
• 18: Yu Hu , Victor Shih , Rupak Majumdar , Lei He, Exploiting symmetry in SAT-based Boolean matching for heterogeneous FPGA technology mapping, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 19: Sean Safarpour , Andreas Veneris , Gregg Baeckler , Richard Yuan, Efficient SAT-based Boolean matching for FPGA technology mapping, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147034]
• 20: Yu Hu , Satyaki Das , Steve Trimberger , Lei He, Design, synthesis and evaluation of heterogeneous FPGA with mixed LUTs and macro-gates, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 21: Alan Mishchenko , Robert K. Brayton, SAT-Based Complete Don't-Care Computation for Network Optimization, Proceedings of the conference on Design, Automation and Test in Europe, p.412-417, March 07-11, 2005 [doi>10.1109/DATE.2005.264]
• 22: 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]
• 23: C. E. Leiserson and J. B. Saxe, "Retiming synchronous circuitry," Algorithmica, 1991.
• 24: Zhong Xiu , David A. Papa , Philip Chong , Christoph Albrecht , Andreas Kuehlmann , Rob A. Rutenbar , Igor L. Markov, Early research experience with OpenAccess gear: an open source development environment for physical design, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055156]
• 25: N. Een and N. Sorensso, http://www.cs.chalmers.se/Cs/Research/ FormalMethods/MiniSat/MiniSat.html.
• 26: MCNC, MCNC Designers' Manual, 1993.
• 27: "Iwls 2005 benchmarks," in http://iwls.org/iwls2005/benchmarks.html.
• 28: 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design

Keywords:
FPGA, SAT, logic synthesis, resynthesis