Principled Design of Indexing Functions for Memory Coloring

On shared multi-core CPUs, memory coloring achieves microarchitectural isolation by partitioning resources between trust domains. Previous work has shown that memory coloring can, in principle, be used to isolate multiple components simultaneously, e.g., both the last-level (L3) cache and DRAM. The number of colors obtained by these methods depends on the algebraic properties of the indexing functions, though, and today's off-the-shelf CPU designs are often not suited for multi-component memory coloring.

We develop algorithms to automatically synthesize indexing functions that guarantee a minimum number of colors. Given a set of typical workloads and some context on the CPU design, our algorithms compute a new linear indexing function that supports the requested number of colors while maximizing the performance on the workloads. Our approach is based on the observation that the number of colors depends on the overlap of the algebraic kernels of the involved indexing functions. Building on this observation, we translate the requirements that the CPU design imposes on the function into algebraic constraints that our algorithms enforce.

In a case study on a 16-core server-class CPU, we show that our framework yields a coloring scheme that partitions the L3 cache and DRAM banks, increasing the number of colors from 1 to 16 while incurring less than 2.5% performance overhead, on average across SPEC and PARSEC benchmarks.