Tue, 30 Aug 1994 09:39:26 GMT

Related articles |
---|

papers on symbolic data dependence analysis gxj@dcs.ed.ac.uk (Graham Jones) (1994-08-30) |

Newsgroups: | comp.compilers |

From: | Graham Jones <gxj@dcs.ed.ac.uk> |

Keywords: | analysis, summary, bibliography |

Organization: | Department of Computer Science, University of Edinburgh |

Date: | Tue, 30 Aug 1994 09:39:26 GMT |

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}

*}*

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.