Adaptive Memory Synchronization (AMS): Balancing the Risks and Benefits of Inter-thread Load Speculation

Speculative parallelization (SP) enables a processor to extract multiple threads from a sequential instruction stream, and execute them in parallel. For speculative parallelization to achieve high performance on integer programs, loads must speculate on the data dependences among threads. Techniques for speculating on inter-thread data dependences have a firstorder impact on the performance, power, and complexity of SP architectures. This paper proposes a store-set based synchronization mechanism for SP architectures that leverages previous work on inter-thread register synchronization. The mechanism is simple to implement, requires no selective re-execution or global store broadcast, and uses existing hardware structures that perform register synchronization. Compared to an SP system that speculates across memory dependences, the store-set based synchronizer improves performance by up to 33%, and reduces load violation rate by 80 % on average. However, we find that the store-set synchronizer does not improve performance for all benchmarks: speculating across dependences instead of synchronizing them is a better approach for some applications. Based on this observation, we extend the store-set synchronizer with a likelihood-of-violation predictor that dynamically adapts to application behavior, and finds the right balance between synchronization and speculation. Adaptive memory synchronization (AMS) further improves the performance of the store-set synchronizer by up to 27%, without a significant degradation in violation rate.