From: roger@gimli.inmos.co.uk (Roger Shepherd)
Subject: Re: Fully associative cache
Organization: INMOS Limited, Bristol, UK
Date: Wed, 30 Sep 1992 09:57:36 GMT

In article <lchjvmINNrs6@spim.mti.sgi.com>, pries@mips.com (Paul Ries) writes:

>| In article <1992Sep28.104703.3493@inmos.co.uk> roger@gimli.inmos.co.uk (Roger Shepherd) writes:
>| 
>| >:: I also don't see any reason why the writes would be faster or the
>| >:: power consumption would be lower.
>| >
>| >In a 4-way set associative cache access is made to 4 direct map caches,
>| >reading tags and data out of each cache; the tags are then checked against
>| >the desired value. Because 4 RAMs are being read, rather than 1 in the
>| >fully associative cache, approximately 4 times as much power is used.
>| >(of course, you could read the tags, check the tags and then access the
>| >data RAM, but that would degrade access time).
>| 
>| The power difference is smaller than you think.  The arrays are 1/4
>| the size so they should consume 1/4 the power (roughly).  How about the
>| power being soaked in the N compare lines which are typically precharged high
>| and pulled down every cycle for all the miss locations? 

Well, less than I say perhaps. The array sizes are the same (4 * 1/4 =
1). The power consumption of the arrays is the same therefore (modulo
different design tradeoffs). The difference in power consumption
therefore, comes from the differnce between a bank of CAM and 2 sets of
sense amps (tag and data). With our design the CAM wins on power. Now,
there is no doubt that by making different design decisions, allowing
different amounts of area, more time for the design etc, that this
situation might change. However, our  analysis showed the fully
associative cache using less power and being smaller.

>| You might respond that this is not the case because you break the caches up into
>| 4 banks.  There is nothing to stop you from breaking a 4-way set associative 
>| cache into banks also.

No. Nothing to do with breaking into 4 banks. We have a 4k fully associative 
cache per bank, and this is what needs to be compared with a 4k 4-way set 
associative cache. We need 4 banks for the bandwidth.

On this point, I believe that ARM do precisely the multi-banking trick
you describe to decrease power - we do it to gain bandwidth. (Different
design goals).

>| >As to writes, the problem is that a write signal cannot be asserted until
>| >it has been identified which direct mapped cache is to be written to. In a
>| >simple on-chip implementation this will require an extra cycle.
>| 
>| On caches that I have worked on (R4000--which is a completely direct-mapped 
>| cache), you need to check the tag array before you write the cache in any
>| event, because you need to detect whether there is a hit or a miss.  

This is precisely my point. 

>|                                                                       The
>| way we did stores, you would check the tag array in one cycle and then
>| hold the data around in a store buffer until the next store or free slot.  

So, you use 2 cache access cycles per write. Provided that the load on the 
cache is small (percentage of cycles reading + 2*percentage cycles writing
< 100) this may be ok. If you have a high proportion of writes you will 
have a problem.

>|                                                                            At
>| that time you could retire the store.  There is no delay since it is pipelined.

Pipelining hides the delay - it does nothing to improve the bandwidth lost
by taking 2 cache cycles to do the write. 

>| For the odd case where you load a location that you just stored there is
>| a bypass mechanism (and another tag comparator--actually two for the R4000).
>| 
>| Now I presume from your statement that the T9000 associative cache can do the
>| tag compare and write all in one cycle and presumably if no tag matches no
>| location is written...

exactly so

                          but I just wanted to point out that a direct-mapped or 
>| 4-way associative cache would not have to pay a performance penalty (in cycles).
>|

I agree. The ``cost'' is in pipelining - which may or may not be a problem. It
depends on what you are designing.

>| Ultimately I would think that the biggest difference between a 4-way associative
>| cache and a fully associative cache would be cycle time.  The data array word
>| lines cannot come on until the compare has been completed, which is the time
>| to pull down a precharged compare line that is width of the tag (24 bits?). 
>| This has got to be slower than a normal decode especially since you have to
>| assume in the worst case that only one bit is miscomparing. Now I suppose
>| that if other parts of your machine are slower then this is not an issue, but
>| cache cycle time is a big concern where I work.  

A 4-way set associative cache has to perform a selection after the data and
tags have been read; this takes time. The difference looks small. Of course,
tag comparison and selection could be pipelined - so could CAM access
and data RAM access.

Power consumption and silicon area are big concerns where I work :-)

Finally, this track all started because someone questioned the wisdom
of using fully-associative caches because "they are expensive". I hope
I have made the point that they are not when implemented on-chip. Whether
they are appropriate to any particular design or not takes careful
investigation; we've done it for our design and we believe that it was
the correct choice.


-- 
Roger Shepherd, INMOS Ltd   JANET:    roger@uk.co.inmos 
1000 Aztec West             UUCP:     ukc!inmos!roger or uunet!inmos-c!roger
Almondsbury                 INTERNET: roger@inmos.com
+44 454 616616              ROW:      roger@inmos.com OR roger@inmos.co.uk
Newsgroups: comp.arch,comp.lang.misc