Re: Can someone explain step by step how one avoid many conditional in forth as described in Moore Fourth essay?

From	Arnold Doray <invalid@invalid.com>
Newsgroups	comp.lang.forth, comp.sys.intel, comp.arch
Subject	Re: Can someone explain step by step how one avoid many conditional in forth as described in Moore Fourth essay?
Date	2012-01-11 15:03 +0000
Organization	A noiseless patient Spider
Message-ID	<jek8ch$frt$3@dont-email.me> (permalink)
References	<19111298.516.1326191150632.JavaMail.geo-discussion-forums@yqbu38> <jehfpu$9de$1@dont-email.me> <jejuor$922$1@speranza.aioe.org>

Cross-posted to 3 groups.

Show all headers | View raw

On Wed, 11 Jan 2012 07:21:53 -0500, Rod Pemberton wrote:

> "Arnold Doray" <invalid@invalid.com> wrote in message
> news:jehfpu$9de$1@dont-email.me...
> ...
> 
>> > [Forth code]
>>
>> CPU pipelining is improved by reducing conditionals. Modern CPUs have
>> branch prediction, but these aren't always successful, in which case
>> the pipline needs to be flushed, lowering the CPU's throughput.
> 
> Is that still true for multiple cores?
> 
> I.e., I would think the following is entirely possible and plausible,
> but I haven't studied a CPU design in decades.  The CPU's designers
> could execute the process in parallel with one core taking one direction
> for the branch and the another core taking the other branch direction. 
> Once the correct branch is determined, the bad execution path is
> discarded.  If the primary core had the good execution path, it just
> continues execution.  If the alternate core had the good execution path,
> it's internal state could be "pushed" to the primary core.  If they used
> static ram for the internal state, then it could be "pushed"
> asynchronously, i.e., between clocks or sub-clocks.  It would require
> reserving a core for the branch path execution, at least temporarily.
> 
> 
> Rod Pemberton

I don't think this is how it's done on modern CPUs. They use branch 
prediction, which can be as good as 70% - 80% right,if I recall 
correctly. When the wrong branch is taken, the entire pipeline needs to 
be flushed. That's the reason to avoid conditionals. 

But let's say for argument's sake that you're right. There are a few 
problems with your scheme: 

1) It's slow: because you're tying up another core. So you effectively 
have one core less than previously. 

2) Also, the switching overhead may be large if it has to be done often. 

3) What happens with code containing multiple branches? You can't follow 
them all. What to do? 

4) Let's suppose you have lots of cores so that (3) is not a big issue. 
Still, the number of instructions before the next branching could be less 
than your pipeline's depth. So you're wasting the advantage offered by a 
deep pipeline. 

Thinking about Gavino's questio again, it occurs to me that with 
predictive branching, a long loop will almost never flush the pipeline 
(because the prediction is done by keeping statistics of the historical 
branch choices). So this reason alone (pipeline flushing) is not a good 
reason avoid using loops. Perhaps CM's comments were made when the 
prediction was not as sophisticated as it is now. 

Of course, avoiding conditionals entirely will give a faster solution. 
How much faster is the question. Anyone has comments/experience with this?

Cheers,
Arnold

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

csiph-web