Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-04-03
2010-12-14
Dinh, Paul (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C703S014000
Reexamination Certificate
active
07853903
ABSTRACT:
An improved method and mechanism for verification of an electrical circuit design is provided. The method and system simultaneously provides the coverage advantage of formal verification with the scaling efficiencies of simulation. In one approach, the method and system generates an intelligent set of test vectors off a resolution proof. The intelligent set of test vectors can be used to simulate the circuit design for complete coverage without having to test the entire set of possible variable assignments for the CNF formula corresponding to the circuit design.
REFERENCES:
patent: 5617510 (1997-04-01), Keyrouz et al.
patent: 6031984 (2000-02-01), Walser
patent: 6247164 (2001-06-01), Ashar et al.
patent: 6816825 (2004-11-01), Ashar et al.
patent: 6912700 (2005-06-01), Franco et al.
patent: 7596770 (2009-09-01), Kuehlmann et al.
patent: 2001/0007970 (2001-07-01), Kohno et al.
Dantsin, E. et al. “A Deterministic (2-2/k+1)n Algorithm for k-SAT Based on Local Search”, 2002, vol. 289, Issue 1, pp. 69-83, Essex UK.
Abramovici, M. et al. Digital Testing and Testable Design, Wiley-IEEE Press, Sep. 1994, Title page, Table of Contents and pp. 1-242.
Abramovici, M. et al. Digital Testing and Testable Design, Wiley-IEEE Press, Sep. 1994, pp. 243-455.
Baptista, L. et al.; “The Interplay of Randomization and Learning of Real-World Instances of Satisfiability”, Proceedings of the AAAI Workshop on Leveraging Probability and Uncertainty in Computation, Jul. 2000, 4 pgs.
Bayardo, R. et al.; “Using CSP Look-Back Techniques to Solve Real-World SAT Instances” Proceedings of the 14th National Conference on Artificial Intelligence and 9th Innovative Applications of Artificial Intelligence Conference, 1997, pp. 203-208.
Ben-Sasson, E. et al. “Near-Optimal Separation of Treelike and General Resolution” Electronic Colloquium on Computational Complexity, Report No. 5 and Third Workshop on the Satisfiabiility Problem—May 2000, Jan. 17, 2000; pp. 1-17.
Biere, A., et al. “Symbolic Model Checking Using SAT Procedures Instead of BDDs”, Proceedings of Design Automation Conference (DAC'99), 1999, pp. 317-320.
Brayton, R.K., et al. “Logic Minimization Algorithms for VLSI Synthesis”, Kluwer Academic Publishers, Boston, MA, USA, 1984.
Burch, J. R., et al. “Tight Integration of Combination Verification Methods” k Proceedings of the International Conference on Computer-Aided Design, 1998, pp. 570-576.
Davis, M., et al. “A Machine Program for Theorem-Proving”, Communications of the ACM, 1962, pp. 394-397.
Dubois, O., et al. “SAT versus UNSAT”, Second DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1996, vol. 26, pp. 415-436.
Freeman, J.W. “Improvements to Propositional Satisfiability Search Algorithms” A Dissertation in Computer and Information Science, University of Pennsylvania, 1995.
Goldberg, E. et al; “Using SAT for Combinational Equivalence Checking” Proceedings of the Design Automation and Test in Europe Conference, 2001, pp. 114-121.
Goldberg, E. et al. “BerkMin: A Fast and Robust SAT-Solver” Proceedings of the design, Automation and Test in Europe Conference and Exhibition (DATE-2002) Paris, FR, Mar. 4-8, 2002, pp. 142-149.
Goldberg, E. “Testing Satisfiability of CNF Formulas by Computing a Stable Set of Points” Proceedings of the Conference Automated Deduction (CADE 2002) Copenhagen, DK, Jul. 27-30, 2002, vol. 2392, pp. 161-180.
Goldberg, E. “Testing Satisfiability of CNF Formulas by Computing a Stable Set of Points” Annals of Mathematics and Artificial Intelligence, Jan. 2005, vol. 43, Issue 1-4, pp. 65-89.
Goldberg, E. “Determinization of Resolution by an Algorithm Operating on Complete Assignments”, SAT-2006, pp. 90-105.
Goldberg, E. “On Bridging Simulation and Formal Verification” Technical Report, University of California at Berkeley, Feb. 2007, CDNL-TR-2007-0212.
Gomes; C. P., et al. “Heavy-Tailed Distributions in Combinatorial Search”, Principles and Practice of Constraint Programming (CP97), 1997, pp. 121-135.
Gomes, C. P., et al. “Boosting Combinatorial Search Through Randomization”. Proceedings of the International Conference on Principles and Practice of Constraint Programming, 1998, pp. 431-437.
Li, C. M. “A Constraint-Based Approach to Narrow Search Trees for Satisfiability”, Information Processing Letters 71, 1999, vol. 71, pp. 75-80.
Marques-Silva, J. P. et al. “GRASP: A New Search Algorithm for Satisfiability”, The University of Michigan, Apr. 10, 1996; pp. 1-17, CSE-TR-292-96.
Marques-Silva, J. P. et al. “GRASP: A Search Algorithm for Propositional Satisfiability”, IEEE Transactions on Computers, May 1999, vol. 48, No. 5, pp. 506-521.
Marques-Silva, J. “The Impact of Branching Heuristics in Propositional Satisfiability Algorithms”, Proceedings of the 9th Portuguese Conference on Artificial Intelligence (EPIA) Sep. 1999, pp. 62-74.
Miroslav Velev's SAT Benchmarks, 3 pgs., located at: http://www.ece.cmu.edu/˜mvelev/sat—benchmarks.html.
Moskewicz, M. W. et al. “Chaff: Engineering an Efficient SAT Solver”, Proceedings of the 38th Design Automation Conference (DAC '01) 2001, pp. 530-535.
Novikov, Y. A. “Using Restarts When Solving SAT-Instances”, Proceedings of the Fourth International Conference on Computer-Aided Design of Discrete Devices (CAD DD '01) 2001, vol. 3, pp. 166-174.
SATLIB—Benchmark Problems, 2004, located at: http://www.satlib.org/benchm.html.
The SAT-Ex site, 2004, located at: http://www.lri.fr/ ˜simon/satex/satex.php3.
Selman, B. et al. “A New Method for Solving Hard Satisfiability Problems” The 10th National Conference on Artificial Intelligence (AAAI-92), San Jose, CA, Jul. 12-16, 1992, pp. 440-446.
Selman, B. et al. “Noise Strategies for Improving Local Search” The 12th National Conference on Artificial Intelligence (AAAI-94), Seattle, WA, Jul. 31-Aug. 4, 1994, pp. 337-343.
Selman, B. et al. “Generating Hard Satisfiability Problems” Artificial Intelligence, 1996, vol. 81, pp. 17-29.
Sentovich, E.M. et al. “SIS: A System for Sequential Circuit Synthesis” Technical Report, University of California at Berkeley, 1992. Memorandum No. UCB/ERL. M92/41.
Stephan, P., et al., “Combinational Test Generation Using Satisfiability”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Sep. 1996, vol. 15, No. 9, pp. 1167-1176.
Velev, M. N., Curriculum Vitae, 2004, located at: http://www.ece.cmu.edu/˜mvelev.
Zhang, H. “SATO; An Efficient Propositional Prover”, Proceedings of the 14th International Conference on Automated Deduction (CADE-14), Jul. 1997, pp. 272-275.
Balarin Felice
Goldberg Evgueni
Cadence Design Systems Inc.
Dinh Paul
Vista IP Law Group LLP
LandOfFree
Method and mechanism for performing simulation off... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and mechanism for performing simulation off..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and mechanism for performing simulation off... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4167640