This work emphasizes the significance of systolic algorithms for massively-parallel computing. It presents, using a unified representation form, a collection of important systolic algorithms for various problems: linear algebra, linear filters, operations with polynomials, comparison problems with some applications to non-linear filtering and data structures, dynamic programming and computational geometry. Design principles and techniques are given and illustrated with concrete examples.The book is also concerned with the results achieved in the past decade in different methodologies for systematic design, efficiency improvement and partitioning of systolic algorithms. In this respect, systolic algorithms still have a unique position among parallel algorithms, in that only this kind of algorithm has mature systematic design techniques. The most important theoretical results achieved in systolic array research are concentrated in Chapter 2 (definitions), Chapter 11 (systematic design) and Chapter 12 (partitioning). The different efficiency improvement techniques are presented when treating concrete algorithms.It should be of great interest to researchers involved in computer science and electrical and computer engineering and to producers of high-performance computers, in particular of massively-parallel computers.
Reihe
Sprache
Verlagsort
Verlagsgruppe
Elsevier Science & Technology
Zielgruppe
Illustrationen
ISBN-13
978-0-444-88769-6 (9780444887696)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Klassifikation
Autor*in
Friedrich-Alexander-Universitaet, Erlangen-Nuernberg, Germany and University of Groningen, The Netherlands
The Systolic Mode of Parallel Processing. Introduction to the Underlying Concept. The Original Motivation: VSLI Implementation. The Present Trend: Efficient Algorithms for Massively Parallel Computers. A List of Known Applications. Defining and Expressing Systolic Arrays and Algorithms. Using Automata Notions. Defining Systolic Automata, Arrays, and Algorithms. Expressing Systolic Algorithms. Analysis and Comparison of Systolic Algorithms. Matrix-Vector and Matrix Multiplication. Introduction to Vectors and Matrices. Matrix-Vector Multiplication. Systolic Simulation of Feedforward Artificial Neural Networks. Matrix Multiplication. Solving Systems of Linear Algebraic Equations. Introduction to Linear Systems. Gaussian Elimination. Systolic Arrays for Triangularization and LU/QR Decomposition. Systolic Algorithms for Back Substitution. Systolic Implementation of Iterative Methods. Further Problems of Linear Algebra. Computing the Inverse of a Matrix. Generalized Elimination. Computing the Characteristic Polynomial. Matrix Transposition and Related Operations. Convolution and Linear Filters. Convolution, Correlation, FIR and IIR Filters. Semi-Systolic Realizations. Unidirectional Full-Systolic Arrays. Systolic Arrays with Bidirectional Data Flow. Bit-Level Systolic Convolver. Operations with Polynomials. Introduction. Multiplication of Polynomials and Integers. Division of Polynomials. Computing the Greatest Common Divisor. Polynomial Interpolation. Evaluation of Polynomials. Comparison Problems. Sorting. Selection and Running Order Statistics. Sorting and Order Statistics for Rank Filtering. A Data Structure: Priority Queue. Dynamic Programming and its Applications. Introduction. Implementing the Dynamic Programming Recurrence in a Two-Dimensional Systolic Array. Implementation in One-Dimensional Arrays. Further Dynamic Programming Recurrences. Computational Geometry. Convex Hull. Nearest-Neighbours Problems. Systematic Design of Systolic Algorithms. Dependence Graphs. Systolic Array Dependence Graphs. Extracting Systolic Algorithms from Dependence Graphs. Modifying the Properties of Systolic Algorithms. Partitioning of Systolic Algorithms. Partitioning, Algorithm Mapping, Design of Flexible Systolic Structures, Time Sharing. Application of c-Slow Automata to the Realization of Parallel Structures. Examples: Mapping Different Filter Banks onto the Same Fixed-Size Processor Array. A Summary of the Technique and Alternative Approaches.References and Additional Literature. Subject Index.
