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 do
2: 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 do
2: 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.