No label defined (Q4023844)

This book provides an intuitive insight into the ``art'' of designing systolic algorithms (a formal description is given in the last chapter). The text distinguishes between systolic algorithms (which are constrained only by basic `axioms' of systolic design) and systolic arrays (which depend on limitations of manufacturing technology). Most of the book deals with applications and performance. Theory is also present, both as an undercurrent in the form of an intuitive design methodology and as a formalized part in the last chapter. The first two chapters establish basic steps required for the synthesis of systolic algorithms. The first chapter is introductory; recurrence relations, interconnection structures, analysis and synthesis are briefly summarized as distinct areas of systolic design. A brief history, applications and axioms of systolic algorithms as well as a presentation of the convolution problem are also included. Chapter two defines the space-time representation of algorithms, presents simple methods for manipulating it and shows how it can be used to derive different systolic algorithms. Chapter three to five present a reference set of useful arrays. Chapter three deals with arrays for basic linear algebra problems; chapter four is concerned with the problem of systolically generating tables of data. Finally, chapter five considers nonnumerical and miscellaneous examples (sorting, pattern matching, representation of data structures -- stacks, queues). The examples discussed in these chapters also introduce a number of design principles (array building blocks, control sequences, generification of cell and array functions, two-level pipelining, problem duality, recursive data structures, etc.). Chapters six and seven deal with some of the practical issues associated with the implementation of systolic designs and ways to overcome them. Some techniques for improving design (multipass, interleaving and folding, block partitioning, etc.) are introduced. Fault tolerance is also discussed. Chapter seven presents the programmable systolic arrays. Chapter eight deals with ``automatic'' synthesis of systolic algorithms. Formal treatments of recurrence equations and data dependencies, canonical (normal) form, timing functions, uniformization, are given. This final chapter formalizes the design process and considers the principle of systolic synthesis. Each chapter ends with a summary of some basic design principles and with a set of exercises which extend the work and improve on examples. The book keeps the presentation at a clear, non-sophisticated level (except for the last chapter, which is more formalized); for readers new in the field, this book provides a very good background for more advanced studies. Professor's Megson book is an excellent introduction to the basic principles of systolic design.