Circuit simulator

1. A computer-implemented method for simulating a circuit, comprising:

representing a circuit using a matrix, wherein the matrix represents a set of linear equations to be solved;

identifying a delta matrix, wherein the delta matrix is a difference of the matrix that changed states from a previous time step to a current time step;

computing an update of the delta matrix using a matrix decomposition approach, wherein computing the delta matrix update comprises updating a representation of the delta matrix from a first column to a last column in a pipelined manner and updating the representation of the delta matrix from top-left to bottom-right in a pipelined manner;

generating a current state of the matrix using a previous state of the matrix and the update of the delta matrix; and

storing the current state of the matrix in a memory device,

wherein the computer-implemented method is executed by a plurality of processors operating in parallel, thereby simulating a model of said circuit.

2. The computer-implemented method of claim 1 , wherein identifying a delta matrix comprises:

identifying active nodes in accordance with at least one of:

rate of voltage change,

rate of voltage change versus time,

rate of current change,

and

estimated current of the active nodes.

3. The computer-implemented method of claim 1 , wherein computing an update of the delta matrix comprises:

decomposing the delta matrix in accordance to ranks of the delta matrix;

summing contributions from each rank of the delta matrix.

4. The computer-implemented method of claim 1 , wherein computing an update of the delta matrix further comprises:

decomposing the delta matrix to form a diagonal matrix and orthogonal matrices;

expressing the diagonal matrix and orthogonal matrices using ranks of the delta matrix; and

summing contributions from each rank of the delta matrix.

5. The computer-implemented method of claim 1 , wherein representing a circuit using a matrix comprises:

computing a circuit topology of the circuit;

forming a universal device (UD) tree for representing the matrix, wherein the UD tree includes a plurality of universal devices arranged in multiple levels in a hierarchical data structure, wherein a UD at a higher level includes ports of its corresponding child UDs, and wherein UDs in a level of the UD tree are independent of each other.

6. The computer-implemented method of claim 5 , wherein forming a UD tree comprises:

computing a Schur complement of each UD; and

stamping the Schur complement of each UD to the matrix.

7. The computer-implemented method of claim 5 , wherein forming a UD tree further comprises at least one of:

processing UDs according to a predefined sequence;

processing UDs according to dynamic events occurred;

processing UDs in a bottom-up manner according to their corresponding levels in the UD tree; and

processing UDs in a depth-first manner according to positions of the UDs in the UD tree.

8. The computer-implemented method of claim 1 , wherein the computer-implemented method is described as a computer program product stored in a non-transitory medium comprising executable program code, which when executed, performs the method of claim 1 .

9. A system for solving a matrix, comprising:

a graphics processing unit (GPU), wherein the GPU comprises one or more multiprocessors and each multiprocessor includes a plurality of processors and a shared memory configured to be used by the plurality of processors;

a graphical-user-interface for viewing representations of the matrix on a display;

a global memory for storing information related to the matrix;

logic for representing a circuit using the matrix, wherein the matrix represents a set of linear equations to be solved;

logic for identifying a delta matrix, wherein the delta matrix is a difference of the matrix that changed states from a previous time step to a current time step;

logic for computing an update of the delta matrix using a matrix decomposition approach, wherein computing the delta matrix update comprises updating a representation of the delta matrix from a first column to a last column in a pipelined manner and updating the representation of the delta matrix from top-left to bottom-right in a pipelined manner;

logic for generating a current state of the matrix using a previous state of the matrix and the update of the delta matrix; and

logic for storing the current state of the matrix in a memory device.

10. The system of claim 9 , wherein the logic for identifying a delta matrix comprises:

logic for identifying active nodes in accordance with at least one of:

rate of voltage change,

rate of voltage change versus time,

rate of current change,

and

estimated current of the active nodes.

11. The system of claim 9 , wherein the logic for computing an update of the delta matrix comprises:

logic for decomposing the delta matrix in accordance to ranks of the delta matrix;

logic for summing contributions from each rank of the delta matrix.

12. The system of claim 9 , wherein the logic for computing an update of the delta matrix further comprises:

logic for decomposing the delta matrix to form a diagonal matrix and orthogonal matrices;

logic for expressing the diagonal matrix and orthogonal matrices using ranks of the delta matrix; and

logic for summing contributions from each rank of the delta matrix.

13. The system of claim 9 , wherein the logic for representing behaviors of a system using a matrix comprises:

logic for computing a circuit topology of the circuit;

logic for forming a universal device (UD) tree for representing the matrix, wherein the UD tree includes a plurality of universal devices arranged in multiple levels in a hierarchical data structure, wherein a UD at a higher level includes ports of its corresponding child UDs, and wherein UDs in a level of the UD tree are independent of each other.

14. The system of claim 13 , wherein the logic for forming a UD tree comprises:

logic for computing a Schur complement of each UD; and

logic for stamping the Schur complement of each UD to the matrix.

15. The system of claim 13 , wherein the logic for forming a UD tree further comprises at least one of:

logic for processing UDs according to a predefined sequence;

logic for processing UDs according to dynamic events occurred;

logic for processing UDs in a bottom-up manner according to their corresponding levels in the UD tree; and

logic for processing UDs in a depth-first manner according to positions of the UDs in the UD tree.

16. A method for simulating a circuit, comprising:

receiving a description of the circuit in a netlist; computing an update of a delta matrix associated with the circuit using a matrix decomposition approach, wherein computing the delta matrix update comprises updating a representation of the delta matrix from a first column to a last column in a pipelined manner and updating the representation of the delta matrix from top-left to bottom-right in a pipelined manner;

computing a circuit topology from the netlist;

creating a universal device (UD) tree for representing the circuit topology, wherein the UD tree includes a plurality of universal devices arranged in multiple levels in a hierarchical data structure, wherein a UD at a higher level includes ports of its corresponding child UDs, and wherein UDs in a level of the UD tree are independent of each other;

calculating a time step for simulation;

simulating the UD tree in accordance with the time step; and

storing simulation results in a memory device.

17. The method of claim 16 , wherein simulating the UD tree comprises:

scheduling tasks to process UDs according to the UD tree, wherein the UDs are arranged in a stack;

selecting one or more UDs from the stack; and

processing the one or more UDs; and

repeating steps (a) and (b) until all UDs in the stack have been processed.