VLSI Digital Signal Processing Systems: Design and Implementation

7.2    SYSTOLIC ARRAY DESIGN METHODOLOGY

Systolic architectures are designed by using linear mapping techniques on regular dependence graphs [3] – [7]. The edges in dependence graphs represent precedence constraints. A dependence graph (DG) is said to be regular if the presence of an edge in a certain direction at any node in the DG represents presence of an edge in the same direction at all nodes in the DG.

Example 7.2.1    As an example, consider the DG for a 3-tap FIR filter

shown in Fig. 7.2. This DG has 3 fundamental edges: input moving upward represented by an edge in [0 1]^T direction, coefficient moving toward the right represented by an edge in [1 0]^T direction, and the result moving in [1 − 1]^T direction. Since all nodes in the DG contain the same three edges, this DG is regular.

The DG corresponds to a space representation where no time instance is assigned to any computation. Typically this corresponds to a t = 0 plane. The mapping technique transforms a space representation to a space-time representation where each node is mapped to a certain processing element and is scheduled to a certain time instance.

The systolic design methodology maps an N-dimensional DG to a lower dimensional systolic architecture. In this chapter, only one-level mapping is considered where a ...