PARASPICE: A parallel direct circuit simulator for shared-memory multiprocessors

A general approach to parallelizing direct method circuit simulation has been developed via novel algorithms. The approach extracts parallel tasks at the algorithmic level for the three most compute-intensive modules: device model evaluation (LOAD), direct solution of sparse linear systems (SOLVE), and local truncation error estimation (TRUNC), which account for at least 95 percent of the total job time. Therefore, it is suitable for a wide range of shared-memory multiprocessors. The implementation of the approach in SPICE2 resulted in a portable parallel direct circuit simulator, PARASPICE. The superior performance of PARASPICE is demonstrated on an eight-CE Alliant FX/80 using a number of benchmark circuits.The success of PARASPICE lies particularly in the SOLVE module, where the solution of a sequence of structurally identical sparse matrices are required. In this dissertation, a class of new algorithms has been systematically developed via a unified model for parallel sparse matrix computation. This model, which explores the parallelism issue in the pivoting schemes, extracts parallel tasks from the solution procedure by exploiting the sparse structure of the matrix. These algorithms have been implemented in DSPACK, a software package for the direct solution of general sparse matrices. Experiments with DSPACK on the Boeing-Harwell collection of benchmark matrices have shown high overall speedup. DSPACK has been successfully used as a workbench to design parallel sparse solvers for circuit simulation.U of I OnlyETDs are only available to UIUC Users without author permissio