USA flag logo/image

An Official Website of the United States Government

An Efficient Parallel SAT Solver Exploiting Multi-Core Environments

Award Information

Agency:
National Aeronautics and Space Administration
Branch:
N/A
Award ID:
90548
Program Year/Program:
2009 / SBIR
Agency Tracking Number:
085391
Solicitation Year:
N/A
Solicitation Topic Code:
N/A
Solicitation Number:
N/A
Small Business Information
Aries Design Automation, LLC
2705 West Byron Street Chicago, IL 60618-3745
View profile »
Woman-Owned: No
Minority-Owned: No
HUBZone-Owned: No
 
Phase 1
Fiscal Year: 2009
Title: An Efficient Parallel SAT Solver Exploiting Multi-Core Environments
Agency: NASA
Contract: NNX09CC48P
Award Amount: $100,000.00
 

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.

Principal Investigator:

Miroslav Velev
Principal Investigator
7738566633
miroslav.velev@aries-da.com

Business Contact:

Miroslav N. Velev
Business Official
7738566633
miroslav.velev@aries-da.com
Small Business Information at Submission:

Aries Design Automation, LLC
6157 N Sheridan Road, Suite 16M Chicago, IL 60660

EIN/Tax ID: 202887585
DUNS: N/A
Number of Employees:
Woman-Owned: No
Minority-Owned: No
HUBZone-Owned: No