Locality and False Sharing in Coherent-Cache Parallel Graph Reduction

Abstract. Parallel graph reduction is a model for parallel program exe-cution in which shared-memory is used under a strict access regime with single assignment and blocking reads. We outline the design of an e-cient and accurate multiprocessor simulation scheme and the results of a simulation study of the performance of a suite of benchmark programs operating under a cache coherency protocol that is representative of pro-tocols used in commercial shared-memory machines and in more scalable distributed shared-memory systems. We analyse the in uence of cache line size on performance and expose the relative contributions of spatial, temporal and processor locality and false sharing to overall performance.