Re: How to determine the L2 cache size on non-AMD CPUs (automatic page queue color tuning)?

On Wed, Jun 16, 2004, Alexander Leidinger wrote:
> I'm working with Alan and Chad David on automatic tuning of the number
> of colors for the page queue. For AMD CPUs (including amd64, but not
> tested) we already have code in identcpu.c to determine the size of the
> L2 cache and its associativity.

I instrumented the page coloring code a while ago, and found that
it actually didn't work as effectively as it was supposed to.  For
instance, when there are 256 colors, the `incr' used in
_vm_object_allocate() is not relatively prime to the number of
colors, so a given vm_object only gets 1/4 of the colors it
should.

Nevertheless, fixing that problem resulted in a performance
increase that I was barely able to measure.  Associativity and
victim caching virtually eliminate the benefits of page coloring
on modern architectures.

Moreover, there's an easier way to do page coloring that will work
on every architecture without you having to figure out the
appropriate number of colors!  Specifically, you pick a fixed
number of bins N that's as big as the widest cache you intend to
support, and do the coloring hierarchically.  If you search the
bins in the right order, you get a coloring that's optimal for
caches of size N, but also for caches of size N/2, N/4, etc.  The
great things about this technique are that it's fast for
reasonably-sized N, it is cache size independent, and it requires
only minor changes to _vm_pageq_find().

See the following paper:

	http://citeseer.ist.psu.edu/kessler92page.html