The Impact of Vector and Parallel Architectures on the Gaussian Elimination Algorithm
Published on 24. January 1991
Book
Hardback
224 pages
978-0-7190-3365-0 (ISBN)
Description
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.
More details
Series
Language
English
Place of publication
Manchester
United Kingdom
Target group
College/higher education
Professional and scholarly
Illustrations
references
Dimensions
Height: 234 mm
Width: 156 mm
ISBN-13
978-0-7190-3365-0 (9780719033650)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Content
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.