Algorithms and Parallel Computing

7.3 INDEPENDENT LOOP SCHEDULING

An independent loop is one that does not contain intermediate or I/O variables. The iterations in an independent loop can be carried out in any order and can still produce the correct results. The FIR digital filter is an example of parallel algorithms that can be described by an independent loop. The following equations describe 1-D, two-dimensional (2-D), and three-dimensional (3-D) FIR filters used to process voice, image, and video data, respectively:

(7.3)

(7.4)

(7.5)

where I is the filter length, W is the width of the filter window, H is the height of the filter window, and F is the number of frames in the filter window. All the variables in the above equations are either an input or output type.

Another example of algorithms that result in independent loops is matrix–vector multiplication (c = Ab) and matrix–matrix multiplication (C = AB):

(7.6)

(7.7)

Consider for illustration the 1-D FIR in Eq. 7.1. If we had N processors and ...