Method for design validation using retiming

Details Method for design validation using retiming Method for design validation using retiming

2005-03-29

2005-03-29

Thompson, A. M. (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

06874135

ABSTRACT:
A method for derivation and abstraction of test models for validation of industrial designs using guided simulation is described. The method employs automatic abstractions for the test model which reduce its complexity while preserving the class of errors that can be detected by a transition tour. A method for design validation comprising generating a state-based test model of the design. The test model is abstracted by retiming and latch removal. Finally, a validation technique is applied on the abstracted test model. First, the number of internal (non-peripheral) latches in a design is minimized via retiming using a method of Maximal Peripheral Retiming (MPR). According to the MPR method, internal latches are retimed to the periphery of the circuit. Subsequently, all latches that can be retimed to the periphery are automatically abstracted in the test model. The validation technique may comprise of model checking, invariant checking or simulation using test sequences generated from the abstracted test model.

REFERENCES:
patent: 5448497 (1995-09-01), Ashar et al.
patent: 5528604 (1996-06-01), El-Maleh et al.
patent: 5553000 (1996-09-01), Dey et al.
Gupta et al., Exploiting Retiming in a Guided Simulation Based Validation Methodology, Proceedings of the 10thConference on Correct Hardware Design and Verification Methods, pp. 350-353, Sep. 1999.*
A. Gupta et al., Toward Formalizing a Validation Methodology Using Simulation Coverage, Proceedings of the 34thDesign Automation Conference, pp. 740-745, Jun. 1997.*
C. Gianpiero et al., Optimizing Sequential Verification by Retiming Transformations,, Proceedings of the 37thConference on Design Automation, pp. 601-606, Jul. 2000.*
R. Ho et al., Architecture Validation for Processors, Proceedings of 22ndInternational Symposium on Computer Architecture, pp. 404-413, May. 1995.*
C. Kim et al., Test Sequence Generation Methods for Protocol Conformance Testing, 18thAnnual International Computer Software and Applications Conference, pp. 169-174 Nov. 1994.*
S. Huang et al., On verifying the correctness of retimed circuits, Proceedings., Sixth Great Lakes Symposium, pp. 277-280, Mar. 1996.*
N. Maheshwari et al., Minimum Area Retiming with Equivalent Initial States, IEEE/ACM International Conf. on Computer-Aided Design, pp. 216-219, Nov. 1997.*
K. Chen et al., Retargetable Static Timing Analysis for Embedded Software, 14th Annual Symposium on System Synthesis, pp. 39-44, Oct. 2001.*
A. Gupta et al., Partition-based Decision Heuristics for Image Computation using SAT and BDD IEEE/ACM International Conference on Computer Aided Design, pp. 286-292, Nov. 2001.*
J-Y Jang et al., Iterative Abstraction-based CTL Model Checking, Proceedings., Design, Automation and Test in Europe Conference. pp. 502-507, Mar. 2000.*
N. Maheshwari et al., Efficient Retiming of Large Circuits, IEEE Transactions, on VLSI Systems, pp. 74-83, Mar. 1998.*
B. Lin, Restructuring of Synchronous Logic Circuits, 1993 European Conference on Design Automation, pp. 205-209, Feb. 1993.*
J. Frossl et al., An Efficient Algorithm for Real-Time Symbolic Model Checking, 1996 European Design and Test Conference, pp. 15-20, Mar. 1996.*
G. York et al., An Integrated Environment for HDL Verification, 1995 International Verilog HDL Conference, pp. 9-18, Mar. 1995.*
A. Casavant et al., Property-specific Witness graph generation for Guided Simulation, Proceedings of Design, Automation and Test in Europe, 2001, p. 799, Mar. 2001.*
Q. Li et al., Evolutionary Computer Aided Prototyping System, 34th International Conference on Technology of Object-Oriented Languages and Systems, pp. 363-372, Aug. 2000.*
O.C.-S. Choy et al., Test Generation with Dynamic Probe Points in High Observability Testing Environment, IEEE Transactions on Computers, pp. 88-96, Jan. 1996.*
K. Eckl et al., A Practical Approach to Multiple-Class Retiming, Proceedings, 36th ACM/IEEE Conference on Design Automation, pp. 237-242, Jul. 1999.*
S. Bommu et al., Retiming-based Factorization for Sequential Logic Optimization, ACM Transactions on Design Automation of Electronic Systems, pp. 373-398, Jul. 2000.*
A. Gupta et al., Property-Specific Testbench Generation for Guided Simulation, Proceedings, 15thInternational Conference on VLSI Design, pp. 1-8, Mar. 2002.*
E. Clarke et al., Model Checking and Abstraction, ACM Transactions on Programming Languages and Systems, pp. 1512-1542, Sep. 1994.*
Shin-ichi Minato, “Generation of BDDs from Hardware Algorithm Descriptions,” ICCAD, pp. 1-6, IEEE, 1996.
Farzan Fallah, et al., “Funtional 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. Bergamaschi, et al., “Observable Time Windows: Verifying High-Level Synthesis Results,” IEEE Design and Test of Computers, IEEE, pp. 40-50, 1997.
J. Yuan, et al., “On Combining Formal and Informal Verification,” In Proceedings of the Workshop on Computer-Aided Verification, vol. 1254 of Lecture Notes in Computer Science, pp. 376-387, NY, Jun. 1997.
Raul Camposano, “Path-Based Scheduling for Synthesis,” IEEE Transactions on Computer-Aided Design, vol. 10, No. 1, pp. 85-93, Jan. 1991.
Roni Potasman, et al., “Percolation Based Synthesis,” 27thACM/IEEE Design Automation Conf., pp. 444-449, 1990.
Subhrajit Bhattacharya, “Performance Analysis and Optimization of Schedules for Conditional and Loop-Intensive Specifications,” 31stDAC, pp. 491-496, 1994.
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 Circuity,” 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.
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 Format 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.

Affiliated with

Also associated with

Rating

Method for design validation using retiming 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 for design validation using retiming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for design validation using retiming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3431332