papers on symbolic data dependence analysis

In answer to my question


      In M. Haghighat and C. Polychronopoulos paper "Symbolic Dependence
      Analysis for High Performance Parallelising Compilers, Advances in
      Languages and Compilers for Parallel Processing, 1991" the authors
      indicate the large number of arrays with symbolic subscripts. Classical
      dependency tests fail in the presence of symbolic terms but can be
      assisted by global constant propagation, forward and induction variable
      substitution. Does anyone know of the number of cases that still remain
      unanalysable after these optimisations have taken place ? Given that some
      subsripts can still not be analysed, we need to develop symbolic
      dependency tests to handle these cases. Does anyone know of any current
      work and useful papers in this area ?


I have received the following replies from


Jim Davies jrbd@craycos.com
Alain Darte darte@acri.fr
Be'atrice Creusillet creusillet@cri.ensmp.fr
Lode Nachtergaele nachterg@imec.be


Many thanks for your help. I have included their replies for anyone
interested in this area. If you know of any other works I would be glad to
hear from you


regards


Graham Jones


-------------------- jrbd@craycos.com -----------------------


I believe there was a study of different types of subscripts and their
frequency in Fortran programs done by Zhiyuan Li and Pen-Chung Yew at CSRD
a few years ago. It might have been in the ICPP proceedings from 1989 or 1990
-- I'm not sure. The authors are apparently both going to be at the University
of Minnesota this fall; the last email addresses I have for them
are li@cs.umn.edu and yew@csrd.uiuc.edu respectively.


gxj > I looked this up, I believe it is
gxj > @InProceedings{shen:89,
gxj > author = " Z. Shen and Z. Li and P-C. Yew ",
gxj > title = "An {E}mpirical {S}tudy on {A}rray {S}ubscripts and
gxj > {D}ata {D}ependences",
gxj > booktitle = "1989 International Conference on Parallel Processing",
gxj > year = "1989",
gxj > pages = "II-145--II-152"




-------------------- darte@acri.fr -------------------------


The best references seem to be the work by Paul Feautrier:


@ARTICLE{Feautrier88b,
                AUTHOR = {Paul Feautrier},
                JOURNAL = {RAIRO Recherche Op\'{e}rationnelle},
                MONTH = sep,
                PAGES = {243--268},
                TITLE = {Parametric Integer Programming},
                VOLUME = {22},
                YEAR = {1988}
}


@INPROCEEDINGS{Feautrier89,
                AUTHOR = {Paul Feautrier},
                ADDRESS = {North Holland},
                BOOKTITLE = {Parallel and distributed algorithms},
                EDITOR = {M. Cosnard and al.},
                PAGES = {309-320},
                PUBLISHER = {Elsevier Science Publishers B.V.},
                TITLE = {Semantical analysis and mathematical programming},
                YEAR = {1989}
}


@ARTICLE{Feautrier91,
                AUTHOR = {Paul Feautrier},
                JOURNAL = {Int. J. Parallel Programming},
                NUMBER = {1},
                PAGES = {23-51},
                TITLE = {Dataflow analysis of array and scalar references},
                VOLUME = {20},
                YEAR = {1991}
}


The last reference explains the dependence analysis technique for flow
dependences. This technique can be easily extended to other kind of
dependences. The first reference describes the linear programming
algorithm that is needed. It is of course a parametric algorithm. These
algorithms have been implemented and I think are available. Ask directly
to Paul Feautrier: Paul.Feautrier@prism.uvsq.fr.


A lot of people now use this kind of technique as a base for their
personal work: you may be interested by work by Vincent Van Dongen in
Montreal, Patrice Quinton in Rennes, Yves Robert and myself in Lyon, etc..
If you are interested, I may send you some papers.


--------------------- creusillet@cri.ensmp.fr ------------------


In PIPS, the Interprocedural Parallelizer of Scientific Programs developed
at Ecole des Mines de Paris, interprocedural symbolic semantics analysis
is performed in order to parallelize large Fortran programs. Several kind
of information are propagated through the flow graph of each procedure or
function and through the call graph.


Briefly, the 'preconditions ' are predicates over scalar integer variable
values, which hold true just before a statement is executed. It is an
interprocedural version of Cousot and Halbwachs' algorithm. For instance,
the predicate 'P(I,K,N,M) {1<=I,I<=N, K==I+N}' shows that variables I, K,
N and M have already been assigned a value, and we know that the current
value of I is between 1 and N and that the values of K, I, and N are
constrained by K==I+N.


The 'regions' are sets of array elements defined by affine equalities and
inequalities. For instance the region <A(PHI1)-{I<=PHI1, PHI1<=I+1}>
represents the set of the two elements A(I) and A(I+1) (PHI1 represents
the elements of the first dimension). Regions are also propagated
interprocedurally. They include the relations given by the repconditions.


Preconditions and regions can be used to improve dependence analsyis.
Experiments performed on codes from the Perfect Club yield encouraging
results.


              & nb of array & independences found
              & pairs & prec. only & regions
              & & &
arc2d & 6843 & 2311 & 2557
flo52 & 3717 & 1216 & 1446
mdg & 2971 & 200 & 342
track & 2028 & 107 & 200
trfd & 1335 & 2 & 6


You will find more precise information in the following papers:


@INPROCEEDINGS{Irig:91,
AUTHOR = "Irigoin, Franc,ois
and Jouvelot, Pierre
and Triolet, Re'mi ",
TITLE = {Semantical Interprocedural Parallelization : An Overview of the
   {PIPS} project},
BOOKTITLE = {Supercomputing'91},
YEAR = 1991,
MONTH = jun,
}


@INPROCEEDINGS{Irig:92,
AUTHOR = "Irigoin, Franc,ois",
TITLE = {Interprocedural Analyses for Programming Environments},
BOOKTITLE = {Workshop on Environments and Tools for Parallel Scientific
Programming, Saint-Hilaire du Touvier, France},
YEAR = 1992,
MONTH = sep,
}


@PHDTHESIS{Yang:93,
AUTHOR = {Yang, Yi-Qing},
TITLE ={Tests des De'pendances et Transformations de Programme},
SCHOOL = {Universite Paris VI, France},
YEAR = 1993,
NOTE = {in French},
MONTH = nov,
}




----------------------- nachterg@imec.be ------------------------


please find included a list of reference to sources that deal with
dependence testing. Some of them only deal with static dependences.




@inproceedings{anc91,
      key = {Anc91},
      author = {C. Ancourt and F. Irigoin},
      title = {Scanning polyhedra with DO loops},
      booktitle = {Third ACM Symposium on Princliples and Practice of parallel
              programming},
      year = {1991},
      month = {April},
      pages = {pp. 39-50},
      note = {no paper copy}
}




@book{ban93,
      key = {Ban93},
      author = {Uptjal Banarjee},
      title = {Loop transformations for restructuring compilers : The foundation},
      year = {1993},
      publisher = {Kluwer Academic Publisher}
}




@article{bar87,
      key = {Bar87},
      author = {I. B{\'a}r{\'a}ny and Z. F{\"u}redi},
      title = {Computing the volume is difficult},
      journal = {Discrete Comput. Geom.},
      year = 1987 ,
      volume = 2 ,
      pages = {319--326},
      keywords = {approximation, volume, convex}
}




@inproceedings{bu88,
      key = {Bu88},
      author = {Jichun Bu and Ed F. Deprettere},
      title = {Converting Sequential Iterative Algorithms to Recurrent Equations for Automatic Design of Systolic Arrays},
      booktitle = {ICASSP '88},
      year = {1988},
      pages = {pp. 2025-2028}
}




@inproceedings{bu88a,
      key = {Bu88},
      author = {Jichun Bu and Ed F. Deprettere},
      title = {Analysis and Modeling of Sequential Iterative Algorithms for parallel and pipeline Implementations},
      booktitle = {ISCAS'88},
      organization = {IEEE},
      year = {1988},
      pages = {pp. 1961-1965}
}




@techreport{col93,
      key = {Col93},
      author = {Jean-Francois Collard and Paul Feautrier and Tanguy Risset},
      title = {Construction of DO loops from systems of affine constraints},
      institution = {Laboratoire de l'informatique du Parallelisme, Ecolo Normale Superieure de Lyon, Institut IMAG},
      year = {1993},
      month = {May},
      note = {ftp://lip.ens-lyon.fr:pub/LIP/Rapports/RR/RR93/RR93-15.ps.Z}
}




@techreport{col93a,
      key = {Col93a},
      author = {Jean-Francois Collard},
      title = {Code generation in automatic parallelizers},
      institution = {Laboratoire de l'informatique du Parallelisme, Ecolo Normal Superieure de Lyon, Institut IMAG},
      year = {1993},
      month = {July},
      note = {ftp://lip.ens-lyon.fr:pub/LIP/Rapports/RR93/RR93-21.ps.Z}
}




@unpublished{eis92,
      key = {Eis92},
      author = {Christine Eisenbeis and Jean-Claude Sogno},
      title = {A general algorithm for data dependence analysis},
      year = {1992},
      month = {May},
      category = {ldde},
      note = {Have to find the number yet}
}




@techreport{eis92a,
      key = {Eis92},
      author = {Christine Eisenbeis and Oliver Temam and Harry Wijshoff},
      title = {On efficiently characterizing solutions of linear Diophantine equations and its application to data dependence analysis},
      institution = {INRIA},
      year = {1992},
      month = {July},
      address = {Domaine de Voluceau, 78153 Le Chersnay CEDEX, France}
}




@phdthesis{hav94b,
      key = {Hav94},
      author = {Paul Havlak},
      title = {Interprocedural Symbolic Analysis},
      year = {1994},
      month = {May},
      address = {Houston, Texas},
      school = {Rice University}
}


@techreport{jeg93,
      key = {Jeg93},
      author = {Yvon Jegou},
      title = {Characterization of program dependencies by integer programming techniques},
      institution = {INRIA},
      year = {1993},
      month = {November},
      address = {IRISA, Campus universitaire de Beaulieu, 35042 RENNES Cedex (France)},
      number = {Nr. 2138}
}




@techreport{kul94,
      key = {Kul94},
      author = {Dattatraya Kulkarni and Michael Stumm},
      title = {Computational alignment: A new, unified program transformation for local and global optimization},
      institution = {Computer Systems Research Institute, Depearment of computer science},
      year = {1994},
      month = {january},
      address = {Toronto, Canada M5S 1A4},
      note = {ftp://ftp.csri.toronto.edu:csri-technical-reports/292/292.ps.Z}
}




@inproceedings{mas94,
      key = {Mas94},
      author = {Vadim Maslov},
      title = {Lazy Array Data-Flow Dependence Analysis},
      booktitle = {Proceedings of the 21st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages},
      year = {1994},
      month = {January},
      pages = {pp. 311-325}
}




@techreport{mas94a,
      key = {Mas94},
      author = {Vadim Maslow and William Pugh},
      title = {Simplifying Polynomial Constraints over integers to make dependence analysis more precise},
      institution = {Dept. of computer Science, University of Maryland},
      year = {1994},
      month = {February},
      address = {College Park, MD 20742},
      number = {CS-TR-3109.1}
}




@techreport{may92,
      key = {May92},
      author = {Dror Eliezer Maydan},
      title = {Accurate analysis of array references},
      institution = {Computer systems laboratory, Stanford University, Stanford},
      year = {1992},
      month = {September},
      number = {CSL-TR-92-547}
}




@incollection{mvs94,
      key = {Mvs94},
      author = {Michael F.X.B. van Swaaij and Frank H.M. Franssen and Francky V.M. Catthoor and Hugo J. De Man},
      title = {Modeling Data Flow and Control Flow for DSP System Synthesis},
      booktitle = {VLSI Design Methodologies for Digital Signal Processing Architectures},
      year = {1994},
      editor = {Magdy A. Bayoumi},
      publisher = {Kluwer Academic Publishers},
      pages = {pp. 219-259}
}


@article{psa93,
      key = {Psa93},
      author = {Kleanthis Psarris and Xiangyun Kong and David Klappholz},
      title = {The Direction Vector I test},
      journal = {IEEE Transactions on Parallel and Distributed Systems},
      year = {1993},
      month = {November},
      volume = {Vol. 4},
      number = {No. 11},
      pages = {pp. 1280}
}




@techreport{pug92,
      key = {Pug92},
      author = {William Pugh and David Wonnacott},
      title = {Static Analysis of Upper Bounds on Parallelism},
      institution = {Institute for Advanced Computer Studies, Dept. of computer science},
      year = {1992},
      month = {November},
      number = {CS-TR-2994},
      category = {ldde}
}




@inproceedings{pug92a,
      key = {Pug92},
      author = {William Pugh and David Wonnacott},
      title = {Eliminating False Data Dependences using the Omage Test},
      booktitle = {SIGPLAN PLDI'92},
      year = {1992}
}




@techreport{pug92b,
      key = {Pug92},
      author = {William Pugh and David Wonnacott},
      title = {Going beyond Integer Programming with the Omega test to Eliminate False Data Dependences},
      institution = {Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland},
      year = {1992},
      month = {December},
      address = {College Park, MD 20742}
}




@techreport{pug93,
      key = {Puh93},
      author = {William Pugh and David Wonnacott},
      title = {An exact method for analysis of value-based array data
              dependences},
      institution = {Institute for advanced computer studies},
      year = {1993},
      month = {December},
      address = {Univ. of Maryland, College Park, MD 20742},
      number = {CS-TR-3196}
}




@techreport{qui94,
      key = {Qui94},
      author = {Patrice Quinton and Sanjay Rajopadhye and Doran Wilde},
      title = {Using static analysis to derive imperative code from ALPHA},
      institution = {Irisa},
      year = {1994},
      month = {May}
}




@inproceedings{ram94,
      key = {Ram94},
      author = {L.Ramachandran and D.Gajski and V.Chaiyakul},
      title = {An Algorithm for Array Variable Clustering},
      booktitle = {Proc. 5th ACM/IEEE Europ. Design and Test Conf.},
      year = {1994},
      month = {Feb.},
      address = {Paris, France},
      pages = {262-266}
}


@techreport{ver94,
      key = {Ver94},
      author = {Herv\'{e} Le Verge and Vincent Van Dongen and Doran K. Wilde},
      title = {Loop nest synthesis using the polyhedral library},
      institution = {IRISA},
      year = {1994},
      month = {May}
}




@phdthesis{vsw92,
      key = {VSw92},
      author = {Michael F.X.B. van Swaaij},
      title = {Data Flow Geometry: Exploiting Regularity in System-level
              Synthesis},
      year = {1992},
      school = {Katholieke Universiteit Leuven}
}




@phdthesis{wal94,
      key = {Wal94},
      author = {Edward Walker},
      title = {Extracting dataflow information for parallelizing FORTRAN nested loop kernels},
      year = {1994},
      month = {April},
      address = {Advanced Computer Architecture Group, The Department of Computer Scinece},
      school = {The University of York},
      note = {ftp://minster.york.ac.uk/pub/edward}
}




@techreport{wil93,
      key = {Wil93},
      author = {Wilde, D.},
      title = {A library for Doing Polyhedral Operations},
      institution = {IRISA},
      year = {1993},
      month = {December},
      address = {Rennes, France},
      number = {Internal Publication 785}
}






@article{wol87,
      key = {Wol87},
      author = {Michael Wolfe and Uptjal Banarjee},
      title = {Data Dependence and its Application to Parallel Processing},
      journal = {International Journal of Parallel Programming},
      year = {1987},
      volume = {Vol. 16},
      number = {No. 2},
      pages = {pp. 137-178}
}




@unpublished{xin93,
      key = {Xin93},
      author = {Zhaoyun Xing and Weijia Shang},
      title = {Accurate Data Dependence Test},
      year = {1993},
      month = {May},
      note = {Submitted to ASAP112A}
}


--

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