| 摘要: |
| SAT求解的CDCL算法被广泛应用于软硬件验证领域, 重启策略是其中的核心组件之一. 目前, 主流的CDCL求解器采用了“热重启”技术, 保留了变元序、赋值倾向、学习子句等主要搜索信息, 且重启频率极高. 热重启技术会使CDCL重启之后更倾向于搜索重启前的搜索空间, 有可能会长期陷于一个不利的局部区域, 缺乏探索性. 首先对现有的CDCL算法进行测试, 证实了在不同的初始搜索设置下, 主流CDCL求解器的求解时间有巨大的扰动. 为了利用上述观察, 提出一种遗忘搜索信息的“冷重启”技术, 即阶段性的遗忘变元序、赋值倾向、学习子句, 实验证明了该技术可以有效地提高主流CDCL算法的性能. 同时, 也进一步拓展了其并行版本, 每个线程探索不同的区域, 提高了并行算法的性能. 此外, 冷重启技术主要改进了串并行求解器可满足实例的求解能力, 为设计可满足导向的 SAT求解器提供了新的改进思路. 通过引入并行冷重启技术, PaKis求解器可满足性实例的PAR2打分平均改进41.81%. 基于相关技术设计的并行SAT求解器ParKissat-RS以领先亚军24%的大幅领先优势取得国内首个国际SAT竞赛并行组冠军. |
| 关键词: 可满足性问题 冷重启 信息遗忘 |
| DOI：10.13328/j.cnki.jos.007509 |
| 分类号:TP301 |
| 基金项目:中国科学院战略性先导科技专项 (前瞻战略科技先导专项) (XDA0320000, XDA0320300) |
|
| Cold Restart Technique for CDCL Algorithms |
|
ZHANG Xin-Di1,2, CHEN Zhi-Han1,2, CAI Shao-Wei1,2
|
|
1.Key Laboratory of Systems Software (Institute of Software, Chinese Academy of Sciences), Beijing 100190, China;2.School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049, China
|
| Abstract: |
| The CDCL algorithm for SAT solving is widely applied in the field of hardware and software verification, with restart being one of its core components. Currently, mainstream CDCL solvers often employ the “warm restart” technique, which retains key search information such as variable order, assignment preferences, and learnt clauses, and has a very high restart frequency. The warm restart technique tends to make CDCL solvers more inclined to visit the search space that is explored before restarts, which may lead to being trapped in an unfavorable local search space for a long time, lacking exploration of other regions. This study first tests the existing CDCL algorithms and confirms that under different initial search settings, the runtime for mainstream CDCL solvers exhibits significant fluctuations. To leverage this observation, the proposed “cold restart” technique forgets search information, specifically by periodically forgetting variable order, assignment preferences, and learnt clauses. Experimental results demonstrate that this technique can effectively improve mainstream CDCL algorithms. In addition, this study further extends its parallel version, where each thread explores different search spaces, enhancing the performance of the parallel algorithm. Moreover, the cold restart technique primarily improves the performance of sequential and parallel solvers on satisfiable instances, providing new insights for designing satisfiable-oriented solvers. Specifically, the proposed parallel cold restart technique improves the PAR2 score of PaKis on satisfiable instances by 41.81% on average. The parallel SAT solver named ParKissat-RS, which integrates the proposed ideas, wins the parallel track of the SAT competition with a significant margin of 24% over the runner-up. |
| Key words: satisfiability problem (SAT) cold restart information forgetting |
