Memory Assignment for Multiprocessor Caches Through Graph Coloring

Abstract

It has become apparent that the achieved performance of multiprocessors is heavily dependent upon the quality of the availabel compilers. In this paper we are concerned with compile-time techniques that can be used to achieve better performance by improving cache utilization. Specifically, we investigate the problem of assigning data chunks to memory in a way that will minimize collisions in direct-mapped multiprocessor caches. We show that while this problem is computationally intractable, there are interesting special cases that can be solved in polynomial time. We also present several techniques that can be used when conflict-free assignment is not possible, or when finding a conflict-free assignment is computationally infeasible. These techniques include uniform decaching, which involves not caching specific data blocks, and data replication, which involves making multiple copies of read-only data. Finally, we present a memory assigment technique, grey coloring, that reduces latency in the presence of collisions by distributing cache misses among processors in a way that minimized the total number of cache misses in any specific cache.