Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What is Branch Prediction?

stackoverflow.com

Post reply on HN
Print view View original

21–30 of 31 posts

Re: What is Branch Prediction?

#21

Post by vvhn »

vault_ wrote: post #18
infogulch wrote: post #14

Question: can a processor have two pipelines? When there's a branch it would be able to start loading both branches and just switch the pipeline when the final branch is determined. It might still need to flush the pipelines when there are several branches in succession but you'd still be able to use branch prediction to predict the two most likely branches, which would help tremendously.

This is basically what computers do, it's called speculative execution. Modern computers actually have several pipelines, each for a different function. This is what makes a computer "superscalar". Basically, the CPU tries to keep the pipelines of all of the execution units filled at all times. If it's able to, it will schedule both sides of a branch to be executed, and flush out whichever half wasn't used.

speculative execution and superscalar are independent concepts. While superscalar does effectively mean multiple pipelines, you don't have to be superscalar for speculative execution. You can reduce pipeline stalls in a single pipeline by "speculating" right as well. The concept that GP is talking was a feature of of Itanium.

http://en.wikipedia.org/wiki/Explicitly_parallel_instruction...

" The EPIC architecture also includes a grab-bag of architectural concepts to increase ILP:

Predicated execution is used to decrease the occurrence of branches and to increase the speculative execution of instructions. In this feature, branch conditions are converted to predicate registers which are used to kill results of executed instructions from the side of the branch which is not taken. . . . Multi-way branch instructions improve branch prediction by combining many alternative branches into one bundle. "

Re: What is Branch Prediction?

#22

Post by wmf »

vault_ wrote: post #18
infogulch wrote: post #14

Question: can a processor have two pipelines? When there's a branch it would be able to start loading both branches and just switch the pipeline when the final branch is determined. It might still need to flush the pipelines when there are several branches in succession but you'd still be able to use branch prediction to predict the two most likely branches, which would help tremendously.

This is basically what computers do, it's called speculative execution. Modern computers actually have several pipelines, each for a different function. This is what makes a computer "superscalar". Basically, the CPU tries to keep the pipelines of all of the execution units filled at all times. If it's able to, it will schedule both sides of a branch to be executed, and flush out whichever half wasn't used.

Generally speculation only executes one side of the branch. Speculative threading has been proposed using SMT to execute both sides, but usually you're better off trusting the branch predictor and using threads as non-speculative state.

Re: What is Branch Prediction?

#23

Post by onan_barbarian »

wmf wrote: post #22
vault_ wrote: post #18

Earlier quoted context omitted.

This is basically what computers do, it's called speculative execution. Modern computers actually have several pipelines, each for a different function. This is what makes a computer "superscalar". Basically, the CPU tries to keep the pipelines of all of the execution units filled at all times. If it's able to, it will schedule both sides of a branch to be executed, and flush out whichever half wasn't used.

Generally speculation only executes one side of the branch. Speculative threading has been proposed using SMT to execute both sides, but usually you're better off trusting the branch predictor and using threads as non-speculative state.

Speculation down both sides is independent of SMT and if I remember correct there were proposals to do this - especially where the branch predictor "knew" it wasn't doing a good job on a branch (no point going down both sides of a 99.9% predicted branch).

The problem is that you rapidly run out of execution resources (what if there are more branches to follow, for example) and you will burn lots of energy executing things that don't happen (not to mention speculatively loading things that aren't needed, etc). I remember seeing some papers on the limits of ILP and I think this was one of the 'extreme' ideas (speculation down multiple paths).

Re: What is Branch Prediction?

#25

Post by pavanky »

stephengillie wrote: post #9
alexkus wrote: post #6

Earlier quoted context omitted.

Karma whoring.

I notice ralphchurch's name is green. That means recently registered, right?

Thanks for asking the question. I noticed the color was different, but wasn't too sure which color it was because of my colorblindness..

Re: What is Branch Prediction?

#26

Post by aaron695 »

mistercow wrote: post #17
alexkus wrote: post #6

Earlier quoted context omitted.

Karma whoring.

Does anybody actually care about karma on HN? If so, why?

Same reason as why we want money? We see it as a proxy for power.

Why do people want power? Evolutionary reasons.

Probably for men we see it as a way to reproduce a lot for women it's probably seen as a way to ensure their children are successful and reproduce.

It gets a bit depressing if you think about it to much. Just enjoy life and accept things.

Re: What is Branch Prediction?

#27

Post by speeder »

jere wrote: post #11
stephengillie wrote: post #9

Earlier quoted context omitted.

I notice ralphchurch's name is green. That means recently registered, right?

I believe so. And they have posted 5 stackoverflow questions in 11 days. IIRC, this is called Power Leveling.

the funny thing is I tried this YESTERDAY even this same post, I wonder how he managed to post a duplicate...

and I did it to test if it would work, and it did not worked, and now it worked.. :/

now I guess that spamming SO does work after all.

Re: What is Branch Prediction?

#29

Post by mistercow »

aaron695 wrote: post #26
mistercow wrote: post #17

Earlier quoted context omitted.

Does anybody actually care about karma on HN? If so, why?

Same reason as why we want money? We see it as a proxy for power. Why do people want power? Evolutionary reasons. Probably for men we see it as a way to reproduce a lot for women it's probably seen as a way to ensure their children are successful and reproduce. It gets a bit depressing if you think about it to much. Just enjoy life and accept things.

But we don't just see money as a proxy for power. It is the closest proxy for power there is. HN karma, on the other hand, is barely a proxy for power at all.

Re: What is Branch Prediction?

#30

Post by wmf »

onan_barbarian wrote: post #23
wmf wrote: post #22

Earlier quoted context omitted.

Generally speculation only executes one side of the branch. Speculative threading has been proposed using SMT to execute both sides, but usually you're better off trusting the branch predictor and using threads as non-speculative state.

Speculation down both sides is independent of SMT and if I remember correct there were proposals to do this - especially where the branch predictor "knew" it wasn't doing a good job on a branch (no point going down both sides of a 99.9% predicted branch). The problem is that you rapidly run out of execution resources (what if there are more branches to follow, for example) and you will burn lots of energy executing t…

To execute both sides, the fetch unit needs to have multiple program counters which is essentially a form of SMT.
Post reply on HN