没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记144(2006)35-50www.elsevier.com/locate/entcsSAT求解技术的自适应应用Ohad Shacham1,2Karen Yorav1,2以色列海法研究实验室摘要近年来,新的算法和策略使SAT解决方案取得了重大进展。然而,实验表明,没有在所有情况下都有效的解决方案。如果选择了错误的启发式,可以观察到数量级的退化。 问题是,不可能事先知道哪种算法最适合给定的问题。因此,许多想法-那些对一小部分情况有用,但在大多数情况下显着增加运行时间的想法-被丢弃。我们提出了自适应解决这个问题的一个可能的解决方案的概念。在我们的框架中,SAT求解器使用性能指标监视搜索的效率。该指标根据其对搜索进度的评估给出分数。 基于该分数,打开或关闭一个或多个搜索引擎。 目标是使用特定的启发式或策略,它是有利的,在它造成太大损害之前,在它不起作用的时候把它关掉。 我们提出了几种可能的度量标准,并比较它们的有效性。我们的自适应求解器在大量示例上实现了显著的加速。我们还表明,在搜索空间的不同部分上应用不同的启发式算法可以提高运行时间,甚至超过最佳启发式算法本身所能达到的效果。关键词:SAT求解1引言近年来已经看到了大量的研究SAT解决[6,12,15]。这个问题在理论上很有趣,但在实践中也很重要。高级求解器的高性能鼓励了它们在1 电子邮件:{ohads,yorav} @ il.ibm.com2 这项研究得到了欧盟合同FP 6-IST-507219(PROSYD)的1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.07.01836O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)35各种领域,如验证、人工智能、CAD等。这反过来又极大地激励了人们对SAT解决技术的研究进行投资我们对SAT求解的观点来自于它在有界模型检查[3](BMC)中的使用,其中硬件设计的验证问题被转换为布尔公式,使得满意的分配(如果存在)表示反例。实现此框架的大多数工具都基于DPLL风格的SAT求解器。虽然在这项工作中提出的想法是通用的,可以很容易地应用到其他类型的SAT求解器,我们的结果是BMC实例调整我们相信这种方法是最有效的当应用于具有内部结构的实例时。现代SAT求解器在很大程度上依赖于各种推理和策略,如决策推理,重新启动策略,学习策略,子句删除策略等[2,6,11,12,15,16]。然而,许多在理论上看起来很有吸引力的想法在实践中表现不佳,一些例子,而增加它对大多数其他人。结果,这些想法被抛弃了。即使是成功的试探法也不是在所有情况下都有用,但是不可能事先知道哪种试探法最适合给定的例子。在本文中,我们提出了自适应求解的概念。自适应求解优化了不同策略的使用方式,当它们有用时应用它们,当它们不有用时将它们转换为无效。自适应解算器跟踪搜索的性能,并使用性能度量对其进行评估。每当搜索似乎进展得不够顺利时,它就通过启用或禁用搜索来更改运行时参数。通过这种方式,自适应解算器能够利用并非在所有情况下都能很好地工作的算法。我们提出了几个度量用于自适应求解。 这些指标很容易计算,并且产生的开销可以忽略不计。他们跟踪搜索的不同方面,并相应地给出分数我们比较了他们的电子邮件-并提出一些见解,以他们的使用。我们的BMC工具是RuleBasePE [9]的一部分,RuleBasePE是IBM海法研究实验室开发的并行模型检查器。此工具使用我们的内部求解器称为法师。我们已经实现了一个自适应版本的Mage,并在大量的例子中使用它。结果表明,自适应求解将整体运行时间减少了三分之一以上,并在单个示例上实现了高达12倍当然,也有运行时间因此启用或禁用启发式。总体减少是通过显著减少许多示例的运行时间来实现的,同时在较小程度上增加其他示例的运行时间。结果表明,在一般情况下,加速比更好的较大的例子,使该方法高度可扩展性。此外,委员会认为,O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)3537我们表明,即使启发式算法在某个例子中表现不佳,将其应用于部分搜索可能会得到比不使用它更好的结果根本这意味着启发式算法的自适应应用程序本身就可以提高性能。我们的实现是自适应求解的初步实验。它只控制一个启发式算法,一次只使用一个度量,但它实现了令人印象深刻的加速。相关工作先前的尝试已经在评估求解器的寻找一个令人满意的任务。Aloul、Sierawski和Sakallah认为,连接子句的连接代表了尚未覆盖的空 间,每增加一个连接子句 他们的Satometer [1]工具保持了这个结合的BDD表示当然,无法计算精确的空间,因此该工具使用近似值。这种方法的缺点是其巨大的开销-在空间和计算方面,这使其无法用作性能指标。另一个相关的工作是由Herbstritt和Becker在[7]中提出的,其中根据一组概率函数动态地选择决策策略。概率根据几个标准而变化。我们的工作是更一般的,因为我们解决任何运行时参数的求解器,而不仅仅是决策启发式。Nudelman等人[14]使用机器学习来识别CNF的特征。使用大型训练集,他们学习问题的难度与CNF的不同分析结果之间的相关性。他们的SATzilla工具[13]使用相同的训练集和功能来描述几个不同求解器的运行时间。当要解决一个新问题时,该工具计算不同的特征,然后选择预测具有最少运行时间的求解器。然而,他们用来选择求解器的特征对我们来说并不适用,因为它们与随机实例的相关性比结构化实例更高,而且它们需要事先计算在Lagoudakis和Littman的工作[ 10 ]中值函数是预先使用训练集创建的。训练集必须是一个非常大的例子集,在某种意义上与我们想要解决的CNF相似。使用训练集是有问题的,因为它会产生很高的开销,而且很难生成足够的训练集,特别是在基于SAT的验证的设置本文其余部分的结构如下。第2节概述了DPLL风格的SAT求解器算法。第3节介绍了各种38O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)35而(1){if(decide_next_branch())while(define()==CONFLICT){ blevel =analyze_conflicts();if(blevel== 0)returnUNSAT;else bactrack(blevel);}其他返回SAT;}性能指标。第4节定义自适应求解。最后,第5节给出了实验结果,第6节给出了我们的结论。2关于SAT Solving给定一个布尔公式F在一组变量V上,SAT求解器的任务是找到V中所有变量的赋值,使得F满足。该公式以合取范式(CNF)给出。一个公式是子句的合取,其中每个子句是文字的析取。字面量是变量x或其否定形式x的实例。一个字面值可以有三个值之一:true、 false或undef(unfined)。如果一个子句中的一个字面值是unfined,而其余的都是false,那么这个子句就叫做unit子句。这样的子句强制将true赋值给未定义的文字,因为这是满足公式的唯一方法2.1SAT求解算法我们的实现面向DPLL风格的求解器[5],具有冲突子句学习和非时序回溯[2,11],尽管自适应求解概念可以应用于其他求解方案。我们给出了一个简单的描述与学习的DPLL。更详细的讨论见[17]。Fig. 1. 具有学习功能的图1给出了具有学习功能的DPLL算法的鸟瞰该算法迭代地为变量选择一个值(decide next branch())。如果所有变量都被赋值,算法停止,并输出一个令人满意的赋值。否则,这个赋值的含义将由define()函数执行。如果define()揭示了一个冲突,则分析冲突的原因,并将一个冲突子句添加到数据库中冲突子句汇总导致冲突的值的组合,并防止再次分配此组合。 函数analyzeconflicts()返回算法回溯到的决策级别。如果这是0级,则意味着即使没有O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)3539一个单一的决定,这意味着公式是不满意的。否则,算法回溯并继续搜索。2.2决定decide next branch()函数选择一个未定义的变量,并将true或false赋给它。这被称为决策,变量被称为决策变量。控制这种选择方式的算法就是决策启发式。每个决策都与一个数字相关联,称为决策级别。一个决策所产生的所有含义都与同一个决策水平相关联。当显示常数值时,它们与决策水平零相关联。2.3布尔约束传播布尔约束传播(BCP)是传播赋值结果的过程。这是图1中的函数define()的任务。每个赋值语句都可以使几个子句成为一个单元。每个单位子句都意味着一个赋值,这又可能导致更多的单元子句。在BCP过程中,这个过程会反复进行,直到没有进一步的赋值由于现代求解器花费大约80%的时间执行BCP,因此有效地执行此过程至关重要。在Mage中使用的技术,就像在zCha和其他人一样,是在每个子句中标记两个字面值为watched字面值。其合理性在于,长度为n(n≥2)的子句只有在n-1个字面量被赋值为false后才能成为单位子句。只有单位子句才能导致蕴涵,所以只要子句的两个被观察的文字是unfined(或true),这个子句就不是单位子句,并且在BCP期间不需要检查它。每当一个文字l被赋值为false时,所有被观察的子句都会被检查,看它们是否已经成为单位。2.4小句学习与非时序回溯当BCP传播某个赋值并发现一个子句的所有字面值都设置为false时,就会发生冲突。在冲突分析中,分析导致冲突的含义链,并将冲突的原因总结在冲突条款中。本条款描述了一种由于相互冲突而不应重复的分配组合。冲突子句被添加到子句数据库中,从而修剪了仍然要遍历的搜索空间。40O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)353性能度量SAT求解器的性能通过求解给定实例所需的时间来衡量。为了评估某种启发式或策略是否有效,比较了许多不同公式的总体运行时间。现实情况是,即使是最好的分析师,也有一些例子他们不能很好地工作。性能度量的作用是评估运行期间特定示例的求解器设置我们对性能指标提出以下要求:(i) 可以在求解器(ii) 它可以高效地计算,即具有低开销,并且具有最小的额外空间消耗。(iii) 该指标给出了一个分数,(大致)对应于搜索的有效性。SAT问题的本质是,期望找到一个与最终结果完美相关的度量标准是不现实的。然而,根据我们对求解器操作方式的理解,我们建议了几个候选项,如下所示。每个指标都是在运行的样本上进行评估的,该样本由恒定数量的决策组成3.1决策水平当决策导致冲突时,求解程序回溯到上一个决策级别,并取消其间进行的所有分配在这种情况下,下一个决策的决策水平将是某个较小的数字。否则,如果不存在冲突,则决策级别递增1。DL指标查看单个样本中的平均决策水平(在我们的案例中为2048个决策)。当求解程序在没有冲突的情况下做出大量决策时,或者当冲突发生时,也没什么损失因此,许多变量在很长一段时间内保持其值。这可能意味着求解器花费大量时间在状态空间的一小部分中搜索。另一方面,低平均值可能指示高冲突率。由于每个冲突条款都限制了有待搜索的空间,因此高冲突率是一个好兆头。这使我们预期,一个有效的运行是一个平均决策水平相对较低。应该注意的是,平均决策水平在很大程度上受到求解器的内部结构和所选择的决策启发式的影响。在实验这个指标时,我们发现zCha的平均决策水平通常是法师平均水平的两倍,O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)3541用同样的公式运行。3.2合同条款大小如前所述,添加的每个冲突子句都是一个约束,它减少了仍然要搜索的状态空间。一般来说,较小的冲突条款能够构成较大的限制。因此,尽管一个特定的小子句可能不如一个非常大的子句有用,但一般来说,我们希望非常小的冲突子句能更快地将搜索推向目标。我们的第二个指标CCS是在样本中学习的所有冲突子句的平均长度-越小越好。 请注意,分数并不显式地反映冲突子句的实际数量,这本身可以是一个度量。3.3二元合同条款一些解决策略强调对短冲突子句的偏好[4],特别是二元子句[15]。这是有道理的,因为这些子句具有最高的生成含义的潜力(单个赋值使子句单元)。因此,我们希望向数据库中添加许多二进制子句可以大大提高搜索速度。BIN度量度量在给定样本中学习的冲突子句总数中,二进制我们还考虑将三元子句作为此度量的一部分。然而,大量的实验表明,三元连接子句的百分比与二元子句的百分比呈线性相关。 在我们所有的例子中,这两个数字几乎相等,并且从一个样本到下一个样本,它们以相同的方式增加和减少。我们的结论是,跟踪三元冲突条款没有额外的好处3.4BCP比率当子句c中的监视文字l变为false时,BCP进程必须遍历c中的文字并查找新的监视文字。在最坏的情况下,检查c中的所有文字。BCP度量检查的文字数量(全部)与访问的子句数量之间的比率,即,它计算每个子句检查的文字的平均数量。这一比率表明,贯彻由于BCP操作是计算的主要部分,因此保持这个数字很重要。42O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)353.5一元小句学习analyzeconflicts()函数能够生成一元冲突子句。这相当于学习某个变量必须具有的值以满足公式。然后,变量被赋予一个永久值。当如果发生这种情况,则算法返回到决策级别零,并应用BCP来发现该分配的所有含义。此BCP流程产生的任何分配也是永久性的。UNARY度量跟踪永久值的签名率.它给出了在最后一个样本中分配的此类值的数量。对该度量的行为的检查表明,学习发生在突发通常情况下,有很长一段时间几乎没有学习,然后突然几十个甚至几百个变量被赋予一个值。4自适应求解如前所述,没有一种启发式算法在所有情况下都能很好地工作,无论它是决策启发式算法还是在搜索过程中使用的任何其他启发式算法。我们的解决方案是一个自适应求解器,能够使其运行时参数适应它正在求解的特定CNF在搜索过程中,求解程序会查找运行时参数不是最佳的迹象,并立即更改这些参数。自适应解算器根据以下方案工作:• 运行分为样本,其中每个样本由在一定数量的决策期间执行• 在每个示例结束时,使用性能度量来评估该示例中搜索的有效性。• 切换条件决定求解器是否正在进行。• 如果切换条件评估为真,则运行的一个或多个参数被改变。我们称之为开关。自适应求解算法的特性包括样本的大小、性能度量的选择、要改变的参数的选择以及切换的条件。所有这些的可能性是无穷无尽的。最后,这些因素的正确选择可以使成功和失败之间的差异此外,每个元素的选择取决于SAT求解器实现的规格。构建自适应解算器没有明确的规则。本节的其余部分描述并激发了为法师所做的一些选择,以及从实验中获得的见解O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)35434.1参数切换参数的选择很重要。我们的想法是选择一个对运行时间有很大影响的参数。同时,自适应地切换总是有用的参数是没有意义的。幸运的是,这样的选择并不缺乏。有许多技巧和策略没有在实践中使用,因为它们只对某些例子有利,但对大多数人来说是有害的。在我们的自适应Mage实现中,我们选择了-sign选项作为控制参数由于这是Adaptive的初步实验,求解时,仅对SAT求解算法的一个方面进行了自适应控制。此选项控制为decide next branch()函数中的决策变量选择值的方式通常,在选择一个变量来决定之后,函数通过检查相应文字的得分来选择是否将其分配为true或false。默认值是将true赋给得分最高的文字。激活-sign选项将使decide next branch()将true赋值给分数较低的文字。实验表明,一般情况下,最好选择得分较高在大多数示例中,这将导致更短的运行时间。然而,对于某些示例,选择得分较低的文字可能会导致高达4倍的加速(参见第5节中的结果)。4.2切换条件我们实现了一种机制来计算第3节中提到的所有指标。我们选择的样本量是2048个决策。当使用较小的样本时,我们发现指标得分并不稳定,另一个转换会很快发生3。对于DL、CCS、BIN和BCP指标中的每一个,我们选择一个初始界限,以便在指标得分超过界限时进行切换。初始边界是通过运行大量没有自适应求解的示例,并检查每个度量产生的分数来选择的。在运行完成后,我们看到哪些是最好的运行时间。我们查看了“坏”运行的平均得分在UNARY度量的情况下,如果添加的永久值的数量在几个样本的周期内较低,则进行切换。由于前面提到的效应,其中永久值是以突发方式添加的,因此该度量的条件被设置为:3样本大小是2的指数,因为这使实施更有效。44O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)35最后16个样本添加的永久值的数量很低同样,这个方案是通过检查好的和坏的例子来开发的。例如,我们注意到,即使在最坏的情况下,每个样本中也可能有一个或两个附加值,这就是为什么我们不要求这个数字为零。最初的实验表明,对于一些困难的问题,度量分数一直很高,自适应求解器在整个运行过程中切换参数。这导致运行时间显著增加。似乎为了使启发式有效,它需要不间断地运行一段时间。因此,我们放置了几种机制来防止自适应求解器切换得太频繁:• 当进行切换时,度量界限递增(或递减),使得为了使另一切换发生,度量分数将必须比它在最后一次切换中稍微差• 在每次切换之后,在接下来的20个样本期间防止进一步切换• 对单次运行期间允许的开关数量进行了限制5实验结果我们对我们的自适应版本的法师进行了广泛的实验。我们的基准测试套件包括来自IBM Benchmarks Suite [8]的 50个示例这是一组CNF文件,源自使用基于SAT的BMC对各种工业设计进行的验证基准测试非常多样化,有长的和短的例子,满意的和不满意的,不同的深度,等等。我们的自适应求解器只有在执行了20,000个决策后才能切换,所以没有简单的问题。基准测试套件仅包括需要超过20,000个决策的示例我们还确保我们考虑的例子不会因为超时而中止这样做是为了让我们选择的超时时间不会影响加速结果。虽然报告有几个本地版本超时而自适应版本成功的例子似乎令人印象深刻,但实际上这只取决于超时常数。我们没有减少这个常数来生成这样这需要10,000秒的相对较高的超时在10, 000上超时的仅有两次运行是使用-符号选项,没有自适应求解。此版本不影响分析在自适应算法的结果中,它仅用于证明-sign选项总体上是有害的。O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)3545通过比较总体加速比,即,所有示例的运行时间总和的加速。这个数字表明了自适应求解在大量不同规模的示例中的效果,例如在完整验证项目的情况下。这种分析更重视较大的例子。这适用于我们的实验,因为我们的目标是减少大型示例的运行时间,而不会过多地损害小型示例,从而减少一个有待完成的核查项目。例如,计算平均加速比时,会更加强调将两秒的运行时间减少到一秒,而不是将一个运行两小时的示例增加一个小时。这可能适用于理论分析,但不适用于工业工具。因为这是一个新想法的原型实现,但是,我们也给出了最小和最大的加速比。我们认为这些都表明了自适应解决的潜力。我们的实验是在Intel Pentium 4上进行的,具有单个2GHz CPU,1GBRAM,运行Linux。表2、3给出了所有50个示例的运行时间结果,单位为秒。它比较了七个版本. Native是使用默认参数运行的Mage,没有自适应算法。特别是,不使用-sign选项,因此在所有决策中选择得分最高的符号。标志是法师运行与-一直都有签名选项 版本DL、CCS、BIN、BCP和UNARY对应于自适应版本,每个版本都使用其名称所暗示的度量(see第3节)。Native和Sign版本不计算任何指标。最初的实验表明,度量分数的计算所产生的开销可以忽略不计(即使对于最大的示例也只有几秒钟)。由于差异非常小,我们省略了计算所有度量但不应用自适应求解的版本的结果。表1给出了结果总结。在此表中,“Time”行显示基准测试中所有示例的运行时间总和(以秒为单位)。 每个版本的“最小”和“最大”行显示每个版本在单个示例上实现的最小和最大加速比。满意和不满意的例子的结果分别给出,表1显示BIN和UNARY是最好的指标,加速比为1。6和1. 5分别。BCP和CCS版本提供了适度的加速,DL的加速可以忽略不计。对于CCS、BIN和UNARY版本,SAT实例的加速比UNSAT更好。仅在SAT实例上,UNARY提供了2倍的加速,而在UNSAT实例上,几乎没有任何增益。另一方面,BCP版本在UNSAT46O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)35实例. 实际上,不建议将-sign选项作为默认选项,因为它会显著增加总体运行时间。通过检查最小和最大加速比,可以发现整体加速比是如何实现的--在某些示例中显著减少了运行时间,而在其他示例中只略微增加了运行时间。例如,最坏的损害年龄的BIN版本的原因是一个加速0。75(相当于增加了约三分之一),而其最佳性能几乎快了12倍。 请注意,基准测试套件中的所有示例都是重要的。最好的加速是在一个例子上实现的,在原生版本上运行3821秒,在BIN版本上运行325秒。我们遇到的一个现象,可以在表2和表3中看到,在许多情况下,自适应版本的性能优于Native或Sign。由此我们得知,搜索空间的不同子空间需要不同的设置。这让我们相信,自适应解决方案具有巨大的潜力。版本原生签署DLCCS斌BCP一元UNSAT时间86621457986097726670270577933加速比-0的情况。5941 .一、0061 .一、1211 .一、2921 .一、2271 .一、091Min-0的情况。0970的情况。7710的情况。8740的情况。8310的情况。8300的情况。913Max-四、3541 .一、6413 .第三章。878四、042二、951四、017坐时间14955252561306792288269126377313加速比-0的情况。5921 .一、1441 .一、6201 .一、8081 .一、157二、044Min-0的情况。0670的情况。1680的情况。5090的情况。7510的情况。4110的情况。523Max-四、4373 .第三章。900五、287十一岁7491 .一、326五、900所有时间23618398352167616954149711969515247加速比-0的情况。5931 .一、0891 .一、3931 .一、5781 .一、1821 .一、549Min-0的情况。0670的情况。1680的情况。5090的情况。7510的情况。4110的情况。523Max-四、4373 .第三章。900五、28711.749二、951五、900表1所有自适应版本O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)35476结论我们将这里提出的自适应求解算法视为起点,而不是最终产品。如前所述,在实现自适应解算器时,有许多设计决策可能会影响其性能。我们的选择并不能保证是最好的。尽管如此,原型算法能够在令人满意的示例中实现高达12倍的运行时间加速,在不满意的考试中实现高达4倍的加速48O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)35原生签署DLCCS斌BCP一元IBM 02 1 1 cycle 4526.6729.1123.6724.7926.8426.7626.62IBM 02 1 1 cycle 5026.8723.5124.827.1127.1127.1726.98IBM 04 cycle 4539.9530.1538.7331.0840.0130.9839.82IBM 05 cycle 4519.2832.7128.2519.2119.1323.0619.1IBM 05 cycle 5023.5842.4730.4823.5623.5330.8823.53IBM 06 cycle 4547.6211.3247.2441.5247.547.4247.43IBM 07 cycle 1062.35341.0540.2944.4243.6546.6242.59IBM 07 cycle 1524.2818.519.6321.8116.416.6919.49IBM 07 cycle 2024.5730.1420.1720.1819.1919.2820.64IBM 07 cycle 2524.7448.8122.0226.5521.4223.6718.41IBM 07 cycle 3025.1450.9517.4322.6318.9118.3215.42IBM 07 cycle 3525.5322.828.722.0214.0115.5717.45IBM 07 cycle 4025.927.1920.8819.9919.6821.9617.8IBM 07 cycle 4526.02192.9815.8622.0228.0429.1626.58IBM 07 cycle 5026.3319.425.4522.916.4516.4124IBM 11 1 cycle 451140.991232.29679.361175.36952.891054.36894.69IBM 14 2 cycle 2525.6222.4225.8819.4325.8720.725.68IBM 14 2 cycle 3051.1858.8666.3946.9643.5237.6250.96IBM 14 2 cycle 50669.846881.23668.32535.39618.71593.9684.73IBM 17 1 2 cycle 4016.238.8919.1416.2516.1916.1716.3IBM 17 1 2 cycle 4519.387.7924.3719.3919.9219.3719.32IBM 17 1 2 cycle 5015.9811.6415.7716.1519.2316.0315.29IBM 19 cycle 3537.9632.830.0951.4243.2937.837.71IBM 19 cycle 4069.01120.8291.0260.0784.7970.6970.41IBM 19 cycle 45112.26120.35124.43220.46144.64112.29155.17IBM 19 cycle 50283.95194.38401.87215.21310.72341.76542.8表2自适应解算器版本在每个CNF实例上的运行时间一个整体,一个整体。6在整个基准测试套件上的加速。所有运行时间总和的加速在基于SAT的验证设置中特别重要,因为它代表了自适应求解对整个验证项目的影响。我们的研究结果表明,项目所需的总时间可以减少,通过让一些运行完成得更快,而其他运行稍慢。其结果是在更短的时间内完成验证,并更快地揭示错误我们展示了-sign选项对运行时间的总体不利影响虽然有一些例子,这个选项是有用的,当使用它对我们所有的例子,总的运行时间要大得多是O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)3549原生签署DLCCS斌BCP一元IBM 20 cycle 2573.5975.1973.3267.8473.8888.6873.86IBM 20 cycle 30378.49313.49378.6304.09378.23366.73377.86IBM 20 cycle 402915.992193.852913.523338.032098.472612.283193.65IBM 20 cycle 452262.221384.751584.614376.081495.491793.882104.08IBM 20 cycle 505688.421281.891458.451075.953400.84287.91964.08IBM 21 cycle 3530.5624.5128.635.6430.4530.4730.38IBM 21 cycle 4097.7173.5290.4292.7897.4397.3997.09IBM 21 cycle 45321.15221.58230.48198.86235.65322.9320.48IBM 21 cycle 50207.1335.21216.49211.32275.71207.17270.92IBM 22 cycle 3538.3441.9247.1340.9638.2437.1338.18IBM 22 cycle 40115.97155.49124.63113.16116.41121.43116.21IBM 22 cycle 45368.1612.17400.4378.86366.91443.05371.93IBM 27 cycle 4512.8321.7219.2318.3112.7319.6712.68IBM 28 cycle 3021.2218.1221.1131.121.2121.3121.19IBM 28 cycle 4021.7221.4127.0839.3121.7452.7921.73IBM 28 cycle 4522.2555.8628.9625.2722.2922.2622.14IBM 29 cycle 15305.51149.21283.99176.02173.99183.16194.88IBM 29 cycle 201828.631792.381817.361745.121948.381542.371764.72IBM 29 cycle 303821.98100003875.551013.73325.293505.24859.39IBM 29 cycle 50673.73100004015.01647.92663.63815.04758.6IBM新2周期20214.05152.21213.85127.869.3592.03207.56IBM新2周期25916.421020.32906.14236.31226.7310.5228.15IBM新5周期20137.8131.65118.62122.975.56124.2680.63IBM新6周期20252.53245.97252.3146.51140.69170.39217.72表3自适应解算器版本在每个CNF实例上的运行时间无法事先预测哪些示例将从该选项中受益由于这个原因,它直到现在还没有在实践中使用因此,自适应求解器能够充分利用总体上没有证明是有益的启发式我们的实现只控制了一个这样的启发式,但还有许多其他的可以使用。我们计划研究如何在多种选择中结合这种优势。一个有趣的现象是,在某些示例中,尽管-sign选项的性能很差,但在搜索空间的某些部分使用它会比根本不使用它得到更好的这表明,不同的子空间需要不同的方法,并清楚地表明,自适应求解的潜力大于它所控制的参数。至于性能指标-我们继续寻找更好的50O. Shacham,K.Yorav/Electronic Notes in Theoretical Computer Science 144(2006)35我们发现,有些指标在令人满意的实例上表现得更好,而另一些指标在不令人满意的实例上表现得更好。这意味着指标的组合可能更有益。自适应算法的细节需要根据求解器的具体实现进行调整。数据库的组织和求解器所使用的决策算法有助于为自适应算法做出正确的选择。这意味着在不同的求解器上实现完全相同的算法可能会产生不同的结果。有许多方向需要进一步研究。找到最佳的度量和参数是至关重要的。用于确定何时切换选项的算法也尚未完善。除此之外,我们还想尝试将学习算法融入到这个过程中。引用[1] F. A. 阿卢尔湾D. Sierawski和K.A. 萨卡拉饱和度计:我们搜索了多少在DAC,第737-742页。 ACM Press,2002.[2] R.小J Bayardo和R. C.施拉格使用CSP回看技术来解决现实世界的SAT实例。InConf. on AI,pages203[3] A. Biere,A. Cimatti,E. Clark和Y.竹 没有BDD的符号模型检查。 在TACAS,第193-207页[4] E.卡瓦略和J.使用奖励机制改进分支算法。SAT,第275-280页,2004年5月[5] M.戴维斯,G。Logemann和D.洛夫兰 定理证明的机器程序。 Comm. of the ACM,5(7):394[6] E. Goldberg和Y.诺维科夫BerkMin:一个快速而强大的SAT求解器。Date,第142-149页,2002年[7] M. Herbstritt和B.贝克基于连接的分支规则选择。载于SAT,第441-451页,2003年5月。[8] IBM HRL。IBM正式验证基准库,2004年。http://www.haifa.il.ibm.com/projects/verification/RBHomepage/bmcbenchmarks.html.[9] IBM.Rulebase并行版,2004年。http://www.haifa.il.ibm.com/projects/verification/RBHomepage/index.html.[10] M. G. Lagoudakis和M. L.利特曼学习在DPLL程序中选择分支规则以获得满意度。载于SAT,第9卷,2001年6月[11] Marques-Silva和K. A. 萨卡拉GRASP:一个命题满足性的搜索算法。IEEETrans. on Comp. ,48(5):506[12] M. W.莫斯凯维奇角F. Madigan,Y.赵湖,加-地Zhang和S.马利克Cha Cha:Engineering anEfficient SAT Solver.在发援会,2001年。[13] E. Nudelman,A. Devkar,Y. Shoham,K. Leyton-Brown和H.呼Satzilla:An algorithmportfolio for sat. 2004年参加SAT竞赛[14] E. Nudelman,K. Leyton-Brown,A. Devkar,H. Hoos和Y.肖汉姆理解随机SAT:超越子句与变量的比率。在Conf.上,和实践。的const. Prog. ,2004年。O. Shach
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- BSC绩效考核指标汇总 (2).docx
- BSC资料.pdf
- BSC绩效考核指标汇总 (3).pdf
- C5000W常见问题解决方案.docx
- BSC概念 (2).pdf
- ESP8266智能家居.docx
- ESP8266智能家居.pdf
- BSC概念 HR猫猫.docx
- C5000W常见问题解决方案.pdf
- BSC模板:关键绩效指标示例(财务、客户、内部运营、学习成长四个方面).docx
- BSC概念.docx
- BSC模板:关键绩效指标示例(财务、客户、内部运营、学习成长四个方面).pdf
- BSC概念.pdf
- 各种智能算法的总结汇总.docx
- BSC概念 HR猫猫.pdf
- bsc概念hr猫猫.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)