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 regard 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

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.[1] Page coloring makes virtual memory as deterministic as physical memory with regard to cache performance. Page coloring is employed in operating systems such as Solaris,[2] FreeBSD,[1] NetBSD,[3] and Windows NT.[4]

References

  1. ^ a b Matthew Dillon. "Page Coloring". Design elements of the FreeBSD VM system. FreeBSD Foundation. Retrieved 2007-02-02.
  2. ^ "Solaris Operating System What's New". Solaris marketing material. Sun Microsystems, Inc. Retrieved 2007-01-13.
  3. ^ Matt Thomas. "Improving NetBSD/mips" (PDF). Managing Page Colors. The NetBSD Foundation. Retrieved 2012-09-24.
  4. ^ 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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.