way selection bit for multi-way cache

way selection bit for multi-way cache

[Jun Sun]

If a cache is multi-way set associative cache, one must
select the way for indexed cache operations.

The most common way selection is to use MSBs in the addressing
range of the whole cache size.  In other word, a two-way
cache of size d would use bit (log(d)-1) to select the way.

Some other CPUs often the LSB(s) in the address to select
ways.  Examples include R5432, R5500, TX49, TX39.  Does
anybody know other such CPUs?

And I think I have seen a third kind way selection, but I
can't remember which CPU it is.  Does anybody know any
other way selection schemes?

Thanks.

Jun

Re: way selection bit for multi-way cache

[Mike Uhler]

> 
> If a cache is multi-way set associative cache, one must
> select the way for indexed cache operations.
> 
> The most common way selection is to use MSBs in the addressing
> range of the whole cache size.  In other word, a two-way
> cache of size d would use bit (log(d)-1) to select the way.
> 
> Some other CPUs often the LSB(s) in the address to select
> ways.  Examples include R5432, R5500, TX49, TX39.  Does
> anybody know other such CPUs?
> 
> And I think I have seen a third kind way selection, but I
> can't remember which CPU it is.  Does anybody know any
> other way selection schemes?
> 
> Thanks.
> 
> Jun
> 

I can't comment on anything but MIPS32 and MIPS64 CPUs, but the
MIPS32 and MIPS64 standard is to use the bits above the index field
to specify the way.  See the figure entitled "Usage of Address Fields
to Select Index and Way" in the CACHE instruction description of the
MIPS32 and MIPS64 Architecture for Programmer's manuals.

/gmu

-- 

  =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  Michael Uhler, VP, Systems, Architecture, and Software Products 
  MIPS Technologies, Inc.   Email: uhler@mips.com   Pager: uhler_p@mips.com
  1225 Charleston Road      Voice:  (650)567-5025   FAX:   (650)567-5225
  Mountain View, CA 94043   Mobile: (650)868-6870   Admin: (650)567-5085

Re: way selection bit for multi-way cache

[Jun Sun]

On Thu, Apr 10, 2003 at 11:50:53AM -0700, Mike Uhler wrote:
> > 
> > If a cache is multi-way set associative cache, one must
> > select the way for indexed cache operations.
> > 
> > The most common way selection is to use MSBs in the addressing
> > range of the whole cache size.  In other word, a two-way
> > cache of size d would use bit (log(d)-1) to select the way.
> > 
> > Some other CPUs often the LSB(s) in the address to select
> > ways.  Examples include R5432, R5500, TX49, TX39.  Does
> > anybody know other such CPUs?
> > 
> > And I think I have seen a third kind way selection, but I
> > can't remember which CPU it is.  Does anybody know any
> > other way selection schemes?
> > 
> > Thanks.
> > 
> > Jun
> > 
> 
> I can't comment on anything but MIPS32 and MIPS64 CPUs, but the
> MIPS32 and MIPS64 standard is to use the bits above the index field
> to specify the way.  

Yes.  This is same as the "most common case" as I said above.
Maybe this is a better way to phrase it.  :)

Jun

Re: way selection bit for multi-way cache

[Ralf Baechle]

On Thu, Apr 10, 2003 at 11:50:53AM -0700, Mike Uhler wrote:

> I can't comment on anything but MIPS32 and MIPS64 CPUs, but the
> MIPS32 and MIPS64 standard is to use the bits above the index field
> to specify the way.  See the figure entitled "Usage of Address Fields
> to Select Index and Way" in the CACHE instruction description of the
> MIPS32 and MIPS64 Architecture for Programmer's manuals.

The question came up between Jun and me when revising the way of handling
multi-way caches.  There is the MIPS32 / MIPS64 way of selecting the
cache way - but that scheme was originally already introduced by the
R4600.  The second somewhat less common scheme is using the lowest bits
of the address.  That was originally introduced with the R10000 but a
few other processors such as the R5432 and the TX49 series are using it
as well.  Unfortunately there has been way to much creativity (usually
a positive property but ...) among designers so this posting is an
attempt to achieve completeness.

  Ralf

Re: way selection bit for multi-way cache

[Mike Uhler]

> On Thu, Apr 10, 2003 at 11:50:53AM -0700, Mike Uhler wrote:
> 
> > I can't comment on anything but MIPS32 and MIPS64 CPUs, but the
> > MIPS32 and MIPS64 standard is to use the bits above the index field
> > to specify the way.  See the figure entitled "Usage of Address Fields
> > to Select Index and Way" in the CACHE instruction description of the
> > MIPS32 and MIPS64 Architecture for Programmer's manuals.
> 
> The question came up between Jun and me when revising the way of handling
> multi-way caches.  There is the MIPS32 / MIPS64 way of selecting the
> cache way - but that scheme was originally already introduced by the
> R4600.  The second somewhat less common scheme is using the lowest bits
> of the address.  That was originally introduced with the R10000 but a
> few other processors such as the R5432 and the TX49 series are using it
> as well.  Unfortunately there has been way to much creativity (usually
> a positive property but ...) among designers so this posting is an
> attempt to achieve completeness.
> 
>   Ralf

Exactly why we made it a standard in MIPS32 and MIPS64.
-- 

  =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  Michael Uhler, VP, Systems, Architecture, and Software Products 
  MIPS Technologies, Inc.   Email: uhler@mips.com   Pager: uhler_p@mips.com
  1225 Charleston Road      Voice:  (650)567-5025   FAX:   (650)567-5225
  Mountain View, CA 94043   Mobile: (650)868-6870   Admin: (650)567-5085

Re: way selection bit for multi-way cache

[Mike Uhler]

> On Thu, Apr 10, 2003 at 11:50:53AM -0700, Mike Uhler wrote:
> 
> > I can't comment on anything but MIPS32 and MIPS64 CPUs, but the
> > MIPS32 and MIPS64 standard is to use the bits above the index field
> > to specify the way.  See the figure entitled "Usage of Address Fields
> > to Select Index and Way" in the CACHE instruction description of the
> > MIPS32 and MIPS64 Architecture for Programmer's manuals.
> 
> The question came up between Jun and me when revising the way of handling
> multi-way caches.  There is the MIPS32 / MIPS64 way of selecting the
> cache way - but that scheme was originally already introduced by the
> R4600.  The second somewhat less common scheme is using the lowest bits
> of the address.  That was originally introduced with the R10000 but a
> few other processors such as the R5432 and the TX49 series are using it
> as well.  Unfortunately there has been way to much creativity (usually
> a positive property but ...) among designers so this posting is an
> attempt to achieve completeness.
> 
>   Ralf

Exactly why we made it a standard in MIPS32 and MIPS64.
-- 

  =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  Michael Uhler, VP, Systems, Architecture, and Software Products 
  MIPS Technologies, Inc.   Email: uhler@mips.com   Pager: uhler_p@mips.com
  1225 Charleston Road      Voice:  (650)567-5025   FAX:   (650)567-5225
  Mountain View, CA 94043   Mobile: (650)868-6870   Admin: (650)567-5085

Re: way selection bit for multi-way cache

[Ralf Baechle]

On Thu, Apr 10, 2003 at 12:37:47PM -0700, Mike Uhler wrote:

> > The question came up between Jun and me when revising the way of handling
> > multi-way caches.  There is the MIPS32 / MIPS64 way of selecting the
> > cache way - but that scheme was originally already introduced by the
> > R4600.  The second somewhat less common scheme is using the lowest bits
> > of the address.  That was originally introduced with the R10000 but a
> > few other processors such as the R5432 and the TX49 series are using it
> > as well.  Unfortunately there has been way to much creativity (usually
> > a positive property but ...) among designers so this posting is an
> > attempt to achieve completeness.
> 
> Exactly why we made it a standard in MIPS32 and MIPS64.

Yep, of the existing variations that was certainly the nicest.  Only a
single function had to be taught about multi-way caches and that only
because it's a bit hard to flush caches for another process due to the
TLB translation required for the hit cacheops.  Alternative schemes need
more support by the code.

  Ralf

Re: way selection bit for multi-way cache

[Mike Uhler]

> On Thu, Apr 10, 2003 at 12:37:47PM -0700, Mike Uhler wrote:
> 
> > > The question came up between Jun and me when revising the way of handling
> > > multi-way caches.  There is the MIPS32 / MIPS64 way of selecting the
> > > cache way - but that scheme was originally already introduced by the
> > > R4600.  The second somewhat less common scheme is using the lowest bits
> > > of the address.  That was originally introduced with the R10000 but a
> > > few other processors such as the R5432 and the TX49 series are using it
> > > as well.  Unfortunately there has been way to much creativity (usually
> > > a positive property but ...) among designers so this posting is an
> > > attempt to achieve completeness.
> > 
> > Exactly why we made it a standard in MIPS32 and MIPS64.
> 
> Yep, of the existing variations that was certainly the nicest.  Only a
> single function had to be taught about multi-way caches and that only
> because it's a bit hard to flush caches for another process due to the
> TLB translation required for the hit cacheops.  Alternative schemes need
> more support by the code.

I'm not sure what you mean by TLB translations required for hit cacheops.
If you mean the Index Writeback or Index Invalidate functions, note that
you can (and should) use a kseg0 address to do this.  This bypasses
the TLB, while still giving you the index that you want.  We simply
OR the kseg0 base address into the index that we've calculated and
use that as the argument to the CACHE instruction.  There's actually
words to this effect in the MIPS32/MIPS64 spec, but it is, perhaps,
not clear enough.

/gmu

Re: way selection bit for multi-way cache

[Mike Uhler]

> On Thu, Apr 10, 2003 at 12:37:47PM -0700, Mike Uhler wrote:
> 
> > > The question came up between Jun and me when revising the way of handling
> > > multi-way caches.  There is the MIPS32 / MIPS64 way of selecting the
> > > cache way - but that scheme was originally already introduced by the
> > > R4600.  The second somewhat less common scheme is using the lowest bits
> > > of the address.  That was originally introduced with the R10000 but a
> > > few other processors such as the R5432 and the TX49 series are using it
> > > as well.  Unfortunately there has been way to much creativity (usually
> > > a positive property but ...) among designers so this posting is an
> > > attempt to achieve completeness.
> > 
> > Exactly why we made it a standard in MIPS32 and MIPS64.
> 
> Yep, of the existing variations that was certainly the nicest.  Only a
> single function had to be taught about multi-way caches and that only
> because it's a bit hard to flush caches for another process due to the
> TLB translation required for the hit cacheops.  Alternative schemes need
> more support by the code.

I'm not sure what you mean by TLB translations required for hit cacheops.
If you mean the Index Writeback or Index Invalidate functions, note that
you can (and should) use a kseg0 address to do this.  This bypasses
the TLB, while still giving you the index that you want.  We simply
OR the kseg0 base address into the index that we've calculated and
use that as the argument to the CACHE instruction.  There's actually
words to this effect in the MIPS32/MIPS64 spec, but it is, perhaps,
not clear enough.

/gmu

Re: way selection bit for multi-way cache

[Ralf Baechle]

On Thu, Apr 10, 2003 at 01:28:41PM -0700, Mike Uhler wrote:

> > Yep, of the existing variations that was certainly the nicest.  Only a
> > single function had to be taught about multi-way caches and that only
> > because it's a bit hard to flush caches for another process due to the
> > TLB translation required for the hit cacheops.  Alternative schemes need
> > more support by the code.
> 
> I'm not sure what you mean by TLB translations required for hit cacheops.
> If you mean the Index Writeback or Index Invalidate functions, note that
> you can (and should) use a kseg0 address to do this.  This bypasses
> the TLB, while still giving you the index that you want.  We simply
> OR the kseg0 base address into the index that we've calculated and
> use that as the argument to the CACHE instruction.  There's actually
> words to this effect in the MIPS32/MIPS64 spec, but it is, perhaps,
> not clear enough.

Linux has a flush_cache_page() cache operation which is used to invalidate
a page given by a virtual user-space address.  That page might be the
page of a current processor which is the easy case - it might also belong
to another process.  In the later case the TLB would miss-translate
the virtual address because the translation in the TLB is actually for
the current process.  So this is what we're doing then:

[...]
        /*
         * Do indexed flush, too much work to get the (possible) TLB refills
         * to work correctly.
	 *
	 * Note: page is the physical address of the page to invalidate.
         */
        page = (KSEG0 + (page & (dcache_size - 1)));
	/*
	 * The following two flush operations have to flush the page from
	 * all cache ways!
	 */
        blast_dcache_page_indexed(page);
        if (exec)
                blast_icache_page_indexed(page);
[...]

This can be a rather expensive operation in particular for caches with
a high degree of associativity.  The worst case would be something like
a page containing code for a processor with a 32k 8-way associative
caches where we'd have to flush the entire cache - costly overkill and
the refills might be even slower ...

  Ralf

Re: way selection bit for multi-way cache

[Dominic Sweetman]

Mike wrote:

> > I'm not sure what you mean by TLB translations required for hit
> > cacheops.  If you mean the Index Writeback or Index Invalidate
> > functions, note that you can (and should) use a kseg0 address to
> > do this.

Mike was proposing a kseg0 address translating to the right physical
address, and used with a hit-type cacheop.  I believe Ralf (and Linux)
are just assuming that's no good because it doesn't work if you have
cacheable memory above 512Mbytes physical address.

I wonder whether anything really bad would happen if you temporarily
changed the (machine) ASID to that of the address space you wanted to
invalidate?

--
Dominic

Re: way selection bit for multi-way cache

[Kevin D. Kissell]

> Mike wrote:
> 
> > > I'm not sure what you mean by TLB translations required for hit
> > > cacheops.  If you mean the Index Writeback or Index Invalidate
> > > functions, note that you can (and should) use a kseg0 address to
> > > do this.
> 
> Mike was proposing a kseg0 address translating to the right physical
> address, and used with a hit-type cacheop.  I believe Ralf (and Linux)
> are just assuming that's no good because it doesn't work if you have
> cacheable memory above 512Mbytes physical address.

More importantly, it doesn't work in the case of virtually tagged caches,
such as those in the SB-1 and MIPS 20K.

> I wonder whether anything really bad would happen if you temporarily
> changed the (machine) ASID to that of the address space you wanted to
> invalidate?

I looked at that when we were investigating the aforementioned
issues with virtually-tagged I-caches.  It looked to me as if exceptions
can occur during the invalidation, and that processing those exceptions
can cause signals to be raised to the current process in a manner that 
assumes that the TLB and ASID are coherent and in sync with 
the scheduler.  It may be that just changing the ASID temporarily
would work - most of the time.  It may even be that, with a bit
of lashing down of state, disabling of interrupts, setting of flags
to be read by traps.c/signal.c, etc, etc, it could be made bulletproof.
But I don't think that the simple, obvious hack is safe.

            Kevin K.

Re: way selection bit for multi-way cache

[Kevin D. Kissell]

> Mike wrote:
> 
> > > I'm not sure what you mean by TLB translations required for hit
> > > cacheops.  If you mean the Index Writeback or Index Invalidate
> > > functions, note that you can (and should) use a kseg0 address to
> > > do this.
> 
> Mike was proposing a kseg0 address translating to the right physical
> address, and used with a hit-type cacheop.  I believe Ralf (and Linux)
> are just assuming that's no good because it doesn't work if you have
> cacheable memory above 512Mbytes physical address.

More importantly, it doesn't work in the case of virtually tagged caches,
such as those in the SB-1 and MIPS 20K.

> I wonder whether anything really bad would happen if you temporarily
> changed the (machine) ASID to that of the address space you wanted to
> invalidate?

I looked at that when we were investigating the aforementioned
issues with virtually-tagged I-caches.  It looked to me as if exceptions
can occur during the invalidation, and that processing those exceptions
can cause signals to be raised to the current process in a manner that 
assumes that the TLB and ASID are coherent and in sync with 
the scheduler.  It may be that just changing the ASID temporarily
would work - most of the time.  It may even be that, with a bit
of lashing down of state, disabling of interrupts, setting of flags
to be read by traps.c/signal.c, etc, etc, it could be made bulletproof.
But I don't think that the simple, obvious hack is safe.

            Kevin K.

Re: way selection bit for multi-way cache

[Ralf Baechle]

On Fri, Apr 11, 2003 at 10:15:06AM +0200, Kevin D. Kissell wrote:

> > > > I'm not sure what you mean by TLB translations required for hit
> > > > cacheops.  If you mean the Index Writeback or Index Invalidate
> > > > functions, note that you can (and should) use a kseg0 address to
> > > > do this.
> > 
> > Mike was proposing a kseg0 address translating to the right physical
> > address, and used with a hit-type cacheop.  I believe Ralf (and Linux)
> > are just assuming that's no good because it doesn't work if you have
> > cacheable memory above 512Mbytes physical address.
> 
> More importantly, it doesn't work in the case of virtually tagged caches,
> such as those in the SB-1 and MIPS 20K.

On SB1 we just switch to a new ASID which effectivly is a cheap way to
invalidate the entire I-cache.  Assuming the other process has at most
4k of code resident in the I-cache from it's previous timeslice this
even is the optimal solution.  But this optimization is a heuristic that
hasn't been verified to be optimal for performance.

> > I wonder whether anything really bad would happen if you temporarily
> > changed the (machine) ASID to that of the address space you wanted to
> > invalidate?
> 
> I looked at that when we were investigating the aforementioned
> issues with virtually-tagged I-caches.  It looked to me as if exceptions
> can occur during the invalidation, and that processing those exceptions
> can cause signals to be raised to the current process in a manner that 
> assumes that the TLB and ASID are coherent and in sync with 
> the scheduler.  It may be that just changing the ASID temporarily
> would work - most of the time.  It may even be that, with a bit
> of lashing down of state, disabling of interrupts, setting of flags
> to be read by traps.c/signal.c, etc, etc, it could be made bulletproof.
> But I don't think that the simple, obvious hack is safe.

Yep - it seems like a can of worms sufficiently large to be left closed
for 2.4 ...

  Ralf

Re: way selection bit for multi-way cache

[Ralf Baechle]

On Fri, Apr 11, 2003 at 07:33:04AM +0100, Dominic Sweetman wrote:

> > > I'm not sure what you mean by TLB translations required for hit
> > > cacheops.  If you mean the Index Writeback or Index Invalidate
> > > functions, note that you can (and should) use a kseg0 address to
> > > do this.
> 
> Mike was proposing a kseg0 address translating to the right physical
> address, and used with a hit-type cacheop.  I believe Ralf (and Linux)
> are just assuming that's no good because it doesn't work if you have
> cacheable memory above 512Mbytes physical address.
> 
> I wonder whether anything really bad would happen if you temporarily
> changed the (machine) ASID to that of the address space you wanted to
> invalidate?

There are non-trivial race conditions related to the IPI mechanism used
on multi-processors when attempting this.  The easy fix would be
temporarily disabling interrupts - but of course that's undesireable as
well.

  Ralf