Piecewise Regular Arrays

Book excerpt: Application-specific regular array processors have been widely used in signal and image processing, multimedia and communication systems, for example, in data compression and HDTV. One of the main problems of application-specific computing is how to map algorithms into hardware. The major achievement of the theory of regular arrays is that an algorithm, represented as a data dependence graph, is embedded into a Euclidean space, where the integer points are the elementary computations and the dependencies between computations are denoted by vectors between points. The process of mapping an algorithm into hardware is reduced to finding, for the given Euclidean space, a new coordinate system that can be associated with the physical properties of space and time - so called space-time. The power of the synthesis method is that it provides a bridge between "abstract" and "physical" representations of algorithms, thus providing a methodological basis for synthesizing computations in space and in time. This book will extend the existing synthesis theory by exploiting the associativity and commutativity of computations. The practical upshot being a controlled increase in the dimensionality of the Euclidean space representing an algorithm. This increase delivers more degrees of freedom in the choice of the space-time mapping and leads, subsequently, to more choice in the selection of cost-effective application-specific designs.