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!)$。 感知性是布尔函数复杂性的一个重要特征和衡量尺度。 用于分析不同字段的算法的复杂性。 这个测量可以被视为布林函数的特征, 并且具有巨大的潜力来帮助减少布尔匹配的搜索空间。 在本文中, 我们引入布林匹配的灵敏度, 并设计一些与敏感度相关的签名, 以加强快速布林匹配。 首先, 我们提出一些与布林函数等同性相关的新签名。 然后, 我们证明这些符号是布林匹配功能的前提条件, 我们可以用来减少匹配文件的搜索空间空间空间空间空间空间空间空间空间空间空间空间空间。 我们提出的快速感知识性计算方法可以比两个布林函数的精度。 将布林匹配的灵敏度和感度比与布尔匹配的精度比范围比, 将让最精细的精细的精细的智能检测方法显示另一个的精度。 的感性测试方法, 我们的精度的精度能性测试的精度可以显示另一个的精度, 的精度的精度的精度的精度的精度的精度可以展示的精度。

0
下载
关闭预览

相关内容

2021工业区块链案例集,68页pdf
专知会员服务
85+阅读 · 2021年12月1日
专知会员服务
25+阅读 · 2021年4月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】(TensorFlow)SSD实时手部检测与追踪(附代码)
机器学习研究会
11+阅读 · 2017年12月5日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】卷积神经网络类间不平衡问题系统研究
机器学习研究会
6+阅读 · 2017年10月18日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Arxiv
9+阅读 · 2021年3月8日
Arxiv
3+阅读 · 2018年10月5日
Arxiv
8+阅读 · 2018年1月25日
Arxiv
6+阅读 · 2017年12月7日
VIP会员
相关VIP内容
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】(TensorFlow)SSD实时手部检测与追踪(附代码)
机器学习研究会
11+阅读 · 2017年12月5日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】卷积神经网络类间不平衡问题系统研究
机器学习研究会
6+阅读 · 2017年10月18日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
相关论文
Arxiv
9+阅读 · 2021年3月8日
Arxiv
3+阅读 · 2018年10月5日
Arxiv
8+阅读 · 2018年1月25日
Arxiv
6+阅读 · 2017年12月7日
Top
微信扫码咨询专知VIP会员