Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have observed that there are two different types of states in branch prediction.

  1. In superscalar execution, where the branch prediction is very important, and it is mainly in execution delay rather than fetch delay.

  2. In the instruction pipeline, where the fetching is more problem since the instructions do not actually get executed till later.

Which of these is very important (as in which of these really matters in the CPU now-a-days)? If both are equally important or in case the second one is more important then Why do we not have two instruction pipeline (probably of half the length ) and then depending on the branches, just choose one of them and then again start the population from the beginning?

share|improve this question
1  
Maybe both are important, depending on the circumstances? –  Raphael Mar 7 '12 at 6:44

2 Answers 2

up vote 5 down vote accepted

I don't know which case is prevalent, but I would like to offer some thoughts on your proposal of double pipelines.

First of all, you would need double the wire which would consume double the energy and produce double the heat while active. While not needed, on the other hand, it would be completely useless. So one could argue that it is not a good use of resources that are rare on modern processors.

More fundamentally, unless you prefer one branch based on probability, how do you know which version to write through? If none, you might not save anything because other processors might have to wait on your decision, anyways. If you stick with one of them, you have essentially the same rollback probability and cost as you have now.

Let us do a rough calculation. For sake of simplicity, let us assume that handling two pipelines instead of one does not cause additional management overhead. The expected cost (e.g. energy, heat) is $C = c + p(c_r + c)$ with one pipeline ($c$ the cost of executing either alternative, $p$ the probability for rollback and $c_r$ the cost for rollback without the cost for executing the other alternative) but either $2c$ or even $2c + pc_r$ -- either is a lot larger than $C$ if $p$ and $c_r$ are relatively small, and $p$ certainly is (as far as I know, modern branch predictions have accuracies over 90%). And we don't get much for this cost! Expected execution times are $t + p(t_r + t)$ with one pipeline and $t$ resp. $t + pt_r$ with two; as $p$ is small, time savings are negligible.

share|improve this answer

In one sense, the effect of branch prediction is more critical in the fetching of instructions since an instruction which is not fetched cannot be executed.

With respect to executing both paths of a branch, this is called eager execution and has been researched somewhat substantially. Augustus K. Uht and Vijay Sindagi's "Disjoint Eager Execution: An Optimal Form of Speculative Execution" (1995) might be a worth a look.

Eager execution has several problems. For deep speculation, the number of paths that must be tracked can grow exponentially (each forked branch path may encounter a branch). Branch prediction is also often very accurate (>90% correct), so always executing both paths would be wasteful. Eager execution can also "contaminate" caches with useless content. (The above mentioned paper proposed intelligently limited eager execution to avoid some of these issues.) Limited eager fetching the alternate path has fewer issues and can be somewhat attractive in reducing misprediction recovery delay in shorter pipelines.

Another approach that has been proposed is dynamically predicating "hammock" branches (short forward branches that join back to the main path of instruction flow). Artur Klauser et al.'s "Dynamic Hammock Predication for Non-predicated Instruction Set Architectures" (1998) might be worth a read for that idea. (Hyesoon Kim et al.'s "Wish Branches: Combining Conditional Branching and Predication for Adaptive Predicated Execution" proposes adding to an ISA branches which facilitate predication of hammocks and extends this method of predication to hard-to-predict loop branches.)

share|improve this answer
    
That is a really nice answer! Thank You. :-) –  Jayesh Badwaik Nov 14 '12 at 4:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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