Efficient Sequential Consistency in GPUs via Relativistic Cache Coherence

Efficient Sequential Consistency in GPUs via Relativistic Cache Coherence Xiaowei Ren and Mieszko Lis The University of British Columbia

Contributions : GPU Sequential Consistency GPU Best Relaxed Consistency Performance Gap: from 28% to 7% Two Possible Solutions : Change Core Microarchitecture Improve Cache Coherence Protocol 2

Cost of SC : store stalls A valid in $ C0 ld A sync through Invalidation messages dir time C1 execution continues st A - longer latency Idealized MESI (no latency for inv-ack): 1.6x faster 3

Cost of SC in Temporal Coherence Problem A valid in $ until t=100 ld A C0 sync through shared clock ld A(hit) 100 dir time C1 st A execution continues + no write stalls + can support SC wait until lease expires cannot support SC TC: 88% faster than MESI TC-SC: 28% slower than TC 4 Shim et al. Library Cache Coherence. MIT CSAIL TR 2011-027, 2011. Singh et al. Cache Coherence for GPU Architectures. In HPCA 2013.

Removing SC Stalls : RCC A is invalidated after clock advancement A valid until C0 s now=10 ld A B valid until C0 s now=25 Assume B was written @ 15 ld B C0 ld A(hit) sync through distributed logical clocks now=0 now=0 now=0 now=15 now=0 Earliest timestamp later than 10 dir physical time now=11 now=11 now=0 now=0 now=11 C1 st A ld A + no write stalls new A valid until C1 s now=21 Store: advance clock of writing core to the logical time store should happen Load: advance clock of reading core to the logical time data were written 5

Distributed Logical-clocks in CPUs ? CPU : latency-critical GPU : throughput-oriented, latency-tolerant GPU : private $ write-through shared $ write-back CPU : private $ write-back shared $ write-back CPU* Yes Yes Yes Yes Complex GPU No No No No Simple need speculation ? downgrade ? invalidation message ? recall message ? implementation ? 6 Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Comm. ACM, 21:558 565, 1978. *Yu & Devadas. TARDIS: Timestamp-based Coherence Algorithm for Distributed Shared Memory. In PACT 2015.

Simple Implementation core state now now, ver and exp are 32-bit. v v v v tag tag tag tag data data data data exp exp exp exp L1$ state Area Overhead : 3% for L1 $ 6% for L2 $ v d v d v d v d v d v d tag tag tag tag tag tag data data data data data data ver ver ver ver ver ver exp exp exp exp exp exp L2$ state 7

Simple Implementation MESI 16 81 15 50 TC-SC 5 27 8 23 TC 5 42 8 34 RCC 5 33 4 14 L1 states L1 transitions L2 states L2 transitions 8

Stall cost improved? 1.0 0.8 0.6 52% less than MESI 0.4 25% less than TC-SC 0.2 0.0 TC-SC MESI RCC Stalls caused by SC 9

Overall Performance 2.0 1.25 inter-workgroup sharing (left): 1.0 1.5 76% faster than MESI 0.75 1.0 29% faster than TC-SC 0.5 intra-workgroup sharing (right): 10% faster than MESI 0.5 0.25 0.0 0.0 3% faster than TC-SC TC-SC MESI RCC TC-SC MESI RCC 10

So, cost of full SC support in GPUs? 1.25 1.25 1.0 1.0 Inter-Workgroup Sharing (left): 7% slower than TC 0.75 0.75 0.5 0.5 Intra-Workgroup Sharing (right): 3% slower than TC 0.25 0.25 0.0 0.0 TC RCC TC RCC 11

Summary Main source of SC inefficiency : stalls for write permission acquisition. Resolve SC stalls with distributed logical clocks. RCC is 29% better than TC-SC, which is the best SC model so far. RCC shortens the performance gap between SC and the best RC within 7%. Questions? 12