Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital logic testing
Patent
1998-05-27
2000-03-14
Teska, Kevin J.
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital logic testing
39550005, 39518317, 714738, G06F 944
Patent
active
060383925
ABSTRACT:
A Boolean SAT solver uses reconfigurable hardware to solve a specific input problem. Each of the plurality of ordered variables has a corresponding one of a plurality of state machines. Each state machine has an implication circuit for its respective variable, and operates in parallel according to an identical state machine. One state machine implements the Davis-Putnam method in hardware and provides improved performance over software by virtue of the parallel checking of direct and transitive implications. Another state machine implements a novel non-chronological backtracking method that takes advantage of the parallel implication checking and avoids the need to maintain or to traverse a GRASP type implication graph in the event of backtracking. The novel non-chronological backtracking provides for setting a blocking variable as a leaf variable and for changing only the value of the leaf variable, but possibly changing both the value and identity of a backtracking variable.
REFERENCES:
patent: 5377201 (1994-12-01), Chakradhar et al.
patent: 5602856 (1997-02-01), Teramoto
patent: 5831996 (1998-11-01), Abramovici et al.
T. Larrabee, "Efficient Generation of Test Patterns Using Boolean Satisfiability," Stanford University, Feb. 1990.
M. Gokhale, et al., "Building and Using a Highly Parallel Programmable Logic Array," Computer, Jan. 1991, pp. 81-89.
T. Larrabee, "Test Pattern Generation Using Boolean Satisfiabiilty, "IEEE Transactions on Computer-Aided Design, vol. 11, No. 1, Jan. 1992, pp. 4-15.
S. Chakradhar, et al., "A Transitive Closure Algorithm for Test Generation," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, No. 7, Jul. 1993, pp. 1015-1028.
P. Athanas, "Processor Reconfiguration Through Instruction-Set Metamorphosis," Computer, Mar. 1993, pp. 11-18.
R. Razdan, et al., "PRISC Software Acceleration Techniques," 1994 IEEE, pp. 145-149.
P. Athanas, et al., "Real-Time Image Processing on a Custom Computing Platform," Computer, Feb. 1995, pp. 16-24.
J. Silva, et al., "GRASP--A New Search Algorithm for Satisfiability," 1996 IEEE, pp. 220-227.
T. Suyama, "Solving Satisfiability Problems on FPGAs".
Ashar Pranav
Malik Sharad
Martonosi Margaret
Zhong Peixin
NEC USA Inc.
Phan Thai
Teska Kevin J.
LandOfFree
Implementation of boolean satisfiability with non-chronological does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Implementation of boolean satisfiability with non-chronological , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementation of boolean satisfiability with non-chronological will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-177749