高级检索

利用SMT约束分解方法求解RTL可满足性问题

Constraints Decomposition for RTL Verification by SMT

  • 摘要: 随着集成电路技术与工艺的不断发展, 目前工业界所采用的形式验证工具已很难适应集成电路规模的飞速增长.为了对RTL电路的可满足性问题进行形式验证, 提出基于超图划分的约束分解实现可满足性模理论 (SMT) 求解的分级验证方法.通过分析RTL电路的结构约束, 对约束集合中的元素和相关变量进行约束建模, 并构建带有合适权重的超图模型;利用超图划分的机制寻找带有最小割集的等量划分, 实现约束分解, 完成RTL电路的定界模型检验.实验结果表明, 该方法能够减小处理问题的规模和求解过程中的搜索空间, 提高验证效率.

     

    Abstract: Most of the verification tools in industry today are hard to fit for the rapid increase of the sizes of integrated circuits.In this paper, a layered verification using SMT solvers through hypergraph partitioning based constraint decomposition is proposed, which is provided for formal verification of the satisfiability of RTL circuit.In this method, after modeling structural constraints of the RTL circuit and its correlative variables as a hypergraph model with appropriate weights, a hypergraph partitioning based constraints decomposition procedure is used to find a proper balanced bi-partitioning with min-cut, in order to accomplish bounded model checking more efficiently for the RTL circuit.The experimental results show the efficiency for pruning of the search space and in solving the satisfiability problem.

     

/

返回文章
返回