SYSTOLIC ALGORITHMS FOR SOLVING A SPARSE SYSTEM OF LINEAR-EQUATIONS IN-CIRCUIT SIMULATION

Systolic algorithms providing near ideal speedups have been developed for solving a dense system of linear equations. However, in applicatio ns like circuit simulation, the resulting matrix equation is quite spa rse( > 99% zeros) which makes the dense matrix solution approach ineff icient. Although sparse matrix solvers for circuit simulation have bee n devised for parallel shared memory machines and vector processors, t heir performance in terms of speedup has been limited due to tightly c oupled and unstructured sparse equations. This paper first develops a systolic sparse matrix algorithm by modifying an existing partitionabl e dense matrix solution algorithm. The sparse algorithm is then furthe r improved to include parallel execution by multiple systolic processo r modules. Reordering schemes based on a modified Markowitz algorithm are also developed that minimize the fill-in-during the matrix solutio n by our sparse algorithms thereby improving the execution time. Resul ts on several randomly generated sparse matrices and those generated f rom ISCAS benchmark circuits are presented to show the efficiency of o ur sparse algorithm and its excellent speedup as the number of process ors in the systolic array is increased.