Cache coloring

From Wikipedia, the free encyclopedia

In computer science, cache coloring (also known as page coloring) is the process of attempting to allocate free pages that are contiguous from the CPU cache's point of view, in order to maximize the total number of pages cached by the processor. Cache coloring is typically employed by low-level dynamic memory allocation code in the operating system, when mapping virtual memory to physical memory. A virtual memory subsystem that lacks cache coloring is less deterministic with regards to cache performance, as differences in page allocation from one program run to the next can lead to large differences in program performance.

Contents 1 Details of operations 2 Example 3 Implementations 4 Notes 5 References 6 External links

[edit] Details of operations

This section requires expansion.

[edit] Example

For example, if page 10 of physical memory is assigned to page 0 of a process' virtual memory and the cache can hold 5 pages, the page coloring code will not assign page 15 of physical memory to page 1 of a process's virtual memory. It would, instead, assign page 16 of physical memory. The page coloring code attempts to avoid assigning page 15 because this maps over the same cache memory as page 10 and would result in non-optimal caching.

[edit] Implementations

This code adds a significant amount of complexity to the virtual memory allocation subsystem, but the result is well worth the effort.^[1] Page coloring makes virtual memory as deterministic as physical memory in regard to cache performance. Page coloring is employed in operating systems such as Solaris^[2], FreeBSD^[1] and Windows NT^[3]

[edit] Notes

[edit] References

[edit] External links

• "Page Placement Algorithms for Large Real-Indexed Caches," by R. E. Kessler, Mark D. Hill, University of Wisconsin, 1992.
• "Colorable Memory," by Jochen Liedtke, IBM T. J. Watson Center, Nov. 1996. Postscript document here.