• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Microelectronics >Parallelization of unit propagation algorithm for SAT-based ATPG of digital circuits
【24h】

Parallelization of unit propagation algorithm for SAT-based ATPG of digital circuits

机译：基于SAT的数字电路ATPG的单元传播算法并行化

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The recent enhancements in Boolean Satisfiability solving has made SAT solvers a core engine for many real world applications especially for Automatic Test Pattern Generation (ATPG) in digital circuits. The majority of solving time is spent on iteratively propagating variable assignments that are inferred by decisions, so the Unit propagation (UP) is the most significant part in the Satisfiability problem. Parallelization of unit propagation in SAT solvers is a compelling way of obtaining an efficient procedure for the propositional satisfiability problem. This paper presents an efficient parallel unit propagation scheme utilizing the NVidia Compute Unified Device Architecture (CUDA), one of the most popular platforms for GPU computing. The paper presents experiments with two different design approaches and evaluates the results using a C++ algorithm for generating a 3D SAT-based formula of VLSI digital circuits from ISCAS'85 benchmark. The outcomes demonstrate the potential for the Unit Propagation (UP), leading to high execution performance using a simple NVIDIA platform. Both parallel algorithms have achieved speeds of 1.88x and 2.13x correspondingly using ISCAS'85 benchmark in comparison to previously published results.
机译：布尔可满足性解决方案的最新增强功能使SAT求解器成为许多实际应用中的核心引擎，尤其是数字电路中的自动测试码型生成（ATPG）。解决方案的大部分时间都花在迭代传播决策所决定的变量分配上，因此，单元传播（UP）是可满足性问题中最重要的部分。 SAT求解器中单元传播的并行化是获得针对命题可满足性问题的有效过程的一种令人信服的方式。本文提出了一种利用NVidia计算统一设备体系结构（CUDA）的高效并行单元传播方案，该体系结构是GPU计算最流行的平台之一。本文介绍了使用两种不同设计方法的实验，并使用C ++算法评估了结果，该算法可根据ISCAS'85基准生成基于3D SAT的VLSI数字电路公式。结果证明了单位传播（UP）的潜力，使用简单的NVIDIA平台可实现较高的执行性能。与以前发布的结果相比，使用ISCAS'85基准测试，两种并行算法的速度分别达到了1.88倍和2.13倍。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号