Andreas Moshovos, Scott E. Breach, T. N. Vijaykumar, Gurindar S. Sohi, Dynamic Speculation and Synchronization of Data Dependences. ISCA 1997: 181-193. ACM DL Link |
> predict if the execution of an instruction is likely to result in a data dependence mis-speculation
> provide sync needed to avoid mis-speculation.
Control speculation and data speculation
data > value and dependence speculation.
small instr window sizes of modern dynamically scheduled processors, the probability of mis-speculation is small, perf loss due to erroneous data dep sep is small. this paper : what if the instr windows are large?
> predict instr whose immediate exec is going to violate true data dependence
> delay the execution of those instr as long as it is nec to avoid the mis-spec.
Dependencies > unambiguous or ambiguous. 2 instr linked via an ambiguous dependence gets resolved to no dependence => speculation is okay.
problem most acute : production and consumption of data through memory. this paper only looks at this.
a load is allowed before a store which its ambiguously dependent. (normally processors do this blindly).
As window sizes grow larger, min the net cost of mis-speculation important.
min the amount of work lost due to misspec
reduce the time required to redo the work that is lost on misspeculation
reduce the prob of mis-spec.
to min the impact
predict if the immediate exec is likely to violate true data dependence
predict the store/stores that the load depends upon
enforce synchronization between the dependent instru.
selective data dependence speculation > choose which loads should be speculated
static store-load instr pairs that cause most of the dynamic data mis-speculations are relatively few and exhibit temporal locality. > build the association eg., save the address accessed. or : use dependence edge as a handle : PC of the store, load. but static dependence between a given store-load pair > multiple dynamic dependencies.
differentiate dynamic instances : same static dependence > a tag for each instance. dependence distance can be used
Implementation
Memory dependence prediction table
valid flag, LD PC, ST PC, DIST, optional prediction
Memory dependence synchronization table
Valid, LD PC, ST PC, LD ID, ST ID, INST, full/empty flag (conditional variable).
Issues
Intelligent prediction required
Incomplete synchronization
avoid deadlock
free MDST entry allocated for sync that will never occur (pipeline flush say)
Misspeculations
squash MDST entries.
Multiple Table Entry matches
discard all but most frequent mis-speculations.
Conclusions
larger dynamic window sizes > net performance loss due to data dependence mis-speculation is higher.
min work lost, min time required to redo, improve spec accuracy
static data dependencies responsible for majority of mis-speculations are few and dynamically exhibit temporal locality.
dynamic dependence prediction and synchronization in hardware