Cache coloring
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.
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. In this way, sequential pages in virtual memory do not contend for the same cache line.
s such as Solaris
, FreeBSD
, and Windows NT
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, cache coloring (also known as page coloring) is the process of attempting to allocate free pages that are contiguous from the CPU cache
CPU cache
A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations...
'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
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
, when mapping virtual memory
Virtual memory
In computing, virtual memory is a memory management technique developed for multitasking kernels. This technique virtualizes a computer architecture's various forms of computer data storage , allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which...
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.
Example
For example, if page 10 of physical memory is assigned to page 0 of a process' virtual memoryVirtual memory
In computing, virtual memory is a memory management technique developed for multitasking kernels. This technique virtualizes a computer architecture's various forms of computer data storage , allowing a program to be designed as though there is only one kind of memory, "virtual" memory, which...
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. 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. Page coloring makes virtual memory as deterministic as physical memory in regard to cache performance. Page coloring is employed in operating systemOperating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
s such as Solaris
Solaris Operating System
Solaris is a Unix operating system originally developed by Sun Microsystems. It superseded their earlier SunOS in 1993. Oracle Solaris, as it is now known, has been owned by Oracle Corporation since Oracle's acquisition of Sun in January 2010....
, FreeBSD
FreeBSD
FreeBSD is a free Unix-like operating system descended from AT&T UNIX via BSD UNIX. Although for legal reasons FreeBSD cannot be called “UNIX”, as the direct descendant of BSD UNIX , FreeBSD’s internals and system APIs are UNIX-compliant...
, and Windows NT
Windows NT
Windows NT is a family of operating systems produced by Microsoft, the first version of which was released in July 1993. It was a powerful high-level-language-based, processor-independent, multiprocessing, multiuser operating system with features comparable to Unix. It was intended to complement...
.
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.