| Author |
Message |
Sander Vesik
Guest
|
 Posted:
Wed Aug 10, 2005 9:12 pm Post subject:
Re: Branch prediction using counters. |
|
|
In comp.arch Skybuck Flying <nospam@hotmail.com> wrote:
| Quote: |
"Paul Hovnanian P.E." <Paul@Hovnanian.com> wrote in message
news:42F97744.959EEC35@Hovnanian.com...
This sort of thing is done at higher levels in various search
algorithms. Far more advanced techniques than just counters are used.
Building this sort of thing into processor firmware or general purpose
library routines might impose an inordinate burden on execution time if
Bullshit... the cpu has extra gates and logic and memory (internal) to
handle it only thing required is more bandwidth for the extra counter data
:)
|
Except that these may be put to a much better use.
--
Sander
+++ Out of cheese error +++ |
|
| Back to top |
|
 |
Zak
Guest
|
| Posted:
Wed Aug 10, 2005 11:15 pm Post subject:
Re: Branch prediction using counters. |
|
|
Andrew Reilly wrote:
| Quote: | Remember that some of the RISC and DSP processors duck the problem by
letting some small number of instructions after the branch happen before
the branch takes effect. This only adds instructions to the code in cases
were nothing can be done before the branch happens. I think this is a
much better way to go if you want a lot of speed per transistor.
Up to 40 instructions, in the case of the TI C6000 series: 5 instruction
issue slots in the branch shadow, up to eight instructions per slot.
Makes loop pre-amble and termination of otherwise single-cycle loops
amusing, but do-able.
|
Isn't is nearly as effective to put these instructions in front of the
branch? This means that if later incarnations need a shorter slot
everything will be compatible.
For extra points auto-insert NOPs if the loop is too small.
This will make things more complex but perhaps not slower.
Thomas |
|
| Back to top |
|
|
Ken Smith
Guest
|
| Posted:
Thu Aug 11, 2005 2:13 pm Post subject:
Re: Branch prediction using counters. |
|
|
In article <pan.2005.08.10.01.52.31.292001@areilly.bpc-users.org>,
Andrew Reilly <andrew-newspost@areilly.bpc-users.org> wrote:
| Quote: | On Wed, 10 Aug 2005 00:24:09 +0000, Ken Smith wrote:
Remember that some of the RISC and DSP processors duck the problem by
letting some small number of instructions after the branch happen before
the branch takes effect. This only adds instructions to the code in cases
were nothing can be done before the branch happens. I think this is a
much better way to go if you want a lot of speed per transistor.
Up to 40 instructions, in the case of the TI C6000 series: 5 instruction
issue slots in the branch shadow, up to eight instructions per slot.
Makes loop pre-amble and termination of otherwise single-cycle loops
amusing, but do-able. There are various multi-cycle NOP instructions to
fiddle the other cases without taking up too much code space.
|
The old ATT one had only one extra instruction per branch and also had
conditional math operations. The result was you could do all sorts of
useful and very fast things.
--
--
kensmith@rahul.net forging knowledge |
|
| Back to top |
|
|
Ken Smith
Guest
|
| Posted:
Thu Aug 11, 2005 2:23 pm Post subject:
Re: Branch prediction using counters. |
|
|
In article <ddccfs$lgp$1@gemini.csx.cam.ac.uk>,
Nick Maclaren <nmm1@cus.cam.ac.uk> wrote:
[... booth's divide ..]
| Quote: | The mind boggles! I have never seen it used, but I can believe that
it is. The most usual software divide is Newton-Raphson.
|
Are you refering to the usual "find 1/X and then multiply by that" method?
Booth's divide is more common in microcontroller land. If you have a micro
that doesn't natively do 32 bit divides and an integer math library,
chances are you are using a Booth's divide.
| Quote: | Whatever
the case, only a few systems lack hardware division for the standard
types, very few applications use it for non-standard types, and the
proportion of time spent in such code is miniscule!
|
Actually this isn't really true. There are a huge number of processors
out there that don't do the divides in hardware for at least some of the
types that are commonly used on them. These are not desk top PCs. They
are systems that contain a processor but are not general purpose
computers.
--
--
kensmith@rahul.net forging knowledge |
|
| Back to top |
|
|
Ken Smith
Guest
|
| Posted:
Thu Aug 11, 2005 2:26 pm Post subject:
Re: Branch prediction using counters. |
|
|
In article <1123684376.739768.282190@g14g2000cwa.googlegroups.com>,
Andy Freeman <anamax@earthlink.net> wrote:
[...]
| Quote: | The instruction history
alone is useless for such codes, but the object address is
(obviously) excellent.
No, the object's address is not obviously "excellent", at least to me.
Please explain what you mean.
The object at a given address tends to have the same type for "a
while".
|
Yes, and once you have XXXXYYYYed that variable, you aren't likely to do
it again. You will XXXXYYYY most of the variables of that same type
though. This I say makes the address of the object a poor input to the
prediction and the VMT a good one.
--
--
kensmith@rahul.net forging knowledge |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Thu Aug 11, 2005 4:15 pm Post subject:
Re: Branch prediction using counters. |
|
|
"Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote in message
news:ddd7j5$l6e$1@gemini.csx.cam.ac.uk...
| Quote: |
In article <ddd6ou$6q0$1@news3.zwoll1.ov.home.nl>,
"Skybuck Flying" <nospam@hotmail.com> writes:
|
|> Dude if this stuff is encoded into the jump instruction then it falls
under
|> my description of inserting counters into jump instructions and
therefore I
|> should still be able to patent it and not you :P
Look, Bubba, no counters! Try rereading what I posted.
|
Ok dinky, then it's aaaalll gooooddddd :)
| Quote: |
Regards,
Nick Maclaren. |
|
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Thu Aug 11, 2005 4:15 pm Post subject:
Re: Branch prediction using counters. |
|
|
In article <ddfn06$7oh$2@blue.rahul.net>,
kensmith@green.rahul.net (Ken Smith) writes:
|> In article <ddccfs$lgp$1@gemini.csx.cam.ac.uk>,
|> Nick Maclaren <nmm1@cus.cam.ac.uk> wrote:
|>
|> [... booth's divide ..]
|> >The mind boggles! I have never seen it used, but I can believe that
|> >it is. The most usual software divide is Newton-Raphson.
|>
|> Are you refering to the usual "find 1/X and then multiply by that" method?
No. That is a component of the method, but you need to do a bit
more to get it quite right.
|> Booth's divide is more common in microcontroller land. If you have a micro
|> that doesn't natively do 32 bit divides and an integer math library,
|> chances are you are using a Booth's divide.
Boggle. Well, if performance isn't a major issue, I suppose that it
doesn't matter what you use.
|> > Whatever
|> >the case, only a few systems lack hardware division for the standard
|> >types, very few applications use it for non-standard types, and the
|> >proportion of time spent in such code is miniscule!
|>
|> Actually this isn't really true. There are a huge number of processors
|> out there that don't do the divides in hardware for at least some of the
|> types that are commonly used on them. These are not desk top PCs. They
|> are systems that contain a processor but are not general purpose
|> computers.
The context was where branch prediction of the division operation
is critical for performance, as the above paragraph makes clear.
If performance of the division IS a major issue, can you explain
why people use Booth's algorithm IN SOFTWARE? As I said, the mind
boggles!
[ All right, I do know of one case. If you have NEITHER hardware
division NOR reasonable hardware multiplication, it is a real pain
to code Newton-Raphson. But anyone who runs codes where division
is a bottleneck on such a system is off his tiny mind. ]
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
Andy Freeman
Guest
|
| Posted:
Thu Aug 11, 2005 9:52 pm Post subject:
Re: Branch prediction using counters. |
|
|
Ken Smith wrote:
| Quote: | In article <1123684376.739768.282190@g14g2000cwa.googlegroups.com>,
Andy Freeman <anamax@earthlink.net> wrote:
The object at a given address tends to have the same type for "a
while".
Yes, and once you have XXXXYYYYed that variable, you aren't likely to do
it again. You will XXXXYYYY most of the variables of that same type
though.
|
Guess why I wrote "object at a given address" and not "variable".
Lots of variables may refer to the same object - the object's address
captures this. The same variable may refer to different objects at
different times; again, object address differences tell you that type
may be different.
-andy |
|
| Back to top |
|
|
Ken Smith
Guest
|
| Posted:
Sat Aug 13, 2005 1:53 am Post subject:
Re: Branch prediction using counters. |
|
|
In article <ddfnlk$6pq$1@gemini.csx.cam.ac.uk>,
Nick Maclaren <nmm1@cus.cam.ac.uk> wrote:
| Quote: |
In article <ddfn06$7oh$2@blue.rahul.net>,
kensmith@green.rahul.net (Ken Smith) writes:
|> In article <ddccfs$lgp$1@gemini.csx.cam.ac.uk>,
|> Nick Maclaren <nmm1@cus.cam.ac.uk> wrote:
|
|> [... booth's divide ..]
|> >The mind boggles! I have never seen it used, but I can believe that
|> >it is. The most usual software divide is Newton-Raphson.
|
|> Are you refering to the usual "find 1/X and then multiply by that" method?
No. That is a component of the method, but you need to do a bit
more to get it quite right.
|
So you say "no" and then "yes".
| Quote: | Boggle. Well, if performance isn't a major issue, I suppose that it
doesn't matter what you use.
|
Performance can be a major issue along with other limitations like low
power or small size.
| Quote: | |> Actually this isn't really true. There are a huge number of processors
|> out there that don't do the divides in hardware for at least some of the
|> types that are commonly used on them. These are not desk top PCs. They
|> are systems that contain a processor but are not general purpose
|> computers.
The context was where branch prediction of the division operation
is critical for performance,
|
No, that is not the context at all. The context was showing a simple
example of code where earlier branches are a very bad predicter of later
branches. The Booth's method only appeared in the discussion because it
is so simple and easy to understand. Other examples were cited.
--
--
kensmith@rahul.net forging knowledge |
|
| Back to top |
|
|
Ken Smith
Guest
|
| Posted:
Sat Aug 13, 2005 1:56 am Post subject:
Re: Branch prediction using counters. |
|
|
In article <1123779133.510860.321150@g44g2000cwa.googlegroups.com>,
Andy Freeman <anamax@earthlink.net> wrote:
| Quote: | Ken Smith wrote:
In article <1123684376.739768.282190@g14g2000cwa.googlegroups.com>,
Andy Freeman <anamax@earthlink.net> wrote:
The object at a given address tends to have the same type for "a
while".
Yes, and once you have XXXXYYYYed that variable, you aren't likely to do
it again. You will XXXXYYYY most of the variables of that same type
though.
Guess why I wrote "object at a given address" and not "variable".
|
You wrote "object" because you couldn't spell "variable". Did I get it
right? :)
[...]
| Quote: | Lots of variables may refer to the same object - the object's address
captures this. The same variable may refer to different objects at
different times; again, object address differences tell you that type
may be different.
|
That has no effect on the argument. Once you have XXXXYYYYed a given
object you are not likely to have to XXXXYYYY it again. This is why the
VMT is the better way to predict.
--
--
kensmith@rahul.net forging knowledge |
|
| Back to top |
|
|
Andy Freeman
Guest
|
| Posted:
Mon Aug 15, 2005 4:15 pm Post subject:
Re: Branch prediction using counters. |
|
|
Ken Smith wrote:
| Quote: | In article <1123779133.510860.321150@g44g2000cwa.googlegroups.com>,
Andy Freeman <anamax@earthlink.net> wrote:
Guess why I wrote "object at a given address" and not "variable".
You wrote "object" because you couldn't spell "variable". Did I get it
right? :)
|
Snark and error in the same sentence.... (Yes, objects aren't
variables.)
| Quote: | Lots of variables may refer to the same object - the object's address
captures this. The same variable may refer to different objects at
different times; again, object address differences tell you that type
may be different.
That has no effect on the argument. Once you have XXXXYYYYed a given
object you are not likely to have to XXXXYYYY it again. This is why the
VMT is the better way to predict.
|
Actually, it does, as my explanation showed. XXXXYYYYing an object's
address does the right thing - it even handles other references to the
same object. XXXYYYing a variable that refers to an object doesn't
work nearly as well because that variable may be used to refer to a
different object at some other time and other references don't get the
benefit of any caching you might do.
-andy |
|
| Back to top |
|
|
Ken Smith
Guest
|
| Posted:
Tue Aug 16, 2005 2:43 am Post subject:
Re: Branch prediction using counters. |
|
|
In article <1124115964.383868.151910@g14g2000cwa.googlegroups.com>,
Andy Freeman <anamax@earthlink.net> wrote:
| Quote: | Ken Smith wrote:
Lots of variables may refer to the same object - the object's address
[...]
That has no effect on the argument. Once you have XXXXYYYYed a given
object you are not likely to have to XXXXYYYY it again. This is why the
VMT is the better way to predict.
Actually, it does, as my explanation showed. XXXXYYYYing an object's
address does the right thing - it even handles other references to the
same object.
|
You are assuming that you need to XXXXYYYY the object more than once.
This is not a good thing to assume. You are very likely to XXXXYYYY many
objects of the same type but much less likely to XXXXYYYY the same
variable more than once.
A good example is some sort of widget that is part of a GUI. The widget
gets constructed, displayed, removed from the display and destroyed. Each
of these is done only once to that object. Others of that same type would
get the same things done to it so optimizing based on the VMT address
would work.
--
--
kensmith@rahul.net forging knowledge |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in