الفهرس 
Problem Statement
Graph Based ParallelOnly 14 pages are availabe for public view
 |  | from | 32 |  |  |
| | | from | 32 | | |
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.