Parallelization of unit propagation algorithm for SAT based ATPG of digital circuits
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.
2016 28th International Conference on Microelectronics (ICM)