* (no subject) @ 2003-01-24 5:08 ` Anoop J. 0 siblings, 0 replies; 16+ messages in thread From: Anoop J. @ 2003-01-24 5:08 UTC (permalink / raw) To: linux-kernel, linux-mm How does page coloring work. Iwant its mechanism not the implementation. I went through some pages of W.L.Lynch's paper on cache and VM. Still not able to grasp it . Thanks in advance ^ permalink raw reply [flat|nested] 16+ messages in thread
* (unknown), @ 2003-01-24 5:08 ` Anoop J. 0 siblings, 0 replies; 16+ messages in thread From: Anoop J. @ 2003-01-24 5:08 UTC (permalink / raw) To: linux-kernel, linux-mm How does page coloring work. Iwant its mechanism not the implementation. I went through some pages of W.L.Lynch's paper on cache and VM. Still not able to grasp it . Thanks in advance ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail 2003-01-24 5:08 ` (unknown), Anoop J. @ 2003-01-24 5:11 ` David Lang -1 siblings, 0 replies; 16+ messages in thread From: David Lang @ 2003-01-24 5:11 UTC (permalink / raw) To: Anoop J.; +Cc: linux-kernel, linux-mm The idea of page coloring is based on the fact that common implementations of caching can't put any page in memory in any line in the cache (such an implementation is possible, but is more expensive to do so is not commonly done) With this implementation it means that if your program happens to use memory that cannot be mapped to half of the cache lines then effectivly the CPU cache is half it's rated size for your program. the next time your program runs it may get a more favorable memory allocation and be able to use all of the cache and therefor run faster. Page coloring is an attampt to take this into account when allocating memory to programs so that every program gets to use all of the cache. David Lang On Fri, 24 Jan 2003, Anoop J. wrote: > Date: Fri, 24 Jan 2003 10:38:03 +0530 (IST) > From: Anoop J. <cs99001@nitc.ac.in> > To: linux-kernel@vger.kernel.org, linux-mm@kvack.org > > > How does page coloring work. Iwant its mechanism not the implementation. > I went through some pages of W.L.Lynch's paper on cache and VM. Still not > able to grasp it . > > > Thanks in advance > > > > - > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > Please read the FAQ at http://www.tux.org/lkml/ > ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail @ 2003-01-24 5:11 ` David Lang 0 siblings, 0 replies; 16+ messages in thread From: David Lang @ 2003-01-24 5:11 UTC (permalink / raw) To: Anoop J.; +Cc: linux-kernel, linux-mm The idea of page coloring is based on the fact that common implementations of caching can't put any page in memory in any line in the cache (such an implementation is possible, but is more expensive to do so is not commonly done) With this implementation it means that if your program happens to use memory that cannot be mapped to half of the cache lines then effectivly the CPU cache is half it's rated size for your program. the next time your program runs it may get a more favorable memory allocation and be able to use all of the cache and therefor run faster. Page coloring is an attampt to take this into account when allocating memory to programs so that every program gets to use all of the cache. David Lang On Fri, 24 Jan 2003, Anoop J. wrote: > Date: Fri, 24 Jan 2003 10:38:03 +0530 (IST) > From: Anoop J. <cs99001@nitc.ac.in> > To: linux-kernel@vger.kernel.org, linux-mm@kvack.org > > > How does page coloring work. Iwant its mechanism not the implementation. > I went through some pages of W.L.Lynch's paper on cache and VM. Still not > able to grasp it . > > > Thanks in advance > > > > - > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > Please read the FAQ at http://www.tux.org/lkml/ > -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail 2003-01-24 5:11 ` David Lang @ 2003-01-24 6:06 ` John Alvord -1 siblings, 0 replies; 16+ messages in thread From: John Alvord @ 2003-01-24 6:06 UTC (permalink / raw) To: David Lang; +Cc: Anoop J., linux-kernel, linux-mm The big challenge in Linux is that several serious attempts to add page coloring have foundered on the shoals of "no benefit found". It may be that the typical hardware Linux runs on just doesn't experience the problem very much. john On Thu, 23 Jan 2003 21:11:10 -0800 (PST), David Lang <david.lang@digitalinsight.com> wrote: >The idea of page coloring is based on the fact that common implementations >of caching can't put any page in memory in any line in the cache (such an >implementation is possible, but is more expensive to do so is not commonly >done) > >With this implementation it means that if your program happens to use >memory that cannot be mapped to half of the cache lines then effectivly >the CPU cache is half it's rated size for your program. the next time your >program runs it may get a more favorable memory allocation and be able to >use all of the cache and therefor run faster. > >Page coloring is an attampt to take this into account when allocating >memory to programs so that every program gets to use all of the cache. > >David Lang > > > On Fri, 24 Jan 2003, Anoop J. wrote: > >> Date: Fri, 24 Jan 2003 10:38:03 +0530 (IST) >> From: Anoop J. <cs99001@nitc.ac.in> >> To: linux-kernel@vger.kernel.org, linux-mm@kvack.org >> >> >> How does page coloring work. Iwant its mechanism not the implementation. >> I went through some pages of W.L.Lynch's paper on cache and VM. Still not >> able to grasp it . >> >> >> Thanks in advance >> >> >> >> - >> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in >> the body of a message to majordomo@vger.kernel.org >> More majordomo info at http://vger.kernel.org/majordomo-info.html >> Please read the FAQ at http://www.tux.org/lkml/ >> >- >To unsubscribe from this list: send the line "unsubscribe linux-kernel" in >the body of a message to majordomo@vger.kernel.org >More majordomo info at http://vger.kernel.org/majordomo-info.html >Please read the FAQ at http://www.tux.org/lkml/ ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail @ 2003-01-24 6:06 ` John Alvord 0 siblings, 0 replies; 16+ messages in thread From: John Alvord @ 2003-01-24 6:06 UTC (permalink / raw) To: David Lang; +Cc: Anoop J., linux-kernel, linux-mm The big challenge in Linux is that several serious attempts to add page coloring have foundered on the shoals of "no benefit found". It may be that the typical hardware Linux runs on just doesn't experience the problem very much. john On Thu, 23 Jan 2003 21:11:10 -0800 (PST), David Lang <david.lang@digitalinsight.com> wrote: >The idea of page coloring is based on the fact that common implementations >of caching can't put any page in memory in any line in the cache (such an >implementation is possible, but is more expensive to do so is not commonly >done) > >With this implementation it means that if your program happens to use >memory that cannot be mapped to half of the cache lines then effectivly >the CPU cache is half it's rated size for your program. the next time your >program runs it may get a more favorable memory allocation and be able to >use all of the cache and therefor run faster. > >Page coloring is an attampt to take this into account when allocating >memory to programs so that every program gets to use all of the cache. > >David Lang > > > On Fri, 24 Jan 2003, Anoop J. wrote: > >> Date: Fri, 24 Jan 2003 10:38:03 +0530 (IST) >> From: Anoop J. <cs99001@nitc.ac.in> >> To: linux-kernel@vger.kernel.org, linux-mm@kvack.org >> >> >> How does page coloring work. Iwant its mechanism not the implementation. >> I went through some pages of W.L.Lynch's paper on cache and VM. Still not >> able to grasp it . >> >> >> Thanks in advance >> >> >> >> - >> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in >> the body of a message to majordomo@vger.kernel.org >> More majordomo info at http://vger.kernel.org/majordomo-info.html >> Please read the FAQ at http://www.tux.org/lkml/ >> >- >To unsubscribe from this list: send the line "unsubscribe linux-kernel" in >the body of a message to majordomo@vger.kernel.org >More majordomo info at http://vger.kernel.org/majordomo-info.html >Please read the FAQ at http://www.tux.org/lkml/ -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail 2003-01-24 6:06 ` John Alvord @ 2003-01-25 2:29 ` Jason Papadopoulos -1 siblings, 0 replies; 16+ messages in thread From: Jason Papadopoulos @ 2003-01-25 2:29 UTC (permalink / raw) To: linux-kernel, linux-mm At 10:06 PM 1/23/03 -0800, John Alvord wrote: >The big challenge in Linux is that several serious attempts to add >page coloring have foundered on the shoals of "no benefit found". It >may be that the typical hardware Linux runs on just doesn't experience >the problem very much. Another strike against page coloring is that it gives tremendous benefits when caches are large and not very associative, but if both of these are not present the benefits are much smaller. In the case of latter-day PCs, neither of these is the case: the caches are very small and at least 8-way set associative. For the record, I finally got to try my own page coloring patch on a 1GHz Athlon Thunderbird system with 256kB L2 cache. With the present patch, my own number crunching benchmarks and a kernel compile don't show any benefit at all, and lmbench is completely unchanged except for the mmap latency, which is slightly worse. Hardly a compelling case for PCs! Oh well. At least now I'll be able to port to 2.5 :) jasonp ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail @ 2003-01-25 2:29 ` Jason Papadopoulos 0 siblings, 0 replies; 16+ messages in thread From: Jason Papadopoulos @ 2003-01-25 2:29 UTC (permalink / raw) To: linux-kernel, linux-mm At 10:06 PM 1/23/03 -0800, John Alvord wrote: >The big challenge in Linux is that several serious attempts to add >page coloring have foundered on the shoals of "no benefit found". It >may be that the typical hardware Linux runs on just doesn't experience >the problem very much. Another strike against page coloring is that it gives tremendous benefits when caches are large and not very associative, but if both of these are not present the benefits are much smaller. In the case of latter-day PCs, neither of these is the case: the caches are very small and at least 8-way set associative. For the record, I finally got to try my own page coloring patch on a 1GHz Athlon Thunderbird system with 256kB L2 cache. With the present patch, my own number crunching benchmarks and a kernel compile don't show any benefit at all, and lmbench is completely unchanged except for the mmap latency, which is slightly worse. Hardly a compelling case for PCs! Oh well. At least now I'll be able to port to 2.5 :) jasonp -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail 2003-01-25 2:29 ` Jason Papadopoulos @ 2003-01-25 2:26 ` Larry McVoy -1 siblings, 0 replies; 16+ messages in thread From: Larry McVoy @ 2003-01-25 2:26 UTC (permalink / raw) To: Jason Papadopoulos; +Cc: linux-kernel, linux-mm > For the record, I finally got to try my own page coloring patch on a 1GHz > Athlon Thunderbird system with 256kB L2 cache. With the present patch, my > own number crunching benchmarks and a kernel compile don't show any benefit > at all, and lmbench is completely unchanged except for the mmap latency, > which is slightly worse. Hardly a compelling case for PCs! If it works correctly then the variability in lat_ctx should go away. Try this for p in 2 4 8 12 16 24 32 64 do for size in 0 2 4 8 16 do for i in 1 2 3 4 5 6 7 8 9 0 do lat_ctx -s$size $p done done done on both the with and without kernel. The page coloring should make the numbers rock steady, without it, they will bounce a lot. -- --- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail @ 2003-01-25 2:26 ` Larry McVoy 0 siblings, 0 replies; 16+ messages in thread From: Larry McVoy @ 2003-01-25 2:26 UTC (permalink / raw) To: Jason Papadopoulos; +Cc: linux-kernel, linux-mm > For the record, I finally got to try my own page coloring patch on a 1GHz > Athlon Thunderbird system with 256kB L2 cache. With the present patch, my > own number crunching benchmarks and a kernel compile don't show any benefit > at all, and lmbench is completely unchanged except for the mmap latency, > which is slightly worse. Hardly a compelling case for PCs! If it works correctly then the variability in lat_ctx should go away. Try this for p in 2 4 8 12 16 24 32 64 do for size in 0 2 4 8 16 do for i in 1 2 3 4 5 6 7 8 9 0 do lat_ctx -s$size $p done done done on both the with and without kernel. The page coloring should make the numbers rock steady, without it, they will bounce a lot. -- --- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail 2003-01-25 2:26 ` Larry McVoy @ 2003-01-25 17:47 ` Eric W. Biederman -1 siblings, 0 replies; 16+ messages in thread From: Eric W. Biederman @ 2003-01-25 17:47 UTC (permalink / raw) To: Larry McVoy; +Cc: Jason Papadopoulos, linux-kernel, linux-mm Larry McVoy <lm@bitmover.com> writes: > > For the record, I finally got to try my own page coloring patch on a 1GHz > > Athlon Thunderbird system with 256kB L2 cache. With the present patch, my > > own number crunching benchmarks and a kernel compile don't show any benefit > > at all, and lmbench is completely unchanged except for the mmap latency, > > which is slightly worse. Hardly a compelling case for PCs! > > If it works correctly then the variability in lat_ctx should go away. > Try this > > for p in 2 4 8 12 16 24 32 64 > do for size in 0 2 4 8 16 > do for i in 1 2 3 4 5 6 7 8 9 0 > do lat_ctx -s$size $p > done > done > done > > on both the with and without kernel. The page coloring should make the > numbers rock steady, without it, they will bounce a lot. On the same kind of vein I have seen some tremendous variability in the stream benchmark. Under linux I have gotten it to very as much as a 100MB/sec by running updatedb, between runs. In one case it ran faster with updatedb running in the background. But at the same time streams tends to be very steady if you have a quiet machine and run it several times in a row repeatedly because it gets allocated essentially the same memory every run. So I do no the variables of cache contention do have effect on some real programs. I have not yet tracked it down to see if cache coloring could be a benefit. I suspect the buddy allocator actually comes quite close most of the time, and tricks like allocating multiple pages at once could improve that even more with very little effort, while reducing page fault miss times. I am wondering if there is any point in biasing page addresses in between processes so that processes are less likely to have a cache conflict. i.e. process 1 address 0 %16K == 0, process 2 address 0 %16K == 4K Eric ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail @ 2003-01-25 17:47 ` Eric W. Biederman 0 siblings, 0 replies; 16+ messages in thread From: Eric W. Biederman @ 2003-01-25 17:47 UTC (permalink / raw) To: Larry McVoy; +Cc: Jason Papadopoulos, linux-kernel, linux-mm Larry McVoy <lm@bitmover.com> writes: > > For the record, I finally got to try my own page coloring patch on a 1GHz > > Athlon Thunderbird system with 256kB L2 cache. With the present patch, my > > own number crunching benchmarks and a kernel compile don't show any benefit > > at all, and lmbench is completely unchanged except for the mmap latency, > > which is slightly worse. Hardly a compelling case for PCs! > > If it works correctly then the variability in lat_ctx should go away. > Try this > > for p in 2 4 8 12 16 24 32 64 > do for size in 0 2 4 8 16 > do for i in 1 2 3 4 5 6 7 8 9 0 > do lat_ctx -s$size $p > done > done > done > > on both the with and without kernel. The page coloring should make the > numbers rock steady, without it, they will bounce a lot. On the same kind of vein I have seen some tremendous variability in the stream benchmark. Under linux I have gotten it to very as much as a 100MB/sec by running updatedb, between runs. In one case it ran faster with updatedb running in the background. But at the same time streams tends to be very steady if you have a quiet machine and run it several times in a row repeatedly because it gets allocated essentially the same memory every run. So I do no the variables of cache contention do have effect on some real programs. I have not yet tracked it down to see if cache coloring could be a benefit. I suspect the buddy allocator actually comes quite close most of the time, and tricks like allocating multiple pages at once could improve that even more with very little effort, while reducing page fault miss times. I am wondering if there is any point in biasing page addresses in between processes so that processes are less likely to have a cache conflict. i.e. process 1 address 0 %16K == 0, process 2 address 0 %16K == 4K Eric -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail 2003-01-25 17:47 ` Eric W. Biederman @ 2003-01-25 23:10 ` Larry McVoy -1 siblings, 0 replies; 16+ messages in thread From: Larry McVoy @ 2003-01-25 23:10 UTC (permalink / raw) To: Eric W. Biederman; +Cc: Larry McVoy, Jason Papadopoulos, linux-kernel, linux-mm > I am wondering if there is any point in biasing page addresses in between > processes so that processes are less likely to have a cache conflict. > i.e. process 1 address 0 %16K == 0, process 2 address 0 %16K == 4K All good page coloring implementation do exactly that. The starting index into the page buckets is based on process id. -- --- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail @ 2003-01-25 23:10 ` Larry McVoy 0 siblings, 0 replies; 16+ messages in thread From: Larry McVoy @ 2003-01-25 23:10 UTC (permalink / raw) To: Eric W. Biederman; +Cc: Larry McVoy, Jason Papadopoulos, linux-kernel, linux-mm > I am wondering if there is any point in biasing page addresses in between > processes so that processes are less likely to have a cache conflict. > i.e. process 1 address 0 %16K == 0, process 2 address 0 %16K == 4K All good page coloring implementation do exactly that. The starting index into the page buckets is based on process id. -- --- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail 2003-01-25 23:10 ` Larry McVoy @ 2003-01-26 8:12 ` David S. Miller -1 siblings, 0 replies; 16+ messages in thread From: David S. Miller @ 2003-01-26 8:12 UTC (permalink / raw) To: Larry McVoy; +Cc: Eric W. Biederman, Jason Papadopoulos, linux-kernel, linux-mm On Sat, 2003-01-25 at 15:10, Larry McVoy wrote: > All good page coloring implementation do exactly that. The starting > index into the page buckets is based on process id. I think everyone interested in learning more about this topic should go read the following papers, they were very helpful when I was fiddling around in this area. These papers, in turn, reference several others which are good reads as well. 1) W. L. Lynch, B. K. Bray, and M. J. Flynn. "The effect of page allocation on caches". In Micro-25 Conference Proceedings, pages 222-225, December 1992. 2) W. Lynch and M. Flynn. "Cache improvements through colored page allocation". ACM Transactions on Computer Systems, 1993. Submitted for review, 1992. 3) William L. Lynch. "The Interaction of Virtual Memory and Cache Memory". PhD thesis, Stanford University, October 1993. CSL-TR-93-587. ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: your mail @ 2003-01-26 8:12 ` David S. Miller 0 siblings, 0 replies; 16+ messages in thread From: David S. Miller @ 2003-01-26 8:12 UTC (permalink / raw) To: Larry McVoy; +Cc: Eric W. Biederman, Jason Papadopoulos, linux-kernel, linux-mm On Sat, 2003-01-25 at 15:10, Larry McVoy wrote: > All good page coloring implementation do exactly that. The starting > index into the page buckets is based on process id. I think everyone interested in learning more about this topic should go read the following papers, they were very helpful when I was fiddling around in this area. These papers, in turn, reference several others which are good reads as well. 1) W. L. Lynch, B. K. Bray, and M. J. Flynn. "The effect of page allocation on caches". In Micro-25 Conference Proceedings, pages 222-225, December 1992. 2) W. Lynch and M. Flynn. "Cache improvements through colored page allocation". ACM Transactions on Computer Systems, 1993. Submitted for review, 1992. 3) William L. Lynch. "The Interaction of Virtual Memory and Cache Memory". PhD thesis, Stanford University, October 1993. CSL-TR-93-587. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ ^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~2003-01-26 8:12 UTC | newest] Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2003-01-24 5:08 Anoop J. 2003-01-24 5:08 ` (unknown), Anoop J. 2003-01-24 5:11 ` your mail David Lang 2003-01-24 5:11 ` David Lang 2003-01-24 6:06 ` John Alvord 2003-01-24 6:06 ` John Alvord 2003-01-25 2:29 ` Jason Papadopoulos 2003-01-25 2:29 ` Jason Papadopoulos 2003-01-25 2:26 ` Larry McVoy 2003-01-25 2:26 ` Larry McVoy 2003-01-25 17:47 ` Eric W. Biederman 2003-01-25 17:47 ` Eric W. Biederman 2003-01-25 23:10 ` Larry McVoy 2003-01-25 23:10 ` Larry McVoy 2003-01-26 8:12 ` David S. Miller 2003-01-26 8:12 ` David S. Miller
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.