Alleviating Memory Contention in Matrix Computations on Large-Scale Shared-Memory Multiprocessors
Ricardo Bianchini, Mark E. Crovella, Leonidas I. Kontothanassis, Thomas J. LeBlanc · Defense Technical Information Center (DTIC) · 1993
Memory contention can be a major source of overhead in large-scale shared-memory multiprocessors. There are many hardware solutions, but they are often complex and expensive, so software solutions are an attractive alternative. This paper evaluates one solution, block-column allocation, which is very effective at reducing memory contention for a large class of SPMD (single-Program-Multiple-Data) programs, and can be implemented easily by the compiler. We first quantify the impact of memory contention on performance by simulating the execution of several application kernels on a large-scale multiprocessor. Our simulation results confirm that memory contention is widespread on large-scale machines; our applications suggest that contention is usually caused by synchronized access to a range of addresses (rather than to a single address). We show that block-column allocation can nearly eliminate this source of memory contention. As our main contribution, we compare block-column allocation to row-major allocation and logarithmic broadcasting. Our analysis demonstrates the clear superiority of block-column allocation over row-major allocation in the presence of memory contention