Difference between cache way and cache set

Question

I am trying to learn some stuff about caches. Lets say I have a 4 way 32KB cache and 1GB of RAM. Each cache line is 32 bytes. So, I understand that the RAM will be split up into 256 4096KB pages, each one mapped to a cache set, which contains 4 cache lines.

How many cache ways do I have? I am not even sure what a cache way is. Can someone explain that? I have done some searching, the best example was

http://download.intel.com/design/intarch/papers/cache6.pdf

But I am still confused.

Thanks.

Answer 1

The cache you are referring to is known as set associative cache. The whole cache is divided into sets and each set contains 4 cache lines(hence 4 way cache). So the relationship stands like this :

cache size = number of sets in cache * number of cache lines in each set * cache line size

Your cache size is 32KB, it is 4 way and cache line size is 32B. So the number of sets is (32KB / (4 * 32B)) = 256

If we think of the main memory as consisting of cache lines, then each memory region of one cache line size is called a block. So each block of main memory will be mapped to a cache line (but not always to a particular cache line, as it is set associative cache).

In set associative cache, each memory block will be mapped to a fixed set in the cache. But it can be stored in any of the cache lines of the set. In your example, each memory block can be stored in any of the 4 cache lines of a set.

Memory block to cache line mapping

Number of blocks in main memory = (1GB / 32B) = 2^25

Number of blocks in each page = (4KB / 32B) = 128

Each byte address in the system can be divided into 3 parts:

1. Rightmost bits represent byte offset within a cache line or block
2. Middle bits represent to which cache set this byte(or cache line) will be mapped
3. Leftmost bits represent tag value

Bits needed to represent 1GB of memory = 30 (1GB = (2^30)B)

Bits needed to represent offset in cache line = 5 (32B = (2^5)B)

Bits needed to represent 256 cache sets = 8 (2^8 = 256)

So that leaves us with (30 - 5 - 8) = 17 bits for tag. As different memory blocks can be mapped to same cache line, this tag value helps in differentiating among them.

When an address is generated by the processor, 8 middle bits of the 30 bit address is used to select the cache set. There will be 4 cache lines in that set. So tags of the all four resident cache lines are checked against the tag of the generated address for a match.

Example

If a 30 bit address is 00000000000000000-00000100-00010('-' separated for clarity), then

1. offset within the cache is 2
2. set number is 4
3. tag is 0

Answer 2

In their "Computer Organization and Design, the Hardware-Software Interface", Patterson and Hennessy talk about caches. For example, in this version, page 408 shows the following image (I have added blue, red, and green lines):

Apparently, the authors use only the term "block" (and not the "line") when they describe set-associative caches. In a direct-mapped cache, the "index" part of the address addresses the line. In a set-associative, it indexes the set.

This visualization should get along well with @Soumen's explanation in the accepted answer.

However, the book mainly describes Reduced Instruction Set Architectures (RISC). I am personally aware of MIPS and RISC-V versions. So, if you have an x86 in front of you, take this picture with a grain of salt, more as a concept visualization than as actual implementation.