hardware prefeth, branch predictor in the context of multitasking
Sid Touati
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
Andy "Krazy" Glew
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.
b) Most branch predictors in my experience use virtual addresses,
although using physical addresses can shave a cycle in front end.
c) P6 anecdote, circa 1991: the IFU (I-cache) designer wanted to flush
the BTB on all context switches. Because we cross checked, we did not
need to do so for correctness, and not flushing turned out to be a
slight performance win.
d) Multicore in some ways *reduces* the frequency of context switches
(compared to the same workload running timesliced), so predictors may
improve. It's all a question of what you measure with respect to.
e) Since many multicore and GP-GPU workloads run the same code on
multiple processors, one might hope for possible IMPROVEMENTS in branch
predictors. Especially if learning from one thread can help another.
E.g. shared BIdB (Branch Identification Buffer) and BTB - basically,
shared big expensive tagged structures. Private histories.
Problem: nobody wants to have shared structures. It's nicer if the
cores are independent. But if your units start becoming clusters of 2,4
processor, then such sharing is reasonable. Similarly, SIMT/CT
(Choherent Threading) warps or clusters may easily emply a shared branch
predictor. There should also be optimizations related to the mainly
shared history.
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.
Sid Touati
>
>
>
> 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 ?
> c) P6 anecdote, circa 1991: the IFU (I-cache) designer wanted to flush
> the BTB on all context switches. Because we cross checked, we did not
> need to do so for correctness, and not flushing turned out to be a
> slight performance win.
It depends on the worksload, and on the application.
> e) Since many multicore and GP-GPU workloads run the same code on
> multiple processors, one might hope for possible IMPROVEMENTS in branch
> predictors. Especially if learning from one thread can help another.
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)
> 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.
I am missing your point here.
Regards
Mayan Moudgill
> Andy "Krazy" Glew a �crit :
>
>> 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.
Quadibloc
> 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).
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.
If one has a multithreaded core, then that core should have separate
branch predictor states for each thread as well.
John Savard
nm...@cam.ac.uk
Quadibloc <jsa...@ecn.ab.ca> wrote:
>On Oct 28, 12:08=A0pm, Sid Touati <SidnospamTou...@inria.fr> wrote:
>
>> With the multicore era, desktop and servers will execute more and more
>> multi-threaded applications, or multiple distinct applications, from
>> 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.
Grrk. It's not that simple :-( Under most circumstances, threads
tend to wander around CPUs, and kernel code is often executed on
the CPU that invoked it. While it is rare for them to make the
problem worse, it can happen.
Regards,
Nick Maclaren.
Chris Gray
> 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.
Is it possible to maintain a small reversible *summary* of the contents of
the branch prediction unit? Something like a 64 bit word that has 6 sets of
low-4-bits-of-PC+1-bit-of-taken plus 4 other bits. I guess what I'm thinking
of here might be just having a second, very small, branch predictor state
that gets a decent number of branches correct. What it suggests is overridden
by the main predictor's state.
Also, what about turning off the use of the branch predictor when switching
into kernel code, then turning it back on on return to user mode? The first
instruction when returning to user mode could be "start reloading the branch
predictor from this summary word", and the last could be "return to user mode
and re-enable branch predictor".
Just throwing out some weird ideas.
--
Experience should guide us, not rule us.
Chris Gray c...@GraySage.COM
http://www.Nalug.ORG/ (Lego)
http://www.GraySage.COM/cg/ (Other)
Andy "Krazy" Glew
> 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 ?
On existing Intel and AMD multicore systems, the processor cores are
separate, and do not were breach predictors.it would be hard to share
BP, since the cores are attached only at the L2 or L3 cache.
Multithreaded cores could share branch predictorsbetween threads.
Whether they share tables but arrange to hash different threads'
versions of the same address to different table entries is interesting.
a minor research toper.
> 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)
Nevertheless, even different apps share many OS services and DLLs-the.
training from one for the shared code may help a separate app, whether
running simultaneously or later in time. The problem is distinguishing
shared from unshared. Standard multi predictor choosers may work,
choosing between shared & unshared. Similarly, standard techniques such
as partial tags, and the aforementioned hashing.
- - -
Sorry if I am cryptic.
Writing this using handwriting recognition on a tablet PC in a shuttle
ran driving from Seattle to Portland as part of my weekly commute
to/from Intellectual Ventures in Bellevue.
The ran bounces so much that keyboard is almost useless.
Interesting: cursive is normally better than printing, but not when
driving/ vibrating.
Andy "Krazy" Glew
Exactly. All work in thisarea has been disappointing. Perhaps as tables
grow bigger - but it is also quite likely that cross app training can be
useful.
Also, r/W interfaces to BP arrays have a cost. Maybe the DFT guys have)
want suchaccess ports.
I am skeptical of any proposal to context switchpredictor state.
Perhaps an efficient delta- not the whole table, but a list of the most
costly mispredicts.
Andy "Krazy" Glew
> If one has a multithreaded core, then that core should have separate
> branch predictor states for each thread as well.
>
> John Savard
could, not necessarily should.
Ken Hagan
> 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.
Sid Touati
> 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.
Yeah, we can imagine lot of games inside a chip. My question was about
what has been done, what has been experimented. All what we see in
papers is good performance numbers of branch predictors and prefetchors
that nobody is able to reproduce simply because rare people use a
machine in a batch mode. The usage is most of the case with
multitasking, multi-threading, etc.
>
> 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.
The term "learning" that is usually used to describe dynamic mechanisms
is a subliminal description of what is going on inside speculative
mechanismes: threads, predictors and prefetchors do not "learn" anything
at execution time, they just play against random. Learning has something
related to "understanding", a simple automata with a table cannot learn
anything :)
Anyway, if someone has an exact reference to a serious experimental
study on branch predictors and data prefetchors in the context of
multi-tasks, multi-threads, could you please point it.
Best regards
Anton Ertl
>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.
Is there much aliasing from using virtual addresses without address
space numbers or similar? I wouldn't expect it.
>c) P6 anecdote, circa 1991: the IFU (I-cache) designer wanted to flush
>the BTB on all context switches. Because we cross checked, we did not
>need to do so for correctness, and not flushing turned out to be a
>slight performance win.
That seems obvious. With flushing, you have no chance of a hit,
without you have (even though it may be small). Am I overlooking
something?
- anton
--
M. Anton Ertl Some things have to be seen to be believed
an...@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
Andy "Krazy" Glew
> "Andy \"Krazy\" Glew" <ag-...@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.
Whereas you could use physical addresses for I-fetch: e.g. have a
current I-fetch PC (Intel parlance, PFIP, physical fetch instruction
pointer (I made that up)), increment it to the next I$ line. Have the
BTB have physical addresses. Trouble is, you have to do extra work,
like translating when sequential instruction fetch crosses a page
boundary, or remembering such crossings. You pretty much have to
maintain the virtual or linear, VFIP or VLIP, instruction pointers as
well, although maybe not as fast as the main PFIP.
Andy "Krazy" Glew
> "Andy \"Krazy\" Glew" <ag-...@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.
Anton Ertl
>Anton Ertl wrote:
>> "Andy \"Krazy\" Glew" <ag-...@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$,
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.
>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.
For the BTB, storing physical addresses may be a good idea (if it
gives any advantage over virtually-indexed physically-tagged access).
Andy "Krazy" Glew
> "Andy \"Krazy\" Glew" <ag-...@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?
Although there have been a number of systems with virtually indexed
physically tagged D$ and I$, including IIRC the Willamette L0 D$, array lookup,
most Intel x86s of the P6 family have physically indexed, physically
tagged, caches.
IMHO virtual indexing has gotten a bit of a bad rap. But, it certainly
had a bad reputation in quite a few design groups.
>> but a virtual branch predictor,
>
> Ah, you mean the addresses coming out of the branch predictor, right?
Could be the address coming out
Could be the address going in.
It is convenient if they are of the same type, so that you can feed
the predictor output right back to the input.
>
> 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.
Why would physical addresses going in increase the latency?
They would not increase latency of the array lookup or tag match.
They add complexity. And they require the target to be translated
when it is put into the array, typically on a misprediction when you are
doing an ifetch anyway.
> For the BTB, storing physical addresses may be a good idea (if it
> gives any advantage over virtually-indexed physically-tagged access).
Like I said, unclear if it is a complexity win. Definitely costs devices.
Quadibloc
> On Fri, 30 Oct 2009 19:21:28 -0000, Quadibloc <jsav...@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.
In other words, I was assuming that the branch predictor would be
crude and simple in design; a handful of gates, not a computer in its
own right, which is why I failed to be sufficiently explicit.
John Savard
Anton Ertl
>Anton Ertl wrote:
>> "Andy \"Krazy\" Glew" <ag-...@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?
>
>Although there have been a number of systems with virtually indexed
>physically tagged D$ and I$, including IIRC the Willamette L0 D$, array lookup,
>most Intel x86s of the P6 family have physically indexed, physically
>tagged, caches.
>
>IMHO virtual indexing has gotten a bit of a bad rap. But, it certainly
>had a bad reputation in quite a few design groups.
Why is that? I never heard about it before.
>> For the addresses going in using physical addresses would increase the
>> latency (or at least the hardware required), and the benefit is
>> probably small.
>
>Why would physical addresses going in increase the latency?
My thoughts were along the following lines (but see below): Either the
CPU produces the physical address by translating from the virtual
address, then there is latency. Or it maintains the physical PC as
well, then there is additional hardware required (plus latency in rare
cases, e.g. page-crossing).
>They would not increase latency of the array lookup or tag match.
Ok, using the common part for indexing, and delaying the tag match
until after the translation, as in virtually-indexed physically-tagged
caches. Yes, that may be possible without extra latency.
Terje Mathisen
> On Nov 2, 3:08 am, "Ken Hagan"<K.Ha...@thermoteknix.com> wrote:
>> On Fri, 30 Oct 2009 19:21:28 -0000, Quadibloc<jsav...@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.
In a multicore cpu, this is very probably exactly the wrong thing to do:
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.
Cores that run different functions, will have a separate set of branches
to consider, and again each set running the same code can share branch info.
The main reason for keeping them separate is simply that the branch
predictions needs to be very close to the instruction fetch and
execution units, something which is hard to achieve if a single large
global branch table is many cycles away.
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
Chris Gray
> 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.
That doesn't mean that the ability to have multiple predictor states
is bad. You need a way for the OS to tell the CPU "thread with key Y
is going to be very similar to thread with key X". That means that
the key Y state should be seeded with the key X state, or that the
two states can be merged into one larger, more detailed state.
I guess it comes down to the question of just how much value is a
more accurate predictor - how many gates can you afford, and is it
worthwhile to need a few extra instructions to initialize it?
Andy "Krazy" Glew
> 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.
This sounds like a good idea on the face of it. And it is probably reasonable
to do this for any large chunks of branch predictor information, such as
BTB arrays - 32+ bits of branch target, to which adding a few bits of
thread identifier is only a small fraction.
However, consider a typical pattern table, such as a Smith bimod or gshare
table. Such tables are logically 2 bits per entry. Adding one or a few
bits of thread ID is a significant increase in the cost of such a table.
You have to ask yourself if it is better to increase the size of the
predictor by 1.5X or 2X, or add bits to distinguish threads.
However, you can get a similar effect by hashing different threads differently
- so that they probably map to different entries. Moreover, this allows you
to do what I suggested earlier: use the same table (a) hashed uniquely from thread i,
and (b) hashed the same for all or a group of threads, to allow sharing.
With a chooser to choose which to use.
Any tagged information can probably have a few bits of thread ID added.
The branch or path histories, of course, are maintained per thread.
Although there is an interesting possibility: as we move from small histories
to very large, we might try dynamically allocating a variable number of bits
per thread.
Quadibloc
> 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.
Ah, I thought the usual operation of a multicore system is to have an
operating system running multiple different applications at once, and
the operating system itself, so that the system would have more
different applications providing threads than there were cores.
Thus, on a Windows PC, when I look at Task Manager, under the
Processes tab, I usually find more than four things listed there.
Admittedly, if I was using multicore chips in a supercomputer in order
to do massively-parallel number-crunching, I probably _would_ be using
the system as you describe. In fact, even on a PC, if I was playing
certain graphics-intensive computer games, that may well be what I
want. So the situation you describe, even if not "usual", is the one
that applies... the only times when performance is critical.
John Savard
Robert Myers
>
> Ah, I thought the usual operation of a multicore system is to have an
> operating system running multiple different applications at once, and
> the operating system itself, so that the system would have more
> different applications providing threads than there were cores.
>
> Thus, on a Windows PC, when I look at Task Manager, under the
> Processes tab, I usually find more than four things listed there.
>
> Admittedly, if I was using multicore chips in a supercomputer in order
> to do massively-parallel number-crunching, I probably _would_ be using
> the system as you describe. In fact, even on a PC, if I was playing
> certain graphics-intensive computer games, that may well be what I
> want. So the situation you describe, even if not "usual", is the one
> that applies... the only times when performance is critical.
>
Windows, VNC, an embedded virtual Linux machine, and Chrome with many
open tabs keep this i7 pretty busy. Add in bloated messengers, and
it's sometimes not enough. Going back to anything less is sort of
depressing, actually. Most of what has been said here and elsewhere
about the uselessness of multiple cores/ multi-threading has been "all
computing is like the computing I'm used to, and it always will be."
Robert.
Ken Hagan
> 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.
I'm still slightly confused, perhaps as much by other people's responses
as by your suggestion.
When we speak of "thread" here, are these CPU hyper-threads or OS threads
(or indeed, some other OS-supplied tag, allowing for groups of
behaviourally similar threads to learn from one another)? Since the
subject came up in the context of multithreaded cores, I presumed the
former, but possibly you were thinking of the latter. If so, would that be
useful even on a single-threaded core?
Quadibloc
My thinking was that at a given moment, there might be, say, 128 OS
threads... and in a commercial CPU, eight of those threads might
actually be executing at that moment - two in each core of a quad-core
CPU. I was thinking that since the threads were likely to be unrelated
in a conventional Windows PC environment, if the cores are "hyper-
threaded" with the grand total of two threads each, they should have
two separate branch predictors each.
Allocating a different OS thread to a core thread slot, I figured,
would take place "infrequently", say during a timer interrupt 60 times
a second (that's how often they had timer interrupts on my
grandpappy's IBM 360...) and so I viewed flushing the branch
predictor, rather than trying to give it the ability to cope with the
operating system's idea of what constitutes a thread, as an acceptable
departure from optimization.
John Savard
Quadibloc
> Most of what has been said here and elsewhere
> about the uselessness of multiple cores/ multi-threading has been "all
> computing is like the computing I'm used to, and it always will be."
Indeed, I feel this thread has been useful in making explicit my
hidden assumptions.
John Savard
nm...@cam.ac.uk
Quadibloc <jsa...@ecn.ab.ca> wrote:
However, almost everything that has been said about the inevitability
of the current semi-independent core designs is also along the lines
of "all hardware is like the hardware I'm used to, and it always will
be." There ARE alternatives, when people stop thinking that way, but
it's extremely unclear which would be generally worthwhile (which also
applies to the current designs).
We live in interesting times ....
Regards,
Nick Maclaren.
Quadibloc
> However, almost everything that has been said about the inevitability
> of the current semi-independent core designs is also along the lines
> of "all hardware is like the hardware I'm used to, and it always will
> be." There ARE alternatives, when people stop thinking that way, but
> it's extremely unclear which would be generally worthwhile (which also
> applies to the current designs).
The hardware that people are used to isn't the same as the hardware
people are using even now.
What people are used to, of course, is one processor that gets more
powerful by being made faster. So what would be desired as the
successor to a single-core 3 GHz Pentium IV would be a single-core 6
GHz processor of the same type. That would be the most general and the
most useful way to double performance, since the doubling would be
applicable even to a program which can't be made to use more than a
single thread, and in which every instruction is dependent on the
last.
Such a program, though, wouldn't even make full use of the potential
performance of a Pentium IV, because that processor is pipelined - the
early parts of some instructions, *including parts that do arithmetic,
not just memory fetch and opcode decoding, which are unlikely to
depend on previous instructions unless they're branches*, execute in
parallel with the later parts of preceding instructions.
So we could speak of NUMA or we could speak of vector processing.
But I don't see the issue being that people assume "all hardware is
like the kind of hardware that I am used to", but "any hardware that
isn't like the kind of hardware that I am used to will largely go to
waste". The problem is not that people don't realize parallel hardware
exists. It is that they don't see how any method of improving the
coupling between parallel processors will be beneficial - except in a
few specialized cases, additional power that is only available in
parallel and not serially is something people don't feel they can make
use of.
Of course, except for number-crunching or even video game playing,
it's highly unclear that we _need_ vastly more computing power. Yes,
we are being sold more and more bloated operating systems to encourage
us to buy new PCs more often than we really want to... Windows 3.1
will let you turn out really nice business letters on your laser
printer, as far as that goes, if it's an old enough one to have a
driver for it.
More computing power is, of course, useful. But it is of value only
insofar as it is appllied to doing useful work - although I define
"useful" liberally, not just meaning practical and serious work: a
video game entertains those who play it, and even that is useful for
the purpose of my statement here. Creating employment in Redmond - or
at Intel, for that matter - is all I seek to exclude.
Eventually, Moore's Law will peter out, but new developments will let
us achieve a slower rate of progress but of a more useful kind. Thus,
one promising recent development is a process developed at MIT for
using Germanium Nitride in such a way to make chips using established
silicon processes, and yet give them a faster kind of transistor.
And perhaps we will make use of massive parallelism in new ways -
neural nets that can be implanted into the brains of stroke victims -
or even used to allow us to achieve immortality through uploading.
All kinds of useful things may happen. And Windows 7 is said to be
good at making use of the extra power of multicore chips. What I don't
see happening, necessarily, is for the ordinary PC market to lead to
one particular parallel topology becoming seen as the solution; it
could happen, if one happens to be a good fit, but I think it's
perfectly possible that none of them will be helpful, and interesting
things will still happen of other kinds.
John Savard
Terje Mathisen
> Terje Mathisen<Terje.M...@tmsw.no> writes:
>
>> 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.
>
> That doesn't mean that the ability to have multiple predictor states
> is bad. You need a way for the OS to tell the CPU "thread with key Y
> is going to be very similar to thread with key X". That means that
> the key Y state should be seeded with the key X state, or that the
> two states can be merged into one larger, more detailed state.
>
> I guess it comes down to the question of just how much value is a
> more accurate predictor - how many gates can you afford, and is it
> worthwhile to need a few extra instructions to initialize it?
Right.
I'm somewhat in love with the idea of a multi-level table:
A large shared but simple (2-bit counter or similar) augmented with a
small exception table per core which only stores branch info for
branches that have missed in the large table.
Is this even feasible? :-)
nm...@cam.ac.uk
Quadibloc <jsa...@ecn.ab.ca> wrote:
>
>> However, almost everything that has been said about the inevitability
>> of the current semi-independent core designs is also along the lines
>> be." =A0There ARE alternatives, when people stop thinking that way, but
>> it's extremely unclear which would be generally worthwhile (which also
>> applies to the current designs).
>
>The hardware that people are used to isn't the same as the hardware
>people are using even now.
>
>What people are used to, of course, is one processor that gets more
Grrk. Maybe I have spent too long on the bleeding edge. That is
a viewpoint that many of us gave up on 20 years ago ....
In particular, when you are dealing with programs limited by memory
latency, as so many area, there has been very little increase over
the years. 15%, if one is feeling generous, less if not.
Regards,
Nick Maclaren.
Quadibloc
> In particular, when you are dealing with programs limited by memory
> latency, as so many area, there has been very little increase over
> the years. 15%, if one is feeling generous, less if not.
What with the huge on-chip caches on today's chips, I suppose it
depends on what one means by "limited by memory latency". To actually
be limited by the latency of external DRAM, a program would have to
try rather harder these days, so that has to count as some sort of an
improvement as well.
John Savard
Andy "Krazy" Glew
> I'm somewhat in love with the idea of a multi-level table:
>
> A large shared but simple (2-bit counter or similar) augmented with a
> small exception table per core which only stores branch info for
> branches that have missed in the large table.
>
> Is this even feasible? :-)
Yes.
But when I submitted papers on such designs, 1996-2000, they got rejected.
Daniel Jimenez eventually broke through, with the second level table
being a great big neural net predictor.
Daniel A. Jimenez
I'd love to take the credit for a multi-level branch predictor, but I
think my contribution was to write up the multi-level idea that had been
around for a while and use it for crazy neural network schemes. (My first ,
idea was to use caching for branch predictor tables. Turns out, nope,
that's a terrible idea, there's no locality in those tables of counters.)
EV6 had what I think of as a multi-level branch predictor: a first level
cache line predictor that's quick and dumb, and a second-level hybrid
predictor that's slow and smart, and can override the line predictor.
I'm sure people are working at doing this for sharing prediction resources
between cores or thread contexts. Dean Tullsen had an interesting paper in
last year's ASPLOS about doing more accurate branch prediction for short
threads, and the TRIPS folks have been working on a hierarchical predictor
for their TFlex microarchitecture.
--
Daniel Jimenez djim...@cs.utexas.edu
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
Andy "Krazy" Glew
> In article <4AF8D67F...@patten-glew.net>,
> Andy \"Krazy\" Glew <ag-...@patten-glew.net> wrote:
>> Terje Mathisen wrote:
>>> I'm somewhat in love with the idea of a multi-level table:
>>>
>>> A large shared but simple (2-bit counter or similar) augmented with a
>>> small exception table per core which only stores branch info for
>>> branches that have missed in the large table.
>>>
>>> Is this even feasible? :-)
>> Yes.
>>
>> But when I submitted papers on such designs, 1996-2000, they got rejected.
>>
>> Daniel Jimenez eventually broke through, with the second level table
>> being a great big neural net predictor.
>
> I'd love to take the credit for a multi-level branch predictor, but I
> think my contribution was to write up the multi-level idea that had been
> around for a while and use it for crazy neural network schemes. (My first ,
> idea was to use caching for branch predictor tables. Turns out, nope,
> that's a terrible idea, there's no locality in those tables of counters.)
1) You can make the BTB into a multilevel table. There *is* locality there.
2) You can make the pattern tables multilevel. But I found that it was
not efficient to make the L1 into a cache - because cache implies cache
tags. My version just had the L1 being a small fast dumb predictor, and
the L2 being a big, slow, smarter and more complex predictor. I
simulated all sorts of combinations, such as an L1 gshare with an L2 a
great big McFarling hybrid, etc., - and overall, I found that it gave
the effective prediction accuracy of the larger predictor, with the
predictor latency (on predicted taken branches) of the small predictor.
I also tried a version where the L1 was a plain old predictor, and the
L2 was a "cache", containing tagged patterns that had produced
mispredictions in the past, with history lengths longer than the L1
uses. It worked, but the area efficiency was questionable. Tags are
expensive, and untagged tables of two bit counters are very cheap.
--
I should also mention that Adam Butts did similar work, after me and
before Daniel.
Paul A. Clayton
wrote:
[snip]
> 2) You can make the pattern tables multilevel. But I found that it was
> not efficient to make the L1 into a cache - because cache implies cache
> tags. My version just had the L1 being a small fast dumb predictor, and
> the L2 being a big, slow, smarter and more complex predictor. I
> simulated all sorts of combinations, such as an L1 gshare with an L2 a
> great big McFarling hybrid, etc., - and overall, I found that it gave
> the effective prediction accuracy of the larger predictor, with the
> predictor latency (on predicted taken branches) of the small predictor.
>
> I also tried a version where the L1 was a plain old predictor, and the
> L2 was a "cache", containing tagged patterns that had produced
> mispredictions in the past, with history lengths longer than the L1
> uses. It worked, but the area efficiency was questionable. Tags are
> expensive, and untagged tables of two bit counters are very cheap.
Would it be useful to have a one-bit quasi-tag for the confidence
bit?
A match means a high-confidence possible hit OR a low-confidence
miss; a mis-match means a low-confidence possible hit OR a
high-confidence miss.
Paul A. Clayton
just a technophile
Del Cecchi
"Andy "Krazy" Glew" <ag-...@patten-glew.net> wrote in message
news:4AF8D67F...@patten-glew.net...
The east Anglia hack has revealed the glory of peer review. Your
papers may have been rejected because they offended one of the
reviewers pre conceived notions.
Robert Myers
wrote:
> The east Anglia hack has revealed the glory of peer review. Your
> papers may have been rejected because they offended one of the
> reviewers pre conceived notions.
Every field where prestige is money is going to have similar
problems. This one had to be coming. Physical reality is never so
simple as the popular theology we've been hearing.
Robert.
Bernd Paysan
The problems Wikipedia (especially the German one) is having lately with
people rather deleting articles than writing new ones and thereby
driving out volunteers shows that it doesn't even need money or prestige
for having these problems. Peer review means that only non-
controversial articles will be published. This means progress is only
allowed into the direction where the participants in peer review think
it should happen.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/