Modeling speedup in parallel sparse matrix factorization

Author

Laura Susan Ostrouchov

Date of Award

12-1990

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Michael T. Heath

Committee Members

Jack Dongarra, Esmond Ng

Abstract

This paper is an attempt to explain the observed performance of sparse matrix factorization algorithms on parallel computers. In particular, we examine whether the disappointing performance of these algorithms is due to insufficient parallelism in the problem or to the architectural characteristics of existing parallel computers. Through a series of theoretical models of increasing realism, we first determine upper and lower bounds on the speedup that can be expected in practice for this problem, and end with a parameterized model that is capable of reproducing the full range of behavior within these bounds, including the speedups actually observed in practice. This model suggests that the current limits on speedup in sparse factorization are due to poor communication performance of the present generation of parallel computer architectures rather than to a lack of parallelism in the problem.

Recommended Citation

Ostrouchov, Laura Susan, "Modeling speedup in parallel sparse matrix factorization. " Master's Thesis, University of Tennessee, 1990.
https://trace.tennessee.edu/utk_gradthes/12744