``MESA: Reducing cache conflicts by integrating static and run-time methods" 

Xiaoning Ding, Dimitrios S. Nikolopoulos, Song Jiang, and Xiaodong Zhang

Proceedings of International Symposium on Performance Analysis of Systems and 
Software (ISPASS-2006), Austin, Texas, March 19-21, 2006.   


Abstract

The paper proposes MESA (Multicoloring with Embedded
Skewed Associativity), a novel cache indexing scheme that
integrates dynamic page coloring with static skewed associativity
to reduce conflicts in L2/L3 caches with a small degree
of associativity. MESA associates multiple cache pages
(colors) with each virtual memory page and uses two-level
skewed associativity, first to map a page to a different color
in each bank of the cache, and then to disperse the lines of
a page across the banks and within the colors of the page.
MESA is a multi-grained cache indexing scheme that combines
the best of two worlds, page coloring and skewed associativity.
We also propose a novel cache management scheme
based on page remapping, which uses cache miss imbalance
between colors in each bank as the metric to track conflicts
and trigger remapping. We evaluate MESA using 24 benchmarks
from multiple application domains and with various
degrees of sensitivity to conflict misses, on both an in-order
issue processor (using complete system simulation) and an
out-of-order issue processor (using SimpleScalar). MESA
outperforms skewed associativity, prime modulo hashing,
and dynamic page coloring schemes proposed earlier. Compared
to a 4-way associative cache, MESA can provide as
much as 76% improvement in IPC.
 

Back to the HPCS Main Page at the Ohio State University.