Pipeline branch prediction performance example

0
votes

I am working through examples of pipeline hazards and am looking at Question 2 from the following document

Question 2

I have found this which has helped somewhat.

As I understand, the strategies work the following way:

  1. Stall until everything is known: will stall until reaching the MEM2 stage is complete. As I understand it, it is the simplest strategy, and the stall cycles will be the same for all => 5,5,5.
  2. Assume not taken: will just assume that the branch is not taken. In this instance, when the branch is taken, you will have to stall everything past the IF1 stage => 7,0,7
  3. Assume taken: would roughly be the inverse of #2; when the branch isn't taken, you will have to stall past the IF1 stage => 0,7,0

I am unsure if my understanding is correct. If someone could critique my solution and tell me if my thinking is correct or explain where I am wrong, it would be greatly appreciated.

EDIT1: To answer questions

1) When do you expect to know when you were right (branch resolution)?

I believe you would know the branch resolution by the EX step.

2) When do you expect to know when you want to take the branch (right or wrong)?

I believe you would know when you want to branch by the AG step.

3) When would you know the address?

I believe you would know the next address after the AG step.

EDIT2: "Stall until everything is known." It is my understanding that whether or not the branch (either conditional or unconditional) is taken, that the pipeline will start stalling DURING the AG stage and will continue stalling until the EX stage is completed. Meaning: it will have to stall for 4 cycles in all cases.

It would look like the following: I# = IF#, M# = MEM#, ST = stall

Branch:    I1-I2-ID-AG-M1-M2-EX-WB   
Successor:    I1-I2-ST-ST-ST-ST-ID-AG-M1-M2-EX-WB

EDIT3: "Assume not taken". It is my understanding that, as the name implies, you are assuming that every branch (either conditional or unconditional) is taken. The only stalls that would occur here would be the case where the branch is taken. The stalls would occur in the same place as earlier. Thus, in this case, you would get 4 stalls in the case where the branches (conditional or unconditional) occur, and no stalls in the case where they do not.

It would look like the following

Branch: I1-I2-ID-AG-M1-M2-EX-WB
Taken:     I1-I2-ST-ST-ST-ST-ID-AG-M1-M2-EX-WB
Not:       I1-I2-ID-AG-M1-M2-EX-WB

EDIT4: "Assume taken". This is essentially the inverse of the previous strategy. There would be 4 stalls in the case where the branches do not occur, but none in the case where branches (conditional or unconditional) occur.

It would look like the following

Branch: I1-I2-ID-AG-M1-M2-EX-WB
Not:       I1-I2-ID-AG-M1-M2-EX-WB
Taken:     I1-I2-ST-ST-ST-ST-ID-AG-M1-M2-EX-WB
1
computer-sciencepipelinecomputer-architecturepipeliningbranch-prediction
You should ask youself two things - When you assume something (taken/not-taken) - when do you expect to know if you were right (branch resolution)? and when you want to take a branch (whether rightfully or not) - when would you know the address? (although the latter doesn't seem to be a factor in this question) – Leeor
Thank you for your input. This might be where my understanding is off. I answered the questions as I understand them (which may be a faulty understanding) in EDIT1. Let me know where/if my understanding needs clarification. – basil
So when you wait for the resolution to be known, you can't start before the condition test instructions finishes EX, and even that is assuming you have forwarding from EX to IF. – Leeor
I do not follow you at all at this point, I apologize. The more I read about this, the more confused I am becoming. Let us try to break down the problem, strategy by strategy, as I feel that is more helpful to think about these questions when given concrete examples. Please refer to EDIT2 - EDIT4, which will represent the three strategies. I appreciate your patience, as I find this stuff rather difficult to grasp. – basil
Also, am I correct in my understanding that in terms of stalls, whether or not the branching is conditional or unconditional will not effect things? – basil

1 Answers

1
votes

You know it's a jump in Decode, you know the jump target in AGen, so you can resolve jumps much earlier than conditional branches.

I believe "Assume Not Taken" means you predict PC+4 always. If there are no taken branches in your code, your pipeline experiences no bubbles. If you hit a jump or branch, then you must kill the misspeculated instructions, and redirect the PC.

I believe "Assume Taken" means once you realize you are taking a branch and have a target to jump to, you take the branch (and kill the assumed misspeculated instructions behind it). This saves you the cycles between AGen and Exe. However, this experiences poor behavior if the Branch is Not Taken, because you need to redirect the PC back to what it was before.