Memory Assignment for Multiprocessor Caches through Grey Coloring

The achieved performance of multiprocessors is heavily dependent on the performance of their caches. Cache performance is severely degraded when data tiles used by a program conflict in the caches. This paper explores techniques for improving multiprocessor performance by improving cache utilization. Specifically, we investigate the problem of statically assigning data tiles to memory in a way that minimizes the impact of collisions in multiprocessor caches. We define the problem precisely and present an efficient procedure for finding solutions to it. The procedure incorporates a new technique, grey coloring, that reduces the maximum number of conflicts in any cache in the system by distributing cache misses evenly among processors. Keywords: multiprocessor design issues, cache organization, compilers, cache coherence, direct-mapped caches, data partitioning, graph-coloring. 1 Introduction Multiprocessors that support a shared-memory programming model provide the abstraction of a si..