Fair caching in a chip multiprocessor architecture

This paper presents a detailed study of fairness in cache sharing between threads in a chip multiprocessor (CMP) architecture. Prior work in CMP architectures has only studied throughput optimization techniques for a shared cache. The issue of fair-ness in cache sharing, and its relation to throughput, has not been studied. Fairness is a critical issue because the Oper-ating System (OS) thread scheduler’s effectiveness depends on the hardware to provide fair cache sharing to co-scheduled threads. Without such hardware, serious problems, such as thread starvation and priority inversion, can arise and render the OS scheduler ineffective. This paper makes several contributions. First, it proposes and evaluates five cache fairness metrics that measure the degree of fairness in cache sharing, and shows that two of them corre-late very strongly with the execution-time fairness. Execution-time fairness is defined as how uniform the execution times of co-scheduled threads are changed, where each change is rel-ative to the execution time of the same thread running alone. Secondly, using the metrics, the paper proposes a dynamic L2 cache partitioning algorithm that optimizes fairness. The dy-namic partitioning algorithm is easy to implement, requires lit-tle or no profiling, has low overhead, and does not restrict the cache replacement algorithm to LRU. Finally, this paper stud-ies the relationship between fairness and throughput in detail. We found that optimizing fairness usually increases throughput, while maximizing throughput does not necessarily improve fair-ness. Using a set of co-scheduled pairs of benchmarks, on aver-age our algorithm improves fairness by a factor of 4 , while in-creasing the throughput by 15%, compared to a non-partitioned shared cache. 1