Re: stats on unresolved dependencies

Graham Jones <gxj@dcs.ed.ac.uk> 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
subscripts.


As part of my thesis "Evaluation of Programs and Parallelizing Compilers
using Dynamic Analysis Techniques" (available via anonymous FTP to
sp2.csrd.uiuc.edu 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
        INTERNET: petersen@csrd.uiuc.edu
--

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