From: roger@gimli.inmos.co.uk (Roger Shepherd)
Subject: Re: Fully associative cache
Organization: INMOS Limited, Bristol, UK
Date: Mon, 28 Sep 1992 10:47:03 GMT

:: In article <1992Sep24.100256.23376@inmos.co.uk> roger@gimli.inmos.co.uk
:: (Roger Shepherd) writes:
::
:: >>> ... 4k byte fully associative cache, giving 16 kbytes of on-chip
:: >>> cache memory in total. Each 4k byte bank of cache is organised as 256 
:: >>> lines of 4 words. 
:: > 
:: >>  I was taught to believe that a fully associative cache was very expensive.
:: >>  
:: > 
:: > Not if implemented on-chip..... The size of each 4k byte fully associative
:: > cache is SMALLER than would be a 4-way set associative cache of the same size.
:: > The 4-way set associative cache would require 4 sets of address decoders, 4
:: > sets of sense amps etc. There are other advantages to using a fully
:: > associtive cache (i) writes easily get performed in one cycle, (ii) the
:: > power consumption of the system is lower. CAMs are very good value for
:: > money.
:: > 
:: I have thought about this a little bit and I must admit I really don't
:: know how the hardware works, but this just doesn't seem right.
:: 
:: How can a fully associative cache possible be smaller than 4-way
:: associative cache?
:: 
:: I thought that CAM's (Content Addressable Memory) were basically a one
:: bit memory cell with a one bit comparitor attached.  So basically, a
:: fully associative cache will just have a comparitor by each cache tag.
:: What am I missing?
:: 
:: I don't see why you would need 4 sets of address decoders.  You only
:: need one address decoder that could be used to select which line in
:: each set to reference.   each set will use the same cache line, right?
:: 
:: I don't see why you would need more sense amps either.  I thought you
:: needed one sense amp for each ram column, so with 4-way set
:: associative cache, you would need only "(cache-line-size)/4" sense
:: amps.  The sense amps might be smaller with a fully associative cache
:: because you are driving a smaller sense line, but you would still need
:: more sense amps.

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....

:: 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).

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. 



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