Hi all,
branch predictors and data prefetchors are usually evaluated by
considering a single task: the fixed benchmark is the unique program
executed for evaluating the efficiency of the hardware data prefetchor
or the branch predictor.

With the multicore era, desktop and servers will execute more and more
multi-threaded applications, or multiple distinct applications, from
distinct users. When executing multiple threads from multiple
applications, branch predictors and data prefetchor are disturbed, and
their "learning" becomes erroneous (especially when they use physical
address as tags).

Does anyone know about a serious experimental study of the performance
of hardware data prefetchor and branch predictor in such context ?

Thanks

S, waiting for the next generation of branch predictors and data
prefetchors for multicore processors

With the multicore era, desktop and servers will execute more and more
multi-threaded applications, or multiple distinct applications, from
distinct users.  When executing multiple threads from multiple
applications, branch predictors and data prefetchor are disturbed, and
their "learning" becomes erroneous (especially when they use physical
address as tags).

On Oct 28, 12:08=A0pm, Sid Touati <SidnospamTou... at (no spam) inria.fr> wrote:

With the multicore era, desktop and servers will execute more and more
multi-threaded applications, or multiple distinct applications, from
distinct users. =A0When executing multiple threads from multiple
applications, branch predictors and data prefetchor are disturbed, and
their "learning" becomes erroneous (especially when they use physical
address as tags).

Multicore processors help, rather than hindering, as someone else
already noted, since threads running on other processors are
irrelevant; the branch predictor is a part of each core, so if there
are other processors, this means fewer threads from the total have to
be handled by each core.

Andy "Krazy" Glew a écrit :

f) I've long wanted to have the option of loading/unloading predictor
state like other context. Trouble is, it is often faster to recompute
than reload.

You can save the branch predictor tables and restore them on a context
switch. Or you can zero out the tables on a context switch. Or you can
just leave them alone, and let them correct themselves as the
switched-in program runs.

Turns out that there is not much point to doing either of the first
two approaches; the branch predictor will correct itself pretty
quickly -
quickly enough that the extra cycles spent unloading and reloading the
predictor tables on a context switch overwhelm the actual performance
gain.

Andy "Krazy" Glew a écrit :



a) There have been studies in academia, published I believe, on the
effects of context switching on branch predictors. As you might
expect, the more context switching, the worse.


do you have exact references on such academic studies ? Of course I was
talking about real experiments, not simulations. Simulating the
performances of multicore systems is tricky.

b) Most branch predictors in my experience use virtual addresses,
although using physical addresses can shave a cycle in front end.

Fine, how do they distinguish between the PC of two separate
applications running in parallel on the same multicore processor ?

you are right when we talk about executing multiple open-mp threads of
the same application. In practice, multiple applications can be run in
parallel, and this is the way we use computers usually (batch mode is
reserved for special situations only)

If one has a multithreaded core, then that core should have separate
branch predictor states for each thread as well.

John Savard

Sid Touati wrote:
Andy "Krazy" Glew a écrit :

f) I've long wanted to have the option of loading/unloading predictor
state like other context. Trouble is, it is often faster to
recompute than reload.


You can save the branch predictor tables and restore them on a context
switch. Or you can zero out the tables on a context switch. Or you can
just leave them alone, and let them correct themselves as the
switched-in program runs.

Turns out that there is not much point to doing either of the first two
approaches; the branch predictor will correct itself pretty quickly -
quickly enough that the extra cycles spent unloading and reloading the
predictor tables on a context switch overwhelm the actual performance gain.

"Andy \"Krazy\" Glew" <ag-news at (no spam) patten-glew.net> writes:
b) Most branch predictors in my experience use virtual addresses,
although using physical addresses can shave a cycle in front end.

I would expect physical addresses to cost extra cycles, because there
is additional translation.

"Andy \"Krazy\" Glew" <ag-news at (no spam) patten-glew.net> writes:
b) Most branch predictors in my experience use virtual addresses,
although using physical addresses can shave a cycle in front end.

I would expect physical addresses to cost extra cycles, because there
is additional translation.

Anton Ertl wrote:
"Andy \"Krazy\" Glew" <ag-news at (no spam) patten-glew.net> writes:
b) Most branch predictors in my experience use virtual addresses,
although using physical addresses can shave a cycle in front end.

I would expect physical addresses to cost extra cycles, because there
is additional translation.

Other way around.

If you have a physically addressed I$,

but a virtual branch predictor,

you have to translate the, e.g., virtual branch target addresses into
physical, giving you latency on a predicted taken branch. On the other
hand, it is I-fetch, where latency can often be tolerated.

"Andy \"Krazy\" Glew" <ag-news at (no spam) patten-glew.net> writes:

If you have a physically addressed I$,

Some years ago the usual way was virtually-indexed physically-tagged
L1 caches. Has this changed?

but a virtual branch predictor,

Ah, you mean the addresses coming out of the branch predictor, right?

I was thinking about the addresses going in; that's because
conditional branch predictors only predict taken/not-taken, and
because the question being discussed was the aliasing in the branch
predictor from merging the histories of different threads.

For the addresses going in using physical addresses would increase the
latency (or at least the hardware required), and the benefit is
probably small.

For the BTB, storing physical addresses may be a good idea (if it
gives any advantage over virtually-indexed physically-tagged access).

On Nov 2, 3:08 am, "Ken Hagan"<K.Ha... at (no spam) thermoteknix.com> wrote:
On Fri, 30 Oct 2009 19:21:28 -0000, Quadibloc<jsav... at (no spam) ecn.ab.ca> wrote:

If one has a multithreaded core, then that core should have separate
branch predictor states for each thread as well.

Isn't that the same as "For a multithreaded core, the space available for
storing branch predictor state should be divided exactly 1/N to each
context."? That's fair to each thread, but not necessarily the best use of
a presumably limited resource.

It's only the same if one has a branch predictor that is capable of
working that way. I certainly do agree that if one can optimally
allocate branch predictor state without incurring inordinate costs for
that capability, one should do so.

However, I was trying to get at something much more simple, and I
think less controversial:

If one has a multithreaded core, branch predictor information should
be labelled by thread, so that information gathered about the branches
in one thread isn't used to control how branches in another thread are
handled. The branch predictor should not simply ignore the fact that
multiple different threads are being executed in the core.

The usual programming paradigm for such a system is to have many threads
running the same algorithm, which means that training information from
one thread is likely to be useful for another, or at least not detrimental.