A Quick Description of my Thesis Project (10/14/96)

Here's a link to the abstract of my thesis.

Here's a link IUCS Technical Report 471 (a.k.a. my thesis) stored in compressed PostScript format.

Some of the details of my work at IU:

Wrote a C++/FORTRAN parallel iterative linear system solver package for matrices in Compressed Sparse Row format on the SGI Power Challenge using MPI. The solver package supports the Conjugate Gradient, GMRES, and Bi-Conjugate Gradient Stabilized algorithms with block Jacobi and block SSOR preconditioning. Now working on porting the code to the IBM SP-2.
Determining the run-times of the key solver operations (kernels) on the Power Challenge and the SP-2. The kernels are the uni-processor mathematical operations that support the solver, point-to-point and collective communications primitives, and a global synchronization primitive.
Deriving simple models of the kernel run-times, using Perl and Matlab to analyze the data and find least squares approximations to the run-times over the vector lengths. Some of these approximations are in "MPI Performance on the SGI Power Challenge" .
Developing an estimate of the solver run-time, based on a discrete event simulation that combines the kernel run-time estimates, while keeping track of the contents of each processor's memory and the communications in transit -- this design is a compromise between estimation function speed and accuracy.
Using this estimate to as part of an algorithm to determine data distribution for the solver. This algorithm is based on the Kernighan-Lin local graph partitioning algorithm -- the idea is to replace the edges cut cost metric of Kernighan-Lin with the run-time estimate discussed above.

The hope is that this new algorithm will lead to faster solver run-times on the parallel processor network due to a better data distribution while not taking too long to execute.