基于布尔可满足性的精确逻辑综合综述

逻辑综合是电子设计自动化(EDA)的重要步骤,随着算力逐渐提升和新的计算范式不断涌现,传统基于全局启发式算法的逻辑综合面临新的挑战。启发式算法面临的主要问题是得到一个次优解,随着算力的提升,逻辑优化越来越追求精确解而不满足于次优解。该文首先简述逻辑函数表达方法和布尔可满足性(SAT)问题;其次针对精确综合的算法、编码等方面介绍了在布尔逻辑网络的面积优化和深度优化方面的精确综合研究进展;最后对精确综合的未来发展趋势进行讨论。

基于伪布尔可满足性的纳米CMOS电路单元配置

针对传统布尔可满足性(SAT)法在处理纳米CMOS电路(CMOL)单元配置时,存在合取范式(CNF)表示的约束子句个数过多、中间处理文件过大的问题,该文提出了利用伪布尔可满足性(PBS)来解决CMOL电路的单元配置问题。实验结果显示,相对于传统的SAT法,PBS法在不增加额外的布尔变量集个数的条件下,通过降低编码过程中的约束个数,能有效减少中间处理文件大小,达到提高算法效率和提高处理大电路的能力。

加强约束的布尔可满足硬件求解器

利用现场可编程门阵列固有的并行性和灵活性,提出在硬件可编程平台上基于随机局部搜索算法的布尔可满足性求解器,用于求解大规模的布尔可满足性问题。相对其他求解器,该求解器的预处理技术能极大提高求解效率;其变元加强策略避免了同一变元被反复连续翻转,降低了搜索陷入局部最优的可能。评估结果表明,求解器最多能处理32 000个变元/128 000个子句的实例。相比当前同类型的求解器,其求解效率明显提高。

基于布尔可满足性的层次化通路时延故障测试

针对现代VLSI电路趋向于层次化的设计,本文提出了基于布尔可满足性的层次化通路时延故障测试方法,采用面向模块级的增量布尔可满足性合取范式的提取,从高到低层次化实现了关键通路的判别及子式生成。利用电路的时延测试条件蕴涵并转化为相应的约束子句,有利于将冲突尽早提前,以减少搜索空间。通过将已有的判别模块储存起来,作为学习子句,避免重复判别,极大的加快了子式的提取且降低了求解的规模和难度。仿真结果表明本文方案具有测试时间短、效率高,特别适合于具有模块化、规则化结构的层次化设计电路。

一种基于伪布尔可满足性FPGA布线算法

为了克服布尔可满足性算法在现场可编程门阵列布线中存在的不足,引进了一种在标准对称阵列(隔离岛状)现场可编程门阵列结构下的新型有效布线方法——伪布尔可满足性算法,并结合实例详细地阐述了将其应用于布线的原理及方法,同时采用实际工业电路将布尔可满足性算法与伪布尔可满足性算法作出比较。实验结果显示,伪布尔可满足性算法比布尔可满足性算法在布线时间上减少了10.5%,在稳定性上提高了3.3%。

基于布尔可满足性的逻辑电路等价性验证方法

提出了基于布尔可满足性(Boolean Satisfiability,SAT)的逻辑电路等价性验证方法。这一验证方法把每个电路抽象成一个有穷自动机(FSM),为两个待验证的电路构造积机,把等价性验证问题转换成了积机的断言判定问题。改进了Tseitin变换方法,并将其用于把电路约束问题变换成(Conjunctive Normal Form,CNF)公式。之后则用先进的CNF SAT求解器zChaff判定积机所生成的布尔公式的可满足性。事例电路验证说明了该方法的有效性。

基于几何规划的布尔可满足问题求解方法

布尔可满足问题是计算机科学中诸多领域的重要问题,它的快速求解具有十分重要的意义。将具有实际物理背景的Solar算法中的拟物算法与几何规划相结合,提出并实现了一种布尔可满足性问题的连续求解方法。经实验验证,这种算法对布尔可满足性问题的求解具有一定的实用价值。

结合逻辑模拟和布尔可满足性的设计错误诊断方法

在集成电路设计验证与调试过程中,逻辑错误诊断工具通常会给出一定数量的候选错误区域,然后通过特定的算法尽可能多地减少候选区域,以方便错误的准确定位。在此提出一种结合模拟与布尔可满足性(SAT)的错误诊断方法,用于提高错误诊断准确性。该方法首先使用模拟方法对候选的错误区域逐一进行判断,对于不能由模拟方法判别的候选区域,使用基于SAT的形式化方法进一步判断。针对ISCAS′85电路的实验结果表明,该方法具有较高的错误诊断准确性和效率。

用布尔可满足性验证逻辑电路的等价性

提出了使用布尔可满足性来验证数字电路的等价性验证方法.这一验证方法把每个电路抽象成一个有限状态机,为两个待验证的电路构造积机,把等价性验证问题转换成了积机的断言问题.改进了Tseitin变换方法,用于把电路约束问题变换成合取范式公式.用先进的布尔可满足性求解器zChaff判定积机所生成的布尔公式的可满足性.事例电路验证说明了该方法的有效性.

基于布尔可满足性的组合电路ATPG算法

布尔可满足性被深入研究并广泛应用于电子设计自动化等领域。该文提出了一种基于布尔可满足性的组合电路ATPG改进算法。在采用当前最新布尔可满足性求解程序加速策略的基础上,比如冲突驱动训练、冲突导向回跳和重启动技术等,引入电路结构信息来实现基于结构的分支决策。通过新增的电路结构信息层,布尔可满足性求解程序只需稍加修改,就能利用和及时更新此信息。最后给出的实验结果表明了算法的可行性和有效性。

基于布尔可满足性的电路设计错误诊断算法

提出了一种组合电路设计错误诊断算法,该算法结合传统基于模拟的方法和可满足性问题求解技术,在不依赖于故障模型的条件下实现对电路逻辑错误的诊断定位.提出了基于布尔可满足性的增量式电路诊断方法,通过对可满足解依据电路结构信息筛选分级,提高了多错误诊断定位的分辨率和准确性;并提出多项启发式方法,避免了大量不必要的操作,使算法在时间和内存上保持有效性.实验结果表明,利用形式验证的技术来导向模拟的过程,抓住了高复杂度的多错误定位问题的特征,提高了电路错误诊断的效率.

基于消息传递关系网络的布尔可满足性预测

布尔可满足性求解能够验证的问题规模通常受限,因此,如何高精度地预测其可满足性既是重要的研究问题,也是一项具有挑战性的工作.相关研究工作一般使用由文字节点和子句节点组成的图来表示布尔可满足性问题的结构,但是这种表征方法缺少了变量、子句之间的重要关系信息.在所提方法中,通过将原始布尔可满足性问题实例表征为多关系异构图的方式来表达变量和句子之间的关系,并设计使用消息传递关系网络模型来捕获实例的关系信息,提取了更多的结构特征.结果表明:该模型在预测精度、泛化能力和资源需求等方面均优于现有模型,对所选数据集的平均预测精度为81%.该模型在小规模问题(变量数为100)上训练,在大规模数据集上预测的平均预测精度达到了80.8%.同时,该模型对随机生成的非均匀随机问题的预测精度达到99%,这意味着它学习了预测可满足性的重要特征.此外,模型预测所花费的时间随着问题规模的增大也只是成线性增长.总结而言,基于关系消息传递网络提出了一个预测精度更高、泛化能力更好的布尔可满足性预测方法.

在形式验证和ATPG中的布尔可满足性问题

介绍布尔可满足性 (SAT)求解程序在测试向量自动生成、符号模型检查、组合等价性检查和RTL电路设计验证等电子设计自动化领域中的应用 着重阐述如何在算法中有机地结合电路拓扑结构及其与特定应用相关的信息 ,以便提高问题求解效率

基于布尔可满足性的伪码捕获方法

为了提高扩频通信系统中伪码序列的检测概率,同时降低捕获时间,提出了一种基于布尔可满足性(SAT)的伪码捕获算法,首先将扩频通信中的捕获算法通过面向模块级的布尔可满足性合取范式进行建模,然后利用先进的SAT求解技术对模型进行求解,从而达到对伪码序列捕获的目的。理论方法和仿真结果表明,该方法能够有效提高捕获过程的检测概率,并降低捕获时间。

基于布尔可满足性的动态路径优化算法

在对现有的经典路径优化算法性能进行分析基础上,指出现有算法的缺点。通过对布尔可满足性理论的研究,提出基于布尔可满足性的路径优化算法,并结合记忆机制,将其应用在动态路径优化中,减少最短路径的搜索时间和不必要的重复搜索,体现该算法的优势。最后,利用该算法对一简单路网进行验证。

极小布尔不可满足子式的提取算法

研究了极小布尔不可满足子式的提取算法 ,它分为近似算法和精确算法两种 文中就精确算法提出了局部预先赋值的优化方案 ,并且在理论上证明了该算法的正确性 ;通过实验显示了此算法可以获得更高的效率 通过模拟实验观察到 ,利用完全算法进行近似提取的一个有趣现象 ,即随着公式密度的增加 。

求解布尔不可满足子式的消解悖论算法

求解布尔不可满足子式在超大规模集成电路设计与验证领域都具有非常重要的理论与应用价值,帮助EDA工具迅速定位错误与不一致。针对求解不可满足子式的非完全方法,提出了消解悖论与悖论解析树的概念,在此基础上提出一种启发式局部搜索算法。该算法根据公式的消解规则,采用局部搜索过程直接构造证明不可满足性的悖论解析树,而后递归搜索得到不可满足子式;算法中融合了布尔推理技术、动态剪枝方法及蕴含消除方法以提高搜索效率。基于随机测试集进行了实验对比,结果表明提出的算法优于同类算法。

一种求解布尔不可满足子式的局部搜索算法

解释布尔公式不可满足的原因在众多领域都具有非常重要的理论与应用价值,而不可满足子式能够为公式不可满足的原因提供精确的解释,帮助应用领域的自动化工具迅速定位错误,诊断问题失败的本质缘由。近年来涌现了许多基于SAT求解器DPLL回溯搜索过程的完全算法,但关于不完全方法提取不可满足子式的研究相对较少。因此,本文提出一种采用启发式局部搜索过程从公式的不可满足性证明中求解布尔不可满足子式的算法。该算法根据公式的消解规则通过局部搜索过程直接构造证明不可满足性的消解序列,并融合了布尔推理技术以提高搜索效率;而后通过一个递归过程遍历证明序列从而得到不可满足子式。通过实验与贪心遗传算法进行对比,结果表明本文提出的算法优于贪心遗传算法。

基于改进连续时间动态系统的模拟SAT求解器

针对布尔可满足性问题的高效求解进行了研究。首先,通过对k-SAT问题和基于耦合常微分方程形式的确定性连续时间动态系统的分析,提出了一种基于时延信息形式的改进连续时间动态系统方程,以保持集中搜索特性;然后,提出了实现该系统方程的三个主要组件即信号动态电路、辅助变量电路和数字验证电路的模拟设计。在信号动态电路的设计中,设计了一种获得更高性能、更小面积和更低功耗的模拟硬件形式;在提出的辅助变量电路和数字验证电路的模拟硬件设计中,实现了避免梯度下降搜索陷入无解和确定给定问题的解是否已经找到的目标;同时提出了降低面积和功耗的可替代辅助变量电路的两种设计方案。仿真实验结果表明,提出的新的模拟SAT求解器不仅是有效的,而且相比于单一软件算法实现的SAT求解器和其他硬件类SAT求解器具有更高的加速性能和更低的功耗。

基于SAT的GRANULE算法不可能差分分析

基于布尔可满足性问题(SAT)的自动化搜索方法可以直接刻画与、或、非、异或等逻辑运算,从而建立更高效的搜索模型。为更高效地评估GRANULE算法抵抗不可能差分攻击的能力,首先,基于S盒差分分布表性质优化S盒差分性质刻画的SAT模型;其次,对GRANULE算法建立基于比特的不可能差分区分器的SAT模型,通过求解模型得到多条10轮GRANULE算法的不可能差分区分器;再次,针对不可能差分区分器,给出改进的SAT自动化验证方法并验证;最后,将得到的区分器往前和往后各扩展3轮,对GRANULE-64/80算法发起16轮的不可能差分攻击,通过该攻击可以恢复80比特主密钥,时间复杂度为251.8次16轮加密,数据复杂度为241.8个选择明文。与表现次优的对GRANULE算法不可能差分分析的方法相比,所得到的区分器轮数和密钥恢复攻击轮数都提高了3轮,且时间复杂度、数据复杂度都进一步下降。