Xuegong Zhou
Skip Abstract Section
Abstract
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× 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.
- A. Kennings, A. Mishchenko, K. Vorwerk, V. Pevzner, and A. Kundu. 2010. Efficient FPGA resynthesis using precomputed LUT structures. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL’10). 532--537. Google Scholar
Digital Library
- W. Yang, L. Wang, and A. Mishchenko. 2012. Lazy man's logic synthesis. In Proceedings of the International Conference on Computer-Aided Design (ICCAD’12). 597--604. Google ScholarDigital Library
- M. Soeken, L. G. Amarù, 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’16). Google ScholarDigital Library
- 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’10). 147--154.Google Scholar
- S. Chatterjee, A. Mishchenko, R. K. Brayton, X. Wang, and T. Kam. 2006. Reducing structural bias in technology mapping. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 25, 12 (2006), 2894--903. Google ScholarDigital Library
- 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’07). 354--361. Google ScholarDigital Library
- A. Mishchenko, R. Brayton, W. Feng, and J. W. Greene. 2015. Technology mapping into general programmable cells. In Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA’15). 70--73. Google ScholarDigital Library
- 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’12). 1579--1584. Google ScholarDigital Library
- W. Feng, J. W. Greene, and A. Mishchenko. 2018. Improving FPGA performance with a S44 LUT structure. In Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA’18). 61--66. Google ScholarDigital Library
- U. Hinsberger and R. Kolla. 1998. Boolean matching for large libraries. In Proceedings of the Design Automation Conference (DAC’98), 206--211. Google ScholarDigital Library
- 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’16). 1079--1084. Google ScholarDigital Library
- S. W. Golomb. 1959. On the classification of Boolean functions. IRE Trans. Circuit Theory CT-6 (1959), 176--186.Google Scholar
- A. Abdollahi and M. Pedram. 2008. Symmetry detection and Boolean matching utilizing a signature-based canonical form of Boolean functions. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 27, 6 (2008), 1128--1137. Google ScholarDigital Library
- G. Agosta, F. Bruschi, G. Pelosi, and D. Sciuto. 2009. A transform-parametric approach to Boolean matching. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 28, 6 (2009), 805--817. Google ScholarDigital Library
- 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’13). 310--313.Google Scholar
- C. C. Tsai, M. Marek-Sadowska, and D. Gatlin. 1997. Boolean function classification via fixed polarity Reed-Muller forms. IEEE Trans. Comput. 46, 2 (1997), 173--186. Google ScholarDigital Library
- 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’16), 61--64.Google Scholar
- 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’18). 1--7.Google Scholar
- D. Slepian. 1952. On the number of symmetry types of Boolean functions of n variables. Can. J. Math. (1952), 185--193.Google Scholar
- L. Benini and G. De Micheli. 1997. A survey of Boolean matching techniques for library binding. ACM Trans. Des. Autom. Electron. Syst. 2, 3 (1997), 193--226. Google ScholarDigital Library
- U. Hinsberger and R. Kolla. 1998. Boolean matching for large libraries. In Proceedings of the Design Automation Conference (DAC’98). 206--211. Google ScholarDigital Library
- 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’04). 591--596. Google ScholarDigital Library
- E. Mailhot and G. De Micheli. 1993. Algorithms for technology mapping based on binary decision diagrams and on Boolean operations. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 12, 5 (1993), 599--620. Google ScholarDigital Library
- E. M. Clarke, K. L. McMillan, X. Zhao, M. Fujita, and J. Yang. 1993. Spectral transforms for large Boolean functions with applications to technology mapping. In Proceedings of the Design Automation Conference (DAC’93), 54--60. Google ScholarDigital Library
- J. Rice. 2009. The autocorrelation transform and its application to the classification of Boolean functions. In Proceedings of the IEEE Pacific Rim Conference on Communications Computers and Signal Processing (PacRim’09). 94--99.Google ScholarCross Ref
- K. Wang, C. Chan, and J. Liu. 2009. Simulation and SAT-based Boolean matching for large Boolean networks. In Proceedings of the Design Automation Conference (DAC’09). 396--401. Google ScholarDigital Library
- C.-F. Lai, J.-H. R. Jiang, and K.-H. Wang. 2010. BooM: A decision procedure for Boolean matching with abstraction and dynamic learning. In Proceedings of the Design Automation Conference (DAC’10). 499--504. Google ScholarDigital Library
- 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’16). 212--227.Google Scholar
- C. C. Tsai and M. Marek-Sadowaska. 1996. Generalized Reed-Muller forms as a tool to detect symmetries. IEEE Trans. Comput. 45, 1 (1996), 33--40. Google ScholarDigital Library
- 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’06), 24--27.Google Scholar
- V. N. Kravets and K. A. Sakallah. 2000. Generalized symmetries in Boolean functions. In Proceedings of the International Conference on Computer Aided Design (ICCAD’00). 526--532. Google ScholarDigital Library
- J. Ciric and C. Sechen. 2003. Efficient canonical form for Boolean matching of complex functions in large libraries. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 22, 5 (2003), 535--544. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Selmer M. Johnson. 1963. Generation of permutations by adjacent transposition. Math. Comp. 17 (1963), 282--285.Google ScholarCross Ref
- Berkeley Logic Synthesis and Verification Group. ABC: A System for Sequential Synthesis and Verification. Retrieved from http://www-cad.eecs. berkeley.edu/∼alanmi/abc.Google Scholar
- R. Ashenhurst. 1957. The decomposition of switching functions. In Proceedings of the International Symposium on the Theory of Switching. Cambridge, Mass, 74--116.Google Scholar
Index Terms
- Fast Adjustable NPN Classification Using Generalized Symmetries
Recommendations
A Group Algebraic Approach to NPN Classification of Boolean Functions
The classification of Boolean functions plays an underpinning role in logic design and synthesis of VLSI circuits. This paper considers a underpinning question in Boolean function classification: how many distinct classes are there for k-input Boolean ...
Efficient Computation of Canonical Form under Variable Permutation and Negation for Boolean Matching in Large Libraries
This paper presents an efficient technique for solving a Boolean matching problem in cell-library binding, where the number of cells in the library is large. As a basis of the Boolean matching, we use the notion NP-representative (NPR): two functions ...
Efficient computation of canonical form for Boolean matching in large libraries
ASP-DAC '04: Proceedings of the 2004 Asia and South Pacific Design Automation ConferenceThis paper presents an efficient technique for solving a Boolean matching problem in cell-library binding, where the number of cells in the library is large. As a basis of the Boolean matching, we use the notion NP-representative (NPR); two functions ...
Comments