Table model circuit simulation acceleration using model caching
View Patent ↗A mechanism for improving speed of table model-based 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 substantially the same 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, a cache lookup is performed to determine table model solution values for the previously-evaluated transistor or device, and those values are used to determine exact output values per the table model of the presently being evaluated transistor or device.
1. A method for simulating a circuit, the method comprising:
determining a table model cell corresponding to a set of input values of a device in the circuit;
determining a hash value for a set of vertex values associated with the table model cell; and
if a model cache entry associated with the hash value comprises values matching the table model vertex values, then
retrieving previously calculated output values corresponding to the model cache entry, and
calculating output values for the device using the previously calculated output values corresponding to the model cache entry and information associated with the table model cell.
2. The method of claim 1 wherein said determining the table model cell comprises:
calculating a nearest vertex value for a dimension of an n-dimensional hypercube associated with the table model, wherein the dimension corresponds to an input value of a set of input values of the device.
3. The method of claim 1 further comprising:
determining whether the model cache entry associated with the hash value comprises values matching the table model vertex values, wherein said determining comprises
looking up a first entry in the model cache having an index that equals the hash value,
determining if the first entry comprises values matching the table model vertex values,
if the first entry comprises values matching the table model vertex values, then selecting the first entry, and
if the first entry does not comprise values matching the table model vertex values, then
looking up one or more entries in a neighborhood of the first entry,
determining if one of the one or more entries in the neighborhood of the first entry comprises values matching the table model vertex values, and
if one of the one or more entries in the neighborhood of the first entry comprises values matching the table model vertex values, selecting the entry comprising the matching values.
4. The method of claim 3 wherein the neighborhood of the first entry comprises a predetermined number of entries following the first entry in the model cache.
5. The method of claim 3 wherein said looking up the one or more entries in a 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.
6. The method of claim 1 wherein an entry of the model cache comprises table model vertex values for a device associated with the entry and an identifier of a memory location storing the previously calculated output values for the device associated with the entry.
7. The method of claim 1 further comprising:
if no model cache entry associated with the hash value comprises values matching the table model vertex values, then
calculating output values for the device using the set of input values,
storing the calculated output values in association with a device identifier, and
storing a new entry in the model cache, wherein
the new entry comprises the table model vertex values and an identifier of the storage location of the output values, and
the new entry is associated with the hash value.
8. The method of claim 7 wherein said storing the new entry in the table model cache further comprises:
determining if a storage entry in the model cache having a index value corresponding to the hash value for the set of table model vertex values is empty;
if the storage entry is empty, then storing the new entry at the storage entry; 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 an empty entry to the neighborhood of the entry in the table model cache having the index value corresponding to the hash value.
9. The method of claim 1 wherein said calculating the output values for the device using the previously calculated output values corresponding to the model cache entry and information associated with the table model cell comprises:
extrapolating the output values for the device from the previously calculated output values corresponding to the table model cache entry.
10. The method of claim 9 wherein said extrapolating comprises:
calculating a difference between an input value of the device from the set of input values and a corresponding input value from a previously-evaluated device corresponding to the previously-calculated output values; and
multiplying the difference by a slope of the solution for the output value in the table model cell and adding the result to the previously calculated output value,
wherein the information associated with the table model cell comprises the slope of the solution for the output value in the table model cell.
11. 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 table model cell corresponding to a set of 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 a set of table model vertex values associated with the table model cell, and
if a model cache entry associated with the hash value stored in the table model cache comprises values matching the table model vertex values, then the analysis engine is further configured to
read previously calculated output values corresponding to the model cache entry from the second memory, and
calculate output values for the device using the previously calculated output values corresponding to the model cache entry and information associated with the table model cell.
12. The circuit simulation system of claim 11 wherein the analysis engine is configured to determine the table model cell for a set of input values of a device by being further configured to calculate a nearest vertex value for a dimension of an n-dimensional array associated with the table model, wherein the dimension corresponds to an input value of the set of input values of the device.
13. The circuit simulation system of claim 11 wherein the analysis engine is further configured to:
determine whether a model cache entry associated with the hash value comprises values matching the table model vertex 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 values matching the table model vertex values,
if the first entry comprises values matching the table model vertex values, select the first entry, and
if the first entry does not comprise values matching the table model vertex values, then
look up one or more entries in a neighborhood of the first entry,
determine if one of the one or more entries in the neighborhood of the first entry comprises values matching the table model vertex values, and
if one of the one or more entries in the neighborhood of the first entry comprises values matching the table model vertex values, select the entry comprising the matching values.
14. The circuit simulation system of claim 11 wherein the analysis engine is further configured to:
if no entry stored in the model cache associated with the hash value comprises values matching the table model vertex values, then the analysis engine is further configured to
calculate output values for the device using the set of 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 table model vertex values and an identifier of the storage location of the output values, and
the new entry is associated with the hash value.
15. The circuit simulation system of claim 14 wherein the analysis engine calculates the output values for the device using the set of input values by being further configured to:
determine if each table model vertex value and nearest neighbor vertex values exists in a vertex table;
calculate any missing table model vertex values and missing nearest neighbor vertex values;
store the calculated table model vertex values and nearest neighbor vertex values in the vertex table; and
calculate the output values using a simplicial interpolation on the table model vertex values.
16. The circuit simulation system of claim 15 wherein the analysis engine is further configured to:
store the calculated output values in the second memory; and
store a corresponding model cache entry in the first memory.
17. The circuit simulation system of claim 16 further comprising:
a third memory storing a temporal cache, corresponding to the device, and comprising one or more entries; and
the analysis engine is further configured to:
store the calculated output values in an entry of the third memory associated with the hash value,
for a subsequent set of input values of the device,
determine a second hash value for a second set of table model vertex values for a second table model cell corresponding to the subsequent set of input values of the device, and
if the second hash value matches the hash value, read the calculated output values stored in the entry of the third memory and calculate subsequent output values using the calculated output values.
18. The circuit simulation system of claim 14 wherein the analysis engine stores the new entry in the model cache by being further configured to:
determine if a storage entry in the table model cache having a index value corresponding to the hash value for the set of table model vertex 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 table 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 table 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 table model cache having the index value corresponding to the hash value, use hopscotch hashing table management to move an empty entry to the neighborhood of the entry in the table model cache having the index value corresponding to the hash value.
19. The circuit simulation system of claim 11 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 table model cache entry, wherein said extrapolating comprises
calculating a difference between an input value of the device from the set of input values and a corresponding input value from a previously evaluated device corresponding to the previously calculated output values; and
multiplying the difference by a slope of the solution for the output value in the table model cell and adding the result to the previously calculated output value, wherein the information associated with the table model cell comprises the slope of the solution for the output value in the table model cell.
20. An apparatus for simulating a circuit, the apparatus comprising:
means for determining a table model cell corresponding to a set of input values of a device in the circuit;
means for determining a hash value for the set of table model vertex values associated with the table model cell; and
if a table model cache entry associated with the hash value comprises values matching the table model vertex values, then
means for retrieving previously calculated output values corresponding to the table model cache entry, and
means for calculating output values for the device using the previously calculated output values corresponding to the table model cache entry and information associated with the table model cell.