Method and apparatus for improvement of sparse matrix evaluation performance

• US 6,374,390 B1
• Filed: 12/15/1999
• Issued: 04/16/2002
• Est. Priority Date: 07/15/1998
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Antrim Design Systems Inc. (Cadence Group)
• Inventors: Quarles, Thomas L., Liebmann, S. Peter, Spruiell, Leslie D.
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US09/461,246
• Time in Patent Office: 853 Days
• Field of Search: 716/1, 716/2, 716/4, 703/13, 703/14, 703/2
• US Class Current: 716/136
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods

Abstract

A device for reducing evaluation time of a matrix representing an electrical circuit. Conductance values of each circuit component in the circuit are written to corresponding models utilizing non-blocking writing techniques. The matrix is represented by a reduced memory structure where each matrix node is represented by a matrix element structure having at least one pointer to a conductance value contained in a model structure corresponding to a circuit component that contributes to a value of the matrix node. A set of rows or columns of the matrix are then processed to calculate final matrix node values independently.

Claims

1. A method of solving for a contribution of matrix coefficients, comprising the steps of:

retrieving data elements corresponding to a first contributing matrix coefficient, and storing each of said data elements as a model stored data element in a first model;

retrieving data elements corresponding to a second contributing matrix coefficient, and storing each of said data elements as a model stored data element in a second model;

linking each model stored data element of said first and second models to the corresponding contributing matrix coefficient by a pointer reference;

determining first and second contributing matrix coefficients by reference to said model stored data elements;

summing said first and second contributing matrix coefficients to produce a sum matrix; and

,

solving said sum matrix.

2. The method of claim 1 wherein said step of linking includes the steps of:

creating a data structure having a plurality of nodes, each of said nodes corresponding to a contributing matrix coefficient and having at least one pointer associated therewith; and

,

referencing said at least one pointer in each of said nodes of said data structure from the data structure to at least one of said model stored data elements corresponding to the contributing matrix coefficient of the respective node.

3. The method of claim 2 wherein said step of determining includes the step of:

determining said first and said second contributing matrix coefficients from said model stored data elements pointed to by said at least one pointer stored in a node of the data structure corresponding to the contributing matrix coefficient being determined.

4. The method of claim 3 wherein said step of determining includes the steps of:

dereferencing each pointer to data elements contained in said model to obtain data elements of the matrix coefficient being determined; and

,

calculating said contributing matrix coefficient utilizing the data elements obtained.

5. The method according to claim 3, further comprising the step of:

calculating a contributing matrix coefficient for each node by utilizing separate determining processes, each separate determining process performing said step of determining for each contributing matrix coefficient.

6. The method of claim 2 wherein the summing steps includes producing a sum matrix without first stamping a contributing matrix coefficient to a node of said data structure.

7. The method of claim 1 wherein said step of summing includes the steps of:

determining an associated value for each of said model stored data elements for each node of said first contributing matrix coefficient;

calculating a sum value for each node due to contributions at that node from each node of said second contributing matrix coefficient; and

,

creating a sum matrix by storing the sum value at a sum matrix location corresponding to model stored data element location.

8. The method of claim 1 wherein said step of solving includes the step of:

determining parametric values at each node on the circuit represented by the matrix.

9. The method of claim 1 further comprising the step of:

converging the process to determine whether or not the result of summing the matrix has reached a steady state.

10. The method of claim 9 wherein said step of converging comprises:

comparing values at a vector of nodal values to values at a vector of nodal values from a previous iteration of the convergent process, according to user defined convergence control variables; and

,

if the vector values do not imply a steady state, repeating the steps of retrieving data, linking, determining, summing and solving.

11. A method of calculating circuit node values in a circuit simulation system, comprising the steps of:

retrieving conductance elements corresponding to a first matrix coefficient and storing each conductance element as a model stored data element in a first component model structure;

retrieving conductance elements corresponding to a second matrix coefficient and storing each conductance element as a model stored data element in a second component model structure;

linking each model stored data element of each model to the corresponding matrix coefficient by pointer reference;

determining first and second matrix coefficients by reference to said model stored data elements;

summing first and second matrix coefficients to produce a sum matrix; and

,

solving the sum matrix to calculate the circuit node values.

12. The method of claim 11 wherein said step of linking includes the steps of:

building a data structure having a plurality of nodes, each of said nodes corresponding to a contributing matrix coefficient and having at least one pointer associated therewith; and

,

referencing said at least one pointer in each of said nodes of said data structure from the data structure to at least one of said model stored data elements corresponding to the contributing matrix coefficient of the respective node.

13. The method of claim 12 wherein said step of determining includes the step of:

determining said first and said second contributing matrix coefficients from said model stored data elements pointed to by said at least one pointer stored in a node of the data structure corresponding to the matrix coefficient being determined.

14. The method of claim 13 wherein said step of determining includes the steps of:

dereferencing each pointer to data elements contained in said model to obtain data elements of the matrix coefficient being determined; and

,

calculating said matrix coefficient utilizing the data elements obtained.

15. The method according to claim 13, further including the step of:

calculating a matrix coefficient for each node by utilizing separate determining processes, each separate determining process performing said step of determining for each matrix coefficient.

16. The method of claim 12 wherein the summing step includes producing a sum matrix without first stamping a contributing matrix coefficient to a node of said structure.

17. The method of claim 11 wherein said step of summing includes the steps of:

determining a value in the model for each node of each matrix coefficient;

calculating a sum value due to contributions at that node from other matrix coefficients; and

,

storing the sum value in a sum matrix model node location.

18. The method of claim 11 wherein said step of solving includes the step of:

determining parametric values at each node on the circuit represented by the matrix.

19. The method of claim 11 further comprising the step of:

converging the process to determine whether or not the result of summing the matrix has reached a steady state.

20. The method of claim 19 wherein said step of converging comprises:

comparing values at a vector of nodal values to values at a vector of nodal values from a previous iteration of the convergent process, according to user defined convergence control variables; and

,

if the vector values do not imply a steady state, repeating the steps of retrieving data, linking, determining, summing and solving.

21. A simulator for evaluating quantities of a physical system represented by mathematical equations with plural variables, comprising:

a computer processing unit with media storage; and

,

a computer simulator program that performs the steps of;

defining a data structure representative of a matrix and having plural nodes, each node corresponding to a matrix coefficient;

retrieving data elements corresponding to a first contributing matrix coefficient, and storing each data element in a first model;

retrieving data elements corresponding to a second contributing matrix coefficient, and storing each data element in a second model;

linking each model stored data element of each model to the corresponding matrix coefficient by pointer reference;

determining said first and second contributing matrix coefficients by reference to said model stored data elements;

summing said first and second contributing matrix coefficients to produce a sum matrix; and

,

solving the sum matrix.

22. The simulator of claim 21, wherein said identifying step identifies data elements from an input net list, and wherein said computer simulator program further performs the step of:

recognizing, based on a predetermined element contained in said net list, at least one element to be placed in said component model structure, and at least one data element reference to be placed in said nodes of said data structure.

23. The simulator of claim 22, wherein said step of recognizing includes the step of:

recognizing, based on a predetermined element contained in said net list, at least one pattern of elements to be placed in said component model structure, and at least one pattern of data element references to be placed in said nodes of said data structure.

24. The simulator according to claim 21, wherein:

said system being evaluated is an electrical circuit;

said quantities are one of voltages and currents at selected nodes of the electrical circuit; and

,

said data elements are conductance components of electrical circuit components in the electrical circuit.

25. The simulator of claim 21 wherein said step of linking comprises the steps of:

building a data structure having a plurality of nodes, each of said nodes corresponding to a contributing matrix coefficient and having at least one pointer associated therewith; and

,

referencing said at least one pointer in each of said nodes of said data structure from the data structure to at least one of said model stored data elements corresponding to the contributing matrix coefficient of the respective node.

26. The simulator of claim 25 wherein said step of determining includes the step of:

determining said first and said second contributing matrix coefficients from said model stored data elements pointed to by said at least one pointer stored in a node of the data structure corresponding to the matrix coefficient being determined.

27. The simulator of claim 26 wherein said step of determining includes the steps of:

dereferencing each pointer to data elements contained in said model to obtain data elements of the matrix coefficient being determined; and

,

calculating said matrix coefficient utilizing the data elements obtained.

28. The simulator according to claim 26, further comprising the step of:

calculating a matrix coefficient for each node by utilizing separate determining processes, each separate determining process performing said step of determining for each matrix coefficient.

29. The simulator of claim 21 wherein said step of summing includes the steps of:

finding an associated value in the model for each node of each matrix coefficient;

calculating a sum value due to contributions at that node from other matrix coefficients; and

,

returning the sum value to the sum matrix model node location.

30. The simulator of claim 21 wherein said step of solving includes the step of:

determining parametric values at each node on the circuit represented by the matrix.

31. The simulator of claim 21 further comprising the step of:

converging the process to determine whether or not the result of summing the matrix has reached a steady state.

32. The simulator of claim 31 wherein said step of converging comprises:

comparing values at a vector of nodal values to values at a vector of nodal values from a previous iteration of the convergent process, according to user defined convergence control variables; and

,

if the vector values do not imply a steady state, repeating the steps of retrieving data, linking, determining, summing and solving.

33. The simulator of claim 21 with the summing step of the computer simulator program producing a sum matrix without first stamping a contributing matrix coefficient to a node of said data structure.

34. A computer readable medium having computer instructions stored thereon that, when loaded into a computer, cause the computer to perform the steps of:

retrieving conductance elements corresponding to at least one matrix coefficient;

storing each conductance element in at least one component model structure;

building a data structure having plural nodes, each node corresponding to a matrix coefficient and having at least one pointer associated therewith;

retrieving data elements corresponding to a first contributing matrix coefficient, and storing each data element in a first model;

retrieving data elements corresponding to a second contributing matrix coefficient, and storing each data element in a second model;

linking each model stored data element of each model to the corresponding matrix coefficient by pointer reference;

determining said first and second contributing matrix coefficients by reference to said model stored data elements;

summing said first and second contributing matrix coefficients to produce a sum matrix; and

,

solving the sum matrix.

35. The computer readable medium of claim 34 wherein said step of linking includes the steps of:

building a data structure having a plurality of nodes, each of said nodes corresponding to a contributing matrix coefficient and having at least one pointer associated therewith; and

,

referencing said at least one pointer in each of said nodes of said data structure from the data structure to at least one of said model stored data elements corresponding to the contributing matrix coefficient of the respective node.

36. The computer readable medium of claim 35 wherein said step of determining includes the step of:

determining said first and said second contributing matrix coefficients from said model stored data elements pointed to by said at least one pointer stored in a node of the data structure corresponding to the matrix coefficient being determined.

37. The computer readable medium of claim 36 wherein said step of determining includes the steps of:

dereferencing each pointer to data elements contained in said model to obtain data elements of the matrix coefficient being determined; and

,

calculating said matrix coefficient utilizing the data elements obtained.

38. The computer readable medium according to claim 34, further comprising the step of:

calculating a matrix coefficient for each node by utilizing separate determining processes, each separate determining process performing said step of determining for each matrix coefficient.

39. The computer readable medium of claim 34 wherein said step of summing includes the steps of:

finding an associated value in the model for each node of each matrix coefficient;

calculating a sum value due to contributions at that node from other matrix coefficients; and

,

returning the sum value to the sum matrix model node location.

40. The computer readable medium of claim 34 wherein said step of solving includes the step of:

determining parametric values at each node on the circuit represented by the matrix.

41. The computer readable medium of claim 34 further comprising the step of:

converging the process to determine whether or not the result of summing the matrix has reached a steady state.

42. The computer readable medium of claim 41 wherein said step of converging comprises:

comparing values at a vector of nodal values to values at a vector of nodal values from a previous iteration of the convergent process, according to user defined convergence control variables; and

,

if the vector values do not imply a steady state, repeating the steps of retrieving data, linking, determining, summing and solving.

43. The computer readable medium of claim 34 with the summing step of the computer instructions producing a sum matrix without first stamping a contributing matrix coefficient to a node of said data structure.