Article

Free access

Efficient sparse matrix factorization for circuit simulation on vector supercomputers

Authors:

V. VisvanathanAuthors Info & Claims

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

Pages 13 - 18

https://doi.org/10.1145/74382.74386

Published: 01 June 1989 Publication History

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 and E. S. Davidson, "Pairwise Reduction for the Direct Parallel Solution of Sparse, Umymmetric Sets of Linear Equations," IEEE Trans. Comp., pp. 1648-1654, Dec. 1988.

Digital Library

[5]

J.J. Dongarra and S. C. Eisenstat, "Squeezing the most out of an Algorithm in CRAY FORTRAN," ACM Trans. Math. So~, pp. 219-230, 1984.

Digital Library

[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, pp. 193-204, 1986.

Digital Library

[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]

I.S. Duff, A. M. Erisman and J. K. Reid, Direct Methods for Sparse Matrices, Oxford University Press, London, 1986.

Digital Library

[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 "{'ask Scheduling for Parallel Sparse Cholesky Factorization," Parallel Computing, pp. 327-342, 1986.

Digital Library

[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 and V. Visvanathan, "Circuit Simulation on Shared-Memory Multiprocessors," IEEE Trans. Comp., pp. t634-1642, Dec 1988.

Digital Library

[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]

R.E. Tarjma and A. C. Yao, "Storing a Sparse Table," Comm. ACM, pp. 606-611, Nov. 1979.

Digital Library

[25]

J. Vlach and K. Singhal, Computer Methods for Circuit Analysis and Design, Van Nostrand Reinhold, New York, 1983.

Digital Library

[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.

Cited By

Bayoumi AHanafy YWatson IEl-Shishiny H(2008)Massive parallelization of SPICE device model evaluation on GPU-based SIMD architecturesProceedings of the 1st international forum on Next-generation multicore/manycore technologies10.1145/1463768.1463784(1-5)Online publication date: 24-Nov-2008
https://dl.acm.org/doi/10.1145/1463768.1463784
Zhang X(2006)Dynamic and static load balancing for solving block bordered circuit equations on multiprocessorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.15999411:9(1086-1094)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.159994
Yul Chu Mahmood ALynch D(1996)Parallel SOLVE for direct circuit simulation on a transputer arrayProceedings of 3rd International Conference on High Performance Computing (HiPC)10.1109/HIPC.1996.565791(27-32)Online publication date: 1996
https://doi.org/10.1109/HIPC.1996.565791
Show More Cited By

Index Terms

Recommendations

A sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of an SPD matrix

In this paper, a method via sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of a symmetric positive definite matrix is proposed. The resulting factorized sparse approximate inverse is used as a preconditioner for ...
Efficient sparse matrix factorization for circuit simulation on vector supercomputers

An efficient approach to sparse matrix factorization on vector supercomputers is described. The approach is suitable for application domains like circuit simulation that require the repeated direct solution of sparse linear systems of equations with ...
GPU-Accelerated Parallel Sparse LU Factorization Method for Fast Circuit Analysis

Lower upper (LU) factorization for sparse matrices is the most important computing step for circuit simulation problems. However, parallelizing LU factorization on the graphic processing units (GPUs) turns out to be a difficult problem due to intrinsic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

June 1989

839 pages

ISBN:0897913108

DOI:10.1145/74382

Chairman:
Donald E. Thomas
Carnegie Mellon Univ., Pittsburgh, PA

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IEEE-CS\TCDA: TC Design Automation
SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC89

Sponsor:

IEEE-CS\TCDA
SIGDA

DAC89: The 26th ACM/IEEE-CS Design Automation Conference

June 25 - 28, 1989

Nevada, Las Vegas, USA

Acceptance Rates

DAC '89 Paper Acceptance Rate 156 of 465 submissions, 34%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
608
Total Downloads

Downloads (Last 12 months)129
Downloads (Last 6 weeks)18

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bayoumi AHanafy YWatson IEl-Shishiny H(2008)Massive parallelization of SPICE device model evaluation on GPU-based SIMD architecturesProceedings of the 1st international forum on Next-generation multicore/manycore technologies10.1145/1463768.1463784(1-5)Online publication date: 24-Nov-2008
https://dl.acm.org/doi/10.1145/1463768.1463784
Zhang X(2006)Dynamic and static load balancing for solving block bordered circuit equations on multiprocessorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.15999411:9(1086-1094)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.159994
Yul Chu Mahmood ALynch D(1996)Parallel SOLVE for direct circuit simulation on a transputer arrayProceedings of 3rd International Conference on High Performance Computing (HiPC)10.1109/HIPC.1996.565791(27-32)Online publication date: 1996
https://doi.org/10.1109/HIPC.1996.565791
Sadayappan PRao SBailey F(1989)Communication reduction for distributed sparse matrix factorization on a processor meshProceedings of the 1989 ACM/IEEE conference on Supercomputing10.1145/76263.76304(371-379)Online publication date: 1-Aug-1989
https://dl.acm.org/doi/10.1145/76263.76304

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten