Adaptive state-to-symbolic transformation in a canonical representation

• US 8,099,690 B2
• Filed: 04/27/2009
• Issued: 01/17/2012
• Est. Priority Date: 04/27/2009
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Goswami, Dhiraj, Hung, Ngai Ngai William, Singh, Jasvinder, Qiang, Qiang
• Primary Examiner(s): Parihar, Suchin
• Application Number:
  US12/430,322
• Publication Number:
  US 20100275169A1
• Time in Patent Office: 995 Days
• Field of Search: 716/100
• US Class Current: 716/100
• CPC Class Codes: G06F 30/3323 using formal methods, e.g. equivalence checking or property checking

Abstract

Some embodiments provide a system for adaptively performing state-to-symbolic transformation in a canonical representation which is used for generating random stimulus for a constrained-random simulation. The system can construct a canonical representation for a set of constraints using the set of random variables and the subset of the state variables in the constraints. Next, the system can use the canonical representation to generate random stimulus for the constrained-random simulation, and monitor parameters associated with the constrained-random simulation. Next, the system can add state variables to or remove state variables from the canonical representation based at least on the monitored parameters. The system can then use the modified canonical representation which has a different set of state variables to generate random stimulus for the constrained-random simulation.

Claims

1. A method for adaptively performing state-to-symbolic transformation during constrained-random simulation, the method comprising:

generating, based on a random stimulus for the constrained-random simulation, wherein the first canonical representation represents a set of constraints defined over a set of random variables and a set of state variables, and wherein the first canonical representation is constructed based on the set of random variables and a first subset of the set of state variables;

monitoring parameters associated with the constrained-random simulation to obtain monitoring data;

determining, based at least on the monitoring data, a second subset of the set of state variables which is different from the first subset of the set of state variables;

constructing, by computer, a second canonical representation based on the set of random variables and the second subset of the set of state variables, wherein the second canonical representation represents the set of constraints; and

generating, based on the second canonical representation, random stimulus for the constrained-random simulation.

2. The method of claim 1, wherein monitoring parameters associated with the constrained-random simulation involves monitoring the number of times a state variable changes its value.

3. The method of claim 1, wherein monitoring parameters associated with the constrained-random simulation involves monitoring the number of simulation cycles a state variable'"'"'s value is equal to 0.

4. The method of claim 1, wherein monitoring parameters associated with the constrained-random simulation involves monitoring the number of simulation cycles a state variable'"'"'s value is equal to 1.

5. The method of claim 1, wherein monitoring parameters associated with the constrained-random simulation involves monitoring a canonical representation'"'"'s size.

6. The method of claim 1, wherein monitoring parameters associated with the constrained-random simulation involves monitoring how many canonical representations are being managed by a canonical representation manager.

7. The method of claim 1, wherein monitoring parameters associated with the constrained-random simulation involves monitoring correlations between two or more parameters associated with the constrained-random simulation.

8. The method of claim 1, wherein monitoring parameters associated with the constrained-random simulation involves monitoring a canonical representation'"'"'s growth rate.

9. The method of claim 1, further comprising maintaining a cache of canonical representations which are used for generating random stimulus during the constrained-random simulation.

10. The method of claim 9, wherein a cache entry in the cache points to a canonical representation, and wherein the cache entry'"'"'s tag is based at least on values of one or more state variables.

11. The method of claim 9, further comprising removing cache entries that are not expected to be used with the second canonical representation.

12. The method of claim 9, wherein monitoring parameters associated with the constrained-random simulation involves monitoring the number of cache entries in the cache.

13. The method of claim 9, wherein monitoring parameters associated with the constrained-random simulation involves monitoring the cache'"'"'s hit rate.

14. The method of claim 9, wherein monitoring parameters associated with the constrained-random simulation involves monitoring the cache'"'"'s miss rate.

15. A computer-readable storage device storing instructions that when executed by a computer cause the computer to perform a method for adaptively performing state-to-symbolic transformation during constrained-random simulation, the method comprising:

generating, based on a first canonical representation, random stimulus for the constrained-random simulation, wherein the first canonical representation represents a set of constraints defined over a set of random variables and a set of state variables, and wherein the first canonical representation is constructed based on the set of random variables and a first subset of the set of state variables;

monitoring parameters associated with the constrained-random simulation to obtain monitoring data;

determining, based at least on the monitoring data, a second subset of the set of state variables which is different from the first subset of the set of state variables;

constructing a second canonical representation based on the set of random variables and the second subset of the set of state variables, wherein the second canonical representation represents the set of constraints; and

generating, based on the second canonical representation, random stimulus for the constrained-random simulation.

16. The method of claim 15, wherein monitoring parameters associated with the constrained-random simulation involves monitoring the number of times a state variable changes its value.

17. The method of claim 15, wherein monitoring parameters associated with the constrained-random simulation involves monitoring a canonical representation'"'"'s size.

18. The method of claim 15, wherein monitoring parameters associated with the constrained-random simulation involves monitoring correlations between two or more parameters associated with the constrained-random simulation.

19. The method of claim 15, further comprising maintaining a cache of canonical representations which are used for generating random stimulus during the constrained-random simulation.

20. An apparatus to adaptively perform state-to-symbolic transformation during constrained-random simulation, the apparatus comprising:

a first generating mechanism configured to generate, based on a first canonical representation, random stimulus for the constrained-random simulation, wherein the first canonical representation represents a set of constraints defined over a set of random variables and a set of state variables, and wherein the first canonical representation is constructed based on the set of random variables and a first subset of the set of state variables;

a monitoring mechanism configured to monitor parameters associated with the constrained-random simulation to obtain monitoring data;

a transforming mechanism configured to;

determine, based at least on the monitoring data, a second subset of the set of state variables which is different from the first subset of the set of state variables; and

construct a second canonical representation based on the set of random variables and the second subset of the set of state variables, wherein the second canonical representation represents the set of constraints; and

a second generating mechanism configured to generate, based on the second canonical representation, random stimulus for the constrained-random simulation.