Cache coloring

Cache coloring

In computer science, cache coloring (also known as page coloring) is the process of attempt 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.

Details of operations

Example

For example, if page 10 of physical memory is assigned to page 0 of a process' virtual memory 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 21 of physical memory. The page coloring code attempts to avoid assigning page 15 because this maps over the same cache memory as page 10 and would result in non-optimal caching.

Implementations

This code adds a significant amount of complexity to the virtual memory allocation subsystem, but the result is well worth the effort.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
] 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 [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.
] , FreeBSDcite 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
] and NetBSD.

Notes

References

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 [http://i30www.ira.uka.de/aboutus/inmemoriam/liedtke/index.php?lid=en Jochen Liedtke] , IBM T. J. Watson Center, Nov. 1996. Postscript document [http://i30www.ira.uka.de/research/documents/l4ka/1996/colmem.ps here] .


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Cache — This article is about the computer science optimization concept. For other uses, see Cache (disambiguation). In computer engineering, a cache (  /ˈk …   Wikipedia

  • CPU cache — Cache memory redirects here. For the general use, see 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… …   Wikipedia

  • Практическое применение раскраски графов — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Раскраска графов практически применяется (постановку задачи различиных раскрасок здесь обсуждаться не будет) дл …   Википедия

  • Compiler optimization — is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the… …   Wikipedia

  • Ruth Heller — (1923–2004) was a children s author and graphic artist known for her use of bright color and detail in both geometric design and the representation of creatures,plants, patterns, and puzzles. She worked primarily with a combination of colored… …   Wikipedia

  • Rodolfo Valentin — Infobox Person name = Rodolfo Valentin residence = New York City other names = |right|thumb imagesize = 200px caption = Rodolfo Valentin in action birth date = birth date and age|1944|06|22 birth place = flagicon|ARGBuenos Aires, Argentina death… …   Wikipedia

  • Distributed computing — is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal …   Wikipedia

  • Drap de Lirey — Suaire de Turin Négatif du visage du linceul de Turin, 1898 Le suaire de Turin aussi désigné linceul de Turin est un drap en lin ancien qui montre l image d un homme présentant les traces de tortures physiques correspondant à un crucifiement. Il… …   Wikipédia en Français

  • Face du Christ — Suaire de Turin Négatif du visage du linceul de Turin, 1898 Le suaire de Turin aussi désigné linceul de Turin est un drap en lin ancien qui montre l image d un homme présentant les traces de tortures physiques correspondant à un crucifiement. Il… …   Wikipédia en Français

  • Linceul de Turin — Suaire de Turin Négatif du visage du linceul de Turin, 1898 Le suaire de Turin aussi désigné linceul de Turin est un drap en lin ancien qui montre l image d un homme présentant les traces de tortures physiques correspondant à un crucifiement. Il… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”