What problem does cache coloring solve?

Problem Detail: 

According to what I have read from two different sources, cache coloring is (was?) required in order to:

• Counter the problem of aliasing: Prevent two different virtual addresses with the same physical address from mapping to different cache sets. (According to a CS Stack Exchange Answer)

• Exploit the spatial locality property of virtual memory: by guaranteeing that two adjacent blocks of virtual memory (not necessarily adjacent in physical memory), do not map to the same cache index. (According to Wikipedia)

These seem to me to be fundamentally different definitions, and without comprehending the motivation for cache coloring, I can't seem to understand the mechanism for selecting the number of colors required. Are they really one and the same?

If the spatial locality of virtual memory is the primary motivation, is cache coloring really required for VIPT caches, where the index of the cache is derived from the virtual memory to begin with? Or is cache coloring simply used in VIPT caches to get around aliasing?

Asked By : peteykun

Answered By : Paul A. Clayton

Both avoiding aliases and avoiding excessive cache conflicts are valid reasons for using page coloring. Requiring page coloring to avoid aliases is unpopular because it places a mandatory constraint on page allocation. In general, modern non-embedded processors do not require page coloring to avoid aliasing.

Avoiding aliasing issues in hardware increases hardware complexity, so earlier processors (and perhaps some more recent embedded processors) chose to place the burden on software. Hardware can avoid aliasing issues in a cache with more index+offset bits than bits in the page offset by (for example):

• checking alternate sets on a cache miss (as done by AMD's Athlon; when an alias was detected the block was moved to the current virtual index)
• including the virtual address bits used for indexing L1 in a (tag) inclusive L2 (on an L1 miss and L2 hit, if the virtual address bits match the corresponding bits for the request, no action is necessary; if the bits do not match, the appropriate set to probe is known [whether the block is also in L1 could also be stored in the L2 tags to reduce coherence overhead, so some probes might be avoided])
• using set prediction to guess the extra physical address bits used for indexing (a misprediction would be discovered after TLB access and corrected)
• using reverse translation (physical to virtual) on a cache miss to find possible aliases (I think a PA-RISC implementation used reverse translation for coherence)

Using page coloring to reduce conflicts (for caches with simple modulo a power of two indexing) is less unpopular because the page coloring is not required for correctness. If a particular color becomes scarce, a page can be mis-colored with only a possible reduction in performance. This rationale for page coloring also means that the number of bits colored is less constrained. The (less practical) ideal may be to match all physical index bits for the last level cache with the corresponding virtual address bits, but even coloring just four bits can substantially reduce conflict issues.

It might be worth noting that coloring for alias avoidance need not match virtual address bits with physical address bits. As long as all potential aliases share the same virtual address bits used for indexing, alias issues are avoided. However, matching physical and virtual address bits may be convenient (and provide predictable conflict in physically addressed levels of cache).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32294