Next: Program Transformations Up: Experimental Framework Previous: Experimental Framework

Data Dependence

We assume an idealistic approach to handling data dependences. The only data dependence constraint enforced is that a read operation in the trace must only wait for the immediately preceding write operation to the same location. This relaxes many constraints in reality.

First, since we are enforcing only true data dependences (reads after writes), we have eliminated all the anti-dependences (writes after reads) and output dependences (writes after writes) for all register as well as memory accesses. In practice, various renaming techniques can be used to remove some of these spurious data dependences.

Second, we also assume that memory references are perfectly disambiguated; that is, the machines can determine if two addresses are identical even before they have been computed. This perfect disambiguation is an upper bound for what can be achieved by compiler analysis and by speculative hardware disambiguation.

Third, an instruction must wait until it can be determined that no preceding instructions will alter the instruction's operands. Different data dependences may occur along different control flow paths, as shown in the following example:

    b = 0;
    if (a < 0)
       b = 1;
    c = b;
Depending on the outcome of the a < 0 condition, the b = 1 assignment may or may not be executed. Therefore, the value assigned to c depends on the outcome of the condition. The potential data dependence between c = b and b = 1 delays the assignment to c at least until the condition a < 0 is resolved.

Since potential data dependence constraints force instructions to wait for branches, speculation with branch prediction can relax these constraints. For example, if we predict that b = 1 will not execute, c = b can execute speculatively with the assumption that b is 0. If the prediction was incorrect, the assignment must be re-executed with the correct value of b.

We are unable to include the potential data dependence constraints in our experiment because only one execution path is captured in a trace. These constraints must be analyzed statically. Static analysis, however, cannot be completely accurate in the presence of indirect memory references because perfect disambiguation is only possible when analyzing a trace. To ensure that our results are upper bounds, we must avoid introducing constraints based on imperfect disambiguation, and so we ignore the potential data dependence constraints.

Next: Program Transformations Up: Experimental Framework Previous: Experimental Framework

Bob Wilson