Alleviating Memory Contention in Matrix Computations on Large-Scale Shared-Memory Multiprocessors.

摘要

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.