The Impact of Vector and Parallel Architectures on the Gaussian Elimination Algorithm

The thesis of this book is that the design of efficient parallel algorithms is dependent on a knowledge of the underlying parallel architecture. The first part of the book is implementation oriented, whereas the second part is devoted to design tools and methodologies. The first section of the book contains some background information on Gaussian elimination and parallel processing terminology and an introduction to pipeline, vector and parallel architectures. The next three chapters of the book are implementation oriented, describing the restructuring techniques needed for shared memory vector multiprocessors, distributed memory systems and systolic arrays. The book describes the recasting of the Gaussian elimination algorithm in terms of vector-vector, vector-matrix and matrix-matrix kernels, discusses hypercube computing and gives real-life examples of implementations on message-passing distributed memory systems. The last three chapters are more theoretical. Subjects covered include task graph scheduling, complexity results and speedup evaluation in a distributed memory environment and automatic synthesis methods for systolic arrays.

Table of Contents:
Introduction: background - Gaussian elimination, speedup and efficiency; vector and parallel architectures: pipeline computers; vector computers; parallel computers; three case studies. Part 1 Parallel algorithm design - vector multiprocessor computing - vectorization of vector-vectr operations, Gaussian elimination in terms of vector-vector kernels, vector register re-use, Gaussian elimination interms of matrix-vector kernels, cache re-use, Gaussian elimination in terms of matrix-matrix kernels, vectorization epilogue, fine-grain parallelism, parallel Gaussian elimination; hypercube computing - topological properties of hypercubes, broadcasting, centralized Gaussian elimination, local pipelined algorithms, a word on speedup evaluation, matrices over finite fields; systolic computing - 2D arrays, solving the triangular system on the fly, 1D arrays, matrices over finite fields. Part 2 Models and tools: task graph scheduling - task system for Gaussian elimation, bounds for parallel execution, an optimal schedule, with an arbitrary number of processors; analysis of distributed algorithms - data allocation strategies, speedup evaluation on distributed memory machines; design methodologies for systolic arrays - dependence mapping method, complexity results, folding.