How Dependencies Influence the Ability Run Code in Parallel

How Dependencies Influence the Ability Run Code in Parallel

Dependencies within an application (or the calculation it performs) define whether the application can possibly run in parallel. There are two types of dependency: loop- or data-carried dependencies and memory-carried dependencies.

With a loop-carried dependency, the next calculation in a loop cannot be performed until the results of the previous iteration are known. A good example of this is the loop to calculate whether a point is in the Mandelbrot set. Listing 3.4 shows this loop.

Listing 3.4     Code to Determine Whether a Point Is in the Mandelbrot Set

int inSet(double ix, double iy)

{

int iterations=0;

double x = ix,  y          = iy,     x2 = x*x, y2 = y*y;    

while ( (x2+y2 <          4) &&  (iterations < 1000)       )

{                                                                     

y          =          2 * x * y + iy;             

x          =          x2 - y2 + ix;                

x2 =     x * x;                                      

y2 =     y * y;                                      

iterations++;

}

return iterations;

}

Each iteration of the loop depends on the results of the previous iteration. The loop terminates either when 1,000 iterations have been completed or when the point escapes a circle centered on the origin of radius two. It is not possible to predict how many iter-ations this loop will complete. There is also insufficient work for each iteration of the loop to be split over multiple threads. Hence, this loop must be performed serially.

Memory-carried dependencies are more subtle. These represent the situation where a memory access must be ordered with respect to another memory access to the same location. Consider the snippet of code shown in Listing 3.5.

Listing 3.5     Code Demonstrating Ordering Constraints

int val=0;

void g()

{

val = 1;

}

void h()

{

val = val + 2;

}

If the routines g() and h() are executed by different threads, then the result depends on the order in which the two routines are executed. If g() is executed followed by h(), then the val will hold the result 3. If they are executed in the opposite order, then val will contain the result 1. This is an example of a memory-carried dependence because to produce the correct answer, the operations need to be performed in the cor-rect order.