A comprehensive overview of the main topics of systolic design is given. The book is “aimed at senior undergraduates, postgraduates beginning research, and their equivalents in the computer science and electrical engineering industries.” It represents a good classroom textbook as well as an excellent introduction to and survey of the developments in systolic algorithms and systolic arrays design. The intuitive presentation will appeal to anyone involved or interested in the subject.

Chapter 1, “Introduction,” lays out the foundation for the book. The classical convolution problem is used as an example on which the main areas of systolic design can be understood. The author makes a useful distinction between systolic algorithms defined according to a set of axioms and systolic arrays, which are more dependent on technology-based heuristics.

Chapter 2, “Space-time and Retiming,” is perhaps the most important chapter and it needs to be thoroughly understood, since it introduces a systolic design methodology that will be used further in subsequent chapters. Systolic algorithms are described here using an intuitive graph model. The main topics of the chapter are space-time and projections, loop unrolling and pipelining, array unrolling and envelopes, retiming, and cuts.

The following three chapters give significant examples of how the methodology defined in chapter 2 can be applied to basic algorithms in order to get systolic algorithms. Chapter3, “Matrix Algorithms,” revolves around some basic themes: array building blocks, control sequences, and making cell and array functions generic. Direct and iterative methods of solving linear systems and their relationship to matrix algorithms are considered, and systolic algorithms and arrays are developed. Chapter 4, “Table Generation,” considers numerical analysis problems that result in the generation of data in tabular form. Basic algorithms for differencing, extrapolation and interpolation, and polynomial root finding are described along with their systolic counterparts.

While chapters 3 and 4 mainly consider systolic architectures in which the sequence of computation is independent of the input data, chapter 5, “Non-numerical Algorithms,” introduces control-flow systolic architectures, in which the sequence of computations depends on the input data. Systolic data structures together with algorithms for pattern matching, sorting, and semi-rings form the backbone of this chapter.

Issues that are closer to practical systolic devices and their implementation are considered in the next two chapters. Chapter 6, “Improving Array Performance,” looks at multiphase algorithms, interleaving, folding, double pipes, block schemes, and the issue of bit-serial versus bit-parallel as ways of increasing the feasibility and performance of systolic arrays. Fault tolerance and error recovery are also considered here. Chapter 7, “Programmable Systolic Arrays,” presents a successful practical method of implementing systolic algorithms using generic systolic architectures or general-purpose processors.

While the rest of the book mainly uses an informal and intuitive presentation, chapter 8, “Synthesis,” does a good job of formalizing systolic design. Uniform recurrence equations together with timing functions and allocation functions are defined in order to derive a formal systolic design methodology. The future of systolic design seems to be with the automatic synthesis made possible by such formal methods, and different systolic algorithm design environments are the tools that will make that possible.

The book accomplishes the hard task of presenting in an intuitive and interesting manner a large number of systolic design examples together with a methodology that can be applied by the reader in an innovative way in order to develop new applications. Solving the exercises that complement each chapter will further strengthen the reader’s ability to approach new systolic designs.