Let's say we have a pipeline with 20 stages. If the testing for the jump condition is done at stage 14 and we have a wrong prediction, then the instructions processed in those 14 stages, that shouldn't have been processed due to the wrong prediction made the processor lose 14 cycles. We know that the jump instruction entered the pipeline 14 stages back, therefore from this behaviour I deduced that 14 cycles were lost. Am I correct? If no, why?
2
-
$\begingroup$ It is quite correct. Practically it can be a bit more difficult as the delay for fetching the new instruction can be variable (depending on various caches...),... $\endgroup$– GrabulCommented Jan 22, 2017 at 13:25
-
$\begingroup$ It's also worth considering that a mispredicted branch is no different from a faulting instruction, which also "kills" all instructions behind it in the execution stream. $\endgroup$– Pseudonym ♦Commented Jan 23, 2017 at 1:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
It's not correct. The instruction that would determine the result of the condition is read at cycle x. The conditional branch is read at cycle x + k. k can be any value, depending on the code. For example I can have a comparison "compare x and 0", then half a dozen unrelated instructions, then an instruction "branch if the comparison result is 'greater'". You are saying the correct condition is determined at cycle x + 14. You lose 14 - k cycles.
You may find out 14 cycles later that the branch was predicted wrongly, or 8 cycles later, or in the next cycle. What is lost is the cycles between branch prediction and the point where the correct way became known, which is variable. In this situation, compilers will often try to issue the comparison as early as possible before the branch instruction, to minimise the penalty for an incorrect branch.
To clarify: If a compare instruction is read at cycle x, and the result of the comparison is available at cycle x+14, and a conditional branch instruction is read at cycle x + k, then it doesn't matter at which stage in the pipeline the incorrect branch is detected. What matters is the time from the start of the conditional branch, to the time of detection of the incorrect branch, and that time is variable. If the compare instruction is issued early enough then the branch isn't even predicted because the result of the compare instruction is known.
-
$\begingroup$ I undestand what are you saying here, but I wasn't talking about general situation, with variable number of cycles between the moment the jump instruction entered the pipeline and the moment it was reported as being incorrectly predicted. I imagined a situation in which always the testing for the jump condition is done at stage 14. From the "formula" you gave me, I guess I was correct about this particular situation. $\endgroup$– PeterCommented Jan 22, 2017 at 15:52
-
$\begingroup$ Putting the comparison early can help instruction scheduling because of the data dependency with the branch instruction, but it do not help minimize penalty for an incorrect branch. $\endgroup$– GrabulCommented Jan 22, 2017 at 16:49
-
$\begingroup$ @TEMLIB: Of course it does. It reduces the number of instructions that are issued wrongly and therefore wasted. $\endgroup$ Commented Jan 22, 2017 at 22:43
-
$\begingroup$ @gnasher729: Wrongly fetched (mispredicted) instructions are after the branch, not between the comparison/test instruction and the conditional branch. If the condition is elaborated soon enough and if the CPU supports it, then there will be no misprediction possible for that particular branch. $\endgroup$– GrabulCommented Jan 23, 2017 at 1:09