Algorithms and Parallel Computing

7.4 DEPENDENT LOOPS

A dependent loop is one that contains intermediate or I/O variables such that the variable has different index dependences on both sides of the iteration statements. As an example, the loop in Listing 7.1 is a dependent loop, but the I/O variable has the same index independence on both sides. Each iteration of the loop can be done independently of the other iterations.

Listing 7.1 A dependent loop where its iterations are independent

1: for i = 1:I do2: a(i) = a(i) + b(i)3: end for

On the other hand, the dependent loop in Listing 7.2 is a dependent loop, but the I/O variable has different index dependencies on both sides. Each iteration of the loop cannot be done independently of the other iterations.

Listing 7.2 A dependent loop where its iterations are dependent

1: for i = 1:I do2: a(i) = a(i - 1) + b(i)3: end for

Inherently, such loops would be executed serially on uniprocessor or multiprocessor systems. However, by using the formal techniques in Chapters 9–11, we will be able to explore a rich set of parallel implementations of such loops. There are some special and obvious cases where dependent loops can be parallelized. This is done through a technique called loop spreading [77] as explained in the next section.