Set associative cache...

Really confusing the way I've been taught this... wondered if anyone could help me out...

A given processor accesses memory using 32-bit addresses. Suppose there is a cache between the processor and main memory of 512 bytes total size and with a line size of 8 bytes. For each of the following cache architectures specify how the 32-bit address would be used by the address translation mechanism in the cache:

2 way set associative
4 way set associative

The diagram I took from the board doesn't seem to make much sense to me...

For 2 way, there's 1 bit for the word, 1 bit for something else and 30 bits for the tag...?

Reply 1

tcassey

How many sets are there in the cache? Once you have worked that out you can calculate how many bits you need for the index.

How many bytes are there in each line? This tells you how many bits you need for byte level addressing.

What is left over? The tag

Hope that helps, if not let me know and ill draw a picture .. they always help.

Reply 2

EvenStevens

Well on a line size of 8 bytes, that's 64 bits per line.

And number of sets in the cache is 2 or 4, relating to my question... right?

Reply 3

tcassey

2 or 4 is the size of each set, the number of sets can be thought of as the number of bins, each bin must have an index which is some number of bits long. We know the cache has size 512 bytes, for the 2 way set associative cache each set contains 2 words, and each word is 8 bytes. So if n is the number of bins we know 2 * 8 * n = 512. Once you know n you can calculate how many bits are needed to index each of the bins.

Reply 4

EvenStevens

Okay so there's 8 bytes in a line, and 512 bytes in total. So looks somewhat like that ^ ?

And from what I got from the board, a 2 way associative address translation looks like...

But I don't...get how there's only 1 bit for a word. Or is that 2 bits for 2 words? *head melts*

Reply 5

tcassey

Sorry for the delay, for some reason I cant sign into either snow or ice. Anyway I've uploaded a drawing to Fluff can be accessed from https://www.bris.ac.uk/fluff/u/tc4124/R5_l5IKTLmYG5wGaWNp6uwBG/ ... you need to sign in to access it. If that doesn't work PM me your email address and I'll email it to you or we can just wait until I can upload it.

So, given my diagram can you redraw your break down of the address.

Reply 6

laser

A word's normally 4 bytes, isn't it?

Reply 7

tcassey

Not necessarily most modern desktop computers are now 64 bit architecture so an 8 byte word ... embedded systems vary more. Id say 16, 32, or 64 bits are the most common word lengths in use nowadays.

Reply 8

laser

Looks like we're both wrong, on Intel 32 and 64-bit systems, a word is 16-bit. For compatibility with the 8086. http://en.wikipedia.org/wiki/Word_(computing)

Reply 9

tcassey

In architecture terms I think the word size is generally taken to be the amount of data processed by the machine, so for a 64 bit processor its 64 bits. My guess is that at the time of 16-bit architecture people associated a 'word' with 16-bits of data and that has stuck around. But arguing semantics probably isn't that important.