🚀 go-pugleaf

In article <lj976dINNg4d@exodus.Eng.Sun.COM> grover@brahmand.Eng.Sun.COM (Vinod Grover) writes:
> I suggest you read the Butler et. al. paper cited [1] earlier by someone
> in this thread. These authors claim that on an unrestricted data flow
> machine, *general purpose* codes like gcc, li, eqntott, (taken from
> SPEC89) have pretty high degree of parallelisms in them. Measured in
> terms of IPC:
> 
>   gcc - 38
>   espresso - 179
>   eqntott - 300
>   li - 162
> 
> Judging from these claims, the issue is not how much parallelism there
> is but how cost-effective is it to extract it. As CPU resources
> approach realistic values the sustainable issue rates on these codes
> fall dramatically, (2-4). These are limits imposed by the
> hardware/compilers. 
> 
> [1] Butler, Yeh, Patt, Alsup, Scales, Shebanow, "Single Instruction
> Stream Parallelism is Greater than Two", Intnl. Symp. on Comp. Arch
> 1991. 

Unfortunately, the limited degree of parallelism in general-purpose
codes is NOT just due to the current state of hardware and compilers.
The study by Butler et al. contains some interesting results and is
definitely worth reading but don't put too much weight on the numbers
for the Unrestricted Dataflow (UDF) Machine.  This machine only considers
data dependences.  In the programs mentioned above, however, most of the
computation centers around executing branches, so the limiting factor is
not just WHEN can the instructions execute, but also WHICH instructions
will be executed.  The UDF machine completely ignores these control
dependences which are an inherent part of the program semantics and not
just a side effect of limited hardware and compilers.

There are, of course, some things we can do to try to mitigate the
effects of control dependences.  Branch prediction with speculative
execution, control dependence analysis, and multiple processors are
three things that we have found so far [2].  As new techniques are
developed, we can certainly expect to extract more parallelism from
general-purpose codes, but for now, I think 2 - 4 is a reasonable
estimate for the IPC of a uniprocessor.

Bob Wilson
bwilson@shasta.stanford.edu

[2] Monica Lam and Robert Wilson, "Limits of Control Flow on Parallelism",
19th Intnl. Symp. on Comp. Arch, 1992.