On the parallelization of blocked LU factorization algorithms on distributed memory architectures

Gregor Von Laszewski; Manish Parashar; A. Gaber Mohamed; Geoffrey C. Fox

doi:10.1109/superc.1992.236696

On the parallelization of blocked LU factorization algorithms on distributed memory architectures

Gregor Von Laszewski, Manish Parashar, A. Gaber Mohamed, Geoffrey C. Fox

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

Solutions to systems of linear equations and specifically, the LU factorization of matrices form the computational core of many scientific and engineering applications. In this paper, we present the parallelization of blocked algorithms for L U factorization. We isolate problems inherent to sequential blocked algorithms and provide approaches to overcome them on distributed memory architectures. The performance of the parallelized versions of three blocked algorithms suited to column oriented Fortran is compared. Experiments are performed on the iPSC/860 Hypercube. Our study shows that it is not intuitively clear which algorithm might perform best on a given architecture, but is dependent on the problem size and the number of available processors.

Original language	English (US)
Title of host publication	Proceedings of the 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992
Editors	Robert Werner
Publisher	Association for Computing Machinery
Pages	170-179
Number of pages	10
ISBN (Electronic)	0818626305
DOIs	https://doi.org/10.1109/superc.1992.236696
State	Published - Dec 1 1992
Externally published	Yes
Event	1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992 - Minneapolis, United States Duration: Nov 16 1992 → Nov 20 1992

Publication series

Name	Proceedings of the International Conference on Supercomputing
Volume	Part F129723

Other

Other	1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992
Country	United States
City	Minneapolis
Period	11/16/92 → 11/20/92

All Science Journal Classification (ASJC) codes

Computer Science(all)

Access to Document

10.1109/superc.1992.236696

Fingerprint Dive into the research topics of 'On the parallelization of blocked LU factorization algorithms on distributed memory architectures'. Together they form a unique fingerprint.

Cite this

Von Laszewski, G., Parashar, M., Mohamed, A. G., & Fox, G. C. (1992). On the parallelization of blocked LU factorization algorithms on distributed memory architectures. In R. Werner (Ed.), Proceedings of the 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992 (pp. 170-179). (Proceedings of the International Conference on Supercomputing; Vol. Part F129723). Association for Computing Machinery. https://doi.org/10.1109/superc.1992.236696

Von Laszewski, Gregor ; Parashar, Manish ; Mohamed, A. Gaber ; Fox, Geoffrey C. / On the parallelization of blocked LU factorization algorithms on distributed memory architectures. Proceedings of the 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992. editor / Robert Werner. Association for Computing Machinery, 1992. pp. 170-179 (Proceedings of the International Conference on Supercomputing).

@inproceedings{577b8ea6ded543d6836edf9062abb99c,

title = "On the parallelization of blocked LU factorization algorithms on distributed memory architectures",

abstract = "Solutions to systems of linear equations and specifically, the LU factorization of matrices form the computational core of many scientific and engineering applications. In this paper, we present the parallelization of blocked algorithms for L U factorization. We isolate problems inherent to sequential blocked algorithms and provide approaches to overcome them on distributed memory architectures. The performance of the parallelized versions of three blocked algorithms suited to column oriented Fortran is compared. Experiments are performed on the iPSC/860 Hypercube. Our study shows that it is not intuitively clear which algorithm might perform best on a given architecture, but is dependent on the problem size and the number of available processors.",

author = "{Von Laszewski}, Gregor and Manish Parashar and Mohamed, {A. Gaber} and Fox, {Geoffrey C.}",

note = "Funding Information: 1This research is sponsored by D.4FwA mder contract #DABT63-91-k-OO05. The content of the information does not necessary reflect the position or the policy of the Government and no official endorsement should be inferred. Use of the Intel iPSC/860 was provided by the Center for Research on Parallel Computation under NSF Cooperative Agreement Nos. CCR-8809615 and CDA-8619893 with support from the Keck fonm dation.; 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992 ; Conference date: 16-11-1992 Through 20-11-1992",

year = "1992",

month = dec,

day = "1",

doi = "10.1109/superc.1992.236696",

language = "English (US)",

series = "Proceedings of the International Conference on Supercomputing",

publisher = "Association for Computing Machinery",

pages = "170--179",

editor = "Robert Werner",

booktitle = "Proceedings of the 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992",

}

Von Laszewski, G, Parashar, M, Mohamed, AG & Fox, GC 1992, On the parallelization of blocked LU factorization algorithms on distributed memory architectures. in R Werner (ed.), Proceedings of the 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992. Proceedings of the International Conference on Supercomputing, vol. Part F129723, Association for Computing Machinery, pp. 170-179, 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992, Minneapolis, United States, 11/16/92. https://doi.org/10.1109/superc.1992.236696

On the parallelization of blocked LU factorization algorithms on distributed memory architectures. / Von Laszewski, Gregor; Parashar, Manish; Mohamed, A. Gaber; Fox, Geoffrey C.

Proceedings of the 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992. ed. / Robert Werner. Association for Computing Machinery, 1992. p. 170-179 (Proceedings of the International Conference on Supercomputing; Vol. Part F129723).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the parallelization of blocked LU factorization algorithms on distributed memory architectures

AU - Von Laszewski, Gregor

AU - Parashar, Manish

AU - Mohamed, A. Gaber

AU - Fox, Geoffrey C.

N1 - Funding Information: 1This research is sponsored by D.4FwA mder contract #DABT63-91-k-OO05. The content of the information does not necessary reflect the position or the policy of the Government and no official endorsement should be inferred. Use of the Intel iPSC/860 was provided by the Center for Research on Parallel Computation under NSF Cooperative Agreement Nos. CCR-8809615 and CDA-8619893 with support from the Keck fonm dation.

PY - 1992/12/1

Y1 - 1992/12/1

N2 - Solutions to systems of linear equations and specifically, the LU factorization of matrices form the computational core of many scientific and engineering applications. In this paper, we present the parallelization of blocked algorithms for L U factorization. We isolate problems inherent to sequential blocked algorithms and provide approaches to overcome them on distributed memory architectures. The performance of the parallelized versions of three blocked algorithms suited to column oriented Fortran is compared. Experiments are performed on the iPSC/860 Hypercube. Our study shows that it is not intuitively clear which algorithm might perform best on a given architecture, but is dependent on the problem size and the number of available processors.

AB - Solutions to systems of linear equations and specifically, the LU factorization of matrices form the computational core of many scientific and engineering applications. In this paper, we present the parallelization of blocked algorithms for L U factorization. We isolate problems inherent to sequential blocked algorithms and provide approaches to overcome them on distributed memory architectures. The performance of the parallelized versions of three blocked algorithms suited to column oriented Fortran is compared. Experiments are performed on the iPSC/860 Hypercube. Our study shows that it is not intuitively clear which algorithm might perform best on a given architecture, but is dependent on the problem size and the number of available processors.

UR - http://www.scopus.com/inward/record.url?scp=0039821550&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039821550&partnerID=8YFLogxK

U2 - 10.1109/superc.1992.236696

DO - 10.1109/superc.1992.236696

M3 - Conference contribution

AN - SCOPUS:0039821550

T3 - Proceedings of the International Conference on Supercomputing

SP - 170

EP - 179

BT - Proceedings of the 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992

A2 - Werner, Robert

PB - Association for Computing Machinery

T2 - 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992

Y2 - 16 November 1992 through 20 November 1992

ER -

Von Laszewski G, Parashar M, Mohamed AG, Fox GC. On the parallelization of blocked LU factorization algorithms on distributed memory architectures. In Werner R, editor, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, Supercomputing 1992. Association for Computing Machinery. 1992. p. 170-179. (Proceedings of the International Conference on Supercomputing). https://doi.org/10.1109/superc.1992.236696