US6816825B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Simulation vector generation from HDL descriptions for observability-enhanced statement coverage
Assignee: NEC Corp
•
Filing: 1999-06-18
•
Granted: 2004-11-09
•
Expires: 2019-06-18
Abstract
Abstract A method of automatically generating vector sequences for an observability based coverage metric supports design validation. A design validation method for Register Transfer Level (RTL) circuits includes the generation of a tag list. Each tag in the tag list models an error at a location in HDL code at which a variable is assigned a value. Interacting linear and Boolean constraints are generated for the tag, and the set of constraints is solved using an HSAT solver to provide a vector that covers the tag. For each generated vector, tag simulation is performed to determine which others of the tags in the tag list are also covered by that vector. Vectors are generated until all tags have been covered, if possible within predetermined time constraints, thus automatically providing a set of vectors which will propagate errors in the HDL code to an observable output. Performance of the design validation method is enhanced through various heuristics involving path selection and tag magnitude maximization.
Inventors
- 👤 Pranav Ashar
- 👤 Srinivas Devadas
- 👤 Farzan Fallah
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 09:34
CPC Classifications
G; G01; G01R; G01R31/00; G01R31/28; G01R31/317; G01R31/3181; G01R31/3183; G01R31/318307; G01R31/318364
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
77 words
A method for automatic vector generation for observability-based statement coverage for a design of a circuit, comprising: providing a representation of said design; and automatically generating a vector sequence, based on said representation of said design, said vector sequence being generated by a computer so that every vector of the generated sequence is capable of propagating an error to an observable output defined by said design of said circuit, said vector sequence being generated by a computer.
Claim 2
Independent Claim
77 words
A method for automatic vector generation for observability-based statement coverage for a design of a circuit, comprising: providing a representation of said design; and automatically generating a vector sequence, based on said representation of said design, said vector sequence being generated by a computer so that every vector of the generated sequence is capable of propagating an error to an observable output defined by said design of said circuit, said vector sequence being generated by a computer.
Claim 3
Dependent Claim
67 words
The method for vector generation as set forth in claim 1 , further comprising a said step of simulating errors for said representation of said design using said vector sequence, comprising: modeling said errors as tags; and injecting said tags to determine whether perturbations in a value at a location will result in a perturbation in a value at said observable output for said generated vector sequence.
Claim 4
Dependent Claim
27 words
The method for vector generation as set forth in claim 2 , wherein said generating step includes using a hybrid linear programming and Boolean satisfiability (HSAT) procedure.
Claim 5
Dependent Claim
146 words
The method for vector generation as set forth in claim 3 , further comprising: said representation of said design being HDL code and including variable assignments; preparing a tag list, each tag corresponding to one of said variable assignments, each of said tags being initially uncovered; selecting an uncovered tag, said selected uncovered tag defining a set of transitive fanout variables and paths among said transitive fanout variables; marking said set of transitive fanout variables; attempting to generate said vector sequence covering said uncovered tag by: generating a set of constraints; setting up an HSAT problem using said set of constraints, and finding a solution to said HSAT problem by solving said set of constraints with said HSAT procedure, said solution defining said vector sequence covering said tag; and when said vector sequence covering said tag can be generated, identifying said tag as a covered tag.
Claim 6
Dependent Claim
56 words
The method for vector generation as set forth in claim 4 , further comprising, after said vector sequence is generated, performing said simulating of said vector sequence and said simulating of said errors with tag simulation using said vector sequence to detect, and to identify as covered, others of said tags covered by said vector sequence.
Claim 7
Dependent Claim
22 words
The method for vector generation as set forth in claim 4 , wherein said constraints include interacting linear constraints and Boolean constraints.
Claim 8
Dependent Claim
57 words
The method for vector generation as set forth in claim 4 , further comprising: after said step of preparing a tag list, randomly generating a plurality of vector sequences; performing said tag simulation using said plurality of randomly generated vector sequences; and identifying as covered ones of said tag list covered by said randomly generated vector sequences.
Claim 9
Dependent Claim
78 words
The method for vector generation as set forth in claim 4 , further comprising: said set of constraints being generated for only a limited number of said paths for said selected uncovered tag, thereby defining said HSAT problem as a limited HSAT problem; attempting to solve said limited HSAT problem; and when a solution to said limited HSAT problem cannot be found, generating said set of constraints for different ones of said paths for said selected uncovered tag.
Claim 10
Dependent Claim
31 words
The method for vector generation as set forth in claim 8 , further comprising selecting said limited number of said paths based on a respective length of each of said paths.
Claim 11
Dependent Claim
30 words
The method for vector generation as set forth in claim 4 , further comprising maximizing a magnitude for said selected tag at which said vector sequence covers the said tag.
Claim 12
Dependent Claim
41 words
The method for vector generation as set forth in claim 10 , wherein said step of maximizing said magnitude for said selected tag is performed by maximizing a difference between an upper bound and a lower bound of said tag magnitude.
Claim 13
Dependent Claim
52 words
The method for vector generation as set forth in claim 10 , wherein said step of maximizing said magnitude for said selected tag is performed by adding constraints to said HSAT problem forcing propagation of said tag only through operators that can propagate said tag independent of said respective tag magnitude thereof.
Claim 14
Dependent Claim
77 words
The method for vector generation as set forth in claim 10 , wherein said step of maximizing said magnitude for said selected tag is performed by making a determination, after said generation of said vector sequence, as to whether said vector sequence can propagate said selected tag independent of said respective tag magnitude, and, when said determination indicates that said vector sequence cannot propagate said selected tag independent of said respective tag magnitude, generating another vector sequence.
Claim 15
Dependent Claim
48 words
The method for vector generation as set forth in claim 4 , further comprising a step of identifying ones of said tags that cannot be propagated to an observable output, and wherein said step of generating vector sequences is not performed for said identified ones of said tags.
Claim 16
Dependent Claim
40 words
The method for vector generation as set forth in claim 4 , further comprising selecting ones of said tags for vector sequence generation in an order based on a respective minimum number of unrollings required for covering each said tag.
Claim 17
Dependent Claim
99 words
A computer system adapted to perform vector generation for observability-based statement coverage for a representation of a design of a circuit, comprising: a processor, and a memory including software instructions adapted to enable the computer system to perform the steps of: automatically generating a vector sequence, based on said representation of said design, said vector sequence being generated by a computer so that every vector of the generated sequence is capable of propagating an error to an observable output defined by said design of said circuit; and simulating errors for said representation of said design using said vector sequence.
Claim 18
Dependent Claim
99 words
A computer system adapted to perform vector generation for observability-based statement coverage for a representation of a design of a circuit, comprising: a processor, and a memory including software instructions adapted to enable the computer system to perform the steps of: automatically generating a vector sequence, based on said representation of said design, said vector sequence being generated by a computer so that every vector of the generated sequence is capable of propagating an error to an observable output defined by said design of said circuit; and simulating errors for said representation of said design using said vector sequence.
Claim 19
Dependent Claim
62 words
The computer system adapted to perform vector generation as set forth in claim 16 , wherein said software instructions, for said step of simulating errors, include: modeling said errors as tags; and injecting said tags to determine whether perturbations in a value at a location will result in a perturbation in a value of said observable output for said generated vector sequence.
Claim 20
Dependent Claim
34 words
The computer system adapted to perform vector generation as set forth in claim 17 , wherein said software instructions, for said generating step, include using a hybrid linear programming and Boolean satisfiability (HSAT) procedure.
Claim 21
Dependent Claim
154 words
The computer system adapted to perform vector generation as set forth in claim 18 , wherein said representation of said design is IIDL code including variable assignments, and wherein said software instructions further comprise: preparing a tag list, each tag corresponding to one of said variable assignments, each of said tags being initially uncovered; selecting an uncovered tag, said selected uncovered tag defining a set of transitive fanout variables and paths among said transitive fanout variables; marking said set of transitive fanout variables; attempting to generate said vector sequence covering said uncovered tag by: generating a set of constraints; setting up an HSAT problem using said set of constraints, and finding a solution to said HSAT problem by solving said set of constraints with said HSAT procedure, said solution defining said vector sequence covering said tag; and when said vector sequence covering said tag can be generated, identifying said tag as a covered tag.
Claim 22
Dependent Claim
62 words
The computer system adapted to perform vector generation as set forth in claim 19 , further comprising software instructions for, after said vector sequence is generated, performing said simulating of said vector sequence and said simulating of said errors with tag simulation using said vector sequence to detect, and to identify as covered, others of said tags covered by said vector sequence.
Claim 23
Dependent Claim
25 words
The computer system adapted to perform vector generation as set forth in claim 19 , wherein said constraints include interacting linear constraints and Boolean constraints.
Claim 24
Dependent Claim
63 words
The computer system adapted to perform vector generation as set forth in claim 19 , further comprising software instructions for: after said step of preparing a tag list, randomly generating a plurality of vector sequences; performing said tag simulation using said plurality of randomly generated vector sequences; and identifying as covered ones of said tag list covered by said randomly generated vector sequences.
Claim 25
Dependent Claim
84 words
The computer system adapted to perform vector generation as set forth in claim 19 , further comprising software instructions for: said set of constraints being generated for only a limited number of said paths for said selected uncovered tag, thereby defining said HSAT problem as a limited HSAT problem; attempting to solve said limited HSAT problem; and when a solution to said limited HSAT problem cannot be found, generating said set of constraints for different ones of said paths for said selected uncovered tag.
Claim 26
Dependent Claim
37 words
The computer system adapted to perform vector generation as set forth in claim 23 , further comprising software instructions for selecting said limited number of said paths based on a respective length of each of said paths.
Claim 27
Dependent Claim
36 words
The computer system adapted to perform vector generation as set forth in claim 19 , further comprising software instructions for maximizing a magnitude for said selected tag at which said vector sequence covers the said tag.
Claim 28
Dependent Claim
44 words
The computer system adapted to perform vector generation as set forth in claim 25 , wherein said step of maximizing said magnitude for said selected tag is performed by maximizing a difference between an upper bound and a lower bound of said tag magnitude.
Claim 29
Dependent Claim
55 words
The computer system adapted to perform vector generation as set forth in claim 25 , wherein said step of maximizing said magnitude for said selected tag is performed by adding constraints to said HSAT problem forcing propagation of said tag only through operators that can propagate said tag independent of said respective tag magnitude thereof.
Claim 30
Dependent Claim
80 words
The computer system adapted to perform vector generation as set forth in claim 25 , wherein said step of maximizing said magnitude for said selected tag is performed by making a determination, after said generation of said vector sequence, as to whether said vector sequence can propagate said selected tag independent of said respective tag magnitude, and, when said determination indicates that said vector sequence cannot propagate said selected tag independent of said respective tag magnitude, generating another vector sequence.
Claim 31
Dependent Claim
54 words
The computer system adapted to perform vector generation as set forth in claim 19 , further comprising software instructions for a step of identifying ones of said tags that cannot be propagated to an observable output, and wherein said step of generating vector sequences is not performed for said identified ones of said tags.
Claim 32
Dependent Claim
46 words
The computer system adapted to perform vector generation as set forth in claim 19 , further comprising software instructions for selecting ones of said tags for vector sequence generation in an order based on a respective minimum number of unrollings required for covering each said tag.
Claim 33
Dependent Claim
107 words
A computer program product for enabling a computer to perform vector generation for observability-based statement coverage for a representation of a design of a circuit, comprising: software instructions for enabling the computer to perform predetermined operations, and a computer readable medium bearing the software instructions; the predetermined operations including the steps of: automatically generating a vector sequence, based on said representation of said design, said vector sequence being generated by a computer so that every vector of the generated sequence is capable of propagating an error to an observable output defined by said design of said circuit; and simulating errors for said modified version of said representation.
Claim 34
Dependent Claim
107 words
A computer program product for enabling a computer to perform vector generation for observability-based statement coverage for a representation of a design of a circuit, comprising: software instructions for enabling the computer to perform predetermined operations, and a computer readable medium bearing the software instructions; the predetermined operations including the steps of: automatically generating a vector sequence, based on said representation of said design, said vector sequence being generated by a computer so that every vector of the generated sequence is capable of propagating an error to an observable output defined by said design of said circuit; and simulating errors for said modified version of said representation.
Claim 35
Dependent Claim
69 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 31 , wherein said predetermined operations, for said step of simulating errors, include: modeling said errors as tags; and injecting said tags to determine whether perturbations in a value at a location will result in a perturbation in a value of said observable output of said representation for said generated vector sequence.
Claim 36
Dependent Claim
38 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 32 , wherein said predetermined operations, for said generating step, include using a hybrid linear programming and Boolean satisfiability (HSAT) procedure.
Claim 37
Dependent Claim
159 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 33 , wherein said representation of said design is HDL code and includes variable assignments, and wherein said predetermined operations further comprise: preparing a tag list, each tag corresponding to one of said variable assignments, each of said tags being initially uncovered; selecting an uncovered tag, said selected uncovered tag defining a set of transitive fanout variables and paths among said transitive fanout variables; marking said set of transitive fanout variables; attempting to generate said vector sequence covering said uncovered tag by: generating a set of constraints; setting up an HSAT problem using said set of constraints, and finding a solution to said HSAT problem by solving said set of constraints with said HSAT procedure, said solution defining said vector sequence covering said tag; and when said vector sequence covering said tag can he generated, identifying said tag as a covered tag.
Claim 38
Dependent Claim
66 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 34 , wherein said predetermined operations include, after said vector sequence is generated, performing said simulating of said vector sequence and said simulating of said errors with tag simulation using said vector sequence to detect, and to identify as covered, others of said tags covered by said vector sequence.
Claim 39
Dependent Claim
29 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 34 , wherein said constraints include interacting linear constraints and Boolean constraints.
Claim 40
Dependent Claim
67 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 34 , wherein said predetermined operations include: after said step of preparing a tag list, randomly generating a plurality of vector sequences; performing said tag simulation using said plurality of randomly generated vector sequences; and identifying as covered ones of said tag list covered by said randomly generated vector sequences.
Claim 41
Dependent Claim
88 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 34 , wherein said predetermined operations include: said set of constraints being generated for only a limited number of said paths for said selected uncovered tag, thereby defining said HSAT problem as a limited HSAT problem; attempting to solve said limited HSAT problem; and when a solution to said limited HSAT problem cannot be found, generating said set of constraints for different ones of said paths for said selected uncovered tag.
Claim 42
Dependent Claim
41 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 38 , wherein said predetermined operations include selecting said limited number of said paths based on a respective length of each of said paths.
Claim 43
Dependent Claim
40 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 34 , wherein said predetermined operations include maximizing a magnitude for said selected tag at which said vector sequence covers the said tag.
Claim 44
Dependent Claim
48 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 40 , wherein said step of maximizing said magnitude for said selected tag is performed by maximizing a difference between an upper bound and a lower bound of said tag magnitude.
Claim 45
Dependent Claim
59 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 40 , wherein said step of maximizing said magnitude for said selected tag is performed by adding constraints to said HSAT problem forcing propagation of said tag only through operators that can propagate said tag independent of said respective tag magnitude thereof.
Claim 46
Dependent Claim
84 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 40 , wherein said step of maximizing said magnitude for said selected tag is performed by making a determination, after said generation of said vector sequence, as to whether said vector sequence can propagate said selected tag independent of said respective tag magnitude, and, when said determination indicates that said vector sequence cannot propagate said selected tag independent of said respective tag magnitude, generating another vector sequence.
Claim 47
Dependent Claim
58 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 34 , wherein said predetermined operations include a step of identifying ones of said tags that cannot be propagated to an observable output, and wherein said step of generating vector sequences is not performed for said identified ones of said tags.
Claim 48
Dependent Claim
50 words
The computer program product for enabling a computer to perform vector generation as set forth in claim 34 , wherein said predetermined operations include selecting ones of said tags for vector sequence generation in an order based on a respective minimum number of unrollings required for covering each said tag.
References Cited (Backward Citations)
US5870308A
Cited
US5748497A
Cited
US5862149A
Cited
US6141630A
Cited
US6256770B1
Cited
US6324673B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-11-09 | 2008-05-10 | 2008-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-11-09 | 2012-05-10 | 2012-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-11-09 | 2016-05-10 | 2016-11-09 | $7700.00 | Window Closed / Lapsed |