Page 389 - DSP Integrated Circuits

374 Chapters DSP Architectures

Figure 8.21 Binary and quad trees

Interconnection networks are also characterized by communication, control,
and switching strategies. The communication strategy used in the interconnection
network can be either synchronous or asynchronous while control, of the data flow
can either be centralized or distributed.
There are two major switching methodologies: packet switching and circuit
switching. In packet switching, a message is partitioned into small packets which
are transmitted through the network. A packet experiences a random delay at
each switching point, depending on the traffic in the network along its path to the
destination. Conversely, circuit switching sets up a physical path between source
and destination. A time delay is incurred in setting up the path. Once the path is
established, it is held for the entire data transmission. Generally, circuit switching
is more suited to long messages, and packet switching to short messages. Flexibil-
ity in multiple PE architectures is often low—e.g. it is difficult to use and exploit
varying data word lengths in an algorithm.

8.7 SYSTOLIC ARRAYS

Systolic and wave front arrays are suitable for applications with very high
throughput requirements. Typical applications can be found in sonar, radar, seis-
mic, video, and image processing where the amount of data is very large. Further,
real-time video applications require high sample rates. Matrix and vector opera-
tions are suitable for implementation using systolic or wave front array architec-
tures [1, 7, 9,12,16,19].
A systolic array is defined as a lattice of synchronous and locally connected
PEs that can perform iterative algorithms with regular data dependencies. A sys-
tolic algorithm is basically described by a set of indexed calculations performed in
a lattice space. Indexing of the dependent variables is local and regular. Ordering
or scheduling of calculations is established by preserving the dependencies. By
selecting appropriate projections of the index set along a direction, lattice points in
the index space can be mapped onto one- or two-dimensional structures. These
time-space mappings result in a scheduled, regular, connected PE structure.