2
$\begingroup$

The Problem: A CPU produces the following sequence of read addresses in hex.
   Suppose the cache is empty to begin with and assuming an LRU replacement, determine whether each address produces a hit or miss for a) direct mapped cache b) fully associative cache c) two way set associative cache.

20 0010 0000
04 0000 0100
28 0010 1000
60 0110 0000
20 0010 0000

Here is the table of my work thus far (ones I highlighted are ones I am unsure about) enter image description here

I know that because the cache is empty to begin with, the first five read addresses will produce produces because the addresses are not already in the cache.

I'am having trouble with the last address. The last address is a repeat of the first address. I know that in fully associative deals with the collision problem by allowing a memory location to go into any cache line so the first won't get overwritten and a hit will be produced.

For directly mapped, how can you tell if the first address has been overwritten or not? I know that LRU replacement is being used so if there was a collision, the first address would get overwritten. But I am not sure if there would be collision within the first five addresses(you don't have access to the number of cache lines.

For two set associative, how would you identify which sets each address belongs to? There could be different interpretations. Like you could see, reading from left to right, bits 4-5 match in addresses starting with 20, 28, 60 so 20 would get overwritten, producing a miss. At the same time, a different interpretation could lead to the conclusion that the first doesn't get replaced.

Improve this question
$\endgroup$
9
  • $\begingroup$ Technically, the fully associative cache would miss if there were only three cache blocks (and so three ways) given LRU replacement. Similarly whether the other accesses hit depends on the cache size and block size. With a 16 Addressable Unit block, 0x20 and 0x28 address the same block, so 0x28 could hit. (Or are these addresses after the offset within the block has been removed?). With four blocks (8 AU sized), addr[3:4] would be the index for 1-way, addr[3] for 2-way; so 20,4,60 map to the same index; likewise for an 8-block cache (addr[3:5]; addr[3:4] 2-way), assuming mod 2^N indexing. $\endgroup$
    – Paul A. Clayton
    Jun 1 '15 at 12:18
  • $\begingroup$ With regards to this - With a 16 Addressable Unit block, 0x20 and 0x28 address the same block, so 0x28 could hit, 0x20 is 32 in decimal while 0x28 is 40 decimal. 32 mod 16 = 0 and 40 % 16 = 8. Wouldn't these two evaluate to different blocks then? $\endgroup$
    – committedandroider
    Jun 1 '15 at 18:47
  • $\begingroup$ If the offset within the block (the mod block size part) is less than the block size, then the access is within the same block. It is ((addr/block_size)%(block_count/associativity)) that provides the index. $\endgroup$
    – Paul A. Clayton
    Jun 2 '15 at 1:39
  • $\begingroup$ @PaulA.Clayton if we consider directly mapped cache, wouldn't it just be addr % block_count? So 0x20 and 0x28 would evaluate to different blocks? $\endgroup$
    – committedandroider
    Jun 2 '15 at 5:02
  • 1
    $\begingroup$ The offset is the address portion within the block. (The index is the portion addressing a block.) $\endgroup$
    – Paul A. Clayton
    Jun 2 '15 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.