Dependence Analysis (Loop Transformation for Restructuring by Utpal Banerjee

By Utpal Banerjee

Dependence Analysis can be thought of to be the second one variation of the author's 1988 ebook, Dependence research for Supercomputing. it's, even though, a totally new paintings that subsumes the cloth of the 1988 book. This booklet is the 3rd quantity in the sequence Loop Transformations for Restructuring Compilers. This sequence has been designed to supply an entire mathematical concept of ameliorations that may be used to immediately swap a sequential software containing FORTRAN-like do loops into an an identical parallel shape.
In Dependence Analysis, the writer extends the version to a application which include do loops and project statements, the place the loops don't need to be sequentially nested and are allowed to have arbitrary strides. within the context of any such software, the writer experiences, intimately, dependence among statements of this system because of software variables which are components of arrays.
Dependence Analysis is directed towards graduate and undergraduate scholars, writers of restructuring compilers. The prerequisite for the ebook includes a few wisdom of programming languages, and familiarity with calculus and graph thought. No wisdom of linear programming is needed.

Show description

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

Best compilers books

A UML Pattern Language, Edition: illustrated edition

A UML development Language pairs the software program layout development proposal with the Unified Modeling Language (UML) to supply a device set for software program pros working towards either process modeling and software program improvement. This ebook presents: a suite of styles within the area of process modeling, together with those who are invaluable to administration, operations, and deployment groups, in addition to to software program builders; a survey of the improvement of styles and the UML; a dialogue of the underlying thought of the styles and directions for utilizing the language; a radical exploration of the layout method and model-driven improvement.

Parallel Machines: Parallel Machine Languages: The Emergence of Hybrid Dataflow Computer Architectures (The Springer International Series in Engineering and Computer Science)

It really is universally accredited this present day that parallel processing is right here to stick yet that software program for parallel machines remains to be tough to increase. even if, there's little popularity of the truth that alterations in processor structure can considerably ease the advance of software program. within the seventies the supply of processors that can tackle a wide identify area at once, eradicated the matter of brand administration at one point and cleared the path for the regimen improvement of huge courses.

Semantics, Logics, and Calculi: Essays Dedicated to Hanne Riis Nielson and Flemming Nielson on the Occasion of Their 60th Birthdays (Lecture Notes in Computer Science)

This Festschrift quantity is released in honor of Hanne Riis Nielson and Flemming Nielson at the social gathering in their sixtieth birthdays in 2014 and 2015, respectively. The papers integrated during this quantity take care of the broad region of calculi, semantics, and research. The ebook beneficial properties contributions from colleagues, who've labored including Hanne and Flemming via their clinical existence and are devoted to them and to their paintings.

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

Sample text

6) b e c o m e s 4~ - 6~ = 2. 7) b e c o m e 0 < [ < 49 and 0 < ~ < 49. 8) s u c h t h a t ~ a n d ~ are non_negative i n t e g e r s n o t larger t h a n 49. One s u c h s o l u t i o n is clearly (2, 1), a n d t h e r e are m a n y o t h e r s . However, a n y s u c h s o l u t i o n m u s t n e c e s s a r i l y s a t i s f y ~ > ~ (Exercise 3). 7) t h a t T 6 S h o l d s a n d t h a t S 6 T d o e s not. W h e t h e r T 6 S is t r u e w o u l d d e p e n d o n t h e p a r t o f t h e loop b o d y n o t s h o w n .

Since c = f(x,y) for s o m e p o i n t ( x , y ) E P, it follows that re_in f ( x , y ) <_ c <_ m a x f ( x , y ) . (x,y)EP (x,y)EP By definition, g ( a , b, p, q, ~) a n d v ( a , b, p, q, ~) are the m i n i m u m and m a x i m u m values, respectively, of the f u n c t i o n ( x , y ) ~ a x + b y in the triangle b o u n d e d by t h e lines: x = p , y = q , a n d x < y - ~. Hence, we have rn~n f ( x , y ) = u ( a , - b , O, ~, O) (x,y)~P max f(x,y) (x,y)~P = v(a,-b,O,~,O), so that the following inequalities hold: g(a,-b,0,~,0) < c < v(a,-b,O,~,O).

I~o - - ~. 5. Since a ~: b, go to Step 9. ] 9 "- 1, (~o,,3o) -- (1, 2). Since c m o d 9 = 0, continue. 10. ( ~ 2 1 , ~ 1 , ¢ 1) "-- (alg, blg, c/9) = (7,3,-5). 5. SOLUTION TO THE LINEAR PROBLEM 11. Go to Case (bl > 0). Vl -- [ - c l [ o / b l ] = 2, T 2 '-- [ ( 3 Cl[o)/bl] = 14. Go to Case (al > 0). T 1 '-- m a x (T1, [ - - C 1 , ~ 0 / / 2 1 ] ) = 2, T 2 "-- m i n (T2, [(t~ - C l ) 0 ) / ~ / 1 ] ) = Since T1 --< T 2 , continue. 12. ~ ~ Cl([0 - 3o)/(al - bl) 43 6. = 5/4. ] 13. T3 "-- [ ~ - - 11 = 1, ,-- + I J = 2, T5 "" m i n ( T 2 , T 3 ) -- max = 1, ('rl, V4) = 2.

Download PDF sample

Rated 4.36 of 5 – based on 20 votes