A parallel direct method circuit simulator based on sparse matrix partitioning

Solving a system of linear simultaneous equations representing an electrica l circuit is one of the most time consuming tasks for large scale circuit s imulations. In order to facilitate a multiprocessor implementation of the c ircuit simulation program SPICE, decomposition algorithms should be employe d to partition a sparse matrix equation of the overall circuit into a numbe r of subcircuit equations for parallel processing. In this paper, the perfo rmance of a parallel direct method matrix equation solving routine was stud ied in several contexts: the theoretical lower bound on performance was der ived and the tradeoff between parallelism and communication is presented; v arious implementation and performance tuning issuing is also reported. This routine is written in such a manner that the data structure is compatible with SPICE Version 3c1. The speedup obtained from the simulation of two tes t circuits on a message passing multiprocessor system built on Transputers will be reported. Finally, the factors affecting the performance of the mul tiprocessor system are outlined and the overheads affecting the system perf ormance in the implementation are identified. (C) 1998 Elsevier Science Ltd . All rights reserved.