Efficient SAT Based Boolean Matching Considering Symmetries and Re-synthesis for LUT based FPGA

 

By Victor Shih and Yu Hu (08/30/07)

 

 

SAT Solvers

  1. MiniSAT [weblink]
  2. WalkSAT: Bart Selman, Henry Kautz, and Bram Chohen, Local Search Strategies for Satisfiability Testing  [pdf]

 

SAT-based Boolean Matching (1, 2, 3) and Re-synthesis for LUT Based FPGA (1 and 3)

  1. Jason Cong and Kirill Minkovich, Improved SAT-Based Boolean Matching Using Implicants for LUT-Based FPGAs, FPGA 2007 [pdf]
  2. Sean Safarpour, Andreas Veneris, Gregg Baeckler and Richard Yuan, Efficient SAT-Based Boolean Matching for FPGA Technology Mapping, DAC 2006 [pdf] [slides]
  3. Andrew Ling, Deshanand P. Singh and Stephen D. Brown, FPGA Technology Mapping: A Study of Optimality, DAC 2005 [pdf]
  4. Andrew Ling, Field-Programmable Gate Array Logic Synthesis Using Boolean Satisfiability, MS Thesis, U of Toronto 2005 [pdf] [slides]

 

Other Boolean Matching Approaches for LUT based FPGAs

  1. Jason Cong and Yean-Yow Hwang, Boolean Matching for LUT-Based Logic Blocks With Applications to Architecture Evaluation and Technology Mapping, TCAD 2001 [pdf]

 

Boolean Matching for ASICs and Symmetry Detection for Boolean Satisfiability

  1. Zile Wei, Donald Chai, Andrews Kuehlmann and A. Richard Newton, Fast Boolean Matching with Don’t Cares, ISQED 2006 [pdf]
  2. Donald Chai and Andrews Kuehlmann, Building a Better Boolean Matcher and Symmetry Detector, DATE 2006 [pdf]
  3. Fadi A. Aloul, Igor L. Markov and Karem A. Sakllah, Shatter: Efficient Symmetry-Breaking for Boolean Satisfiability,  DAC 2003 [pdf] [slides]
  4. Fadi A. Aloul, Arathi Ramani, Igor L. Markov and Karem A. Sakllah, Solving Difficult Instances of Boolean Satisfiability in the Presence of Symmetry, TCAD 2003 [pdf]
  5. Victor N. Kravets and Karem A. Sakallah, Generalized Symmetries in Boolean Functions, ICCAD 2000 [pdf]
  6. Uwe Hinsberger and Reiner Kolla, Boolean Matching for Large Libraries, DAC 1998 [pdf]
  7. Luca Benini and Glovanni De Micheli, A Survey of Boolean Matching Techniques for Library Binding, TODAES 1997 [pdf]

 

Technology Mapping for Multiple Output Functions

  1. Kai-hui Chang, Igor L. Markov and Valeria Bertacco, Post-Placement Rewiring and Rebuffering by Exhaustive Search for Functional Symmetries, ICCAD 2005 [pdf]
  2. Jason Cong and Deming Chen, Performance-Driven Mapping for CPLD Architecture, FPGA 2001 [pdf]
  3. Kania, D., A technology mapping algorithm for PAL-based devices using multi-output function graphs, Euromicro Conference, 2000 [pdf]