1
$\begingroup$

Lets suppose that 20 percent of the instructions in a program are branch instructions.The static prediction of the jumps supposes that the jumps don't happen.

I should find the execution time in two cases : When 30 percent of the branches happen and when 70 percent of the branches happen I also should find the speedup of one case compared to the other and express it in percentage.

Thing is,how do I find the execution time here ? I usually find the execution time where the pipeline is separated in different phases and there is given the time for each phase ....

Edit : This is NOT homework.I found this in my computer architecture textbook and its not a familiar exercise.

$\endgroup$
2
$\begingroup$

With a static prediction of not-taken, when the branch is not taken (correct prediction) there is no penalty. When the branch is taken ("happens"), all the instructions that were fetched after the branch instruction are flushed from the pipeline (except for any branch delay slot instructions) when the branch instruction is evaluated. Instruction fetch restarts at the correct address.

With a simple five-stage pipeline (instruction fetch, decode, execute, memory, writeback) where branch direction and target are determined in the third (execute) stage and no branch delay slots are used, a taken branch will take three cycles (i.e., the instructions in the fetch and decode stages are flushed). If all other instructions have a cycles per instruction of one, then the total CPI would be the fraction of instructions that are taken branches times three cycles plus one minus that fraction (all other instructions including not taken branches) times one cycle (for 30% taken branches: 0.20*0.30*3 cycles + (1-(0.20*0.30))*1 cycle; for 70% taken branches: 0.20*0.70*3 cycles + (1-(0.20*0.70))*1 cycle). (This is simply the sum of the products for each instruction type of the number of cycles for that instruction type times the fraction of instructions of that type. For this case, the instruction types are taken branches (three cycles, 30% of 20%) and all other instructions (1 cycle, 100% - taken branch percentage).

The execution time (in cycles) is simply the CPI times the instruction count. The speedup factor would be the execution time for one case divided by the execution time of the other case. Subtracting one from the speedup factor and multiplying by 100 gives the speedup percentage. (If the factor is less than one, the speedup percentage will be negative. Negating this would provide the slowdown percentage.)

$\endgroup$
  • $\begingroup$ I should multiply for example this 0.20*0.30*3 cycles + (1-(0.20*0.30))*1 cycle with 0.2 to find execution time? $\endgroup$ – Xizi Jun 24 '15 at 14:55
  • $\begingroup$ what about the speedup? $\endgroup$ – Xizi Jun 24 '15 at 15:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.