Editing Cache coloring

{{Short description|Technique for increasing efficiency in computer memory allocation}}
In [[computer science]], '''cache coloring''' (also known as '''page coloring''') is the process of attempting to allocate free [[page (computer science)|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.

==Details of operations==
[[File:Page Cache Coloring.svg|thumb|450px|left|Illustration of cache coloring. Left is [[virtual memory]] spaces, center is the physical memory space, and right is the [[CPU cache]].]]
A physically indexed CPU cache is designed such that addresses in adjacent physical memory blocks take different positions ("cache lines") in the cache, but this is not the case when it comes to virtual memory; when virtually adjacent but not physically adjacent memory blocks are allocated, they could potentially both take the same position in the cache. Coloring is a technique implemented in memory management software, which solves this problem by selecting pages that do not contend with neighbor pages.

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 maps them to the virtual memory. In this way, sequential pages in virtual memory do not contend for the same cache line.

==Implementations==
This code adds a significant amount of complexity to the virtual memory allocation subsystem, but the result is well worth the effort.<ref name="freebsd.org">{{cite web
| url = http://www.freebsd.org/doc/en_US.ISO8859-1/articles/vm-design/page-coloring-optimizations.html
| title = Page Coloring
| accessdate = 2007-01-13
| author = Matthew Dillon
| authorlink = Matt Dillon (computer scientist)
| work = Design elements of the FreeBSD VM system
| publisher = FreeBSD Foundation
}}</ref> Page coloring makes virtual memory as deterministic as physical memory with regard to cache performance. Page coloring is employed in [[operating system]]s such as [[Solaris (operating system)|Solaris]],<ref>{{cite web
| url = http://www.sun.com/software/solaris/whats_new.jsp
| title = Solaris Operating System What's New
| accessdate = 2007-01-13
| work = Solaris marketing material
| publisher = Sun Microsystems, Inc.
}}</ref> [[FreeBSD]],<ref name="freebsd.org"/> [[NetBSD]],<ref name="netbsd.org">
{{cite web
| url = http://www.netbsd.org/~matt/bsdcan2012.pdf
| title = Improving NetBSD/mips
| accessdate = 2012-09-24
| author = Matt Thomas
| authorlink = Matt Thomas (computer scientist)
| work = Managing Page Colors
| publisher = The NetBSD Foundation
}}</ref> and [[Windows NT]].<ref name="stanford.edu">{{cite web
| url = http://suif.stanford.edu/papers/asplos96.ps
| title = Compiler Directed Page-Coloring for Multiprocessors
| accessdate = 2009-10-06
|author1=Edouard Bugnion |author2=Jennifer M. Anderson |author3=Todd C. Mowry* |author4=Mendel Rosenblum |author5=Monica S. Lam | publisher = Stanford University
}}</ref>

==References==
{{reflist|2}}

== External links ==

*"[http://citeseer.ist.psu.edu/kessler92page.html Page Placement Algorithms for Large Real-Indexed Caches]," by  R. E. Kessler, Mark D. Hill, University of Wisconsin, 1992.
*"[http://citeseer.ist.psu.edu/419609.html Colorable Memory]," by [https://archive.today/20041212160309/http://i30www.ira.uka.de/aboutus/inmemoriam/liedtke/index.php?lid=en Jochen Liedtke], IBM T. J. Watson Center, Nov. 1996.
*"[http://blog.csdn.net/maray/article/details/3599845 缓存着色技术]," by  Maray, CSDN Technological Blog, 2008.

{{DEFAULTSORT:Cache Coloring}}
[[Category:Cache (computing)]]