Systolic Parallel Processing

Book excerpt: 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.