To: linux-kernel@vger.rutgers.edu Subject: Page coloring HOWTO [ans] From: lm@bitmover.com (Larry McVoy) Date: Sat, 30 Jan 1999 13:20:22 -0800 [ lots of stuff on how to do page coloring deleted ] I've seen how this was done twice, both at Sun and SGI. Here's what they do. This assumes a direct mapped level 2 cache, which is typical. It's different if it is set associative, how it is different is an exercise left for the reader. This alg will do two critical things: (a) make sure that each process maps the same virtual addresses to different locations in the cache, if possible. (b) make sure that a contiguous chunk of virtual address space in one process occupies a contiguous chunk of cache, if possible. The first thing you do is to take your page free list and turn it into a hash list, where the # of buckets in hash list is your cache size divided by page size. Then take each page, hash on physical address, stick it in the appropriate bucket. Page allocation becomes hash on virtual address and take a page from the bucket.However, here's the trick that fans them out in the cache, you hash on virtual address plus pid (I don't remember the exact details but you'll get it immeditately when you implement it - you just process 0 to take page 0 from bucket 0, process 1 to take page 0 from bucket 1, and so on). This works really well; Linus may object because it puts some logic in the alloc_page/free_page path that isn't there right now, so we should figure out how to measure that and see what it costs. I don't have a good feel for the page alloc/free rate under various loads, does anyone? The nice thing about this model, by the way, is that it makes the system much more deterministic in its performance. Some programs will go faster, some will go slower, but the nice thing is that unlike the current situation, you can figure out which programs go slower and shuffle their data around to make them go faster. Under the current model, you're screwed because you get different results each time you run and there isn't a damn thing you can do about it. The point is that we should *not* use the fact that some programs go slower to mean that page coloring is bad. Fix the programs. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/