Re: performance measurement and caches

Hans Boehm (boehm@parc.xerox.com) wrote:
: ... Apparently the L2 cache is physically indexed, and direct
: mapped. The executable files were read once and loaded into the file
: system cache. Thus their location in physical memory did not change
: across runs. (The performance did change when I repeated the test a
: day later.) Apparently slowtest was loaded in an unfortunate
: position, so that two very frequently accessed code sections collided
: in the cache. The only way to remedy the situation was to flush the
: file system cache.
: ...
: Do we need the "shuffle physical memory" OS call?


What you'd like is to have the operating system to shuffle physical
memory for you, automatically. Given some feedback about the location
of cache misses, the OS can change virtual->physical page mappings to
resolve cache conflicts in a physically-indexed, direct mapped cache.
The one-time cost to shuffle the pages and remap is high, but the
resulting reduction in cache misses results in a net improvement in
performance.


There is a nice paper by Kessler and Hill in TOCS discussing the
interaction between mapping policies and cache performance that
presents several static page mapping policies (page coloring, bin
hopping). More recently, we did some work on dynamic page mapping
policies. Your program is exactly the "strawman" test case we used to
motivate remapping pages at runtime, but larger programs can benefit
from cache conflict detection and resolution as well.


Ted


Shameless self-promotion goes here:


Romer, Lee, Bershad, and Chen, "Dynamic Page Mapping Policies for Cache
Conflict Resolution on Standard Hardware", OSDI 1994, pp. 255-266.
ftp://ftp.cs.washington.edu/homes/romer/scml.paper.ps


Bershad, Lee, Romer, and Chen, "Avoiding Conflict Misses Dynamically
in Large Direct-Mapped Caches," ASPLOS VI, pp. 158-170.
http://www.cs.washington.edu/homes/bershad/paper-cml.ps


R. Kessler and M. D. Hill, "Page Placement Algorithms for Large
Real-Indexed Caches," ACM Transactions on Computer Systems, vol. 10,
pp. 338-359, November 1992.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.