I am currently revising for a Computer Architecture exam, and have gotten stuck on the question relating to caches. I have a sample solution, but I do not understand how it was derived.
This is the sample question:
Q1. Compute the number of hits and misses if the subsequent list of hexadecimal addresses is applied to caches with the following organisations.
(i) 128 byte 1-way cache with 16 bytes per line (direct mapped)
(ii) 128 byte 2-way set associative cache with 16 bytes per line
(iii) 128 byte 4-way set associative cache with 16 bytes per line
(iv) 128 byte 8-way associative cache with 16 bytes per line (fully associative)
0000 => 0004 => 000c => 2200 => 00d0 => 00e0 => 1130 => 0028 => 113c => 2204 => 0010 => 0020 => 0004 => 0040 => 2208 => 0008 => 00a0 => 0004 => 1104 => 0028 => 000c => 0084 => 000c => 3390 => 00b0 => 1100 => 0028 => 0064 => 0070 => 00d0 => 0008 => 3394 =>Assume that the first 4 bits of the address is used as the offset within the cache line, the next log2(N) bits select the set and the remaining bits form the tag. Furthermore, assume that the all cache lines are initially invalid and that a LRU replacement policy is used.
Q2. Determine the number of compulsory, capacity and conflict misses for each cache organisation in Q1.
And this is the sample answer: (i) and (ii) (iii) and (iv)
I was wondering if it would be possible for someone to explain to me how the first few elements from one of these lists was derived? I can figure out L, K and N for each of these and the number of bits for address, set and tag but but after that I do not know how to proceed. Thanks very much.
Edit - this is where I am stuck:
i):
L=16, K=1, N=8
address = 4 bits, set = 3 bits, tag = 9 bits.
0000 = miss (I know this is a miss because it is the first one)
0004 = ???? How do I tell whether this is a hit or miss? What is the "algorithm" that I need to use?
Thanks very much.
0004 = ???? How do I tell whether this is a hit or miss? What is the "algorithm"?
Because the memory request just preceding this one pulled an entire line in. A line here is 16 bytes so encompasses addresses from 0x0000 until 0x000f.
I think it might be helpful if you open up an excel sheet and do the following. 1. Convert the addresses from hexidecimal to binary, it will be easier to reason about. 2. Write all the addresses in one column 3. Make adjacent columns and extract the offset, set and tag for each address. 4. follow the algorithm carefully and write down a timeline of the contents of your 8 sets.
I've done the first few values of the first question (direct mapped cache). Try doing the rest yourself and then come back if you have more trouble.
+------+---------------------+--------+-----+-----------+--------------------------------------------+
| hex | binary | offset | set | tag | status |
+------+---------------------+--------+-----+-----------+--------------------------------------------+
| 0000 | 0000 0000 0000 0000 | 0000 | 000 | 000000000 | miss |
| 0004 | 0000 0000 0000 0004 | 0004 | 000 | 000000000 | hit |
| 000c | 0000 0000 0000 1100 | 1100 | 000 | 000000000 | hit |
| 2200 | 0010 0010 0000 0000 | 0000 | 000 | 001000100 | miss (this also replaces the previous tag) |
| 00d0 | 0000 0000 1101 0000 | 0000 | 101 | 000000001 | miss |
| 00e0 | 0000 0000 1110 0000 | 0000 | 110 | 000000001 | miss |
| 1130 | 0001 0001 0011 0000 | 0000 | 011 | 000100010 | miss |
| 0028 | 0000 0000 0010 1000 | 1000 | 010 | 000000000 | miss |
+------+---------------------+--------+-----+-----------+--------------------------------------------+
Your structure after processing these particular addresses should resemble this.
+-----+-----------+
| set | tag |
+-----+-----------+
| 000 | 001000100 |
| 001 | xxxxxxxxx |
| 010 | 000000000 |
| 011 | 000100010 |
| 100 | xxxxxxxxx |
| 101 | 000000001 |
| 110 | 000000001 |
| 111 | xxxxxxxxx |
+-----+-----------+
You should make this diagram after processing every address to understand what is happening.