Cache Model
- Each thread has its own cache.
- Caches are divided in cache lines (of some constant size). A field at memory address a1 and another field at address a2 are in the same cache line if a1 = a2 (mod C) where C is the cache line size in bytes.
- A cache line is updated only when accessed and only if there is a need to update it (some other thread has modified the cache line since it was last accessed by the current thread).
- The total cache size is infinite. That is, after the first access to data on a cache line, there is always a (possibly outdated) copy of it in the thread's cache.
Notation
The notation OP(t,f,c) is defined to be the OP operation, performed by thread t on a field f which lies in cache line c. OP can be R (read), W (write) or A (access; read or write). A star (*) replacing any of t, f or c means any thread, field or cache line, respectively.
Unless otherwise noted, different names represent distinct elements. For example, W(t1,*,*) and W(t2,*,*) respectively represent a write by thread t1 and a write by thread t2, where t1 and t2 are distinct threads. Conversely, if two names are the same, they refer to the same element (thread, field or cache line).
True Sharing
Let r = R(t1,f,c) and consider the most recent W(t2,f,c) that happened before r (call it w). w is considered truly shared if there is no W(t1,f,c) between it and r.
False Sharing
- Let a = A(t1,f1,c) and consider the most recent W(t2,f2,c) that happened before a and is not truly shared (call it w). w is considered falsely shared if none of the following happen between a and w:
- Let w1 = W(t1,f,c) and consider the most recent W(t2,f,c) that happened before w1 and is not truly shared (call it w2). w2 is considered falsely shared if no R(*,f,c) (except R(t2,f,c)) happened between w1 and w2.
- Let w1 = W(t1,f,c) and consider the most recent W(t2,f,c) that happened before w1 and is not truly shared (call it w2). w2 is considered falsely shared if at least one R(t,f,c) (where t != t1) and no A(t1,*,c) happen between w1 and w2.