Using compile-time analysis and transformations to reduce false sharing on shared-memory multiprocessors
Tor Jeremiassen · 1996
On bus-based, shared-memory multiprocessors, much of the unnecessary bus traffic, i.e., that which could be eliminated with better processor locality, is coherency overhead caused by false sharing. False sharing occurs when multiple processors access (both read and write) different words in the same cache block. False sharing is caused by a mismatch between the memory layout of write-shared data and the cross-processor memory reference pattern to it. By changing the way shared data is laid out in memory to better conform to the memory reference pattern, false sharing can be eliminated. However, changing the data layout may have a negative impact on spatial locality that outweighs the gain in processor locality. Therefore, it is important to carefully balance the tradeoff between processor and spatial locality so as to maximize program performance. This dissertation presents a compiler-directed approach to eliminating false sharing. A series of compiler algorithms and a suite of shared data transformations were developed and incorporated into a source-to-source restructurer. The algorithms analyze explicitly parallel programs; they produce information about each processor's memory reference patterns that identifies data structures susceptible to false sharing, decide whether transforming them will pay off and then choose appropriate transformations. The algorithms are evaluated on the accuracy of their analysis, as well as their run-time cost. The effectiveness of the compiler-directed approach is evaluated on a set of ten explicitly parallel programs. Trace driven simulation shows that the compile-time analysis successfully identifies the data structures responsible for most false sharing misses, and makes appropriate tradeoffs between eliminating false sharing and reducing spatial locality. The reduction in false sharing misses positively impacts both execution time and program scalability when executed on a KSR 2. Both factors combine to increase the maximum achievable speedup for all programs, more than doubling it for several. Despite being able to only approximate actual inter-processor memory accesses, the compiler-directed transformations outperformed programmer efforts to eliminate false sharing in these programs.