| Author |
Message |
Skybuck Flying
Guest
|
 Posted:
Mon Aug 08, 2005 1:32 pm Post subject:
Branch prediction using counters. |
|
|
Hi,
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At the
lower levels this would mean inserting counters into jump instructions and
recording which branch is executed the most by incrementing or maybe even
decrementing counters everytime the branch gets executed.
Then the execute-ahead logic would execute those branches with the highest
counter. Also a execute-ahead flag could be inserted into the jump
instruction to indicate if execute-ahead is allowed. For example a compiler
can use this flag to indicate that execute-ahead is not possible etc.
Ofcourse branch prediction is nothing new and processors nowadays have that.
So I was browsing through some patents. (Not all because that would take way
too much time... It would maybe take a day maybe even a few days to browse
through them all ;))
So far I have seen one patent which mentions using a "taken/not taken" bit
which indicates if a branch was taken or not.
So I have few questions about branch prediction.
1. Is it common to use counters as described above to do branch prediction
or is this something novel ? ;)
2. Suppose it's not novel... then why only use 1 bit to do branch prediction
?
Some reasons which I can think of:
1. It requires less memory than bigger counters.
2. Counters might take to long to change. For example Branch A might be
executed many times, then suddenly Branch B has to be executed many times.
Using large counters might take to long for the prediction to catch up ;)
What are your thoughs on this ? ;)
Any references to patents or other information about branch prediction ?
Bye,
Skybuck. |
|
| Back to top |
|
 |
Ken Smith
Guest
|
| Posted:
Mon Aug 08, 2005 2:26 pm Post subject:
Re: Branch prediction using counters. |
|
|
In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
| Quote: | Hi,
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At the
lower levels this would mean inserting counters into jump instructions and
recording which branch is executed the most by incrementing or maybe even
decrementing counters everytime the branch gets executed.
[...]
1. Is it common to use counters as described above to do branch prediction
or is this something novel ? ;)
|
No, its is not common. For that matter I've never heard of the idea being
used. There are problems that the counter. It should not be part of the
instruction because that would mean that code space has to be written into
as the program runs. This will slow things down.
Many processors have caches on them. The cache will contain the code that
was done on the last pass around the loop and as a result repeating a loop
the same way is faster than taking some new path.
Many pipelined processors perform an instruction or two after the jump
instuction even when the jump is taken. A good compiler will take
advantage of this if it can.
Some processors have a conditional skip the next instruction and some have
conditional instructions. These allow logic to be done without taking a
branch. This increases the speed of things like "if X<0 then X := 0".
Some processors have multiple pipelines. In many cases this is one for
integers and one floating point. This allows those instructions that can
be done to skip past those that have to wait for a memory transfer.
--
--
kensmith@rahul.net forging knowledge |
|
| Back to top |
|
|
Jeroen
Guest
|
| Posted:
Mon Aug 08, 2005 4:15 pm Post subject:
Re: Branch prediction using counters. |
|
|
"Stephen Fuld" <s.fuld@PleaseRemove.att.net> schreef in bericht
news:q1LJe.78310$5N3.61411@bgtnsc05-news.ops.worldnet.att.net...
| Quote: |
"Skybuck Flying" <nospam@hotmail.com> wrote in message
news:dd7sjv$1vs$1@news1.zwoll1.ov.home.nl...
"Ken Smith" <kensmith@green.rahul.net> wrote in message
news:dd7q2v$ns0$4@blue.rahul.net...
In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Hi,
|
<snip>
| Quote: | If it slows down the system then that would mean the bottleneck is in
the
bandwidth/speed of the bus/whatever used to read/write instructions
from/to
main memory.
You really need to do some more basic study. You have depricated the MIT
on-line courses, calling them "for dummies". First of all, I doubt that
any
MIT course is "for dummies". Second of all, while you may not be a dummy
in
general, in this area, you are, simply because you lack the basic
knowledge.
I admire your enthusiasm, but you need to channel it better so as not to
appear as foolish as you currently do to members of the group who have
lots
of experience.
|
Do a search for his name in Google newgroups to see some interesting threads
;) |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Mon Aug 08, 2005 4:15 pm Post subject:
Re: Branch prediction using counters. |
|
|
"Stephen Fuld" <s.fuld@PleaseRemove.att.net> wrote in message
news:q1LJe.78310$5N3.61411@bgtnsc05-news.ops.worldnet.att.net...
| Quote: |
"Skybuck Flying" <nospam@hotmail.com> wrote in message
news:dd7sjv$1vs$1@news1.zwoll1.ov.home.nl...
"Ken Smith" <kensmith@green.rahul.net> wrote in message
news:dd7q2v$ns0$4@blue.rahul.net...
In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Hi,
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At
the
lower levels this would mean inserting counters into jump instructions
and
recording which branch is executed the most by incrementing or maybe
even
decrementing counters everytime the branch gets executed.
[...]
1. Is it common to use counters as described above to do branch
prediction
or is this something novel ? ;)
No, its is not common. For that matter I've never heard of the idea
being
used. There are problems that the counter. It should not be part of
the
instruction because that would mean that code space has to be written
into
as the program runs. This will slow things down.
If it slows down the system then that would mean the bottleneck is in
the
bandwidth/speed of the bus/whatever used to read/write instructions
from/to
main memory.
You are mising an important point. There typically is no need to write to
the code space at all. Instruction caches have no write to memory
circuitry. To write the counters to memory you would have to add an
additional path, and if you were going to write the updated value on every
branch, you are going to add a huge amount of memory traffic (studies show
that typically a branch occurs once every 6-10 instructions on average).
If
you are not going to write the counter back every time, when are you? How
are you going to associate the multiple counters you then must keep with
branches? There are a lot of problems you would have to solve for what is
probably a small gain (hint, current branch predictors do pretty well
already).
You really need to do some more basic study. You have depricated the MIT
on-line courses, calling them "for dummies". First of all, I doubt that
any
MIT course is "for dummies". Second of all, while you may not be a dummy
in
general, in this area, you are, simply because you lack the basic
knowledge.
I admire your enthusiasm, but you need to channel it better so as not to
appear as foolish as you currently do to members of the group who have
lots
of experience.
|
I could depricate you as dummy ;) for not seeing the obvious solutions to
this idea :P
But I guess you didn't put much thought into it... but I have a little bit
;)
However I do not see a need to share my wisedom to make dummies rich :)
In fact you didn't answer any of my questions ;)
Bye,
Skybuck. |
|
| Back to top |
|
|
Stephen Fuld
Guest
|
| Posted:
Mon Aug 08, 2005 4:15 pm Post subject:
Re: Branch prediction using counters. |
|
|
"Skybuck Flying" <nospam@hotmail.com> wrote in message
news:dd7sjv$1vs$1@news1.zwoll1.ov.home.nl...
| Quote: |
"Ken Smith" <kensmith@green.rahul.net> wrote in message
news:dd7q2v$ns0$4@blue.rahul.net...
In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Hi,
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At the
lower levels this would mean inserting counters into jump instructions
and
recording which branch is executed the most by incrementing or maybe
even
decrementing counters everytime the branch gets executed.
[...]
1. Is it common to use counters as described above to do branch
prediction
or is this something novel ? ;)
No, its is not common. For that matter I've never heard of the idea
being
used. There are problems that the counter. It should not be part of the
instruction because that would mean that code space has to be written
into
as the program runs. This will slow things down.
If it slows down the system then that would mean the bottleneck is in the
bandwidth/speed of the bus/whatever used to read/write instructions
from/to
main memory.
|
You are mising an important point. There typically is no need to write to
the code space at all. Instruction caches have no write to memory
circuitry. To write the counters to memory you would have to add an
additional path, and if you were going to write the updated value on every
branch, you are going to add a huge amount of memory traffic (studies show
that typically a branch occurs once every 6-10 instructions on average). If
you are not going to write the counter back every time, when are you? How
are you going to associate the multiple counters you then must keep with
branches? There are a lot of problems you would have to solve for what is
probably a small gain (hint, current branch predictors do pretty well
already).
You really need to do some more basic study. You have depricated the MIT
on-line courses, calling them "for dummies". First of all, I doubt that any
MIT course is "for dummies". Second of all, while you may not be a dummy in
general, in this area, you are, simply because you lack the basic knowledge.
I admire your enthusiasm, but you need to channel it better so as not to
appear as foolish as you currently do to members of the group who have lots
of experience.
--
- Stephen Fuld
e-mail address disguised to prevent spam |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Mon Aug 08, 2005 4:16 pm Post subject:
Re: Branch prediction using counters. |
|
|
"Ken Smith" <kensmith@green.rahul.net> wrote in message
news:dd7q2v$ns0$4@blue.rahul.net...
| Quote: | In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Hi,
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At the
lower levels this would mean inserting counters into jump instructions
and
recording which branch is executed the most by incrementing or maybe even
decrementing counters everytime the branch gets executed.
[...]
1. Is it common to use counters as described above to do branch
prediction
or is this something novel ? ;)
No, its is not common. For that matter I've never heard of the idea being
used. There are problems that the counter. It should not be part of the
instruction because that would mean that code space has to be written into
as the program runs. This will slow things down.
|
If it slows down the system then that would mean the bottleneck is in the
bandwidth/speed of the bus/whatever used to read/write instructions from/to
main memory.
I know games and stuff like that uses tremendous ammounts of bandwidth but
that goes via special bussess like agp or pci express.
How much memory bandwidth/speed is available to transfer instruction from/to
main memory where program code is located ? ;) and how much of that
bandwidth is generally used for application or maybe even games ? ;)
In other words... is bandwidth from main memory to cpu and back, truely the
limiting factor ? ;)
<other optimizations snipped ;)>
Bye,
Skybuck |
|
| Back to top |
|
|
Colonel Forbin
Guest
|
| Posted:
Mon Aug 08, 2005 9:38 pm Post subject:
Re: Branch prediction using counters. |
|
|
In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
| Quote: |
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At the
lower levels this would mean inserting counters into jump instructions and
recording which branch is executed the most by incrementing or maybe even
decrementing counters everytime the branch gets executed.
|
Actually this is sort of analogous to runtime profiling feedback to
compilers, which is used on a number of systems.
The problem is that it is often impossible to predict an event until
the outcome is observed (think quantum mechanics).
If we knew the outcome of each branch, we could simply eliminate the
branch in most cases and still have a reasonable approximation.
Inserting counters into production code typically comes at a great
price in terms of overhead.
We typically do this in development in order to optimize the most
costly sections of code for the most common outcomes, but trying
to put some sort of low level adaptive optimization metrics into
production code would consume more in overhead than the cost of
doing the task to begin with. |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Mon Aug 08, 2005 10:15 pm Post subject:
Re: Branch prediction using counters. |
|
|
"Colonel Forbin" <forbin@dev.nul> wrote in message
news:3ULJe.50331$B52.10566@tornado.ohiordc.rr.com...
| Quote: | In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At the
lower levels this would mean inserting counters into jump instructions
and
recording which branch is executed the most by incrementing or maybe even
decrementing counters everytime the branch gets executed.
Actually this is sort of analogous to runtime profiling feedback to
compilers, which is used on a number of systems.
|
I used profilers, they use procedure calls to do their thing... and also
write to harddisk
making everything slllllllowwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww.
| Quote: | The problem is that it is often impossible to predict an event until
the outcome is observed (think quantum mechanics).
|
Often the same branch is executed. So prediction can help.
| Quote: | If we knew the outcome of each branch, we could simply eliminate the
branch in most cases and still have a reasonable approximation.
|
No you cannot, you have to execute the rare case sometimes as well.
| Quote: |
Inserting counters into production code typically comes at a great
price in terms of overhead.
|
Define overhead ;)
| Quote: |
We typically do this in development in order to optimize the most
costly sections of code for the most common outcomes, but trying
to put some sort of low level adaptive optimization metrics into
production code would consume more in overhead than the cost of
doing the task to begin with.
|
Screw profiling, try it at lower levels and see what happens.
Instructions have to be loaded anyway... they sit in cache, counters sit
there too, not much overhead,
then after jumps counter increments and other logic has to be done which can
be done by additional gates so no real overhead there.
Also these updated instructions/jumps have to go back to main memory...
which in my oppinion isn't that much... but that's what I don't know
about... if the bandwidth is available I would say use it ! ;)
Ofcourse there are other problems to solve like compiler changes and some
things can't be pre-computed, etc... and in the end the counters might even
be counter-productive ;)
Since the feedback on my questions is running low I have only one last thing
to say to you people:
Screw you and fuck you too lol if doesn't work lol...
Bye,
Skybuck :D |
|
| Back to top |
|
|
Colonel Forbin
Guest
|
| Posted:
Mon Aug 08, 2005 10:38 pm Post subject:
Re: Branch prediction using counters. |
|
|
In article <dd83ru$4ec$1@news1.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
| Quote: |
Screw you and fuck you too lol if doesn't work lol...
|
Thank you for that insightful contribution to our collective knowledge.
I am sure it will inspire many lurkers on these groups to come forth and
bestow you with their knowledge and to spend many hours of independent
research on their own time to answer your future questions.
The amusing thing is that we might have some useful conversations
peripherally related to issues you raised.
Aol to you, too. |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Mon Aug 08, 2005 11:26 pm Post subject:
Re: Branch prediction using counters. |
|
|
"Colonel Forbin" <forbin@dev.nul> wrote in message
news:EMMJe.52504$zY4.12162@tornado.ohiordc.rr.com...
| Quote: | In article <dd83ru$4ec$1@news1.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Screw you and fuck you too lol if doesn't work lol...
Thank you for that insightful contribution to our collective knowledge.
I am sure it will inspire many lurkers on these groups to come forth and
bestow you with their knowledge and to spend many hours of independent
research on their own time to answer your future questions.
The amusing thing is that we might have some useful conversations
peripherally related to issues you raised.
Aol to you, too.
|
Exactly motherfucker... so go spent all your time on discussing my filthy
wortless ideas and then... write nice reports about them how much they rule
or suck... meanwhile I have influenced the worrrrrrlldddddddd heheheh.
The fact of the matter is that I might be tooooooooooo lazzzzyyy to do it
myself... so go ahead and use it, abuse it, test it, analyze it etc......
But in the end I tooooooooooooooo will learn if it was usefull or not...
:PPPPPPPPPP******* hihihihihihihihihihihihihihihi
Bye,
Skybuck. ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh hehe. |
|
| Back to top |
|
|
Colonel Forbin
Guest
|
| Posted:
Mon Aug 08, 2005 11:41 pm Post subject:
Re: Branch prediction using counters. |
|
|
In article <dd881i$dh1$1@news5.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
| Quote: |
Exactly motherfucker... so go spent all your time on discussing my filthy
wortless ideas and then... write nice reports about them how much they rule
or suck... meanwhile I have influenced the worrrrrrlldddddddd heheheh.
The fact of the matter is that I might be tooooooooooo lazzzzyyy to do it
myself... so go ahead and use it, abuse it, test it, analyze it etc......
But in the end I tooooooooooooooo will learn if it was usefull or not...
:PPPPPPPPPP******* hihihihihihihihihihihihihihihi
Bye,
Skybuck. ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh hehe.
|
I think I was wrong about the crystal meth. This guy needs to take his
Haldol. His probation officer is worried... |
|
| Back to top |
|
|
Bob Monsen
Guest
|
| Posted:
Mon Aug 08, 2005 11:41 pm Post subject:
Re: Branch prediction using counters. |
|
|
Ken Smith wrote:
| Quote: | In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Hi,
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At the
lower levels this would mean inserting counters into jump instructions and
recording which branch is executed the most by incrementing or maybe even
decrementing counters everytime the branch gets executed.
[...]
1. Is it common to use counters as described above to do branch prediction
or is this something novel ? ;)
No, its is not common. For that matter I've never heard of the idea being
used. There are problems that the counter. It should not be part of the
instruction because that would mean that code space has to be written into
as the program runs. This will slow things down.
|
GCC has a profiling mode that will allow one to capture this
information, for optimizing MIPS output (where it is quite useful, since
they have alternate opcodes depending on which branch is more likely).
As I recall (I've never used it) you run your code for a while, and then
get a dump of the counters, which you then feed back into GCC.
--
Regards,
Bob Monsen
If a little knowledge is dangerous, where is the man who has
so much as to be out of danger?
Thomas Henry Huxley, 1877 |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Mon Aug 08, 2005 11:48 pm Post subject:
Re: Branch prediction using counters. |
|
|
"Colonel Forbin" <forbin@dev.nul> wrote in message
news:3HNJe.52896$zY4.35348@tornado.ohiordc.rr.com...
| Quote: | In article <dd881i$dh1$1@news5.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Exactly motherfucker... so go spent all your time on discussing my filthy
wortless ideas and then... write nice reports about them how much they
rule
or suck... meanwhile I have influenced the worrrrrrlldddddddd heheheh.
The fact of the matter is that I might be tooooooooooo lazzzzyyy to do it
myself... so go ahead and use it, abuse it, test it, analyze it etc......
But in the end I tooooooooooooooo will learn if it was usefull or not...
:PPPPPPPPPP******* hihihihihihihihihihihihihihihi
Bye,
Skybuck. ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
hehe.
I think I was wrong about the crystal meth. This guy needs to take his
Haldol. His probation officer is worried...
|
You speak in difficult medication terms... I need a manual...
|
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Mon Aug 08, 2005 11:49 pm Post subject:
Re: Branch prediction using counters. |
|
|
"Bob Monsen" <rcsurname@comcast.net> wrote in message
news:dfydncj3QpTKOmrfRVn-oA@comcast.com...
| Quote: | Ken Smith wrote:
In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Hi,
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At the
lower levels this would mean inserting counters into jump instructions
and
recording which branch is executed the most by incrementing or maybe
even
decrementing counters everytime the branch gets executed.
[...]
1. Is it common to use counters as described above to do branch
prediction
or is this something novel ? ;)
No, its is not common. For that matter I've never heard of the idea
being
used. There are problems that the counter. It should not be part of
the
instruction because that would mean that code space has to be written
into
as the program runs. This will slow things down.
GCC has a profiling mode that will allow one to capture this
information, for optimizing MIPS output (where it is quite useful, since
they have alternate opcodes depending on which branch is more likely).
As I recall (I've never used it) you run your code for a while, and then
get a dump of the counters, which you then feed back into GCC.
|
Ohhhhh that's really fancy pancy.
| Quote: |
--
Regards,
Bob Monsen
If a little knowledge is dangerous, where is the man who has
so much as to be out of danger?
Thomas Henry Huxley, 1877 |
|
|
| Back to top |
|
|
Ben Bradley
Guest
|
| Posted:
Tue Aug 09, 2005 12:16 am Post subject:
Re: Branch prediction using counters. |
|
|
In comp.arch,sci.electronics.design, On Mon, 08 Aug 2005 16:38:23 GMT,
forbin@dev.nul (Colonel Forbin) wrote:
| Quote: | In article <dd756m$38b$1@news3.zwoll1.ov.home.nl>,
Skybuck Flying <nospam@hotmail.com> wrote:
Some time ago I already had this idea of inserting counters into if
statements to predict which branch is most likely to be executed. At the
lower levels this would mean inserting counters into jump instructions and
recording which branch is executed the most by incrementing or maybe even
decrementing counters everytime the branch gets executed.
Actually this is sort of analogous to runtime profiling feedback to
compilers, which is used on a number of systems.
The problem is that it is often impossible to predict an event until
the outcome is observed (think quantum mechanics).
If we knew the outcome of each branch, we could simply eliminate the
branch in most cases and still have a reasonable approximation.
Inserting counters into production code typically comes at a great
price in terms of overhead.
We typically do this in development in order to optimize the most
costly sections of code for the most common outcomes, but trying
to put some sort of low level adaptive optimization metrics into
production code would consume more in overhead than the cost of
doing the task to begin with.
|
I recall reading of a processor that does pipelining through
branches (I don't remember which, but it might be a TI DSP) by using
several execution units. One executes the instruction(s) where the
branch is taken, the other executes the code where the branch is not
taken. When the branch is decided, the results from the corresponding
execution unit are taken and execution continues from there, and the
other results are 'thrown away' unused. This method takes a lot more
silicon space for the processor, but results in a speed increase that
apparently can't be done otherwise.
-----
http://www.mindspring.com/~benbradley |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in