Antidependencies and Output Dependencies

Antidependencies and Output Dependencies

Suppose one task, A, needs the data produced by another task, B; A depends on B and cannot start until B completes and releases the data needed by A. This is often referred to as true dependency. Typically, B writes some data, and A needs to read that data. There are other combinations of two threads reading and writing data. Table 3.1 illustrates the four ways that tasks might have a dependency.

Table 3.1      Possible Ordering Constraints

When both threads perform read operations, there is no dependency between them, and the same result is produced regardless of the order the threads run in.

With an antidependency, or write after read, one task has to read the data before the second task can overwrite it. With an output dependency, or write after write, one of the two tasks has to provide the final result, and the order in which the two tasks write their results is critical. These two types of dependency can be most clearly illustrated using serial code.

In the code shown in Listing 3.6, there is an antidependency on the variable data1. The first statement needs to complete before the second statement because the second statement reuses the variable data1.

Listing 3.6     An Example of an Antidependency

void anti-dependency()

{

result1 =          calculation(      data1 );            //          Needs to complete first

data1   =          result2 + 1;                  //          Will overwrite data1

}

If one of the statements was modified to use an alternative or temporary variable, for example, data1_prime, then both statements could proceed in any order. Listing 3.7 shows this modified code.

Listing 3.7     Fixing an Antidependency

void anti-dependency()

{

data1_prime = data1;  // Local            copy of data1

result1 =          calculation( data1_prime         );         

data1   =          result2 + 1;      // No longer     has antidependence

}

The code shown in Listing 3.8 demonstrates an output dependency on the variable data1. The second statement needs to complete after the first statement only because they both write to the same variable.

Listing 3.8     An Output Dependency

void output-dependency()

{

data1 = result1 + 2;

data1 = result2 + 2; // Overwrites same variable

}

If the first target variable was renamed data1_prime, then both statements could proceed in any order. Listing 3.9 shows this fix.

Listing 3.9     Fixing an Output Dependency

void output-dependency()

{

data1_prime = result1 + 2;

data1     = result2 + 2; // No longer has output-dependence

}

What is important about these two situations is that both output and antidependen-cies can be avoided by renaming the data being written, so the final write operation goes to a different place. This might involve taking a copy of the object and having each task work on their own copy, or it might be a matter of duplicating a subset of the active variables. In the worst case, it could be resolved by both tasks working independently and then having a short bit of code that sets the variables to the correct state.