A two-step search engine for large scale boolean matching under NP3 equivalence
Chak-Wa Pui, Peishan Tu, Haocheng Li, Gengjie Chen, Evangeline F. Y. Young · 2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC) · 2018
Boolean matching is one of the most widely used engines in industrial applications. However, existing Boolean matching researches mainly focus on NPNP-equivalence. In this paper, we study a more practical problem of Boolean matching, which is Non-exact Projective NPNP (NP3). A two-step search engine is used to solve the problem and several heuristics and constraints are proposed to accelerate the whole process. In particular, we explore a new kind of symmetry properties in NP3 equivalence checking which helps to prune the solution space efficiently. Experimental results show that our proposed approach can achieve the best results among the winning teams of the ICCAD 2016 contest in quality within a given time limit.