Abstract
An efficient pairwise Boolean matching algorithm for solving the problem of matching single-output specified Boolean functions under input negation and/or input permutation and/or output negation (NPN) is proposed in this paper. We present the structural signature (SS) vector, which comprises a first-order signature value, two symmetry marks, and a group mark. As a necessary condition for NPN Boolean matching, the SS is more effective than the traditional signature. A symmetry mark can distinguish symmetric variables and asymmetric variables and be used to search for multiple variable mappings in a single variable-mapping search operation, which reduces the search space significantly. Updating the SS vector via Shannon decomposition provides benefits in distinguishing unidentified variables, and the group mark and phase collision check can be used to discover incorrect variable mappings quickly, which also speeds up the NPN Boolean matching process. Using the algorithm proposed in this paper, we test both equivalent and non-equivalent matching speeds on the MCNC benchmark circuit sets and random circuit sets. In the experiment, our algorithm is shown to be 4.2 times faster than competitors when testing equivalent circuits and 172 times faster, on average, when testing non-equivalent circuits.
Similar content being viewed by others
References
Agosta, G., Bruschi, F., Pelosi, G., Sciuto, D.: A transform-parametric approach to Boolean matching [J]. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 28(6), 805–817 (2009)
Wei, Z., Chai, D., Newton, A.R., Kuehimann, A.: Fast Boolean matching with don’t cares [C]. In: International Symposium on Quality Electronic Design, pp. 347–351. IEEE (2006)
Abdollahi, A.: Signature based Boolean matching in the presence of don’t cares [C]. Design Automation Conference, pp. 642–647. IEEE (2008)
Lai C F, Jiang J H R, Wang K H. BooM: a decision procedure for Boolean matching with abstraction and dynamic learning[C]. In: Design Automation Conference, pp. 499–504. IEEE (2010)D
Damiani, M., Selchenko, A.Y.: Boolean technology mapping based on logic decomposition [C]. In: Proceedings of the 16th Symposium on Integrated Circuits and Systems Design, IEEE Computer Society (2003)
Abdollahi, A., Pedram, M.: Symmetry detection and Boolean matching utilizing a signature-based canonical form of Boolean functions [J]. IEEE Trans. Comput. Aided De. Integr. Circuits Syst. 27(6), 1128–1137 (2008)
Wang, K.H.: Exploiting k-distance signature for Boolean matching and G-symmetry detection [C]. In: Design Automation Conference, ACM/IEEE, pp. 516–521 (2006)
Zhang, J.S., Chrzanowska-Jeske, M., Mishchenko, A., et al.: Generalized symmetries in Boolean functions: fast computation and application to Boolean matching [C]. In: IWLS, pp. 424–430 (2004)
Zhang, J., Yang, G., Hung, W.N.N., et al.: A canonical-based NPN Boolean matching algorithm utilizing Boolean difference and cofactor signature [J]. IEEE Access 5, 27777–27785 (2017)
Chai, D., Kuehlmann, A.: Building a better Boolean matcher and symmetry detector [C]. In: Design, Automation and Test in Europe, IEEE, pp. 1–6 (2006)
Debnath, D., Sasao, T.: Efficient computation of canonical form for Boolean matching in large libraries [C]. In: Asia and South Pacific Design Automation Conference, pp. 591–596. IEEE (2004)
Ciric, J., Sechen C.: Efficient canonical form for boolean matching of complex functions in large libraries [C]. In: International Conference on Computer-Aided Design, pp. 610–617. IEEE (2001)
Huang, Z., Wang, L., Nasikovskiy, Y., Mishchenko, A.: Fast Boolean matching based on NPN classification [C]. In: International Conference on Field-Programmable Technology, pp. 310–313. IEEE (2013)
Petkovska, A., Soeken, M., Micheli, G.D., Ienne, P., Mishchenko, A.: Fast hierarchical NPN classification [C]. In: International Conference on Field Programmable Logic and Applications, pp. 1–4. IEEE (2016)
Abdollahi, A., Pedram, M.: A new canonical form for fast boolean matching in logic synthesis and verification [C]. In: Design Automation Conference, pp. 379–384. ACM (2005)
Agosta, G., Bruschi, F., Pelosi, G., Sciuto, D.: A unified approach to canonical form-based boolean matching [J], pp. 841–846 (2007)
Chang, C.H., Falkowski, B.J.: Boolean matching filters based on row and column weights of reed-muller polarity coefficient matrix [J]. VLSI Des. 14(3), 259–271 (2007)
Zhang, C., Hu, Y., Wang, L., et al.: Accelerating Boolean matching using bloom filter [J]. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 93–A(10), 1775–1781 (2010)
Bao, J., Wang, L.: Boolean matching method based on function classification and bloom filter [J]. Comput. Eng. 40(6), 275–280 (2014)
Chatterjee, Mishchenko, Wang, : Reducing structural bias in technology mapping [J]. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25(12), 2894–2903 (2006)
Yu, C., Wang, L., Zhang, C., Hu, Y., He, L.: Fast filter-based Boolean matchers [J]. IEEE Embed. Syst. Lett. 5(4), 65–68 (2013)
Hu, Y., Shih, V., Majumdar, R., He, L.: Exploiting symmetry in SAT-based Boolean matching for heterogeneous FPGA technology mapping [C]. In: IEEE/ACM International Conference on Computer-Aided Design, pp. 350–353. IEEE (2007)
Matsunaga, Y.: Accelerating SAT-based Boolean matching for heterogeneous FPGAs using one-hot encoding and CEGAR technique [C]. In: Design Automation Conference, pp. 255–260. IEEE (2015)
Cong, J., Hwang, Y.Y.: Boolean matching for LUT-based logic blocks with applications to architecture evaluation and technology mapping [J]. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 20(9), 1077–1090 (2001)
Soeken, M., Mishchenko, A., Petkovska, A., et al.: Heuristic NPN Classification for Large Functions Using AIGs and LEXSAT [M]. Springer, Belin (2016)
Katebi, H., Igor, L.: Large-scale Boolean matching [J]. Advanced Techniques in Logic Synthesis Optimizations & Applications, pp. 771–776 (2010)
Katebi, H., Sakallah, K.A., Markov, I.L.: Generalized Boolean symmetries through nested partition refinement [C]. In: IEEE/ACM International Conference on Computer-Aided Design, pp. 763–770. IEEE (2013)
Lai, C.F., Jiang, J.H.R., Wang, K.H.: Boolean matching of function vectors with strengthened learning [C]. In: Proceedings of the International Conference on Computer-Aided Design, pp. 596–601. IEEE Press (2010)
Zhang, J.S., Chrzanowska-Jeske, M., Mishchenko, A., Burch, J.R.: Linear cofactor relationships in Boolean functions [J]. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25(6), 1011–1023 (2006)
Acknowledgements
We would like to thank the National Natural Science Foundation of China (Grant Nos. 619 61572109, 11371003) and the Special Fund for Bagui Scholars of Guangxi for their support for technology.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, J., Yang, G., Hung, W.N.N. et al. An efficient NPN Boolean matching algorithm based on structural signature and Shannon expansion. Cluster Comput 22 (Suppl 3), 7491–7506 (2019). https://doi.org/10.1007/s10586-018-1787-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10586-018-1787-x