Dependence Analysis (Loop Transformation for Restructuring by Utpal Banerjee

By Utpal Banerjee

Dependence research might be thought of to be the second one variation of the author's 1988 booklet, Dependence research for Supercomputing. it really is, besides the fact that, a totally new paintings that subsumes the cloth of the 1988 e-book. This publication is the 3rd quantity in the sequence Loop differences for Restructuring Compilers. This sequence has been designed to supply a whole mathematical conception of differences that may be used to immediately switch a sequential application containing FORTRAN-like do loops into an identical parallel shape. In Dependence research, the writer extends the version to a application which includes do loops and task statements, the place the loops don't need to be sequentially nested and are allowed to have arbitrary strides. within the context of this sort of software, the writer experiences, intimately, dependence among statements of this system attributable to application variables which are components of arrays. Dependence research is directed towards graduate and undergraduate scholars, writers of restructuring compilers. The prerequisite for the e-book comprises a few wisdom of programming languages, and familiarity with calculus and graph idea. No wisdom of linear programming is needed.

Show description

Read or Download Dependence Analysis (Loop Transformation for Restructuring Compilers) PDF

Best compilers books

Programming in Prolog

Initially released in 1981, this was once the 1st textbook on programming within the Prolog language and continues to be the definitive introductory textual content on Prolog. notwithstanding many Prolog textbooks were released on the grounds that, this one has withstood the attempt of time as a result of its comprehensiveness, instructional strategy, and emphasis on basic programming purposes.

XML and Web Technologies for Data Sciences with R (Use R!)

Internet applied sciences are more and more appropriate to scientists operating with facts, for either getting access to information and growing wealthy dynamic and interactive displays.  The XML and JSON info codecs are standard in internet providers, typical websites and JavaScript code, and visualization codecs similar to SVG and KML for Google Earth and Google Maps.

Additional resources for Dependence Analysis (Loop Transformation for Restructuring Compilers)

Example text

First, note that the sets YI, ~ - 1, Y0 r e p r e s e n t the following three d e p e n d e n c e s , respectively: 1. loop-carried d e p e n d e n c e of T on S, 2. loop-carried d e p e n d e n c e of S o n T, 3. l o o p - i n d e p e n d e n t d e p e n d e n c e of T on S (provided S < T). We cannot have a l o o p - i n d e p e n d e n t d e p e n d e n c e of S on T, since S < T by hypothesis. A s s u m e n o w that a, b are n o t b o t h zero. The values of t defining a n o n e m p t y Y-set f o r m a finite sequence of c o n t i g u o u s integers (steps 8, 12, 13).

The iteration p o i n t s are c o n t i g u o u s while the index p o i n t s generally are not. The iteration variable [ always increases f r o m zero in steps of one as the loop is e x e c u t e d sequentially. The index variable I, on the o t h e r hand, m a y increase or decrease d e p e n d i n g on the sign of 0, a n d will n o t c h a n g e in s t e p s of one if 101 > 1. For this reason, it is easier to w o r k with ~ rather t h a n with I. 5) where ~ is an integer. Also, I m u s t lie b e t w e e n 120 and 10.

12(a) become /~(7, - 3 , 0, 38, 0) < c < v ( 7 , - 3 , 0 , 3 8 , 0 ) . 21), and get the inequalities - 1 1 4 < - 5 < 152 which obviously hold. 12, a d e p e n d e n c e of T on S m a y exist. 5 that this is indeed the case. Next, s t u d y the possible d e p e n d e n c e of S on T.

Download PDF sample

Rated 4.16 of 5 – based on 35 votes