Boolean matching is significant to digital integrated circuits design. An exhaustive method for Boolean matching is computationally expensive even for functions with only a few variables, because the time complexity of such an algorithm for an n-variable Boolean function is $O(2^{n+1}n!)$. Sensitivity is an important characteristic and a measure of the complexity of Boolean functions. It has been used in analysis of the complexity of algorithms in different fields. This measure could be regarded as a signature of Boolean functions and has great potential to help reduce the search space of Boolean matching. In this paper, we introduce Boolean sensitivity into Boolean matching and design several sensitivity-related signatures to enhance fast Boolean matching. First, we propose some new signatures that relate sensitivity to Boolean equivalence. Then, we prove that these signatures are prerequisites for Boolean matching, which we can use to reduce the search space of the matching problem. Besides, we develop a fast sensitivity calculation method to compute and compare these signatures of two Boolean functions. Compared with the traditional cofactor and symmetric detection methods, sensitivity is a series of signatures of another dimension. We also show that sensitivity can be easily integrated into traditional methods and distinguish the mismatched Boolean functions faster. To the best of our knowledge, this is the first work that introduces sensitivity to Boolean matching. The experimental results show that sensitivity-related signatures we proposed in this paper can reduce the search space to a very large extent, and perform up to 3x speedup over the state-of-the-art Boolean matching methods.
翻译:布尔匹配对于数字集成电路设计来说意义重大。 布尔匹配的详尽方法在计算上成本非常昂贵, 即使对于只有几个变量的函数也是如此。 因为用于 n可变布林函数的精密算法的时间复杂性是$O( 2 ⁇ n+1}n!)$。 感知性是布尔函数复杂性的一个重要特征和衡量尺度。 用于分析不同字段的算法的复杂性。 这个测量可以被视为布林函数的特征, 并且具有巨大的潜力来帮助减少布尔匹配的搜索空间。 在本文中, 我们引入布林匹配的灵敏度, 并设计一些与敏感度相关的签名, 以加强快速布林匹配。 首先, 我们提出一些与布林函数等同性相关的新签名。 然后, 我们证明这些符号是布林匹配功能的前提条件, 我们可以用来减少匹配文件的搜索空间空间空间空间空间空间空间空间空间空间空间空间空间。 我们提出的快速感知识性计算方法可以比两个布林函数的精度。 将布林匹配的灵敏度和感度比与布尔匹配的精度比范围比, 将让最精细的精细的精细的智能检测方法显示另一个的精度。 的感性测试方法, 我们的精度的精度能性测试的精度可以显示另一个的精度, 的精度的精度的精度的精度的精度的精度可以展示的精度。