Graph Based Techniques Applied in Electrical Circuit Simulation

Abstract

In this dissertation, the acceleration of electrical circuit simulation problem is addressed. As SPICE simulator core engine is the base of most current electrical circuit simulator, this engine is studied for detecting performance bottlenecks. Due its time complexity, solving sparse matrix step in SPICE engine is targeted in this dissertation to enhance the performance of the simulator. A novel technique based on graph theory is introduced to solve sparse linear systems. The proposed technique enhances the ability to build sparse parallel solvers for circuit simulation matrices. Thus the proposed technique accelerated the performance of circuit simulation algorithms. The new tech- nique represents sparse linear system as a signal flow graph (SFG). Then it divides the graph into separate strongly connected components (SCCs). SCCs relations are detected and represented in reduced graphs which are used to enhance the parallelism of the solver. To benefit from the paral- lel nature of the reduced graph representation, Graphics Processing Unit (GPU) is used to accelerate sparse Lower Upper (LU) factorization.