W. Blume, Symbolic Analysis techniques for Effective Automatic Parallelization, PhD Thesis, University of Illinois at Urbana-Champaign, June 1995  @ NUS  Home/Search   Document Details and Download   Summary   Related Articles   Check

....in which every nonrecursive call chain is distinguished; the result is similar to a program which is fully inlined except for recursive calls. 2.7. 3 Interprocedural Symbolic Analysis Some other approaches to symbolic analysis incorporate the additional features of demand based propagation [16, 115] and sparseness [55, 115] within a procedure to reduce the expense of the analysis. While they may improve analysis performance, due to the complexity of the techniques, interprocedural analysis is handled differ ently than intraprocedural analysis. Since the cost of the parallelization analysis ....

....that the compiler understands. By contrast, our approach can be used to derive more general predicates, run time evaluable predicates constituting of arbitrary program statements. flow problems including constant propagation [119] type analysis [108] symbolic analysis for parallelization [49, 16], and the array data flow analysis [47, 116, 115] Tu and Padua present a limited sparse approach on a gated SSA graph that is demand based, only examining predicates if they might assist in loop bounds or subscript val ues for parallelization, a technique that appears to be no more powerful than ....

[Article contains additional citation context not shown here]

W. J. Blume. Symbolic Analysis Techniques for Effective Automatic Paral- lelization. PhD thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, June 1995.

....array #, the triplet notation for the array is denoted by #(# # :# # :# # , # # :# # :# # , # # :# # :# # ) where # # , # # and # # are respectively the lower bound, upper bound and stride in the #th dimension of #. Triplet notation is simple, yet practical. Many experimental studies [6, 10, 22, 41] also have shown that for most array accesses, the representation with triplet notation is exact, and that when the representation is exact, a compiler can use fast (mostly linear time) interval arithmetic [29] to perform region operations without losing any precision. This advantage has led ....

....the accuracy in a given situation. The Polaris compiler [7] at the University of Illinois has used full symbolic triplet notation to represent array accesses within its array privatization pass [41] and a partial triplet notation (lower:upper) for representing value ranges for dependence analysis [6]. 4 Analysis of Array Access Patterns The development of a new array region descriptor was originally motivated by our project [32, 34] to retarget the Polaris compiler at nonuniform memory access (NUMA) multiprocessors. In that project, the triplet notation used by Polaris for array access ....

[Article contains additional citation context not shown here]

W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Univ. of Illinois at Urbana-Champaign, Dept. of Computer Science, June 1995.

....and subscript expression coefficients. Exacerbating the problem of dependence testing techniques with a limited domain of applicability is the limited form typically used for representing memory accesses. Triplet notation (begin : end : stride) and various derivatives of this form have been tried [2, 6, 18], as have sets of linear constraints. As indicated in [8, 15] neither of these forms can handle all types of memory accesses that are usable within programs. This represents a further limitation on these dependence testing techniques. We have observed that the equation solving paradigm for ....

W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Univ. of Illinois at UrbanaChampaign, Dept. of Computer Science, June 1995.

....implementing this representation in Polaris [1] which is the parallelizing compiler being developed by the authors and others at Illinois. 2 Motivation The Polaris parallelizer uses a triplet notation for array access patterns in modules such as the privatizer [4] and the dependence analyzer [6]. Polaris has been successfully obtaining speedups for many scientific applications on a variety of shared memory multiprocessors, but we have seen that Polaris still fails to obtain good speedups for some applications. We carefully studied these programs, and found one of the reasons is that ....

....must support the notion of accuracy. In our quest for a better access pattern representation, we considered the convex regions, but forms which represent access patterns by sets of constraints typically must use a more general dependence test [22] which cannot handle non affine expressions [5, 6]. Forms which use the triplet notation cannot handle such complicated access patterns as discussed earlier, but lend themselves to more efficient manipulation in many parts of a compiler. So, we decided to develop a new representation by combining the expressiveness of convex regions with the ....

[Article contains additional citation context not shown here]

W. Blume, Symbolic Analysis techniques for Effective Automatic Parallelization, PhD Thesis, University of Illinois at Urbana-Champaign, June 1995

.... loop bounds, conditionals, and array index functions. Non linear symbolic expressions are commonly caused by inductionvariable substitution, linearizing arrays, parameterizing data parallel programs with symbolic number of processors and or problem size, and so forth. Numerous researchers [7, 2, 9, 8] have reported on the occurrence of non linear symbolic expressions in practical codes and the need of effective techniques to analyze such programs. Non linear symbolic expressions seriously hamper crucial compiler analysis including testing for data dependences, optimizing communication, ....

....E 1 ) 0 for all values of variables and parameters appearing in E 1 and E 2 . This theorem has been proved in [6] The theorem for inequality relationships and is similar. Algorithm EXPR BOUND can therefore also be used to detect and eliminate redundant inequalities. 4 Related Work Blume [2] developed an algorithm to compare two expressions based on symbolic ranges. A range [a : b] for a variable x defines a single lower and upper bound on x, which can also be written as a x y. The main difference between our algorithm and the one of Blume is that Blume s techniques are based on ....

[Article contains additional citation context not shown here]

W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Center for Supercomputing Research and Development, University of Illinois at UrbanaChampaign, June 1995.

.... a number of cases in which we can eliminate a dependence by using the fact that a nonlinear induction variable takes on a strictly increasing sequence of values (using this fact requires our techniques from Section 4) Other information, such as information about the possible ranges of variables [Blume 1995], might also help to eliminate dependences or improve our conditional analysis. We have not performed extensive studies of the impact of such additional information on our techniques. 2.2 Constraints Generated During Conditional Analysis When both p and q are conjunctions of constraints, we ....

....substantially. While the time taken to perform our analysis seems large by comparison to the uniprocessor f77 compiler, it may not be prohibitive for high levels of optimization for parallelizing compilers, where the potential payoff from optimization is much greater. For example, according to Blume [1995, Table 3.3] the Polaris compiler is many times slower than f77 (for example, it takes over 300 seconds for MDG) Furthermore, we can apply techniques to reduce the time required for our techniques if we are willing to settle for a less detailed analysis. For example, techniques in Chapter 13 of ....

[Article contains additional citation context not shown here]

Blume, W. J. 1995. Symbolic analysis techniques for effective automatic parallelization. Ph.D. thesis, Dept. of Computer Science, U. of Illinois at Urbana-Champaign.

.... parallelism, include data dependence analysis, inlining, induction variable substitution, reduction recognition, and privatization [14, 31, 59, 69] To support data dependence analysis expressions with symbolic values, additional modules for powerful symbolic constant and range manipulation [12] have been implemented in Polaris. The frontend outputs the parallel program in IR form extended with annotations that identify the parallelism detected by these modules. Using the parallelism identified by the frontend, the backend applies machine specific transformations and generates the target ....

.... variables whose values are unknown at compile time) In our access region analysis, we employ various techniques already implemented in Polaris for this purpose, such as constant propagation, induction variable substitution, symbolic range propagation, and simplification of symbolic expressions [12]. 1.4 Organization of Dissertation The rest of this dissertation is organized as follows. In Chapter 2, we will discuss the access region analysis used in our code transformation algorithm. In the discussion, we will first present the motivation for a more powerful representation to be introduced ....

[Article contains additional citation context not shown here]

W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Univ. of Illinois at Urbana-Champaign, Dept. of Computer Science, June 1995.

.... 2. Because the value N is not known, the constraint cannot be proven at compile time. However, using the Region test, a parallel loop can be generated for intraf 1000 under the constraint, N 2, for run time testing. Although parallelizing loops under run time constraints is not a new idea [2], little research has been done on how to efficiently collect the predicates from the program. The LMAD representation facilitated gathering the predicates. In this example, to generate the LMAD for the accesses to array F, first notice that the accesses are driven by two indices: I and an ....

....because they are very time critical loops. Some loops (e.g. ftrvmt 109) provide enough information for M and N to statically prove the non overlap constraint so that they can be parallelized without run time tests. This example also shows the importance of symbolic range analysis techniques [2]. In fact, with powerful analysis techniques, it is possible to disprove dependence at compile time by showing that the condition above is always true even though the current implementation of the Region test can not yet perform such an accurate symbolic analysis. The simplification operations on ....

[Article contains additional citation context not shown here]

W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Univ. of Illinois at Urbana-Champaign, Dept. of Computer Science, June 1995.

....In many cases, the simplicity of the real access is hidden inside the subscript expressions, making it difficult to discover. Sometimes originally simple subscript expressions are converted to complex ones during compiler transformations, such as induction variable substitution, value propagation [3], and subroutine inlining [18, 13] although the original access patterns remain intact. Previous techniques sometimes fail to recognize these simple patterns and, as a result, lose accuracy in their access analysis. When an m dimensional array is allocated in memory, it is linearized and laid out ....

....and not triangular affine. In order for the difference between the last offset and the first offset (the span) to represent the true distance moved for a dimension, the subscript function must cause movement to be consistently in the same direction. Such a function is called monotonic [3], which will be formally defined in Section 4. This implies that the LMAD can be accurate only when the subscripting functions are monotonic. Thus, to see how often the LMAD can be accurate in reality, we determined the percentage of array accesses that were provably monotonic at compile time. By ....

[Article contains additional citation context not shown here]

W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Univ. of Illinois at Urbana-Champaign, Dept. of Computer Science, June 1995.

....control flow paths that will be taken or testing for boundary conditions. A few existing data flow analyses incorporate predicates, particularly guarded array data flow analysis by Gu, Li and Lee [5] but none of these analysis based techniques use these predicates to derive run time tests [2, 5, 6, 8, 15, 16]. Because predicates in previous work are used only during compile time analysis, they are restricted to some domain of values that the compiler understands. By contrast, our approach can derive more general predicates, run time evaluable predicates consisting of arbitrary program statements. ....

....any other analysis based technique capable of parallelizing this loop. 2. 3 Relationship to Previous Work Analysis techniques exploiting predicates have been developed for specific data flow problems including constant propagation [16] type analysis [14] symbolic analysis for parallelization [6, 2], and the array data flow analysis described above[5, 15] Tu and Padua present a limited sparse approach on a gated SSA graph that is demand based, only examining predicates if they might assist in loop bounds or subscript values for parallelization, a technique that appears to be no more ....

[Article contains additional citation context not shown here]

W. J. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, June 1995.

....treatise Arithmetica is the earliest known work which studied this type of equation in a systematic way [100] CHAPTER 2. AUTOMATIC PARALLELISATION 26 the Perfect Benchmarks 6 [27] led Blume and Eigenmann to the development of a similar dependence test capable of handling symbolic expressions [26, 28]; whenever the latter fails to provide an answer, run time techniques for data dependence analysis are also considered [24] A different approach is taken by Maslov [154] under certain conditions, his algorithm breaks a nonlinear expression into several linear expressions which can be analysed ....

....suggested that the use of symbolic expressions may lead to greater rewards due to the extra information contained in them [196, p. 157] As already mentioned, in the context of parallelising compilers, symbolic analysis techniques have been considered crucial for advanced data dependence tests [28, 92], as well as for interprocedural analysis [99] 2.6 Concluding Remarks The remainder of this thesis investigates the use of symbolic techniques in the context of estimating performance; in particular, Chapter 3 is devoted to the issue of counting loop iterations. Using this information, it is ....

W. J. Blume, Symbolic Analysis Techniques for Effective Automatic Parallelization, PhD Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 1995.

....is resolvable and exact at compile time. However, in many cases, such as for formal array parameters, the size is not directly available. The following series of successively more conservative rules is used to determine the best compile time approximation of array size: 1. First, range propagation [4] is used to attempt to symbolically and intraprocedurally determine the union of subscript ranges accessed. Range propagation attempts to compute the range of values that each program expression can take on. Note that the compiler need only consider array references which are being tested. 2. If ....

W. Blume. Symbolic analysis techniques for effective automatic parallelization. Ph. D. Thesis. University of Illinois, Urbana, IL, 1995.

....control flow paths that will be taken or testing for boundary conditions. A few existing data flow analyses incorporate predicates, particularly guarded array data flow analysis by Gu, Li and Lee [5] but none of these analysis based techniques use these predicates to derive run time tests [2, 5, 6, 8, 15, 16]. Because predicates in previous work are used only during compile time analysis, they are restricted to some domain of values that the compiler understands. By contrast, our approach can derive more general predicates, run time evaluable predicates consisting of arbitrary program statements. ....

....of any other analysis based technique capable of parallelizing this loop. 2. 4 Relationship to Previous Work Analysis techniques exploiting predicates have been developed for specific data flow problems including constant propagation [16] type analysis [14] symbolic analysis for parallelization [6, 2], and the array data flow analysis described above [5, 15] Tu and Padua present a limited sparse approach on a gated SSA graph that is demand based, only examining predicates if they might assist in loop bounds or subscript values for parallelization, a technique that appears to be no more ....

[Article contains additional citation context not shown here]

W. J. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, June 1995.

No context found.

W. Blume, Symbolic Analysis techniques for Effective Automatic Parallelization, PhD Thesis, University of Illinois at Urbana-Champaign, June 1995

No context found.

W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Univ. of Illinois at Urbana-Champaign,Dept. of Computer Science, June 1995.

No context found.

W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Univ. of Illinois at Urbana-Champaign, Dept. of Computer Science, June 1995.

No context found.

W. Blume, Symbolic Analysis techniques for Effective Automatic Parallelization, PhD Thesis, University of Illinois at Urbana-Champaign,1995

No context found.

W. Blume, Symbolic Analysis techniques for Effective Automatic Parallelization, PhD Thesis, University of Illinois at Urbana-Champaign, June 1995

No context found.

W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Univ. of Illinois at Urbana-Champaign, Dept. of Computer Science, June 1995.

No context found.

W. Blume, Symbolic Analysis techniques for Effective Automatic Parallelization, PhD Thesis, University of Illinois at Urbana-Champaign, 1995

Online articles have much greater impact   More about CiteSeer.IST at NUS   Add search form to your site   Submit documents   Feedback  

CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.