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

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

应用不可满足子式的解码电路综合优化方法

解释布尔公式不可满足的原因在很多领域都具有实际的应用需求,而最小不可满足子式能够为诸如电路的自动综合等应用领域中的不可满足原因提供最精确的解释。因此,将两种能够高效求解最小不可满足子式的算法——分支-限界算法与贪心遗传算法,集成到解码电路的自动综合工具中。采用通信领域的标准编码电路作为测试集,将两种算法进行对比。实验结果表明,在运行时间与每秒剔除的短句数方面,贪心遗传算法优于分支-限界算法;不可满足子式在解码电路的自动综合过程中发挥重要作用。     

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

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

一种128位高性能全流水浮点乘加部件

高精度的浮点乘加融合(FMA)部件一直是高性能微处理器设计追求的目标。提出了一种128位精度全流水FMA体系结构,采用10级平衡流水线,重点对超宽位的乘法器、加法器、前导零预测和规格化进行了流水优化。设计综合的结果表明,基于SMIC0.13μm工艺,该结构频率可以达到465MHz,比现有128位FMA性能提高了130%;在TSMC65nm工艺下,该结构的频率可达到1.075GHz,基本满足高性能计算的要求。     

一种基于Wallace树的分散式DCT/IDCT体系结构

提出了一种新的基于Wallace树的分散式DCT/IDCT体系结构。它不依赖于ROM和乘法器,用面积开销低的加法器、移位器和4-2压缩器,实现了乘法密集的DCT/IDCT算法。该体系结构在SMIC 0.18μm工艺上进行了设计和综合,可以达到100Mpixels/s的吞吐率,只消耗了36 141个晶体管和1024bits转换存储器,时序—面积性能较已有的体系结构有了显著的改善。     

基于SAT的电路错误定位方法研究进展

随着VLSI芯片复杂度不断增加,功能验证与调试已占到整个芯片设计周期的60%以上。而错误的定位往往消耗大量的时间与精力,因此迫切需要一种高效的方法诊断与定位电路中的错误。针对近年来出现的许多电路错误定位方法,介绍了电路错误诊断方法的分类与工作流程,深入分析了基于SAT的错误定位方法的基本原理;对各种算法进行了概述评论,并简要介绍了在不可满足子式求解方面所做的一些研究工作,而不可满足子式能够显著提高错误定位效率与精度;讨论了电路错误定位技术所面临的主要挑战,并对今后的研究方向进行了展望。     

基于深度优先搜索与增量式求解的极小一阶不可满足子式提取算法

随着寄存器传输级甚至行为级的硬件描述语言应用越来越广泛,基于一阶逻辑的可满足性模理论(Satisfiability Modulo Theories,SMT)逐渐替代布尔可满足性(Boolean Satisfiability,SAT),在VLSI形式化验证领域具有更加重要的应用价值。而极小不可满足子式能够帮助EDA工具迅速定位硬件中的逻辑错误。针对极小SMT不可满足子式的求解问题,采用深度优先搜索与增量式求解策略,提出了深度优先搜索的极小SMT不可满足子式求解算法。与目前最优的宽度优先搜索算法对比实验表明:该算法能够有效地求解极小不可满足子式,随着公式的规模逐渐增大时,深度优先搜索算法优于宽度优先搜索算法。