Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>> Since each chased pointer starts back at LSQ, the cost is no different
>> than an explicit Prefetch instruction, except without (a),(b) and (c)
>> having been applied first.
>
> I thought the important difference is that the decision to prefetch or
> not can be done dynamically based on past history.

Programmers and compilers are notoriously bad at predicting
branches (except for error branches), but ought to be quite good
at predicting prefetches. If a pointer is loaded, chances are
very high that are it will be dereferenced.

Thomas Koenig wrote:

> Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>>> Since each chased pointer starts back at LSQ, the cost is no different
>>> than an explicit Prefetch instruction, except without (a),(b) and (c)
>>> having been applied first.
>>
>> I thought the important difference is that the decision to prefetch or
>> not can be done dynamically based on past history.

> Programmers and compilers are notoriously bad at predicting
> branches (except for error branches),

Which are always predicted to have no error.

> but ought to be quite good
> at predicting prefetches.

What makes you think programmers understand prefetches any better than
exceptions ??
> If a pointer is loaded, chances are
> very high that are it will be dereferenced.

What if the value loaded is NULL.

MitchAlsup1 <mitchalsup@aol.com> schrieb:
> Thomas Koenig wrote:
>
>> Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>>>> Since each chased pointer starts back at LSQ, the cost is no different
>>>> than an explicit Prefetch instruction, except without (a),(b) and (c)
>>>> having been applied first.
>>>
>>> I thought the important difference is that the decision to prefetch or
>>> not can be done dynamically based on past history.
>
>> Programmers and compilers are notoriously bad at predicting
>> branches (except for error branches),
>
> Which are always predicted to have no error.

On the second or third time, certainly. Hmmm... given hot/cold
splitting which is fairly standard by now, do branch predictors
take this into account?

>> but ought to be quite good
>> at predicting prefetches.
>
> What makes you think programmers understand prefetches any better than
> exceptions ??

Pointers are used in many common data structures; linked list,
trees, ... A programmer who does not know about dereferencing
pointers should be kept away from computer keyboards, preferably
at a distance of at least 3 m.

>
>> If a pointer is loaded, chances are
>> very high that are it will be dereferenced.
>
> What if the value loaded is NULL.

Then it should be trivially predicted that it should not be prefetched.

Thomas Koenig wrote:

> MitchAlsup1 <mitchalsup@aol.com> schrieb:
>> Thomas Koenig wrote:
>>
>>> Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>>>>> Since each chased pointer starts back at LSQ, the cost is no different
>>>>> than an explicit Prefetch instruction, except without (a),(b) and (c)
>>>>> having been applied first.
>>>>
>>>> I thought the important difference is that the decision to prefetch or
>>>> not can be done dynamically based on past history.
>>
>>> Programmers and compilers are notoriously bad at predicting
>>> branches (except for error branches),
>>
>> Which are always predicted to have no error.

There I mean that the programmer wrote the code::

if( no error so far )
{
then continue
}
else
{
deal with the error
}

Many times, the "deal with the error" code is never even fetched.

> On the second or third time, certainly. Hmmm... given hot/cold
> splitting which is fairly standard by now, do branch predictors
> take this into account?

First we are talking about predicting branches at compile time and
the way the programmer writes the source code, not about the dynamic
predictions of HW.

Given that it is compile time, one either predicts it is taken
(loops) or not taken (errors and initialization) and arrange
the code such that fall through is the predicted pattern (except
for loops).

Then at run time, all these branches are predicted with the standard
predictors present in the core.
Initialization stuff is mispredicted once or twice
error code is only mispredicted when an error occurs
loops are mispredicted once or twice per entrance.

Also note:: With an ISA like My 66000, one can preform branching using
predication and neither predict the branch nor modify where FETCH is
fetching. Ideally, predication should deal with hard to predict branches
and all flow control where the then and else clauses are short. When
these are removed from the predictor, prediction should improve--maybe
not in the number of predictions that are correct, but in the total time
wasted on branching (including both repair and misfetching overheads).

>>> but ought to be quite good
>>> at predicting prefetches.
>>
>> What makes you think programmers understand prefetches any better than
>> exceptions ??

> Pointers are used in many common data structures; linked list,
> trees, ... A programmer who does not know about dereferencing
> pointers should be kept away from computer keyboards, preferably
> at a distance of at least 3 m.

3Km ??

>>
>>> If a pointer is loaded, chances are
>>> very high that are it will be dereferenced.
>>
>> What if the value loaded is NULL.

> Then it should be trivially predicted that it should not be prefetched.

mitchalsup@aol.com (MitchAlsup1) writes:
>Thomas Koenig wrote:
>
>> MitchAlsup1 <mitchalsup@aol.com> schrieb:
>>> Thomas Koenig wrote:
>>>
>>>> Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>>>>>> Since each chased pointer starts back at LSQ, the cost is no different
>>>>>> than an explicit Prefetch instruction, except without (a),(b) and (c)
>>>>>> having been applied first.
>>>>>
>>>>> I thought the important difference is that the decision to prefetch or
>>>>> not can be done dynamically based on past history.
>>>
>>>> Programmers and compilers are notoriously bad at predicting
>>>> branches (except for error branches),
>>>
>>> Which are always predicted to have no error.
>
>There I mean that the programmer wrote the code::
>
> if( no error so far )
> {
> then continue
> }
> else
> {
> deal with the error
> }
>
>Many times, the "deal with the error" code is never even fetched.
>
>> On the second or third time, certainly. Hmmm... given hot/cold
>> splitting which is fairly standard by now, do branch predictors
>> take this into account?
>
>First we are talking about predicting branches at compile time and
>the way the programmer writes the source code, not about the dynamic
>predictions of HW.

gcc provides a way to "annotate" a condition with the expected
common result:

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

if (likely(bus_enable.s.enabled)) {
do something
} else {
do something else
}

This will affect the layout of the code (e.g. deferring generation
of the else clause with the result that it ends up in a different
cache line or page).

It's used in the linux kernel, and in certain cpu bound applications.

Scott Lurndal wrote:

> mitchalsup@aol.com (MitchAlsup1) writes:
>>Thomas Koenig wrote:
>>
>>> MitchAlsup1 <mitchalsup@aol.com> schrieb:
>>>> Thomas Koenig wrote:
>>>>
>>>>> Stefan Monnier <monnier@iro.umontreal.ca> schrieb:
>>>>>>> Since each chased pointer starts back at LSQ, the cost is no different
>>>>>>> than an explicit Prefetch instruction, except without (a),(b) and (c)
>>>>>>> having been applied first.
>>>>>>
>>>>>> I thought the important difference is that the decision to prefetch or
>>>>>> not can be done dynamically based on past history.
>>>>
>>>>> Programmers and compilers are notoriously bad at predicting
>>>>> branches (except for error branches),
>>>>
>>>> Which are always predicted to have no error.
>>
>>There I mean that the programmer wrote the code::
>>
>> if( no error so far )
>> {
>> then continue
>> }
>> else
>> {
>> deal with the error
>> }
>>
>>Many times, the "deal with the error" code is never even fetched.
>>
>>> On the second or third time, certainly. Hmmm... given hot/cold
>>> splitting which is fairly standard by now, do branch predictors
>>> take this into account?
>>
>>First we are talking about predicting branches at compile time and
>>the way the programmer writes the source code, not about the dynamic
>>predictions of HW.

> gcc provides a way to "annotate" a condition with the expected
> common result:

> #define likely(x) __builtin_expect(!!(x), 1)
> #define unlikely(x) __builtin_expect(!!(x), 0)

> if (likely(bus_enable.s.enabled)) {
> do something
> } else {
> do something else
> }

> This will affect the layout of the code (e.g. deferring generation
> of the else clause with the result that it ends up in a different
> cache line or page).

> It's used in the linux kernel, and in certain cpu bound applications.

Thank you for pointing this out.

>>> Since each chased pointer starts back at LSQ, the cost is no different
>>> than an explicit Prefetch instruction, except without (a),(b) and (c)
>>> having been applied first.
>> I thought the important difference is that the decision to prefetch or
>> not can be done dynamically based on past history.
> Programmers and compilers are notoriously bad at predicting
> branches (except for error branches), but ought to be quite good
> at predicting prefetches. If a pointer is loaded, chances are
> very high that are it will be dereferenced.

I don't think it's that simple: prefetches only bring the data into L1
cache, so they're only useful if:

- The data is not already in L1.
- The data will be used soon (i.e. before it gets thrown away from the cache).
- The corresponding load doesn't occur right away.

In all other cases, the prefetch will be just wasted work.

It's easy for programmers to "predict" those (dependent) loads which will occur
right away, but those don't really benefit from a prefetch.
E.g. if the dependent load is done 2 cycles later, performing a prefetch
lets you start the memory access 2 cycles early, but since that access
is not in L1 it'll take more than 10 cycles, so shaving
2 cycles off isn't of great benefit.

Given that we're talking about performing a prefetch on the result of
a previous load, and loads tend to already have a fairly high latency
(3-5 cycles), "2 cycles later" really means "5-7 cycles after the
beginning of the load of that pointer". That can easily translate to 20
instructions later.

My gut feeling is that it's difficult for programmers to predict what
will happen more than 20 instructions further without looking at
detailed profiling.

Stefan

Stefan Monnier wrote:

>>>> Since each chased pointer starts back at LSQ, the cost is no different
>>>> than an explicit Prefetch instruction, except without (a),(b) and (c)
>>>> having been applied first.
>>> I thought the important difference is that the decision to prefetch or
>>> not can be done dynamically based on past history.
>> Programmers and compilers are notoriously bad at predicting
>> branches (except for error branches), but ought to be quite good
>> at predicting prefetches. If a pointer is loaded, chances are
>> very high that are it will be dereferenced.

> I don't think it's that simple: prefetches only bring the data into L1
> cache, so they're only useful if:

> - The data is not already in L1.
> - The data will be used soon (i.e. before it gets thrown away from the cache).
> - The corresponding load doesn't occur right away.

> In all other cases, the prefetch will be just wasted work.

> It's easy for programmers to "predict" those (dependent) loads which will occur
> right away, but those don't really benefit from a prefetch.
> E.g. if the dependent load is done 2 cycles later, performing a prefetch
> lets you start the memory access 2 cycles early, but since that access
> is not in L1 it'll take more than 10 cycles, so shaving
> 2 cycles off isn't of great benefit.

> Given that we're talking about performing a prefetch on the result of
> a previous load, and loads tend to already have a fairly high latency
> (3-5 cycles), "2 cycles later" really means "5-7 cycles after the
> beginning of the load of that pointer". That can easily translate to 20
> instructions later.

> My gut feeling is that it's difficult for programmers to predict what
> will happen more than 20 instructions further without looking at
> detailed profiling.

Difficult becomes impossible when the code has to operate "well" over
a range of implementations. {{With some suitable definition of "well"}}

Consider deciding how far into the future (counting instructions) a
prefetch has to be placed so that the data arrives before use. Then
consider the smallest execution window is 16 instructions and the
largest execution window is 300 instructions; and you want the same
code to be semi-optimal on both.

> Stefan

On 4/4/24 4:09 PM, MitchAlsup1 wrote:> Thomas Koenig wrote:
[snip]
> Given that it is compile time, one either predicts it is taken
> (loops) or not taken (errors and initialization) and arrange
> the code such that fall through is the predicted pattern (except
> for loops).

"Boolean Formula-based Branch Prediction for Future Technologies"
(Daniel A. Jiménez et al., 2001) presents a mechanism for branch
prediction based on a static formula using global history, so *in
theory* a compiler could provide more than just taken/not-taken
predictions. ("Static Methods in Hybrid Branch Prediction", Dirk
Grunwald et al., 1998, proposed static predictor selection,
removing the selector table; Donald Lindsay, the second author of
that paper, had a PhD thesis "Static Methods in Branch Prediction".)

(A static prediction can also be used only for an agree predictor.
It is even conceivable that the dominant direction might not be
the best static agreeing prediction; e.g., if aliases would train
to an agree/disagree state that more often mispredicts the branch
[and the branch has few global entries]. Such would be a very
fragile optimization requiring considerable analysis, so it seems
very unlikely to be practical. [I have wondered if a hash of the
branch address might be XORed with predictor bits to provide a
quasi-tagging. XORing with the prediction could cause the most
interference, good for destructive aliasing; XORing with counter
or hysteresis bits would seem to moderate interfence, allowing a
prediction to be stable such that a selector would tranfer a
mispredicting branch to another table. If an expected/agree sense
was available, such tagging might be more useful.])

> Then at run time, all these branches are predicted with the
standard
> predictors present in the core.
> Initialization stuff is mispredicted once or twice

Or not at all if BTB miss generates a correct predict not taken.
(Even without that mechanism, a first encounter might be
correctly predicted by accident.)

> error code is only mispredicted when an error occurs
> loops are mispredicted once or twice per entrance.

Or never mispredicted for only-counted loops for which the
counter value is available early enough in the pipeline. (Gshare
can also predict loop exit/entry correctly for small loop counts
with few internal branches. TAGE can do better.)

> Also note:: With an ISA like My 66000, one can preform
branching using
> predication and neither predict the branch nor modify where
FETCH is
> fetching. Ideally, predication should deal with hard to predict
branches
> and all flow control where the then and else clauses are short.
When
> these are removed from the predictor, prediction should
improve--maybe
> not in the number of predictions that are correct, but in the
total time
> wasted on branching (including both repair and misfetching
overheads).

Rarely-executed blocks should presumably use branches even when
short to remove the rarely-executed code from the normal
instruction stream. I would guess that exceptional actions are
typically longer/more complicated.

(Consistent timing would also be important for some real-time
tasks and for avoiding timing side channels.)

The best performing choice would also seem to be potentially
microarchitecture-dependent. Obviously the accuracy of branch
prediction and the cost of aliasing would matter (and
perversely mispredicting a branch can _potentially_ improve
performance, though not on My 66000, I think, because more
persistent microarchitectural state is not updated until
instruction commitment).

If the predicate value is delayed and predicated operations
wait in the scheduler for this operand and the operands of one
path are available before the predicate value, branch prediction
might allow deeper speculation. For highly dynamically
predictable but short branches, deeper speculation might help
more than fetch irregularity hurts. (The predicate could be
predicted — and this prediction is needed later in the pipeline —
but not distinguishing between prediction-allowed predication
and normal predication might prevent prediction from being
implemented to avoid data-dependent timing of predication.)

(The cost of speculation can also be variable. With underutilized
resources (thermal, memory bandwidth, etc.) speculation would
generally be less expensive than with high demand on resources.)

Paul A. Clayton wrote:

> On 4/4/24 4:09 PM, MitchAlsup1 wrote:> Thomas Koenig wrote:
> [snip]

> > Also note:: With an ISA like My 66000, one can preform
> branching using
> > predication and neither predict the branch nor modify where
> FETCH is
> > fetching. Ideally, predication should deal with hard to predict
> branches
> > and all flow control where the then and else clauses are short.
> When
> > these are removed from the predictor, prediction should
> improve--maybe
> > not in the number of predictions that are correct, but in the
> total time
> > wasted on branching (including both repair and misfetching
> overheads).

> Rarely-executed blocks should presumably use branches even when
> short to remove the rarely-executed code from the normal
> instruction stream. I would guess that exceptional actions are
> typically longer/more complicated.

If you will arrive at the join point by simply fetching there
is no reason to use a branch.

> (Consistent timing would also be important for some real-time
> tasks and for avoiding timing side channels.)

Predication is closer to fixed timing than any branching.

> The best performing choice would also seem to be potentially
> microarchitecture-dependent. Obviously the accuracy of branch
> prediction and the cost of aliasing would matter (and
> perversely mispredicting a branch can _potentially_ improve
> performance, though not on My 66000, I think, because more
> persistent microarchitectural state is not updated until
> instruction commitment).

While not committed, it is still available.

> If the predicate value is delayed and predicated operations
> wait in the scheduler for this operand and the operands of one
> path are available before the predicate value, branch prediction
> might allow deeper speculation.

Just like data forwarding, branch prediction forwarding is
easily achieved in the pipeline.

< For highly dynamically
> predictable but short branches, deeper speculation might help
> more than fetch irregularity hurts.

What can possibly be more regular than constant time ??

> (The predicate could be
> predicted — and this prediction is needed later in the pipeline —

One HAS TO assume that GBOoO machines will predict predicates.

> but not distinguishing between prediction-allowed predication
> and normal predication might prevent prediction from being
> implemented to avoid data-dependent timing of predication.)

> (The cost of speculation can also be variable. With underutilized
> resources (thermal, memory bandwidth, etc.) speculation would
> generally be less expensive than with high demand on resources.)