![]() | Only 14 pages are availabe for public view |
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 technique 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 parallel nature of the reduced graph representation, Graphics Processing Unit (GPU) is used to accelerate sparse Lower Upper (LU) factorization. The main contribution in this dissertation is the parallelization of KLU (”Clark Kent” LU) algorithm through introducing the concept of the reduced graph. A theory that states that Reduced Graph are Non-Cyclic and hence can be processed in parallel is introduced and proved. The GPU is used to implement proposed parallel KLU. To validate the performance of the proposed technique, it is tested against real circuit matrices from the University of Florida sparse matrix collection. The proposed technique outperformed sequential KLU in most of the test cases. |