IMPLEMENTATION OF BOOLEAN SATISFIABILITY WITH NON-CHRONOLOGICAL BACKTRACKING IN RECONFIGURABLE HARDWARE

Web Published:
11/30/2011
Description:

 

Researchers at Princeton University have developed a novel method for implementing formula-specific Boolean Satisfiability solver circuits in configurable hardware. Princeton is currently seeking industrial collaborators to commercialize this technology.

 

As the complexity of designing electronic systems increases, the effectiveness and efficiency of Computer Aided Design (CAD) tools becomes paramount. Techniques that accelerate core CAD algorithms can bring about important changes in product design times. This new method for accelerating automatic test pattern generation (ATPG) and logic synthesis can offer substantial speedups (>200X in many cases) over traditional software approaches.

 

It is envisioned that these techniques will be most useful on SAT problems with very long GRASP runtimes or in cases where GRASP aborts.

 

Patent protection is pending.

 

For more information please contact:

             William H. Gowen
             Office of Patents and Licensing
             Princeton University
             5 New South Building
             Princeton, NJ 08544-0036
             (609) 258-6762
             (609) 258-1159 fax
            
wgowen@princeton.edu 

Patent Information:
Category(s):
Computers and Software
For Information, Contact:
John Ritter
Director
Princeton University
609-258-1570
jritter@Princeton.EDU
Inventors:
Pranav Ashar
Margaret Martonosi
Peixin Zhong
Sharad Malik
Keywords:
computers/software