Performance estimation of LU factorisation on messasge passing multiprocessors

Abstract

The paper proposes an analytical model for estimating the performance of Pipelined Ring algorithm for LU factorisation on any distributed memory message passing multiprocessor. Expressions for parallel execution time and speedup are derived from the computation-communication characteristics of the algorithm. Earlier methods on performance estimation of LU factorisation have been based on determining the number of floating point operations in the best and worst cases. The methodology proposed in this paper follows a different approach and estimates the performance of LU factorisation from a measurement of the execution time of the algorithm on a single processor and from a knowledge of the number of bytes communicated in different steps of the algorithm. The expression for parallel execution time of LU factorisation derived from the analytical model has been validated with experimental values obtained 011 a sixty-four transputer based multiprocessor. Results indicate that the methodology proposed in this paper can be used for estimating the execution time of Pipelined Ring algorithm for LU factorisation on any distributed memory message passing multiprocessor with high accuracy.