An Efficient Parallel SAT Solver Exploiting Multi-Core Environments

Award Information
Agency: National Aeronautics and Space Administration
Branch: N/A
Contract: NNX09CC48P
Agency Tracking Number: 085391
Amount: $100,000.00
Phase: Phase I
Program: SBIR
Awards Year: 2009
Solicitation Year: N/A
Solicitation Topic Code: N/A
Solicitation Number: N/A
Small Business Information
Aries Design Automation, LLC
6157 N Sheridan Road, Suite 16M, Chicago, IL, 60660
DUNS: 361627933
HUBZone Owned: N
Woman Owned: N
Socially and Economically Disadvantaged: N
Principal Investigator
 Miroslav Velev
 Principal Investigator
 (773) 856-6633
 miroslav.velev@aries-da.com
Business Contact
 Miroslav Velev
Title: Business Official
Phone: (773) 856-6633
Email: miroslav.velev@aries-da.com
Research Institution
N/A
Abstract
The hundreds of stream cores in the latest graphics processors (GPUs), and the possibility to execute non-graphics computations on them, open unprecedented levels of parallelism at a very low cost. We will investigate ways to efficiently exploit this parallelism in order to accelerate the execution of a Boolean Satisfiability (SAT) solver. SAT has a wide range of applications, including formal verification and testing of software and hardware, scheduling and planning, cryptanalysis, and detection of security vulnerabilities and malicious intent. We bring a tremendous expertise in SAT solving, formal verification, and solving of Constraint Satisfaction Problems (CSPs) by efficient translation to SAT. In our previous work (done on the expenses of our company) we obtained 2 orders of magnitude speedup in solving Boolean formulas from formal verification of complex pipelined microprocessors, as well as 4 orders of magnitude speedup in SAT-based solving of CSPs. We expect to achieve speedups of up to 1 ýý 2 orders of magnitude in Phase 1, and up to 3 ýý 4 orders of magnitude in Phase 2.

* information listed above is at the time of submission.

Agency Micro-sites

SBA logo
Department of Agriculture logo
Department of Commerce logo
Department of Defense logo
Department of Education logo
Department of Energy logo
Department of Health and Human Services logo
Department of Homeland Security logo
Department of Transportation logo
Environmental Protection Agency logo
National Aeronautics and Space Administration logo
National Science Foundation logo
US Flag An Official Website of the United States Government