rosy Sheet 4 ex. 2

Question

Hi,

I don't really understand the idea behind hits/misses and how they work. In ex2, how do we know which one is a hit, or a miss, without the simulator?

Answer 1

Well, you need to understand what the program does and in case of the program you mention, there is no other way that checking step by step what the content of the memory, the cache, and the registers is. Without the simulator that is quite some work, of course.

We have first executed some code such that reg[i]=i holds. Then, we execute the following:

    sti $1,$0,0     // mem[0] := 1
    sti $2,$0,1     // mem[1] := 2
    ldi $2,$0,1     // reg[2] := mem[1] = 2
    sti $3,$0,2     // mem[2] := 3
    sti $4,$0,3     // mem[3] := 4
    ldi $2,$0,1     // reg[2] := mem[1] = 2
    sti $5,$0,7     // mem[7] := 5
    sti $6,$0,8     // mem[8] := 6
    sti $7,$0,9     // mem[9] := 7
    ldi $2,$0,1     // reg[2] := mem[1] = 2

We have a cache with 8 bytes, 2 bytes, i.e., one memory word, in a block and we use direct mapping. Hence, a memory address m is split into its cache address adr(m) = m mod 4 and its tag tag(m) = m div 4. This gives the following execution with memory transactions:

    sti $1,$0,0     // mem[0] := 1              cache[0] := mem[0]
    sti $2,$0,1     // mem[1] := 2              cache[1] := mem[1]
    ldi $2,$0,1     // reg[2] := mem[1] = 2     
    sti $3,$0,2     // mem[2] := 3              cache[2] := mem[2]
    sti $4,$0,3     // mem[3] := 4              cache[3] := mem[3]
    ldi $2,$0,1     // reg[2] := mem[1] = 2
    sti $5,$0,7     // mem[7] := 5              cache[3] := mem[7]; mem[3] := cache[3]
    sti $6,$0,8     // mem[8] := 6              cache[0] := mem[8]; mem[0] := cache[0]
    sti $7,$0,9     // mem[9] := 7              cache[1] := mem[9]; mem[1] := cache[1]
    ldi $2,$0,1     // reg[2] := mem[1] = 2     cache[1] := mem[1]; mem[9] := cache[1]

Note that the following memory addresses refer to the same cache address:

• 0,4,8,12
• 1,5,9,13
• 2,6,10,14
• 3,7,11,15

After each step, you need to remember the content of the cache, i.e., which memory block is currently at which address in the cache to find out whether there is a hit or a miss and which memory transaction is required. In particular, the last instruction is a miss since at that point of time, there is mem[9] at cache address 1 and we want to load address 1 which is also mapped to the same cache address. Hence, we first have to write back cache address 1 before loading mem[1] into cache[1].

Comments

as far as i remember, the registers had to be in the same block? but i don't understand in a) why sti $2, $0, 1 is a miss and ldi $2, $0,1 is a hit as they are working with the same register. we should not expect these kind of exercises in the exam or not to this extent?

---

Registers are not in a block. Load and store instructions access memory addresses and load memory words to a register or write a register content to a memory word. We have a cache hit if a load/store instruction finds its memory word in a block in the cache and a miss otherwise. In the program you are considering, the two instructions sti $2,$0,1 and ldi $2,$0,1 are executed one after the other. Since both access the same memory address content($0)+1, it is clear that the execution of ldi $2,$0,1 must be a cache hit, since the former instruction sti $2,$0,1 has put the block of address content($0)+1 in the cache. The former instruction has a cache miss since at that time (and initially) none of the memory blocks are in the cache.

---

why is the last instruction a miss then? and in b) the second is a hit?

---

See my extended answer.