Systolic Arrays - Signal Processing Systems - page 1105

to compensate. On the other hand, as the number of on-chip transistors increases,
so does the complexity and size of on-chip clock distribution network. The power
consumption required to distribute giga-hertz clock signal synchronously over entire
chip becomes too large to be practical.
In view of the potential difficulties in realizing a globally synchronous clocking
scheme as required by the original systolic array design, a asynchronous array
processor, known as wavefront array processor has been proposed.

4.2 Wavefront Array Processor Architecture

According to [ 14 , 16 ] , a wavefront array is a computing network with the following
features:

￿ Self-timed, data-driven computation : No global clock is needed, as the computa-

tion is self-timed.

￿ Regularity, modularity and local interconnection : The array should consist of

modular processing units with regular and (spatially) local interconnections.

￿ Programmability in wavefront language or data flow graph ( DFG ): Computing

algorithms implemented on a wavefront array processor may be represented with
a data flow graph. Computation activities will propagate through the processor
array as if a series of wavefronts propagating through the surface of water.

￿ Pipelinability with linear-rate speed-up : A wavefront array should exhibit a

linear-rate speed-up. With M PEs, a wavefornt array promises to achieve an O(M)
speed-up in terms of processing rates.

The major distinction between the wavefront array the systolic array is that there
is no global timing reference in the wavefront array. In the wavefront architecture,
the information transfer is by mutual agreements between a PE and its immediate
neighbors using, say, an asynchronous hand-shaking protocol [ 4 , 16 ] .

4.3 Mapping Algorithms to Wavefront Arrays

In general, there are three formal methodologies for the derivation of wavefront
arrays [ 15 ] :

(1) Map a localized dependence graph directly to a data flow graph (DFG). Here a
DFG is adopted as a formal abstract model for wavefront arrays. A systematical
procedure can be used to map a dependence graph (DG) to a DFG.
(2) Convert an signal flow graph into a DFG (and hence a wavefront array), by
properly imposing several key data flow hardware elements.
(3) Trace the computational wavefronts and pipeline the fronts through the proces-
sor array. This will be elaborated below.