Re: 200 way issue? (Paul Petersen)
Thu, 30 Sep 1993 14:12:29 GMT

          From comp.compilers

Related articles
200 way issue? (1993-09-29)
Re: 200 way issue? (1993-09-30)
Re: 200 way issue? (1993-09-30)
Re: 200 way issue? grover@brahmand.Eng.Sun.COM (1993-09-30)
Re: 200 way issue? (1993-09-30)
Re: 200 way issue? (1993-10-01)
Re: 200 way issue? (1993-10-01)
Re: 200 way issue? (Dave Gillespie) (1993-10-04)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Paul Petersen)
Keywords: performance, bibliography
Organization: UIUC Center for Supercomputing Research and Development
References: 93-09-142
Date: Thu, 30 Sep 1993 14:12:29 GMT (David Moore) writes:

>Suppose, for example, we took the spec benchmarks and optimized for an
>infinite issue machine. Now suppose we built a histogram of actual number
>of instructions issued per machine cycle. Has anyone published a paper on
>what this histogram would look like?

Yes, many of these histograms have been generated and some published. You
might start with the article:

      ,AUTHOR="Manoj Kumar"
      ,TITLE="{M}easuring {P}arallelism in {C}omputation-{I}ntensive {S}cience
                        / {E}ngineering {A}pplications"
      ,JOURNAL="IEEE Transactions on Computers"

The idea is to treat a sequential program as if it were a description for
a dataflow computation. You enforce the flow-dependences and ignore the
output- and anti- dependences that are found as you dynamically simulate
the execution of the program. The output- and anti- dependences are
ignored to simulate the effect of scalar and array expansion and variable

Also, I should plug my recent dissertation. I used the Perfect Benchmarks
to generate my information. It is available on in
CSRD_Info/reports/1273.Z. This describes how to do the instrumentation
and also how to interpret the results in the context of the source code.
The model I used mostly is for loop-level parallelism, but simulating
operation level parallelism is also possible.

@phdthesis{ petersen:93
      ,TITLE="{Evaluation of Programs and Parallelizing Compilers Using Dynamic
                        Analysis Techniques}"
      ,AUTHOR="Paul M. Petersen"
      ,SCHOOL="University of Illinois at Urbana-Champaign"

Many other people have done work in this area, a student here at CSRD has
recently released a paper which gives parallelism information for the SPEC
benchmarks. I may have to convince him to post a little information about
his system.

In general the parallelism rates for the loop-level are usually in the
10's-100's. The parallelism rates for operation level are in the
10's-1000's. This is all assuming that no algorithm substitution is
performed, the parallelism implicit in the flow-dependences is exploited
using a very simple model of a parallel machine.

I guess the conclusion is, the potential for parallelism is contained in
almost all programs. The problems come in trying to get enough
information available at compile time to exploit the parallelism.

-Paul Petersen (
University of Illinois, Urbana-Champaign
Center for Supercomputing Research and Development

        UUCP: {uunet,convex}!uiucuxc!uicsrd!petersen

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.