Font Size: a A A

Design And Implementation Of Instance Specified SAT Sorve Chip Based On FPGA

Posted on:2018-12-02Degree:MasterType:Thesis
Country:ChinaCandidate:Z X ChenFull Text:PDF
GTID:2348330512487083Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
As the first proved NP-hard problem,the Boolean satisfiability problem(SAT)has important applications in many aspects,it is the core problem in the field of artificial intelligence,integrated circuit design and verification,computer science,mathematical logic,and plays an important role in computer complexity theory.As a NP-hard problem,this problem can not be solved in polynomial time,therefore the design of high efficient SAT solver has been valued by many scholars in the world,the SAT algorithms are divided into complete algorithms and incomplete algorithms,SAT solvers are divided into software solvers and hardware solvers,and the hardware solvers are divided into instance-specified solvers and application-specified solvers.This paper proposed two types of instance-specified solving framework based on FPGA,which are the circuit features based framework and the DPLL algorithm based framework,by changing the drive module of the circuit features based framework,three different solving methods are implemented,which are sequential traversal drived solver,true random number drived solver and pseudo random number drived solver,the experimental results of the three methods were analyzed and compared.For the DPLL algorithm based solver,this paper innovatively randomly sorted the variable selection order and variable assignment order before the solving circuit was composed,different solving circuits are generated and run for the same instance,the results of different running times were analyzed.The results of all instances were compared with other hardware and software solver Minisat.
Keywords/Search Tags:Boolean satisfiability, FPGA, conjunction normal form, true random number, pseudo-random number, DPLL algorithm, formal verification method
PDF Full Text Request
Related items