Cache coloring

<h2 id="details-of-operations">Details of operations</h2>

<p>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.
</p><p>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.
</p>
<h2 id="implementations">Implementations</h2>
<p>This code adds a significant amount of complexity to the virtual memory allocation subsystem, but the result is well worth the effort.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> Page coloring makes virtual memory as deterministic as physical memory with regard to cache performance. Page coloring is employed in <a href="/facts/Operating_system/8XTuvMh2">operating systems</a> such as <a href="/facts/Solaris_(operating_system)/KPfT98EJ">Solaris</a>,<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> <a href="/facts/FreeBSD/RKsFTm7F">FreeBSD</a>,<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> <a href="/facts/NetBSD/PTm5HWls">NetBSD</a>,<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> and <a href="/facts/Windows_NT/EtccWvxQ">Windows NT</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>

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

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Matthew Dillon. "Page Coloring". Design elements of the FreeBSD VM system. FreeBSD Foundation. Retrieved 2007-01-13. <a href="/wiki/Matt_Dillon_(computer_scientist)" target="_blank">/wiki/Matt_Dillon_(computer_scientist)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"Solaris Operating System What's New". Solaris marketing material. Sun Microsystems, Inc. Retrieved 2007-01-13. <a href="http://www.sun.com/software/solaris/whats_new.jsp" target="_blank">http://www.sun.com/software/solaris/whats_new.jsp</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Matthew Dillon. "Page Coloring". Design elements of the FreeBSD VM system. FreeBSD Foundation. Retrieved 2007-01-13. <a href="/wiki/Matt_Dillon_(computer_scientist)" target="_blank">/wiki/Matt_Dillon_(computer_scientist)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Matt Thomas. "Improving NetBSD/mips" (PDF). Managing Page Colors. The NetBSD Foundation. Retrieved 2012-09-24. <a href="/w/index.php?title=Matt_Thomas_(computer_scientist)&action=edit&redlink=1" target="_blank">/w/index.php?title=Matt_Thomas_(computer_scientist)&action=edit&redlink=1</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Edouard Bugnion; Jennifer M. Anderson; Todd C. Mowry*; Mendel Rosenblum; Monica S. Lam. "Compiler Directed Page-Coloring for Multiprocessors". Stanford University. Retrieved 2009-10-06. <a href="http://suif.stanford.edu/papers/asplos96.ps" target="_blank">http://suif.stanford.edu/papers/asplos96.ps</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Cache coloring open-in-new

Cache coloring