| Author |
Message |
gnncj
Guest
|
 Posted:
Fri Nov 11, 2005 5:15 pm Post subject:
Why forward branch false and backward branch true? |
|
|
Hi all,
When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
Thank you very much! |
|
| Back to top |
|
 |
Tom Truscott
Guest
|
| Posted:
Fri Nov 11, 2005 5:15 pm Post subject:
Re: Why forward branch false and backward branch true? |
|
|
| Quote: | When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
|
Because it difficult to predict the future, but hindsight is 20/20. |
|
| Back to top |
|
|
Andy Freeman
Guest
|
| Posted:
Fri Nov 11, 2005 5:15 pm Post subject:
Re: Why forward branch false and backward branch true? |
|
|
| Quote: | When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
|
Patents. |
|
| Back to top |
|
|
Finn Schiermer Andersen
Guest
|
| Posted:
Fri Nov 11, 2005 10:13 pm Post subject:
Re: Why forward branch false and backward branch true? |
|
|
"Dennis M. O'Connor" <dmoc@primenet.com> writes:
| Quote: | "Andy Freeman" <anamax@earthlink.net> wrote ...
When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
Patents.
No, they've all expired. It's done because the instructions behind
you are more likely to be in the instruction cache. See, why bother
predicting a branch to code that is probably going to take
a lot of cycles to fetch, during which the CPU does nothing ?
Plus, fetching instructions you don't need is a waste of power.
--
Dennis M. O'Connor dmoc@primenet.com
|
Nice one ;-)
/Finn |
|
| Back to top |
|
|
Patrick Schaaf
Guest
|
| Posted:
Fri Nov 11, 2005 11:47 pm Post subject:
Re: Why forward branch false and backward branch true? |
|
|
"gnncj" <linziheng@gmail.com> writes:
| Quote: | When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
|
Assume that the most common branch is the branch involved in loop
bounds checking, executed once per iteration of the loop. Further
assume that most loops have more than two iterations.
Think about this branch for loops which have their bounds check
up front, at the top of the loop. This should give you an understanding
of the choice for the forward case.
Think about this branch for loops which have their bounds check
at the end. This should give you an understanding of the choice
for the backward case.
best regards
Patrick |
|
| Back to top |
|
|
Peter \"Firefly\" Lund
Guest
|
| Posted:
Sat Nov 12, 2005 12:07 am Post subject:
Re: Why forward branch false and backward branch true? |
|
|
On Fri, 11 Nov 2005, gnncj wrote:
| Quote: | When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
|
Because progress is difficult and hard to make sometimes, so in order to
conserve power the CPU predicts that it won't (usually) happen. Like
people, CPUs are conservative.
-Peter
The cheapest, fastest, and most reliable components of a computer system
are those that aren't there.
--Gordon Bell |
|
| Back to top |
|
|
Guest
|
| Posted:
Sat Nov 12, 2005 1:15 am Post subject:
Re: Why forward branch false and backward branch true? |
|
|
Patrick Schaaf wrote:
[snip]
| Quote: | Assume that the most common branch is the branch involved in loop
bounds checking, executed once per iteration of the loop. Further
assume that most loops have more than two iterations.
|
The first assumption seems untenable, especially in the forward
branch case.
For non-loop-terminating forward branches, one might choose
a predict-not-taken strategy to avoid flushing the fall through
instructions from the pipeline (assuming the architecture does
not have enough branch delay slots to hide the time between
when an address is needed to fetch the next instruction[s] and
when the branch is detected, predicted, and the target address
predicted/calculated). If the programmer/compiler is aware of
a particular branch's bias, such a prediction strategy allows
the unlikely to be executed code to be moved out of the cache
block (increasing effective cache capacity) or even out of the
current page (reducing TLB misses); this also increases
effective fetch bandwidth when wider fetching is done in a
simple cache (wider fetch can be desirable even in a scalar
implementation to reduce power consumption or to provide
cache idle times which can be used for cache filling).
Paul A. Clayton
just a technophile |
|
| Back to top |
|
|
Dennis M. O'Connor
Guest
|
| Posted:
Sat Nov 12, 2005 1:15 am Post subject:
Re: Why forward branch false and backward branch true? |
|
|
"Andy Freeman" <anamax@earthlink.net> wrote ...
| Quote: | When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
Patents.
|
No, they've all expired. It's done because the instructions behind
you are more likely to be in the instruction cache. See, why bother
predicting a branch to code that is probably going to take
a lot of cycles to fetch, during which the CPU does nothing ?
Plus, fetching instructions you don't need is a waste of power.
--
Dennis M. O'Connor dmoc@primenet.com |
|
| Back to top |
|
|
Peter \"Firefly\" Lund
Guest
|
| Posted:
Sat Nov 12, 2005 9:15 am Post subject:
Re: Why forward branch false and backward branch true? |
|
|
On Fri, 11 Nov 2005, Dennis M. O'Connor wrote:
| Quote: | predicting a branch to code that is probably going to take
a lot of cycles to fetch, during which the CPU does nothing ?
Plus, fetching instructions you don't need is a waste of power.
|
Like I said, work avoidance (because it is so hard to make progress).
-Peter |
|
| Back to top |
|
|
Dennis M. O'Connor
Guest
|
| Posted:
Sat Nov 12, 2005 9:15 am Post subject:
Re: Why forward branch false and backward branch true? |
|
|
"Peter "Firefly" Lund" <firefly@diku.dk> wrote ...
| Quote: | On Fri, 11 Nov 2005, Dennis M. O'Connor wrote:
predicting a branch to code that is probably going to take
a lot of cycles to fetch, during which the CPU does nothing ?
Plus, fetching instructions you don't need is a waste of power.
Like I said, work avoidance (because it is so hard to make progress).
|
No, no, no. The idea of predicting backward branches true,
because the instructions there are more likely to be in
the cache, is all about trying to do as much work as possible,
not about avoiding work. And the idea of predicting forward
branches false, since the code far ahead is less likely to be in
cache than the very next instruction is, isn't so much about
avoiding work as about avoiding useless busy-work.
Everyone hates useless busy-work, even CPUs.
A well-designed pipeline tries to do as much useful work
as possible. But you want to avoid doing useless work
because that wastes power. You might think this argues
against doing any branch prediction at all. But re-executing
instructions that are already in the cache is very cheap,
power-wise, compared to fetching new instructions. Given that,
it makes sense to predict branches to instructions that
are already in the cache as being taken, especially
when you consider that the clock distribution tree is going
to dissipate power regardless of whether you execute
an instruction or not. And on leaky deep submicron processes,
there's even more reason to predict branches, as long as
you can be pretty sure that the instructions you predict
the branch as going to are already in the cache.
Modern CPU design is all about doing as much useful
work as possible with as little energy as possible, and
as quickly as possible. Back before CPUs needed heatsinks
(much less fan-sinks or water cooling) power wasn't as much
of an issue, and you didn't see the extensive use of
branch prediction we see today. And of course, back
in the days before non-trivial sized I-caches, you didn't see
any branch prediction at all: when no instructions
are in cache, it makes no sense to do branch prediction.
--
Dennis M. O'Connor dmoc@primenet.com |
|
| Back to top |
|
|
Torben Ęgidius Mogensen
Guest
|
| Posted:
Mon Nov 14, 2005 5:15 pm Post subject:
Re: Why forward branch false and backward branch true? |
|
|
"gnncj" <linziheng@gmail.com> writes:
| Quote: | When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
|
If the compiler can see that one way is more likely than the other, it
can arrange the blocks so the static branch prediction will predict
correctly most of the time. So, it is really a way of getting the
effect of a brach prediction bit without using a bit in the
instruction word (effectively providing one more bit for the branch
target address). By why not the other way around? The reason is that
you want the commonly executed block at the beginning of the file, so
you can start executing before everything is loaded in with little
risk of stalling because a branch goes to not-yet-loaded code. This
is related to the cache issue that Dennis O'Connor mentioned.
Torben |
|
| Back to top |
|
|
Guest
|
| Posted:
Tue Nov 15, 2005 12:02 am Post subject:
Re: Why forward branch false and backward branch true? |
|
|
gnncj wrote:
| Quote: | When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
|
Consider that we have only direction as our guide. For the situation
where the direction is forward from the point of the conditional
branch; the likely high level language senario is that we are
processing an If statement. When the direction is backwards we are
likely (highly likely) that we are processing the termination point of
a loop (statement).
Without any branch prediction whatsoever, the probability of 'taking'
that branch is around 70%. By separating backwards branches from
forward branches, we end up with better statistics, 85%-ish of
backwards branches are 'taken' while much closer to 50% of forward
branches are 'taken'.
Forward branches have the probability that some of the fetch and
decoder pipeline work will survive the forward branch so it is worth
setting up the pipeline for this case. In the backwards branch case,
vey little of the work that can be setup by the fetch and decode
pipeline in the forward direction ends up being useful.
So, it is more benefitial (without information to the contrary) to
'guess' that backwards branches are 'taken' and that forward branches
are not 'taken'. So predicting backwards branches is A) easy, B)
productive. Predicting forward branches is fraught with peril unless
some other mechanism is available to guide the selection between
'taken' and not 'taken'. Thus branch predictors were born (late 1980's)
and then got really good in the late 9990's.
Back in the days before caches (360-85) higher end processors used
instructions buffers to smooth the flow of instructions through the
decoder pipeline. Backwards branches would check the instruction buffer
for hits and not have the latency to main memory in the case that the
IB generates the required instructions--also saving time. Notice that
(essentially) ONLY backwards branches had (much of) an opportunity to
find instructions in the IB, so predicting backwards branches 'taken'
optimized performance. At this point in time, predicting forward
branches did not generally do anything positive for the pipeline
processes. |
|
| Back to top |
|
|
John Savard
Guest
|
| Posted:
Tue Nov 15, 2005 8:13 am Post subject:
Re: Why forward branch false and backward branch true? |
|
|
On 11 Nov 2005 08:53:43 -0800, "gnncj" <linziheng@gmail.com> wrote, in
part:
| Quote: | When we are using a static prediction, why do we predict forward branch
as false and backward branch as true, but not the other way round
(forward true and backward false)?
|
Backward branches are most often...
FOR I = 1 TO 100
....
NEXT I
used to implement loops. Thus, the conditional branch at "NEXT I" is
true 99 times, and then false on the 100th time.
Forwards branches are _sometimes_ used for an early exit from a loop,
which is rare. Other times, they're just ordinary conditional branches,
with a 50/50 chance of being true. So false is slightly favored.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
http://www.quadibloc.com/index.html
_________________________________________
Usenet Zone Free Binaries Usenet Server
More than 140,000 groups
Unlimited download
http://www.usenetzone.com to open account |
|
| Back to top |
|
|
Torben Ęgidius Mogensen
Guest
|
| Posted:
Tue Nov 15, 2005 5:15 pm Post subject:
Re: Why forward branch false and backward branch true? |
|
|
MitchAlsup@aol.com writes:
| Quote: | Without any branch prediction whatsoever, the probability of 'taking'
that branch is around 70%.
|
I recall seeing a paper about an early version of AMULET (an
asynchroneous ARM), where they added a 1-bit dynamic branch
prediction. The remark was something to the effect of "Before adding
this, we had a branch mispredict of around 65%, which by the addition
was reversed to a 65% correct prediction rate". I wondered at the
time why they didn't just predict all branches taken. :-)
Torben |
|
| Back to top |
|
|
Ian Rogers
Guest
|
| Posted:
Tue Nov 15, 2005 5:15 pm Post subject:
Re: Why forward branch false and backward branch true? |
|
|
Torben Ęgidius Mogensen wrote:
| Quote: | I recall seeing a paper about an early version of AMULET (an
asynchroneous ARM), where they added a 1-bit dynamic branch
prediction. The remark was something to the effect of "Before adding
this, we had a branch mispredict of around 65%, which by the addition
was reversed to a 65% correct prediction rate". I wondered at the
time why they didn't just predict all branches taken. :-)
|
I think you are refering to Richard York's MSc thesis:
http://www.cs.manchester.ac.uk/apt/publications/thesis/york94_msc.php
The history of the Amulet processors is available here:
http://www.cs.manchester.ac.uk/apt/projects/processors/amulet/
The Amulet 1 was a proof of concept asynchronous ARM processor. The
Amulet 2 processor improved upon the Amulet 1 by adding branch
prediction. The branch prediction hit rate was > 85% in the Amulet 2.
The Amulet 1 always predicted that branches weren't taken for
simplicity. This led to a branch mispredict rate of slightly over 65%
and wasn't ideal, hence it was improved :-)
Ian Rogers |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in