MIPS CPI: Why is my answer off by one?

  • #1
bremenfallturm
66
11
Homework Statement
See post (is an image)
Relevant Equations
HIt rate = ##\frac{\text{number of cache hits}}{\text{total number of cache accesses}}##
CPI = ##\frac{\text{number of cycles}}{\text{number of instructions}}##
Hello!

So, my answer is off by one from the answer sheet to this question. I can not spot where and nor can online friendly chatbots.

Here is the question:
1735832359193.png

And here is the answer key:
1735832381108.png

I have problems in specifically the CPI question. I am correct with the other questions (data/instruction cache hit rate), so I don't think it makes much sense to provide my calculations for those, since the important things for the CPI instruction calculation is that there are 5 I-cache misses and 25 D-cache misses.

My solution for the CPI part:
So we know that there are ##5(25+5)=150## cycles from the cache misses
since the question noted that the miss penalty is 5 and
there are 5 I-cache misses and 25 D-cache misses.

We have ##705## instructions that execute in total.

However, every time we reach the "j loop" line, there will be an extra stall (control hazard). Therefore, we have ##100## stalls from "j loop".

Additionally, I assume there is a data hazard before beq due to dependecy on sllti result. Here I start to wonder: Do they not take that into account in the solution because of the footnote? Because I get an off by one answer if I consider this data hazard.
Namely, if we consider slti and beq and a F-->W 5 stage pipeline, we need to stall beq for one cycle assuming that the result from slti can not be forwarded within the same cycle from E->D:
F-D-E-M-W # slti
F-D-D-E-M-W # beq
This gives me ##101## stalls from "beq" (the loop is executed 100 times + beq executed 1 time before we branch to done)

Finally, the "beq" will result in a branch the 101th time it is ran. Assuming that we can branch in the decode stage+using assume branch note taken, then the misprediction penalty will be 1. We add 1 cycle due to that control hazard from beq.
Summing up everything in bold from above, I get

##CPI=\frac{\text{number of cycles}}{\text{number of instructions}}=\frac{150+705+100+101+1}{705}=\frac{105\mathbf 7}{705}##


The correct answer is ##\frac{105\mathbf 6}{705}##, so I am off by one. But why? Also see "here I start to wonder" above in the post. If I get the same result as the solution (almost) by also considering something the solution does not, then I am clearly more wrong than off by one.
 
Physics news on Phys.org
  • #2
bremenfallturm said:
This gives me ##101## stalls from "beq" (the loop is executed 100 times + beq executed 1 time before we branch to done)
This is where you are off by one.

Consider the code
pseudocode:
count = 0
while true:
    count++
    if count < 1 continue
    break

How many times is the while loop executed?

How many times is the 'branch' instruction if count < 1 continue executed?
 
  • #3
pbuk said:
This is where you are off by one.

Consider the code
pseudocode:
count = 0
while true:
    count++
    if count < 1 continue
    break

How many times is the while loop executed?

How many times is the 'branch' instruction if count < 1 continue executed?
Hmm, I don't think the pseudocode matches the MIPS assembly code, as count is incremented at the end of the loop
(addi t0, t0, 1). Since t0 starts at 0, then slti will be executed with values 0,1,..,99,100. Values 0-99 will make the slti return 1, hence continuing to run the loop (not branching). The end of the loop when t0=99 (the 100th iteration) increments it to 100. However, we now jump back up to the slti comparison again, so the beq comparison will be executed 101 times.

The answer key also says this if I am not mistaken:
1735998824533.png
 
Back
Top