lkml.org 
[lkml]   [1999]   [Jan]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: your mail

I'm certainly interested... and I agree.. the 'inc' approach is great
for simplicity... the 'bitmap' approach is great for efficiency... And
I'll certainly find time to do this and give you the code...

And I'd like to see which approach works best... but note, I want to do
this without the ioctl approach because that seems like a kludge. A
program can't set 'coloring' for itself because it is already partially
loaded before it gets to do that. And it would seem that if the bitmap
approach can be done efficiently, perhaps this can be turned on for
everyone.

IE the time-consuming part is when the bitmap gets nearly full. We might
want to say 90% of the bits set is enough.. clear and start over, which
means we at least use 90% of cache before aliasing hits. Lots of options
including maybe when the cpu is going to 'halt' maybe we can do something
with the pt list to make this more efficient. IE it might be nice to
do like normal unix does for its file cache, and have the 'alias bits'
index into 128 pte lists, where the pte's are put into the list where they
belong... then we can have a new pte allocator that goes right to the
right list to give the optimal pte... no searching, _no_ efficiency
issues at all there, so the ioctl might not be needed...


Robert Hyatt Computer and Information Sciences
hyatt@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

On Sun, 31 Jan 1999, Richard Gooch wrote:

> Robert M. Hyatt writes:
> >
> > Apologies if I am going back over old stuff... but I've thought about
> > the page coloring idea and have some comments:
>
> This is exactly one of the things I was hoping for when I put out my
> patch: to stir discussions about efficient page colouring algorithms.
>
> > First, a definition, since I don't have a good term to use... 'alias
> > index'. I am defining this as the cache-size / page-size... this
> > gives me the number of pages that fit into cache at one time. And
> > when you think about the aliasing problem, the page numbers you
> > allocate to a process (assuming his program completely fits into
> > cache) have to be different in the low order bits (low order bits =
> > log2(alias number).
>
> DaveM and I just called that NUM_COLOURS.
>
> > For my xeon, cache=512K. I assume page-size=4k, but if that is wrong,
> > just plug in the right number. So the 'alias index' == 128 (512K/4K).
> >
> > This means that when I allocate pages, assuming my program is _exactly_
> > 128 pages (512K) long, the physical pages I want to allocate must be
> > different in the low order 7 bits. Which means every physical page
> > will map to a different group of lines in cache, exactly what I want.
>
> That low 7 bits is what we're calling the colour.
>
> > I see two (at least) ways to do this:
> >
> > I believe what Richard is doing is to allocate the first page, then
> > try to find the next page in ascending sequence (hopefully in the
> > alias index bits only but I didn't look at his code carefully).
>
> I alllocate in ascending colour numbers (aka. alias index bits). This
> number rolls over at NUM_COLOURS. You can see where I do the test:
> if (goal++ >= NUM_COLOURS) goal = 0;
> where goal is the current colour.
>
> > This works, but I don't like the inefficiency since small programs
> > still get stuck into adjacent cache 'pages' and that isn't
> > necessary.
>
> I agree it's inefficient. I'm unsure whether the ascending colours
> requirement is necessary or not.
>
> > way 2 is cuter: create a 128 bit 'map'. Allocate a page for the
> > program and set the 'alias index bit' for that page in this map.
> > when the next page is requested, call the code to return a free pte,
> > and all that is needed is to extract the 'alias index' from the page
> > number and check that bit in the 'map'. If set, this page
> > 'collides' and should be 'returned'. If it doesn't, we are done.
> > We keep doing this until the map gets pretty full where efficiency
> > drops to the same level as what Richard is doing in his patch, but
> > note that for small programs, this isn't inefficient at all, which
> > has to be a goal if this becomes a standard part of the MM code.
>
> This is an interesting approach. I think it's definately worth
> trying. Are you planning on implementing this? I think it would be
> worthwhile to do so and preserve both coloured page allocation schemes
> so lots of people can compare them (using an ioctl() to chose on a per
> process basis). If I receive such a patch I'll be happy to include it
> in my patch.
>
> The one concern I have about this (probably because I'm too lazy to
> think hard about the implications), is what happens if you allocate
> far more than the cache size (in my case, a dataset of ~13
> MBytes) and you access that dataset in some fashion (say for(y) for(x)
> for(z) where x is contiguous in memory).
>
> Obviously, once you've filled the bitmap, you clear it again and
> esentially start "fresh" for the next set of allocations. What I'm
> wondering is whether the bitmap scheme could result in page
> allocations which are less favourable for the access pattern I
> mentioned above.
>
> > problems:
> >
> > cache size affects the size of the collision map. For a 2M cache
> > xeon, we need 512 bits rather than 128. Not exactly bad, but maybe
> > Linux might not want to see that added to _every_ proc struct.
>
> I shouldn't worry about that for the moment. You would only need to
> allocate the bitmap for each process that turns on page colouring.
> And anyway, 64 bytes is trivial.
>
> > this sure becomes 'architecture' dependent, but we _could_ assume
> > that cache is 4M (1024 bits which is still not real big (32 words)
> > and we could allocate based on that, which would work great for
> > caches 4M or smaller, and now this code doesn't have to know if you
> > have 512 or 1024 or whatever. There is a minor performance hit,
> > since we would be 'working hard' to do really optimal mapping for
> > smaller cache machines, but it would work quite well... And the +
> > for using a 1024 bit alias map is that programs < 1024 pages would
> > 'map fast'. But this is not quite optimal for my 512K xeon, since I
> > could still map 4 physical pages to the same cache line if I assume
> > there is really 2M. Needs some thought, as in maybe a hybrid, where
> > we don't allow mapping to the high 3/4 of the alias map until the
> > lower 1/4 is nearly full. And we don't allow mapping to the high
> > 1/2 until the lower 1/2 is nearly full.
>
> I prefer the fully dynamic approach where you allocate the bitmap
> according to the cache size.
>
> > And note that once the map is full, or if a pass thru all available
> > pte's doesn't find a physical page that has the right 'alias bits'
> > set, we just clear the map and start over, assuming we have filled
> > the 'first page of coloring' as well as possible.
>
> Yep.
>
> > I'm really interested in playing with this now, but before I start,
> > any comments, suggestions, flaws, improvements, etc?
>
> Please go ahead and send me a patch. I'm happy to integrate it into my
> patch and distribute it if you like.
>
> Regards,
>
> Richard....
>


-
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/

\
 
 \ /
  Last update: 2005-03-22 13:50    [W:0.070 / U:0.368 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site