I was solving problems from the exercise of the book "Computer Organization and Design" by Patterson. The problem reads like this:
SW R16,12(R6) LW R16,8(R6) BEQ R5,R4,Label ; Assume R5 != R4 ADD R5,R1,R4 SLT R5,R15,R4
Assuming stall-on-branch and no delay slots, what speedup is achieved on this code if branch outcomes are determined in the ID stage, relative to the execution where branch outcomes are determined in the EX stage?
The solution given was:
Stall-on-branch delays the fetch of the next instruction until the branch is executed. When branches execute in the EXE stage, each branch causes two stall cycles:
F D X M W //branch instruction F D X M W //NOP F D X M W //NOP F D X M W
When branches execute in the ID stage, each branch only causes one stall cycle:
F D X M W // branch instruction F D X M W //NOP F D X M W
Without branch stalls (e.g., with perfect branch prediction) there are no stalls, and the execution time is k+n-1+b*p, where k is number of stages, n is number of instructions executed, b is number of branches taken, p is stall cycles per branch. Thus, We have:
My doubt is:
Here, we don’t take any branch (as branch condition evaluated to false), so there is no stall, then why it says branches executed = 1? If we assume no branches executed, then for both “Cycles with Branch in EXE” and “Cycles with Branch in ID” will be 4+5 = 9, right?
PS: The execution will be straight:
SW: F D X M W LW: F D X M W BEQ: F D X M W //branch wont be taken as R5!=R4 is given and hence next instruction ADD is executed ADD: F D X M W SLT: F D X M W