"Colo[u]rs"

"Colo[u]rs"

[Stevie O]

After a few failed web searches (combos like 'linux cache color' just gave 
me a bunch of references to video), I am resorting to this list for this 
question.

What exactly do y'all mean by these "colors"? Task colors, cache colors, 
and probably a few other colors i've missed/forgotten about. What do these 
colors represent? How are they used to group tasks/cache entries? Is what 
they're actually for?


--
Stevie-O

The first real programmer used COPY CON VMLINUZ and rebooted.

Re: "Colo[u]rs"

[Robert Love]

On Mon, 2001-12-10 at 02:07, Stevie O wrote:
> After a few failed web searches (combos like 'linux cache color' just gave 
> me a bunch of references to video), I am resorting to this list for this 
> question.
> 
> What exactly do y'all mean by these "colors"? Task colors, cache colors, 
> and probably a few other colors i've missed/forgotten about. What do these 
> colors represent? How are they used to group tasks/cache entries? Is what 
> they're actually 

Cache color is how many indexes there are into a cache.  Caches
typically aren't direct mapped: they are indexed into cache lines by a
hash.  This means that certain memory values (of the 2^32 on your PC)
will map to the same cache line.  This means only one can be there at
the same time, and the newer one throws the old one out.

Coloring of data structures is down to give random offsets to data such
that they are not are multiples of the some value and thus don't map to
the same cache line.  This is what Linux's slab allocator is meant to
do.

	Robert Love

Re: "Colo[u]rs"

[Larry McVoy]

On Mon, Dec 10, 2001 at 02:07:06AM -0500, Stevie O wrote:
> After a few failed web searches (combos like 'linux cache color' just gave 
> me a bunch of references to video), I am resorting to this list for this 
> question.
> 
> What exactly do y'all mean by these "colors"? Task colors, cache colors, 
> and probably a few other colors i've missed/forgotten about. What do these 
> colors represent? How are they used to group tasks/cache entries? Is what 
> they're actually for?

Coloring usually means the laying out of data such that the data will 
not collide in the cache, usually the second (or third) level cache.

Data references are virtual, most caches are physically tagged.  That 
means that where data lands in the cache is a function of the physical
page address and offset within that page.  If the cache is what is called
direct mapped, which means each address has exactly one place it can be
in the cache, then page coloring becomes beneficial.  More on that in
a second.  Most caches these days are set associative, which means there
are multiple places the same cache line could be.  A 2 way set associative
cache means there are 2 places, 4 way means there are 4, and so on.  The
trend is that the last big cache before memory is at least 2 way and more
typically 4 way set associative.  There is a cost with making it N-way
associative, you have to run all the tag comparitors in parallel or
you have unacceptable performance.  With shrinking transistors and high
yields we are currently enjoying, the costs are somewhat reduced.

So what's page coloring?  Suppose we have a 10 page address space and
we touch each page.  As we touch them, the OS takes a page fault, grabs
a physical page, and makes it part of our address space.  The actual
physical addresses of those pages determine where the cache lines
will land in the cache.  If the pages are allocated at random, worst
case is that all 10 pages will map to the same location in the cache,
reducing the cache effectiveness by 10x assuming a direct mapped cache,
where there is only one place to go.   Page coloring is the careful
allocation of pages such that each virtual page maps to a physical page
which will be at a different location in the cache.  Linus doesn't like
it because it adds cost to the page free/page alloc paths, they now have
to go put/get the page from the right bucket.  He also says it's pointless
because the caches are becoming enough associative that there is no need
and he's mostly right.  Life can really suck on small cache systems that
are direct mapped, as are some embedded systems, but that's life.  It's
a tradeoff.
-- 
---
Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm 

Re: "Colo[u]rs"

[David Lang]

Larry, I thought that direct mapped caches had full mapping from any cache
address to any physical address while the N-way mapped caches were more
limited. modern caches are N-way instead of direct mapped becouse it's
much more expensive (transistor count wise) for the direct mapped
approach.

If I'm mistaken about my termonology (very possible :-) what is the term
for what I am refering to as direct mapped?

David Lang



 On Sun, 9 Dec 2001, Larry McVoy wrote:

> Date: Sun, 9 Dec 2001 23:28:59 -0800
> From: Larry McVoy <lm@bitmover.com>
> To: Stevie O <stevie@qrpff.net>
> Cc: linux-kernel@vger.kernel.org
> Subject: Re: "Colo[u]rs"
>
> On Mon, Dec 10, 2001 at 02:07:06AM -0500, Stevie O wrote:
> > After a few failed web searches (combos like 'linux cache color' just gave
> > me a bunch of references to video), I am resorting to this list for this
> > question.
> >
> > What exactly do y'all mean by these "colors"? Task colors, cache colors,
> > and probably a few other colors i've missed/forgotten about. What do these
> > colors represent? How are they used to group tasks/cache entries? Is what
> > they're actually for?
>
> Coloring usually means the laying out of data such that the data will
> not collide in the cache, usually the second (or third) level cache.
>
> Data references are virtual, most caches are physically tagged.  That
> means that where data lands in the cache is a function of the physical
> page address and offset within that page.  If the cache is what is called
> direct mapped, which means each address has exactly one place it can be
> in the cache, then page coloring becomes beneficial.  More on that in
> a second.  Most caches these days are set associative, which means there
> are multiple places the same cache line could be.  A 2 way set associative
> cache means there are 2 places, 4 way means there are 4, and so on.  The
> trend is that the last big cache before memory is at least 2 way and more
> typically 4 way set associative.  There is a cost with making it N-way
> associative, you have to run all the tag comparitors in parallel or
> you have unacceptable performance.  With shrinking transistors and high
> yields we are currently enjoying, the costs are somewhat reduced.
>
> So what's page coloring?  Suppose we have a 10 page address space and
> we touch each page.  As we touch them, the OS takes a page fault, grabs
> a physical page, and makes it part of our address space.  The actual
> physical addresses of those pages determine where the cache lines
> will land in the cache.  If the pages are allocated at random, worst
> case is that all 10 pages will map to the same location in the cache,
> reducing the cache effectiveness by 10x assuming a direct mapped cache,
> where there is only one place to go.   Page coloring is the careful
> allocation of pages such that each virtual page maps to a physical page
> which will be at a different location in the cache.  Linus doesn't like
> it because it adds cost to the page free/page alloc paths, they now have
> to go put/get the page from the right bucket.  He also says it's pointless
> because the caches are becoming enough associative that there is no need
> and he's mostly right.  Life can really suck on small cache systems that
> are direct mapped, as are some embedded systems, but that's life.  It's
> a tradeoff.
> --
> ---
> Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm
> -
> 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/
>

Re: "Colo[u]rs"

[Larry McVoy]

On Sun, Dec 09, 2001 at 11:21:23PM -0800, David Lang wrote:
> Larry, I thought that direct mapped caches had full mapping from any cache
> address to any physical address while the N-way mapped caches were more
> limited. modern caches are N-way instead of direct mapped becouse it's
> much more expensive (transistor count wise) for the direct mapped
> approach.

That's not correct unless they changed terminology without asking my 
permission :-)  A direct mapped cache is the same as a 1-way set
associative cache.  It means each cache line has one and only one 
place it can be in the cache.  It also means there is only one set
of tag comparitors, which makes it cheaper and easier to build.

> If I'm mistaken about my termonology (very possible :-) what is the term
> for what I am refering to as direct mapped?

Fully associative cache, I believe.
-- 
---
Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm 

Re: "Colo[u]rs"

[David Lang]

On Sun, 9 Dec 2001, Larry McVoy wrote:

> On Sun, Dec 09, 2001 at 11:21:23PM -0800, David Lang wrote:
> > Larry, I thought that direct mapped caches had full mapping from any cache
> > address to any physical address while the N-way mapped caches were more
> > limited. modern caches are N-way instead of direct mapped becouse it's
> > much more expensive (transistor count wise) for the direct mapped
> > approach.
>
> That's not correct unless they changed terminology without asking my
> permission :-)  A direct mapped cache is the same as a 1-way set
> associative cache.  It means each cache line has one and only one
> place it can be in the cache.  It also means there is only one set
> of tag comparitors, which makes it cheaper and easier to build.
>
> > If I'm mistaken about my termonology (very possible :-) what is the term
> > for what I am refering to as direct mapped?
>
> Fully associative cache, I believe.

Yep, that's it. thanks for the correction.

David Lang

Re: "Colo[u]rs"

[Stevie O]

At 10:56 PM 12/9/2001 -0800, Tim Hockin wrote:
> > What exactly do y'all mean by these "colors"? Task colors, cache colors,
> > and probably a few other colors i've missed/forgotten about. What do these
> > colors represent? How are they used to group tasks/cache entries? Is what
> > they're actually for?
>
>Read up on page coloring.

Could you point me in the right direction, please? A google search turned 
up a  nice pile of sites like crayola.com, but nothing about memory 
pages... except one thing on 'compiler-directed page coloring for 
multiprocessors', which assumes certain knowledge that I don't have...


--
Stevie-O

Real programmers use COPY CON PROGRAM.EXE

Re: "Colo[u]rs"

[Alan Cox]

> >Read up on page coloring.
> 
> Could you point me in the right direction, please? A google search turned 
> up a  nice pile of sites like crayola.com, but nothing about memory 
> pages... except one thing on 'compiler-directed page coloring for 
> multiprocessors', which assumes certain knowledge that I don't have...

"Unix systems for modern architectures" - Schimmel

if you have a library handy

Re: "Colo[u]rs"

[Robert Love]

On Mon, 2001-12-10 at 02:26, Robert Love wrote:

> Cache color is how many indexes there are into a cache.  Caches
> typically aren't direct mapped:

Shouldn't of said direct mapped there, they actually are direct mapped. 
I meant the function from virtual memory to cache isn't one-to-one, i.e.
multiple virtual addresses map to similar cache lines.

I should of added that n-way set associativity is increasingly making
this all less needed, but its still has benefits (the downside is there
is overhead, obviously, to making sure everything maps appropriately). 

	Robert Love

Re: "Colo[u]rs"

[Stevie O]

At 02:26 AM 12/10/2001 -0500, Robert Love wrote:
>Cache color is how many indexes there are into a cache.  Caches
>typically aren't direct mapped: they are indexed into cache lines by a
>hash.  This means that certain memory values (of the 2^32 on your PC)
>will map to the same cache line.  This means only one can be there at
>the same time, and the newer one throws the old one out.
>
>Coloring of data structures is down to give random offsets to data such
>that they are not are multiples of the some value and thus don't map to
>the same cache line.  This is what Linux's slab allocator is meant to
>do.

(I'm not too familiar with how this caching stuff works, so if anyone could 
give me a URL describing it to a relative newbie, i'd be quite grateful)

So lemme see if I got this straight from what you and Larry have told me:

For the direct map deal:

For every byte (probably page?) in the CPU's cache, say byte(page) 0x31337 
can be used to cache the bytes(pages) at:
0x00031337, 0x00131337, 0x00231337, ... 0xfff31337

So, if a program ran, and happened to have its pages #0-4095 mapped to 
physical pages:
0x00031337, 0x00131337, 0x00231337, ... 0xfff31337

and the program went through an array and accessed each of those pages in 
sequence, every successive iteration would have to replace the previous 
page in the cache with the new one; i.e. exactly one of those pages would 
be in cache at any given time. Which would obviously make the program's 
performance suck majorly.

For the n-way associative deal:

Don't quite get it enough to make an example yet ;)


--
Stevie-O

Real programmers use COPY CON PROGRAM.EXE

Re: "Colo[u]rs"

[ncw]

Robert Love <rml@tech9.net> wrote:
>  On Mon, 2001-12-10 at 03:00, Stevie O wrote:
>  
> > For the n-way associative deal:
>  
>  If the cache is n-way associative, it can store n lines at each
>  mapping.  So even though two virtual addresses map to the same cache
>  line, they can both be stored.  Of course, if you have k addresses such
>  that k>n, then you reach the same problem as direct map (the case where
>  n=1) caches.

That is a good explanation.  Related would be the TLB and its
thrashing...

>  To reiterate, the point of coloring would be to prevent the case of
>  multiple addresses mapping to the same line.

Can you get colo[u]red memory from user-space?  This would be really
useful for certain memory intensive applications (I'm thinking of
large FFT users like mprime/ARMprime here)

-- 
Nick Craig-Wood
ncw@axis.demon.co.uk

>  Let me give you a
>  real-life example.  We recently have been trying to color the kernel
>  stack.  If every process's stack lies at the same address (let alone the
>  same page multiple and offset), then they all map to the same place in
>  the cache and we can effectively only cache one of them (and
>  subsequently cache miss on every other access).  If we "color" the
>  location of the stack, we make sure they don't all map to the same
>  place.  This obviously involves some knowledge of the cache system, but
>  it tends to be general enough that we can get it right for all cases.
>  
>  If you are _really_ interested in this, an excellent and very thorough
>  book is UNIX Systems for Modern Architectures: Symmetric Multiprocessing
>  and Caching for Kernel Programmers, by Curt Schimmel.
>  
>  	Robert Love
>  
>  -
>  To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>  the body of a message to 
>  More majordomo info at  http://vger.kernel.org/majordomo-info.html
>  Please read the FAQ at  http://www.tux.org/lkml/
>  

Re: "Colo[u]rs"

[Chris Wedgwood]

On Mon, Dec 10, 2001 at 12:22:15PM +0000, ncw@axis.demon.co.uk wrote:

    Can you get colo[u]red memory from user-space?  This would be really
    useful for certain memory intensive applications (I'm thinking of
    large FFT users like mprime/ARMprime here)

By colored I assume you mean such that the pages are allocated to
process in such a way as to increase the cache's effectiveness (using
as many colors as possible and potentially not having too many
instances of the same color in successive pages)?

If so, then under Linux this is presently not possible and probably
never will be.  DaveM did some patches for this a while ago which is
of arguable use for things like sparc32 and MIPS, not sure about
sparc64.

SunOS and (I think) FreeBSD do take into account page coloring when
allocating memory though, I've told for some memory intensive MIPS
applications the performance difference can get as great as 15%, but
this is perhaps because of something else unique to MIPS (there are
ambiguities that mean only having one color present in the TLB for an
application at any one time solves).



  --cw

Re: "Colo[u]rs"

[Robert Love]

On Mon, 2001-12-10 at 03:00, Stevie O wrote:

> For the n-way associative deal:

If the cache is n-way associative, it can store n lines at each
mapping.  So even though two virtual addresses map to the same cache
line, they can both be stored.  Of course, if you have k addresses such
that k>n, then you reach the same problem as direct map (the case where
n=1) caches.

To reiterate, the point of coloring would be to prevent the case of
multiple addresses mapping to the same line.  Let me give you a
real-life example.  We recently have been trying to color the kernel
stack.  If every process's stack lies at the same address (let alone the
same page multiple and offset), then they all map to the same place in
the cache and we can effectively only cache one of them (and
subsequently cache miss on every other access).  If we "color" the
location of the stack, we make sure they don't all map to the same
place.  This obviously involves some knowledge of the cache system, but
it tends to be general enough that we can get it right for all cases.

If you are _really_ interested in this, an excellent and very thorough
book is UNIX Systems for Modern Architectures: Symmetric Multiprocessing
and Caching for Kernel Programmers, by Curt Schimmel.

	Robert Love