(2.1.6) Dynamic speculation and syn of Data Dependencies


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