Efficient sparse matrix factorization for circuit simulation on vector supercomputers

ABSTRACT

This paper describes an efficient approach to sparse matrix factorization on vector supercomputers. The approach is suitable for application domains like circuit simulation that require the repeated direct solution of unsymmetric sparse linear systems of equations with identical zero-nonzero structure. An Overlap-Scatter data structure is used to represent the sparse matrix, enabling the use of multiple operand access modes to achieve higher performance than earlier proposed approaches. The superior performance of the new solver is demonstrated using a number of matrices derived from circuit simulation runs.

REFERENCES

• 1: R. Betancourt, "Efficient Parallel Processing Technklue for Inverting Matrices with Random Sparsity," lEE Proc., Vol. 133, Pu E, No. 4, JuLy 1986, pp. 235-240.
• 2: (3. Bischoff and S. Greenberg, "CAYENNE: A Parallel Implementation of the Circuit Simulator SPICE" Proc. ICCAD 1986, pp. 182-185.
• 3: D.A. Calahan, "Multi-level Vectorized Spal~e Solution of LSI Circuits," Proc. ICCC 1980, pp. 976-979.
• 4: T. A. Davis , E. S. Davidson, Pairwise Reduction for the Direct, Parallel Solution of Sparse, Unsymmetric Sets of Linear Equations, IEEE Transactions on Computers, v.37 n.12, p.1648-1654, December 1988 [doi>10.1109/12.9742]
• 5: Jack J. Dongarra , Stanley C. Eisenstat, Squeezing the most out of an algorithm in CRAY FORTRAN, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.219-230, Sept. 1984 [doi>10.1145/1271.319413]
• 6: J. J. Dongalra, F. G. Gustavson and A. Karp, "Implementing Linear Algebra Algorithms for Dense Matric~s on a Vector Pipeline Machine," Siam Rev., pp. 91-112, 198,$.
• 7: I S Duff, Parallel implementation of multifrontal schemes, Parallel Computing, v.3 n.3, p.193-204, July 1986 [doi>10.1016/0167-8191(86)90019-0]
• 8: I.S. Duff, "MA28 - A Set of FORTRAN Subroutines for Sparse Unsymmetric Linear Equations" AERE Ret~rt R.8730, HMSO, London 1977.
• 9: I.S. Duff, "Multiprocessing a Sparse Matrix Code on the Alliant FX/8," Report CSS210, Harwell, 1987.
• 10: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 11: S.C. Eisenstat, M. C. Gursky, M. H. Schultz and A. H. Sherman, Yale Sparse Matrix Package {I: The Nonsymmetric Codes, Yale U. Comp. Sci. Dept. Res. RepL 114, 1977.
• 12: J.W. Huang and O. Wing, "Optimal Parallel Triangulation of a Sparse Matrix," IEEE Trans. CAS, Sept. 1979, pp.726-732.
• 13: G. K. Jacob, A. R. Newton and D. O. Pederson, "Parallel Linear-Equation Solution in Direct-Method Circuit Simulators," Proc. ISCAS 1987. pp. 1056.1059.
• 14: J W H Liu, Computational models and task scheduling for parallel sparse Cholesky factorization, Parallel Computing, v.3 n.4, p.327-342, Oct. 1986 [doi>10.1016/0167-8191(86)90014-1]
• 15: R. Lucas, T. Blank and J. Tiemann, "A Parallel Solution Method for Large Sparse Systems of Equations," IEEE Trans. CAD, pp. 981-991, Nov. 1987.
• 16: L.W. Nagel, "SPICE2: A Computer Program to Simulate Semiconductor Circuits," Memo. no. ERL-M520, UC Berkeley, May 1975.
• 17: L.W. Nagel, Unpublished work, AT&T Bell Labs.
• 18: B.R. Penumalli, Unpublished work, AT&T Bell Labs.
• 19: S.K. Rao, B.D. Actdand, T.B. London and M. Hatamian, "Perfect Hashing for Sparse Matrix Elimination," submitted to IEEE Trans. Comp. , 1988.
• 20: P. Sadayappan , V. Visvanathan, Circuit Simulation on Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.37 n.12, p.1634-1642, December 1988 [doi>10.1109/12.9740]
• 21: P. Sadayappan and V. Visvanathan, "Comparative Analysis of Approaches for Hardware Acceleration for Sparse-Matrix Factorization," Proc. {FEE ICCD 1988. pp. 32-35.
• 22: L.K. Steger, "Vectorization of the LU-Decomposition for Circuit Simulation," Proc. VLSI'87, pp. 353-362, Vancouver, Canada, August 1987.
• 23: D. Smart and J. White, "Reducing the Parallel Solution Time of Sparse Circuit Matrices using Reordered Gaussian Elimination and Relaxation" Proc. ISCAS 1988, pp. 627-630.
• 24: Robert Endre Tarjan , Andrew Chi-Chih Yao, Storing a sparse table, Communications of the ACM, v.22 n.11, p.606-611, Nov. 1979 [doi>10.1145/359168.359175]
• 25: Jiri Vlach , Kishore Singhal, Computer Methods for Circuit Analysis and Design, John Wiley & Sons, Inc., New York, NY, 1983
• 26: A. Vladimirescu, "LSI Circuit Simulation on Vector Computers," Memo. No. ERL 3482/75, UC Berkeley, Oct. 1982.
• 27: W. T. Weeks, A. J. Jimencz, (3. W. Mahoney, D. Mehta, H. Qassemzadeh and T. R. Scott, "Algorithms for ASTAP -A Network Analysis Program," IEEE Trans. CT. pp. 628-6.34, Nov. 1973.
• 28: F. Yamamoto and S. Takahashi, "Vectorized LU Decomposition Algorithms for Large-Scale Circuit Simulation," IEEE Trans. CAD, pp. 232-238, July 1985.
• 29: S.F. Ziegler, "Smaller Faster Table Driven Parser," Unpublished Manuscript, Madison Academic Computing Center, Univ. of Wisconsin, Madison, Wisconsin, 1977.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods); Linear systems (direct and iterative methods)

General Terms:
Algorithms, Design, Theory, Verification