FPGA Central

Hi,

today's DSP often use a static branch predictor instead of dynamic ones
to safe energy and improve predictability. The predicted outcome
of a jump depends on the instruction, i.e. a 16-bit conditional jump
instruction is predicted as taken while a 32-bit instruction with a
forward displacement is predicted as not taken.

If the outcome of a jump would be known in advance, one could use the
appropriate jump instructions to avoid misprediction, thus
accelerating the program execution. I assume that profiling data could
be used for that to figure out the more probable jump behavior.

This idea is probably not new, so I wonder if you know any
compilers/optimizers that apply this technique? Do you have own
experiences or know any papers/reports where any results are
presented?

Regards,
Tim

"Tim Frink" <[email protected]> wrote in message
news:[email protected]..
> Hi,
>
> If the outcome of a jump would be known in advance, one could use the
> appropriate jump instructions to avoid misprediction, thus
> accelerating the program execution. I assume that profiling data could
> be used for that to figure out the more probable jump behavior.
>
> This idea is probably not new, so I wonder if you know any
> compilers/optimizers that apply this technique? Do you have own
> experiences or know any papers/reports where any results are
> presented?

VDSP++ allows giving the compiler a hint if a conditional statement is
usually true or false. The compiler arranges the instructions so the most
likely path is executed faster. In my experience, it doesn't make much
difference.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com

Tim Frink wrote:
> Hi,
>
> today's DSP often use a static branch predictor instead of dynamic ones
> to safe energy and improve predictability. The predicted outcome
> of a jump depends on the instruction, i.e. a 16-bit conditional jump
> instruction is predicted as taken while a 32-bit instruction with a
> forward displacement is predicted as not taken.
>
> If the outcome of a jump would be known in advance, one could use the
> appropriate jump instructions to avoid misprediction, thus
> accelerating the program execution. I assume that profiling data could
> be used for that to figure out the more probable jump behavior.
>
> This idea is probably not new, so I wonder if you know any
> compilers/optimizers that apply this technique? Do you have own
> experiences or know any papers/reports where any results are
> presented?

If you know in advance the outcome of a conditional branch, what is its
purpose?

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

On Mar 5, 7:42 am, Jerry Avins <j...@ieee.org> wrote:
> Tim Frink wrote:
> > Hi,
>
> > today's DSP often use a static branch predictor instead of dynamic ones
> > to safe energy and improve predictability. The predicted outcome
> > of a jump depends on the instruction, i.e. a 16-bit conditional jump
> > instruction is predicted as taken while a 32-bit instruction with a
> > forward displacement is predicted as not taken.
>
> > If the outcome of a jump would be known in advance, one could use the
> > appropriate jump instructions to avoid misprediction, thus
> > accelerating the program execution. I assume that profiling data could
> > be used for that to figure out the more probable jump behavior.
>
> > This idea is probably not new, so I wonder if you know any
> > compilers/optimizers that apply this technique? Do you have own
> > experiences or know any papers/reports where any results are
> > presented?
>
> If you know in advance the outcome of a conditional branch, what is its
> purpose?

Ones accuracy of knowing the outcome of a conditional branch
only needs to reach a certain probability for that
optimization to be helpful, on average, over some number of
branches. Many optimization methods (both hardware and
software) accelerate statistical biases in the benchmark
suites and profiling data sets used during their development
(which one hopes, but cannot guarantee, are sufficiently
similar in any actual running application). But these types
of data dependent optimizations make life a pain for hard
real-time development is situations where those statistics
cannot be absolutely guaranteed. Maybe Jerry is referring
to that types of development?



IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

Ron N. wrote:
> On Mar 5, 7:42 am, Jerry Avins <j...@ieee.org> wrote:
>> Tim Frink wrote:
>>> Hi,
>>> today's DSP often use a static branch predictor instead of dynamic ones
>>> to safe energy and improve predictability. The predicted outcome
>>> of a jump depends on the instruction, i.e. a 16-bit conditional jump
>>> instruction is predicted as taken while a 32-bit instruction with a
>>> forward displacement is predicted as not taken.

>>> If the outcome of a jump would be known in advance, one could use the
>>> appropriate jump instructions to avoid misprediction, thus
>>> accelerating the program execution. I assume that profiling data could
>>> be used for that to figure out the more probable jump behavior.

>>> This idea is probably not new, so I wonder if you know any
>>> compilers/optimizers that apply this technique? Do you have own
>>> experiences or know any papers/reports where any results are
>>> presented?

>> If you know in advance the outcome of a conditional branch, what is its
>> purpose?
>
> Ones accuracy of knowing the outcome of a conditional branch
> only needs to reach a certain probability for that
> optimization to be helpful, on average, over some number of
> branches. Many optimization methods (both hardware and
> software) accelerate statistical biases in the benchmark
> suites and profiling data sets used during their development
> (which one hopes, but cannot guarantee, are sufficiently
> similar in any actual running application). But these types
> of data dependent optimizations make life a pain for hard
> real-time development is situations where those statistics
> cannot be absolutely guaranteed. Maybe Jerry is referring
> to that types of development?

I was, but I misled myself with too quick a reading of "If the outcome
of a jump would be known in advance, ...." Hard real-time systems have
little place for statistical inference except when the number of cases
are similar to those in the gas laws.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

On 2008-03-05, Jerry Avins <[email protected]> wrote:
>
> I was, but I misled myself with too quick a reading of "If the outcome
> of a jump would be known in advance, ...." Hard real-time systems have
> little place for statistical inference except when the number of cases
> are similar to those in the gas laws.

The measurement may be statistical, but you can still have concrete
results. For example, let's say you call a function f(x) from an inner
loop and that loop always goes from 0..255. A test `if (x > 200)' should
be statically predicted to be not taken. Then the total cost of that
loop is always less than it was with a wrong prediction. You might *find*
that case by measuring statistics, since the compiler is unlikely to find
such a case automatically. You would expect the compiler to automatically
get the static prediction right on the loop itself.

GCC provides a way to hint with the __builtin_expect() pseudo-function.
A lot of code wraps those with 'likely()' and 'unlikely()' macros.

--
Ben Jackson AD7GD
<[email protected]>
http://www.ben.com/

Jerry Avins wrote:


> Hard real-time systems have
> little place for statistical inference except when the number of cases
> are similar to those in the gas laws.

In the real systems, there are many checks for the special situations
like overflow, out of range, if something wrong, if not initialized,
etc. It is very unlikely that a branch is going to be taken, however you
have to check the condition anyway. In this case, the static branch
prediction can save dozens of the CPU cycles on every check at the
average. However the hard realtime systems are designed to satisfy the
timing for the worst case, not at the average. Hence there is a little
benefit.

Also, the modern CPUs will fetch the code in the right direction if the
conditional statement is evaluated several cycles before the branch
instruction. So the compiler is trying to arrange the code like that:

r0 = fu;
r1 = bar;
cc = r0 < r1 (iu); // Check condition
p0 = [sp++]; // Do something else
r2 = r1;
r1 = r1 + r0;
r0 = blablabla;
if cc jump label; // Branch predicted because the condition is known in
advance

This minimizes the stalls of the pipeline due to the mispredictions, so
there is little or no advantage if you give hints to the compiler.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com