Parallel algorithm synthesis for message-passing distributed-memory architectures

This thesis presents a systematic approach to the design of parallel algorithms for message-passing distributed-memory processing architectures. The basic idea of the methodology has been to devise a description of a robust subset of all the possible parallel algorithms by parameterizing the assignment of the operations of an algorithm to processors, parameterizing the number of operations between communications, expressing the performance of the algorithm as a function of the computational and communication performance parameters of the architecture, and then optimizing with respect to the parameters to find the best implementation within the subset for a particular architecture. This methodology has been applied to a diverse set of algorithms: successive over-relaxation (SOR), fast-Givens, and triangular substitution. All of these algorithms are of noted interest to parallel processing communities and have been well studied over the past decade. When the methodology described in this thesis was applied to these algorithms, significant performance improvements were achieved beyond the existing literature.