Design of parallel algorithms for a multiple bus multiprocessor system.

Abstract

Matrix operations play a crucial role in scientific computations. This thesis presents the design and analysis of four parallel matrix computation algorithms specifically suited for a broadcast bus-based Multiple Bus Multiprocessor System (MMS). Additionally, a cost-optimal 3D VLSI algorithm for matrix-matrix multiplication is proposed. The MMS is a homogeneous private memory multicomputer system. The study includes parallel algorithm designs for the following applications:

(a) Matrix-matrix multiplication (b) Matrix inversion (c) Solution of a system of linear equations (d) Solution of a system of nonlinear equations

Each algorithm is analyzed, and parametric equations for various performance evaluation factors are derived. All five parallel algorithms presented in this thesis are shown to be cost-optimal.