From: pries@mips.com (Paul Ries)
Newsgroups: comp.arch
Subject: Re: Fully associative cache
Date: 29 Sep 1992 21:51:50 GMT
Organization: MIPS Computer Systems, Sunnyvale, California
NNTP-Posting-Host: meter.mti.sgi.com

In article <1992Sep28.104703.3493@inmos.co.uk> roger@gimli.inmos.co.uk (Roger Shepherd) writes:

>Lets do the comparison; 4k fully associative cache v. 4k 4-way set assciative,
>both with 4 words per line.
>
>A fully associative cache has 256 lines, each of 4 words, each with 
>a tag CAM, and an address decoder. It has a single set of sense amps
>for the data, and a set of sense amps for the CAM. It also has some logic
>between the CAM and the RAM.
>
>A 4-way set associative cache has 4 direct map caches. Each direct map cache
>has 64 lines, each of 4 words with a tag RAM and an address decoder. Each
>direct map cache has a set of sense amps. (Of, course, it may that for an
>on-chip implementation you build it as a single array - but you still need 
>4 sets of sense amps).
>
>Now, the total amount of data RAM is the same in both cases, the total 
>amont of address decoder is the same in both cases. The CAM will be
>bigger than the RAM. So, far the 4-way cache is winning. However, the
>fully  associative cache requires one set of sense amps but the 4-way
>set associative requires 4 sets. So, the comparison revolves around the
>relative sizes of CAM and sense amps/periphery. This will vary from
>process to process; for the T9000's process the fully associative cache
>would turn out smaller. 
>
>Also, remember that in teh T9000 size was not the only consideration....
>


Well there is another way (probably many) to implement the set-associative 
cache.  You could chose to have the outputs of the tag compare for the set
associative cache control address decoding for the data array, such that the
number of sense amps is the same for the data array.  Granted the tag arrays
will still have four times as many sense amps, but it is not at all clear that
these sense amps and the external tag comparatos will be as large as the 
internal tag comparators in the CAM cells of the fully associative approach.  
This approach may end up being slower, but if you use column muxing before your
sense amps, typically you can tolerate some late address bits.   If this ends 
up being too slow, then do it the way you said....I still find it hard to 
believe that the extra sense amps take up more area that the cam cells....but
this is probably a strong function of the actual cache size and cache line size,
which we have not fixed in this conversation.



>:: 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? 

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.

>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.  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.  At
that time you could retire the store.  There is no delay since it is pipelined.
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...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).

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.  
-- 
-Paul Ries DISCLAIMER: <generic disclaimer, I speak for me only, etc>
UUCP: 	pries@mti.sgi.com                 Phone:	415-390-4481 
USPS: 	Silicon Graphics Computer Systems, MS 10L-135 2011 N. Shoreline Blvd,
	Mountain View, CA 94039-7311