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
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
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
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
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.
Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.