Algorithms and Parallel Computing

16.6 HARDWARE DESIGN OF THE HIERARCHY BLOCKS

In this section, we derive the hardware required to implement the different functional blocks in the hierarchical description of the algorithm shown in Fig. 16.4. We start with the leftmost level since the timing of the outputs of this level dictates the input timing of the blocks at the next higher level.

16.6.1 Hierarchy Level 3 Hardware Design

Level 3 of the hierarchy is probably the most important one since the hardware that implements it will have the most impact on the timing and hardware resource requirements. The blocks at this level implement 1-D SAD operations as described by Eq. 16.3. To study the data dependency in this equation, we write a 1-D SAD calculation equation in the general form

(16.7)

where D(x) represents the absolute difference calculation when the 1-D current block c is being compared to a reference 1-D block r that is shifted by x positions. The dependence graph of the above equation is shown in Fig. 16.5 for B = 3, P = 3, and W = 15.

Figure 16.5 Dependence graph for the 1-D absolute difference calculation for B = 3, P = 3, and W = 15. Circles represent operations to be performed.

Output variable D(x) is represented by vertical lines so that each vertical line corresponds to a particular instance of D