Fast computation of computer algorithms is an important research area in applied computer science. Many applications, for example, image processing, digital signal processing, and computer graphics, require real-time computations. Toward that end, researchers developed computer architectures that could provide fast computations. Over time, the number of computing elements was increased, and different ways of connecting them evolved. Now, this communication medium can be dynamically configured to achieve fast solutions for many computing algorithms. This book is dedicated to the study of these dynamically configured architectures.

The research community has developed many algorithms for different applications to run on these reconfigurable architectures. This book presents a single computational platform called R-mesh (reconfigurable mesh) to present these algorithms. R-mesh is representative of many existing similar architectures, and runs most of the algorithms described in the book.

The book contains 11 chapters, and a list of over 300 references for more in-depth study in this area. Chapter 1 offers an introduction to dynamically reconfigurable architecture and R-mesh. It presents some simple algorithms, to illustrate the use of the model. Chapter 2 details the R-mesh, and the coding conventions used to describe algorithms. A collection of algorithms from arithmetic and graph theory is used to illustrate the applications. Chapter 3 discusses the extensions and restrictions of the R-mesh model. It also describes other bus-based models, optical models, and field programmable gate arrays (FPGA), and their relationships with R-mesh in terms of computing power and implementation.

The next four chapters are devoted to algorithms in different areas. Chapter 4 covers fast arithmetical algorithms for addition, multiplication, and division. Chapter 5 is on sorting algorithms, and discusses speed-efficiency concerns. Chapter 6 is on graph algorithms for trees, spanning tree algorithms, directed graphs, and so on. List ranking is also discussed. Chapter 7 is devoted to computational geometry and image processing. This chapter contains discussions on convex hull, nearest neighbors, histograms, quadtrees, and so on. Chapter 8 discusses scalability problems for reconfigurable architectures. It addresses the relationship between problem size and machine size. It details methods to cope with the problem of scalability, using examples. Chapter 9 goes into the computational complexity of reconfigurable architectures, and presents comparisons with other models. It also compares them with Turing machines and circuit complexity classes. Chapter 10 addresses the use of fiber optic buses in reconfigurable architectures. The bus can move large amounts of data between processors, thus providing a speed advantage. This chapter provides models for such architectures, and describes the complexity results for algorithms implemented on these machines. Finally, chapter 12 details the runtime configuration (RTR) for FPGA, and relates it to R-mesh type situations. It also describes how R-mesh can be implemented on a FPGA platform.

The book is well written, and there are ample illustrations. Examples are plentiful, and described in detail. Issues are addressed both in practical and theoretical terms. The book will be useful as a text at the graduate level, and may also prove valuable to the research and industrial communities.