Re: 200 way issue?

davidm@questor.rational.com (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:


@article{kumar:88
      ,AUTHOR="Manoj Kumar"
      ,TITLE="{M}easuring {P}arallelism in {C}omputation-{I}ntensive {S}cience
                        / {E}ngineering {A}pplications"
      ,JOURNAL="IEEE Transactions on Computers"
      ,PAGES="5--40"
      ,VOLUME=37
      ,NUMBER=9
      ,YEAR=1988
}


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
renaming.


Also, I should plug my recent dissertation. I used the Perfect Benchmarks
to generate my information. It is available on sp2.csrd.uiuc.edu 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"
      ,MONTH="January"
      ,YEAR=1993
}


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 (petersen@csrd.uiuc.edu)
--
University of Illinois, Urbana-Champaign
Center for Supercomputing Research and Development


        UUCP: {uunet,convex}!uiucuxc!uicsrd!petersen
        INTERNET: petersen@csrd.uiuc.edu
--

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