1999-02-01 09:28:04

by Sebastien Gignoux

[permalink] [raw]
Subject: Page coloring (found a PhD Dissertation)

I have found a Dissertation (supervised by M.J. Flynn) who study page coloring.
It looks interesting (I have not read it yet) and with detailed results.

You can download (PS file) it at: http://umunhum.stanford.edu/phds.html ("The
Interaction of Virtual Memory and Cache Memory.")

Reference and abstract bellow.

I hope it could help.


The Interaction of Virtual Memory and Cache Memory
by William L. Lynch

October 1993
Computer Systems Laboratory
Departments of Electrical Engineering and Computer Science
Stanford University

Abstract :
This dissertation concerns itself with the interactions of unified-,
instruction-, and data-cache memory, and
virtual memory: specifically, the interactions caused by the continued trends
increasing the cache size and
decreasing the cache associativity, resulting in the indexing of caches with
physical page number bits.
Caches indexed with physical page-number bits possess two problems. First, the
cache miss rate varies
between runs, as data location in the cache depends on the placement of virtual
pages in physical memory.
Secondly, the virtual-to-physical address translation must precede cache
indexing, increasing latency.
Controlling (coloring) page allocation eliminates the inter-run variation and
improves the mean miss rate.
Simulation results provide distribution of miss rates caused by conventional
page allocation for a variety of
cache organizations and size, and several page sizes.
Several page coloring heuristics demonstrate a reduction in the variation of
miss rate, including a strict page
coloring algorithm which also allows cache indexing to precede address
This strict page allocation partitions physical memory, and thus may increase
the page fault rate. Simulations
show that this change in page fault rate is small for a range of memory sizes
and degrees of partitioning.

Key Words and Phrases: Page Coloring, Virtual Memory, Direct-Mapped Caches