Cache coloring
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 |
[edit] Details of operations
Cache is designed so addresses in continuous memory block take different position at the cache, but it's not the story when it comes to virtual memory; when logically continuous but not physically continuous memory allocated, addresses can take the same position. Coloring solve this problem by selecting pages which do not contend with neighbor pages when initializing or manipulating page tables.
Physical memory pages are "colored" so that pages with different "colors" have different positions in CPU cache memory. When allocating sequential pages in virtual memory for processes, the kernel collects pages with different "colors" and map them to the virtual memory. In this way, sequential pages in virtual memory do not contend for the same cache line.
[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
- ^ a b Matthew Dillon. "Page Coloring". Design elements of the FreeBSD VM system. FreeBSD Foundation. http://www.freebsd.org/doc/en_US.ISO8859-1/articles/vm-design/page-coloring-optimizations.html. Retrieved 2007-01-13.
- ^ "Solaris Operating System What's New". Solaris marketing material. Sun Microsystems, Inc.. http://www.sun.com/software/solaris/whats_new.jsp. Retrieved 2007-01-13.
- ^ Edouard Bugnion, Jennifer M. Anderson, Todd C. Mowry*, Mendel Rosenblum and Monica S. Lam. "Compiler Directed Page-Coloring for Multiprocessors". Stanford University. http://suif.stanford.edu/papers/asplos96.ps. Retrieved 2009-10-06.
[edit] References
 |
This section is empty. You can help by adding to it. |
[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.
