I was solving problems from the exercise of the book "Computer Organization and Design" by Patterson. The problem reads like this:

Assume instructions:

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:

enter image description here

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
  • \$\begingroup\$ (1) The table doesn't show the no-stall case. It shows the two other cases: execute-in-ID and execute-in-EXE. (2) With perfect branch prediction, \$p=0\$, so the equation they present still works fine. \$\endgroup\$ – jonk Apr 20 at 21:13

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.