{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:47Z","timestamp":1750220867204,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T00:00:00Z","timestamp":1555027200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SRC","award":["2710.001 and 2867.001"],"award-info":[{"award-number":["2710.001 and 2867.001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>NPN classification of Boolean functions is a powerful technique used in many logic synthesis and technology mapping tools in both standard cell and FPGA design flows. Computing the canonical form is the most common approach of Boolean function classification. This article proposes two different hybrid NPN canonical forms and a new algorithm to compute them. By exploiting symmetries under different phase assignment as well as higher-order symmetries, the search space of NPN canonical form computation is pruned and the runtime is dramatically reduced. Nevertheless, the runtime for some difficult functions remains high. Fast heuristic method can be used for such functions to compute semi-canonical forms in a reasonable time. The proposed algorithm can be adjusted to be a slow exact algorithm or a fast heuristic algorithm with lower quality. For exact NPN classification, the proposed algorithm is 40\u00d7 faster than state-of-the-art. For heuristic classification, the proposed algorithm has similar performance as state-of-the-art with a possibility to trade runtime for quality.<\/jats:p>","DOI":"10.1145\/3313917","type":"journal-article","created":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T12:07:04Z","timestamp":1555330024000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast Adjustable NPN Classification Using Generalized Symmetries"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4178-4094","authenticated-orcid":false,"given":"Xuegong","family":"Zhou","sequence":"first","affiliation":[{"name":"State Key Lab of ASIC and System, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lingli","family":"Wang","sequence":"additional","affiliation":[{"name":"State Key Lab of ASIC and System, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Mishchenko","sequence":"additional","affiliation":[{"name":"Department of EECS, UC Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2010.105"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429513"},{"volume-title":"Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE\u201916)","author":"Soeken M.","key":"e_1_2_1_3_1","unstructured":"M. Soeken , L. G. Amar\u00f9 , P. Gaillardon , and G. De Micheli . 2016. Optimizing majority-inverter graphs with functional hashing . In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE\u201916) . M. Soeken, L. G. Amar\u00f9, P. Gaillardon, and G. De Micheli. 2016. Optimizing majority-inverter graphs with functional hashing. In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE\u201916)."},{"volume-title":"Proceedings of the International Workshop on Logic and Synthesis (IWLS\u201910)","author":"Kennings A.","key":"e_1_2_1_4_1","unstructured":"A. Kennings , A. Mishchenko , K. Vorwerk , V. Pevzner , and A. Kundu . 2010. Generating efficient libraries for use in FPGA resynthesis algorithms . In Proceedings of the International Workshop on Logic and Synthesis (IWLS\u201910) . 147--154. A. Kennings, A. Mishchenko, K. Vorwerk, V. Pevzner, and A. Kundu. 2010. Generating efficient libraries for use in FPGA resynthesis algorithms. In Proceedings of the International Workshop on Logic and Synthesis (IWLS\u201910). 147--154."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.882484"},{"volume-title":"Proceedings of the International Conference on Computer-Aided Design (ICCAD\u201907)","author":"Mishchenko A.","key":"e_1_2_1_6_1","unstructured":"A. Mishchenko , S. Cho , S. Chatterjee , and R. Brayton . 2007. Combinational and sequential mapping with priority cuts . In Proceedings of the International Conference on Computer-Aided Design (ICCAD\u201907) . 354--361. A. Mishchenko, S. Cho, S. Chatterjee, and R. Brayton. 2007. Combinational and sequential mapping with priority cuts. In Proceedings of the International Conference on Computer-Aided Design (ICCAD\u201907). 354--361."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684746.2689082"},{"volume-title":"Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE\u201912)","author":"Ray S.","key":"e_1_2_1_8_1","unstructured":"S. Ray , A. Mishchenko , N. Een , R. Brayton , S. Jang , and C. Chen . 2012. Mapping into LUT structures . In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE\u201912) . 1579--1584. S. Ray, A. Mishchenko, N. Een, R. Brayton, S. Jang, and C. Chen. 2012. Mapping into LUT structures. In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE\u201912). 1579--1584."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3174243.3174272"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/277044.277100"},{"volume-title":"Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE\u201916)","author":"Chai D.","key":"e_1_2_1_11_1","unstructured":"D. Chai and A. Kuehlmann . 2016. Building a better Boolean matcher and symmetry detector . In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE\u201916) . 1079--1084. D. Chai and A. Kuehlmann. 2016. Building a better Boolean matcher and symmetry detector. In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE\u201916). 1079--1084."},{"key":"e_1_2_1_12_1","volume-title":"On the classification of Boolean functions. IRE Trans. Circuit Theory CT-6","author":"Golomb S. W.","year":"1959","unstructured":"S. W. Golomb . 1959. On the classification of Boolean functions. IRE Trans. Circuit Theory CT-6 ( 1959 ), 176--186. S. W. Golomb. 1959. On the classification of Boolean functions. IRE Trans. Circuit Theory CT-6 (1959), 176--186."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923256"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2016547"},{"volume-title":"Proceedings of the International Conference on Field Programmable Technology (ICFPT\u201913)","author":"Huang Z.","key":"e_1_2_1_15_1","unstructured":"Z. Huang , L. Wang , Y. Nasikovskiy , and A. Mishchenko . 2013. Fast Boolean matching based on NPN classification . In Proceedings of the International Conference on Field Programmable Technology (ICFPT\u201913) . 310--313. Z. Huang, L. Wang, Y. Nasikovskiy, and A. Mishchenko. 2013. Fast Boolean matching based on NPN classification. In Proceedings of the International Conference on Field Programmable Technology (ICFPT\u201913). 310--313."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.565592"},{"volume-title":"Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201916)","author":"Petkovska A.","key":"e_1_2_1_17_1","unstructured":"A. Petkovska , M. Soeken , G. De Micheli , P. Ienne , and A. Mishchenko . 2016. Fast hierarchical NPN classification . In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201916) , 61--64. A. Petkovska, M. Soeken, G. De Micheli, P. Ienne, and A. Mishchenko. 2016. Fast hierarchical NPN classification. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201916), 61--64."},{"volume-title":"Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201918)","author":"Zhou X.","key":"e_1_2_1_18_1","unstructured":"X. Zhou , L. Wang , P. Zhao , and A. Mishchenko . 2018. Fast adjustable NPN classification using generalized symmetries . In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201918) . 1--7. X. Zhou, L. Wang, P. Zhao, and A. Mishchenko. 2018. Fast adjustable NPN classification using generalized symmetries. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201918). 1--7."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"D. Slepian. 1952. On the number of symmetry types of Boolean functions of n variables. Can. J. Math. (1952) 185--193.  D. Slepian. 1952. On the number of symmetry types of Boolean functions of n variables. Can. J. Math. (1952) 185--193.","DOI":"10.4153\/CJM-1953-020-x"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/264995.264996"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/277044.277100"},{"volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201904)","author":"Debnath D.","key":"e_1_2_1_22_1","unstructured":"D. Debnath and T. Sasao . 2004. Efficient computation of canonical form for Boolean matching in large libraries . In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201904) . 591--596. D. Debnath and T. Sasao. 2004. Efficient computation of canonical form for Boolean matching in large libraries. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201904). 591--596."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.277607"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/157485.164569"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACRIM.2009.5291390"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630016"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837398"},{"volume-title":"Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT\u201916)","author":"Soeken M.","key":"e_1_2_1_28_1","unstructured":"M. Soeken , A. Mishchenko , A. Petkovska , B. Sterin , P. Ienne , R. Brayton , and G. De Micheli . 2016. Heuristic NPN classification for large functions using AIGs and LEXSAT . In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT\u201916) . 212--227. M. Soeken, A. Mishchenko, A. Petkovska, B. Sterin, P. Ienne, R. Brayton, and G. De Micheli. 2016. Heuristic NPN classification for large functions using AIGs and LEXSAT. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT\u201916). 212--227."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.481484"},{"volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201906)","author":"Kettle N.","key":"e_1_2_1_30_1","unstructured":"N. Kettle and A. King . 2006. An anytime symmetry detection algorithm for ROBDDs . In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201906) , 24--27. N. Kettle and A. King. 2006. An anytime symmetry detection algorithm for ROBDDs. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC\u201906), 24--27."},{"volume-title":"Proceedings of the International Conference on Computer Aided Design (ICCAD\u201900)","author":"Kravets V. N.","key":"e_1_2_1_31_1","unstructured":"V. N. Kravets and K. A. Sakallah . 2000. Generalized symmetries in Boolean functions . In Proceedings of the International Conference on Computer Aided Design (ICCAD\u201900) . 526--532. V. N. Kravets and K. A. Sakallah. 2000. Generalized symmetries in Boolean functions. In Proceedings of the International Conference on Computer Aided Design (ICCAD\u201900). 526--532."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.810744"},{"volume-title":"Proceedings of the International Conference on Computer Design. 36--39","author":"Wu Q.","key":"e_1_2_1_33_1","unstructured":"Q. Wu , C. Y. R. Chen , and J. M. Acken . 1994. Efficient Boolean matching algorithm for cell libraries . In Proceedings of the International Conference on Computer Design. 36--39 . Q. Wu, C. Y. R. Chen, and J. M. Acken. 1994. Efficient Boolean matching algorithm for cell libraries. In Proceedings of the International Conference on Computer Design. 36--39."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1963-0159764-2"},{"key":"e_1_2_1_35_1","unstructured":"Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification. Retrieved from http:\/\/www-cad.eecs. berkeley.edu\/\u223calanmi\/abc.  Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification. Retrieved from http:\/\/www-cad.eecs. berkeley.edu\/\u223calanmi\/abc."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the International Symposium on the Theory of Switching","author":"Ashenhurst R.","year":"1957","unstructured":"R. Ashenhurst . 1957 . The decomposition of switching functions . In Proceedings of the International Symposium on the Theory of Switching . Cambridge, Mass, 74--116. R. Ashenhurst. 1957. The decomposition of switching functions. In Proceedings of the International Symposium on the Theory of Switching. Cambridge, Mass, 74--116."}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313917","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313917","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:47Z","timestamp":1750202627000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313917"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,12]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3313917"],"URL":"https:\/\/doi.org\/10.1145\/3313917","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2019,4,12]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}