Cache matching: thread scheduling to maximize data reuse
Wei Zhang, Fang Cherry Liu, Rui Xiang Fan · High Performance Computing Symposium · 2014
Datacenters today often execute multiple data-intensive threads concurrently. To improve the latency of threads accessing slow external storage, data is often cached in memory. The way in which the cache is shared between concurrent threads has a significant impact on overall system performance. Two widely used methods are processing thread requests on a first-come first-serve (FCFS) basis, and partitioning the cache and assigning each thread its own cache region. In some types of applications, certain data may be read by multiple threads. Neither FCFS nor cache partitioning effectively captures this type of inter-thread data locality. To show this, we first prove that cache partitioning leads to an O(m1/2−e) times lower hit rate compared to not partitioning when processing m threads issuing random read requests, where e > 0 is an arbitrarily small constant. We then propose the Cache Matching (CM) algorithm which captures data locality both within threads and across multiple threads. The algorithm uses a small buffer to store parts of the incoming request sequences, then interleaves these into a single sequence that has a high cache hit rate. We compare CM against FCFS and uniform cache partitioning on a variety of synthetic workloads capturing different data characteristics such as item popularity, temporal locality, and data size. For 16 threads, CM achieves on average 2.18x and 4.96x higher hit rate than the alternatives, and is up to 3.72x and 12.64x better on certain workloads.