Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Circuit simulation
Reexamination Certificate
2008-06-03
2008-06-03
Shah, Kamini (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Circuit simulation
C703S013000, C703S015000, C703S016000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
07383166
ABSTRACT:
A method of checking correctness of scheduling of a circuit where a schedule for the circuit is obtained from a behavioral description. The method comprising extracting loop invariants to determine a sufficient set of acyclic threads when loops are present, performing symbolic simulation to extract the above loop invariants, and proving equivalence of the acyclic threads. Systems, computer systems and computer program products that incorporate the techniques of verification and correctness checking according to the present invention have also been disclosed.
REFERENCES:
patent: 5331568 (1994-07-01), Pixley
patent: 5452239 (1995-09-01), Dai et al.
patent: 5513122 (1996-04-01), Cheng et al.
patent: 5801958 (1998-09-01), Dangelo et al.
patent: 5870308 (1999-02-01), Dangelo et al.
patent: 5875196 (1999-02-01), Chakradhar et al.
patent: 6163876 (2000-12-01), Ashar et al.
patent: 6212669 (2001-04-01), Jain
patent: 6216252 (2001-04-01), Dangelo et al.
patent: 6295626 (2001-09-01), Nair et al.
patent: 6308313 (2001-10-01), Lakshminarayana et al.
patent: 6324678 (2001-11-01), Dangelo et al.
patent: 6484134 (2002-11-01), Hoskote
patent: 6745160 (2004-06-01), Ashar et al.
Chow, Fred et al. “A New Algorithm for Partial Redundancy Elimination based on SSA Form.” ACM 1997.
Shen, Jun et al. “An Object-Oriented Net Graph Model for Agent Group Based Network Management.” IEEE 1999.
McFarland, Michael C. “Formal Verification of Sequential Hardware: A Tutorial.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12 No. 5., May 1993.
S. Owre, et al., “PVS: A Prototype Verification System,” 11thInt'l. Conf. on Automated Deduction, NY, pp. 748-752; Jun. 1992.
S. Malik, et al., “Retiming and Resynthesis: Optimizing Sequential Networks with Combinational Techniques,” IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 10(1):74-84, Jan. 1991.
Charles E. Leiserson, et al., “Retiming Synchronous Circuitry,” Algorithmica, 6(1):5-36, 1991.
E. M. Sentovich, et al., “Sequential Circuit Design Using Synthesis and Optimization,” In Proceedings of the IEEE Int'l. Conf. on Computer Design, 1992.
A. Balakrishnan, et al., “Software transformations for Sequential Test Generation,” In Fourth Asian Test Symposium, pp. 266-272, 1995.
J. R. Burch, et al., “Symbolic Model Checking for Sequential Circuit Verification,” IEEE Transactions on Computer-Aided Design, 13(4):401-424, Apr. 1994.
Wayne Wolf, et al., “The Princeton University Behavioral Synthesis System,” 29thACM/IEEE Design Automation Conf., pp. 182-187, 1992.
A. Gupta, et al., “Toward Formalizing a Validation Methodology Using Simulation Coverage,” IN Proceedings of the 34thACM/IEEE Design Automation Conf., pp. 740-745, Jun. 1997.
Pranav Ashar, et al., “Verification of RTL Generated from Scheduled Behavior in a High-Level Synthesis Flow,” ICCAD, pp. 517-524, 1998.
R. C. Ho, et al., “Validation Coverage Analysis for Complex Digital Designs,” In Proceedings of the IEEE Int'l. Conf. on Computer-Aided Design, pp. 146-151, Nov. 1996.
O. Coudert, “Verification of Sequential Machines Using Boolean Functional Vectors,” In L. M. J. Claesen, Editor, Proceedings of the IFIP International Workshop on Applied Formal Methods for Correct VLSI Design, Belgium, 1989, vol. II, pp. 179-196, Amsterdam, 1989.
0 in Design Automation. Directed Search. http://www.0-in.com/directed—search.html.
R. K. Brayton et al., “VIS: A System for Verification and Synthesis,” Technical Report UCS/ERL M95, Electronics Research Lab, University of California, Dec. 1995.
“Formal Verification in Hardware Design: A Survey”, C. Kern, ACM Trans. On Design Automation of Electronic System, vol. 4, No. 2, Apr. 1999.
“Automatic functional test generation using the extended finite state machine model”, K.T. Cheng, in Proc. Design Automation conf., Jun. 1993.
“Incorporating speculative execution into scheduling for control-flow intensive behaviors”, G. Lakshinarayana, in Proc. Design Automation conf., Jun. 1998.
“Verification of Scheduling in the Presence of Loops Using Uninterpreted Symbolic Simulation”, P. Ashar, Technical Report, C&C Research Labs, NEC USA, Oct. 16, 1998.
Chih-Tung Chen, et al., “A hybrid Numeric/Symbolic Program for Checking Functional and Timing Compatibility of Synthesized Designs,” Technical Report Ceng, Univ. of Southern California, pp. 112-117, 1994.
D. Lewin, et al., “A Methodology for Processor Implementation Verification,” In Proceedings of the Int. Conf. on Formal Methods in CAD, pp. 126-142, Nov. 1996.
Robert E. Shostak, “An Algorithm for Reasoning About Equality,” Communications of the ACM, vol. 21, No. 7, pp. 583-585, Jul. 1978.
R. C. Ho, et al. “Architecture Validation for Processors,” In Proceedings of the 22ndAnnual Intl. Symposium on Computer Architecture, Jun. 1995.
K. Cheng, et al., “Automatic Functional Test Generation Using the Extended Finite State Machine Model,” In Proceedings of the 30thACM/IEEE Design Automation Conf., pp. 86-91, Jun. 1993.
Yatin V. Hoskote, et al., “Automatic Extraction of the Control Flow Machine and Application to Evaluating Coverage of Verification Vectors,” Technical Report Ceng, Univ. of Texas at Austin, pp. 532-537, 1995.
H. Iwashita, et al., “Automatic Test Program Generation for Pipelined Processors,” In Proceedings of the IEEE Intl. Conf. on Computer Design, pp. 580-583, Oct. 1994.
A. K. Chandra, et al., “Avpgen—A Test Case Generator for Architecture Verificaton,” IEEE Transactions on VLSI Systems, 6(6), Jun. 1995.
R. Gupta, et al., “Ballast: A Methodology for Partial Scan Design,” In Proceedings of the Intl. Symposium on Fault Tolerant Computing, pp. 118-125, Jun. 1989.
D. Knapp, et al., “Behavioral Synthesis Methodology for HDL-Based Specification and Validation,” 32nd Design Automation Conf., pp. 286-291, 1995.
F. Brglez, et al., “Combinational Profiles of Sequential Benchmark Circuits,” In Proceedings of the International Symposium on Circuits and Systems, Portland, Oregon, May 1989.
D. Geist, et al., “Coverage-Directed Test Generation Using Symbolic Techniques,” In Proceedings of the Int. Conf. on Formal Methods in CAD, pp. 143-158, Nov. 1996.
Robert B. Jones, et al., “Efficient Validity Checking for Processor Verification,” pp. 2-6, IEEE, 1995.
Ivan Radivojevic, et al., “Ensemble Representation and Techniques for Exact Control-Dependent Scheduling,” pp. 60-65, IEEE, 1994.
P. Wolper, “Expressing Interesting Properties of Programs in Propositional Temporal Logic,” In Proceedings of the 13thAnnual ACM Symposium on Principles of Programming Languages, pp. 184-192, ACM, NY, Jan. 1986.
Anton T. Dahbura, “Formal Methods for Generating Protocol Conformance Test Sequences,” Proceedings of the IEEE, vol. 70, No. 8, pp. 1317-1326, Aug. 1990.
R. P. Kurshan, “Formal Verification in a Commercial Setting,” In Proceedings of the ACM/IEEE Design Automation Conf., pp. 258-262, Jun. 1997.
Shin-ichi Minato, “Generation of BDDs from Hardware Algorithm Descriptions,” ICCAD, pp. 1-6, IEEE, 1996.
Farzan Fallah, et al., “Functional Vector Generation for HDL Models Using Linear Programming and 3-Satisfiability,” DAC, pp. 528-533, 1998.
H. J. Touati, et al., “Implicit State Enumeration of Finite State Machines Using BDDs,” In Proceedings of the IEEE International Conf. on Computer-Aided Design, pp. 130-133, IEEE Computer Society Press, CA., 1990.
Ganesh Lakshminarayana, et al. “Incorporating Speculative Execution into Scheduling of Control-Flow Intensive Behavioral Descriptions,” ACM, San Francisco, CA., pp. 108-113, 1998.
Reinaldo A.
Ashar Pranav
Bhattacharya Subhrajit
Raghunathan Anand
Day Herng-Der
NEC Corporation
Shah Kamini
Sughrue & Mion, PLLC
LandOfFree
Verification of scheduling in the presence of loops using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Verification of scheduling in the presence of loops using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Verification of scheduling in the presence of loops using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2801548