Circuit simulation acceleration using model caching
View Patent ↗A mechanism for improving speed of simulation of complex circuits that include transistors and other devices that share similar properties is provided. Circuit simulation speed is improved by efficiently identifying transistors and other devices having identical properties that share a same state at the time of interest in the simulation. Transistors and other devices are collected into groups having the same characteristics and topologies prior to simulation. Then during simulation, a determination is made as to whether a previously-evaluated transistor or device in the same group as a presently-being evaluated transistor or device has terminal input values that are the same, or nearly the same. If so, then output values of the previously-evaluated transistor or device are used in calculating the output values of the present transistor or device.
1. A method implemented by a semiconductor design system for simulating a circuit, the method comprising:
generating, from a schematic description of a semiconductor device, a first set of data comprising descriptions of circuit elements in the semiconductor device and connectivity of the circuit elements in the semiconductor device;
calculating, by an analysis engine of the semiconductor design system, using the first set of data, a set of approximate input values for a set of actual input values of one of the circuit elements in the semiconductor device;
determining, by the analysis engine, a hash value for the set of approximate input values; and
if a model cache entry in a model cache stored in a first memory coupled to the analysis engine and associated with the one of the circuit elements and the hash value comprises values matching the approximate input values, then
determining, by the analysis engine, previously calculated output values corresponding to the model cache entry, and
calculating, by the analysis engine, output values for the one of the circuit elements using the previously calculated output values, stored in a second memory coupled to the analysis engine, corresponding to the model cache entry and the set of actual input values of the circuit element.
2. The method of claim 1 wherein said calculating the set of approximate input values comprises:
calculating, by the analysis engine, a single precision input value for each actual input value of the set of actual input values, wherein each actual input value is a double precision value.
3. The method of claim 1 wherein said determining the hash value comprises calculating, by the analysis engine, the hash value using the approximate input values.
4. The method of claim 1 further comprising:
determining, by the analysis engine, whether the model cache entry associated with the hash value comprises the values matching the approximate input values, wherein said determining whether the model cache entry associated with the hash value comprises the values matching the approximate input values comprises
looking up a first entry in the model cache having an index that equals the hash value,
determining if the first entry comprises the values matching the approximate input values,
if the first entry comprises the values matching the approximate input values, selecting the first entry, and
if the first entry does not comprise the values matching the approximate input values, then
looking up one or more entries in a neighborhood of the first entry, and
if one of the one or more entries in the neighborhood of the first entry comprises the values matching the approximate input values, selecting the entry comprising the matching values.
5. The method of claim 4 wherein the neighborhood of the first entry comprises a predetermined number of entries following the first entry in the model cache.
6. The method of claim 4 wherein said looking up the one or more entries in the neighborhood of the first entry comprises:
reading a hop-information word stored in association with the first entry, wherein the hop-information word comprises indicia of entries in the neighborhood that are associated with the index of the first entry; and
looking up entries in the model cache that correspond to the indicia provided in the hop-information word.
7. The method of claim 1 wherein each entry of the model cache comprises associated approximate input values for an associated circuit element associated with said each entry and an identifier of a memory location in the second memory storing associated previously calculated output values for the associated circuit element.
8. The method of claim 1 further comprising:
if no model cache entry associated with the hash value comprises the values matching the approximate input values, then
calculating the output values for the one of the circuit elements using the set of actual input values,
storing the calculated output values in association with a circuit element identifier in the second memory, and
storing a new entry in the model cache in the first memory, wherein
the new entry comprises the approximate input values and an identifier of a storage location in the second memory of the calculated output values, and
the new entry is associated with the hash value.
9. The method of claim 8 wherein said storing the new entry in the model cache further comprises:
determining, by the analysis engine, if a storage entry in the model cache having an index value corresponding to the hash value for the set of approximate input values is empty;
if the storage entry is empty, then storing the new entry at the storage entry in the first memory; and
if the storage entry is not empty, then
finding a closest empty entry to the entry in the model cache having the index value corresponding to the hash value,
if the closest empty entry is in a neighborhood of the entry in the model cache having the index value corresponding to the hash value, storing the new entry at the closest empty entry, and
if the closest empty entry is not in the neighborhood of the entry in the model cache having the index value corresponding to the hash value, using hopscotch hashing table management to move another empty entry to the neighborhood of the entry in the model cache having the index value corresponding to the hash value.
10. The method of claim 1 wherein a set of matching approximate input values are within a range of the actual input values such that the calculated output values are within an acceptable error range from an actual output value.
11. The method of claim 10 wherein said calculating the output values for the circuit element using the previously calculated output values corresponding to the entry comprises:
extrapolating, by the analysis engine, the output values for the circuit element from the previously calculated output values corresponding to the entry.
12. The method of claim 11 wherein said extrapolating comprises:
calculating a difference between an input value of the device from the set of actual input values and a corresponding actual input value from a previously evaluated circuit element corresponding to the previously calculated output values; and
multiplying the difference by a derivative of a previously calculated output value of said previously calculated output values and adding the result of said multiplication to the previously calculated output value.
13. A circuit simulation system comprising:
an input module configured to receive a description of a circuit for simulation;
a first memory storing a model cache comprising one or more entries;
a second memory storing output values corresponding to the one or more entries;
an analysis engine configured to;
determine a set of approximate input values for a set of actual input values of a device, wherein the input module provides information regarding the device from the description of the circuit,
determine a hash value for the set of approximate input values, and
if an entry of said one or more entries associated with the hash value stored in the model cache comprises values matching the approximate input values, then the analysis engine is further configured to,
read previously calculated output values corresponding to the entry from the second memory, and
calculate output values for the device using the previously calculated output values corresponding to the entry and the set of actual input values of the device.
14. The circuit simulation system of claim 13 wherein the analysis engine is configured to determine the set of approximate input values for the set of actual input values of the device by being further configured to calculate a single precision input value for each actual input value of the set of actual input values, wherein each actual input value is a double precision value.
15. The circuit simulation system of claim 13 wherein the analysis engine is further configured to:
determine whether the model cache entry associated with the hash value comprises the values matching the approximate input values by being further configured to,
look up a first entry in the model cache having an index that equals the hash value,
determine if the first entry comprises the values matching the approximate input values,
if the first entry comprises the values matching the approximate input values, select the first entry, and
if the first entry does not comprise the values matching the approximate input values, then
look up one or more entries in a neighborhood of the first entry, and
if one of the one or more entries in the neighborhood of the first entry comprises the values matching the approximate input values, select the entry comprising the matching values.
16. The circuit simulation system of claim 13 wherein the analysis engine is further configured to:
if no entry of said one or more entries stored in the model cache associated with the hash value comprises the values matching the approximate input values, then the analysis engine is further configured to
calculate the output values for the device using the set of actual input values,
store the calculated output values in association with a device identifier in the second memory, and
store a new entry in the model cache in the first memory, wherein
the new entry comprises the approximate input values and an identifier of a storage location of the calculated output values, and
the new entry is associated with the hash value.
17. The circuit simulation system of claim 16 wherein the analysis engine stores the new entry in the model cache by being further configured to:
determine if a storage entry in the model cache having an index value corresponding to the hash value for the set of approximate input values is empty;
if the storage entry is empty, then store the new entry at the storage entry; and
if the storage entry is not empty, then
find a closest empty entry to the entry in the model cache having the index value corresponding to the hash value,
if the closest empty entry is in a neighborhood of the entry in the model cache having the index value corresponding to the hash value, store the new entry at the closest empty entry, and
if the closest empty entry is not in the neighborhood of the entry in the model cache having the index value corresponding to the hash value, use hopscotch hashing table management to move another empty entry to the neighborhood of the entry in the model cache having the index value corresponding to the hash value.
18. The circuit simulation system of claim 13 wherein a set of matching approximate input values are within a range such that the calculated output values are within an acceptable error range from an actual output value.
19. The circuit simulation system of claim 18 wherein the analysis engine calculates the output values for the device using the previously calculated output values corresponding to the entry by being configured to:
extrapolate the output values for the device from the previously calculated output values corresponding to the entry.