Re: stats on unresolved dependencies (Paul Petersen)
Fri, 28 Jan 1994 16:38:33 GMT

          From comp.compilers

Related articles
stats on unresolved dependencies (Graham Jones) (1994-01-24)
Re: stats on unresolved dependencies (1994-01-28)
Re: stats on unresolved dependencies (Beatrice Apvrille) (1994-01-31)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Paul Petersen)
Keywords: analysis, parallel
Organization: UIUC Center for Supercomputing Research and Development
References: 94-01-096
Date: Fri, 28 Jan 1994 16:38:33 GMT

Graham Jones <> writes:
>Dependencies that can not be resolved at compile time force compilers to
>generate serial code. I am interested in finding out how often (in
>scientific applications), and in what programs they tend to occur.

This is one of the topics on which I've had some discussion/arguments with
other people in this area. From reading many papers about static
dependence analysis it seems to me that the first thing people do in an
experiment is to throw out the "hard" non-affine subscripts and only
report the results on the remaining subscript pairs. Obviously, defining
the potential universe in this way makes the static dependence tests look
much better since they would have no chance at all on the non-affine

As part of my thesis "Evaluation of Programs and Parallelizing Compilers
using Dynamic Analysis Techniques" (available via anonymous FTP to as CSRD_Info/reports/1273.Z), I did a static evaluation
of the dependence analysis to give a background to the dynamic evaluation.
As part of this work I wanted to see when the dependence tests I used
failed. For the Perfect Benchmarks, I classified them according to the
worst coefficient type and then by the worst part of the constant term. I
came up with the following table. To get more details on how the
experiment was performed please refer the my thesis.

                                                                                    Coefficient Type
                                              Numeric Loop Invariant Loop Variant Array
Constant Type Constant Scalar Scalar
Numeric Constant | --- | 1709 | 103 | 477 |
Loop Invariant Scalar | 367 | 3599 | 141 | --- |
Loop Variant Scalar | 3204 | 2517 | 105 | --- |
Array | 3736 | 91 | --- | --- |

                                              Classification of unanalyzable subscripts

>From examining this table it appears obvious that the worst case was
simple subscripted subscripts. The reference pattern A(C*I+IP(I))
occurred 3736 times. The next most common case A(M*I+N) occurred 3599
times. And the case A(I+X) occurred 3204 times. In these examples A() is
an array, IP() is an index array, M & N are loop invariant scalars, and X
is a loop variant scalar. The token C refers to a numeric constant,
usually either 1 or 0.

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