RU2411569C2 - Method for automatic paralleling of programs - Google Patents

Abstract

FIELD: information technologies.

SUBSTANCE: in method for automatic paralleling of cycle areas in algorithmic part of program, previously graph of control flow, dominator trees, cycle trees, graph of data flow are produced; intermediate representations of procedures are substituted into areas of calls; procedure-by-procedure analysis of data flow is carried out; to detect equivalent operations, analysis of data flow is carried out, preferably by method of values numbering. Analysis of cycle variables is carried out for invariance and inductance; analysis of operations of access to massifs is made, indices of access to massifs are built in the form of canonical forms of product sums. Cycles are merged; invariant conditions are taken out; procedure of iteration cycle space bypass is changed; analysis of parallel cycles is carried out.

EFFECT: reduced time of information processing by increasing number of parallel realised operations.

5 dwg

Description

The invention relates to the field of computer programming and, in particular, to the field of converting program text into machine codes (compilation).

The inventive method relates to the field of optimizing compilation. The compiler converts the program written in the source language (C, C ++, Fortran, etc.) into the target architecture code (Intel x86, Sparc, etc.). The optimizing compiler performs this conversion so as to achieve the best performance for the resulting code according to some criteria. Most often, this criterion is the maximum speed of program execution on the target architecture (platform).

Terms

Interim presentation of the program . The semantics of the program can be presented in the operational form. The element of this representation is the operation. An operation can be understood as an arbitrary action on the surrounding context. All operations are ordered according to semantic dependencies. For example, if c = a + b is written in the program, then the 'operation' object appears in the intermediate representation, which indicates that the two arguments a and b are added and the result is written in c.

Linear section . The sequence of operations, without internal branching and convergence of the control flow. Program view:

Control flow graph . The graph of the control flow of the procedure is an analytical data structure, a reflection of the results of the analysis of the topology and semantics of the program. Each node of the control graph corresponds to a certain linear section. The control flow graph is oriented. Each arc of such a graph corresponds to the possibility of transferring control in the program between linear sections. In the graph, the start node and the stop node are selected. From these nodes, all nodes of the control graph are reachable.

Dominance . For two nodes, a dominance relation is introduced. The first node dominates the second if all the paths from the start node to the second node pass through the first node. Based on this relationship, a tree of dominators is constructed, the nodes of which are nodes of the control graph, and the arcs correspond to the dominance relation.

Tree of cycles . Based on the analysis of the control flow, the factorization of the program, called the tree of cycles, is built. This factorization is needed to highlight areas of the program that are interesting in terms of optimization, called loops. Tree nodes are loops. Arcs represent nesting cycles.

Data flow graph . A data flow graph is an analytical data structure in which nodes are operations, and arcs represent the transfer of values between operations. For the program fragment (1) c = a + b; (2) f = dc, the two nodes corresponding to operations 1 and 2 will be connected by an arc in the graph of the data stream, which corresponds to the transfer of data through the variable c.

The conflict . For two memory access operations, there is a concept of conflict. Conflict means access to the same memory area.

Addiction For two access operations, a dependency relation is entered into the memory. Dependence means confict and reachability according to the control flow graph.

Parallel loop . Parallel is a cycle that has no inter-iteration dependencies.

Invariant variable . An invariant loop variable is a variable that does not change in the loop.

Inductive variable . An inductive variable is a loop variable that is incremented or decremented by a constant value at each iteration of the loop.

Recurrence . Recurrence is a sequence of operations inter-iteratively connected in a data flow graph.

Reduction . Reduction is a variable that commutatively changes at each iteration of the loop.

BACKGROUND

The main role in the effective use of architectures with explicit parallelism (multicore, cluster, etc.) is played by programming systems designed to create parallel programs. Such systems include both language means for setting parallelism in the program (explicit parallel programming systems - OrenMR standard [31], RapidMind platform [35], ...), and automatic parallel computing search tools (Intel compilers [32], Portland Group [33], ...) and their subsequent presentation using existing parallelism support libraries (MPI ([30]), libgomp ([34]), ...).

Explicit parallel programming and automatic programming, taken independently of each other, have serious drawbacks. The compromise solution described in [29] is to create an implicit parallel programming system. On the one hand, a programmer in traditional programming languages (C, C ++, Fortran) creates a program with parallel computations. By automatic means, these parallel computations must be recognized. In case of problems with the analysis, the programmer can add tips to the program, resolving any conflict that interferes with the determination of parallelism. Then, the found parallel computations are automatically presented in parallel terms of a particular architecture. In fact, this is some interactive environment for developing parallel programs, in which the efforts of man and automated tools are balanced. In such a system, the main work on the analysis, optimizations and instrumentation of parallel code is performed by the automaton, and a person only resolves conflicts with point-by-point pragmas that the static analyzer cannot handle. The inability to automatically resolve the conflict arises for two reasons: the imperfection of static analysis and the dynamic nature of conflicts. Despite the fact that the first factor will be leveled over time, the resolution of dynamic conflicts will require hints.

In the work of Drozdov A.Yu. [1] a component approach to the construction of optimizing compilers was proposed [2] and a technology for porting components to the context of any existing optimizing compilation technology was developed. This method is selected as a prototype.

The technical result achieved by the application of the proposed solution is to reduce the processing time of information by increasing the number of parallel operations for more cases encountered in practice.

Known methods do not allow to obtain the claimed technical result.

This work describes an automatic program parallelizer created on the basis of the component approach described in [1] and built into the GCC process chain [34].

DESCRIPTION OF GRAPHIC MATERIAL

Figure 1 shows the algorithm for representing the operation.

Figure 2 shows a graph of a data stream in the form of a single assignment.

Figure 3 shows the structure of the method of implementation of the canonical form.

Figure 4 shows an example of the construction of the canonical form for the operations of addition and multiplication.

Figure 5 shows the algorithm for dynamically checking the efficiency of parallelization.

DETAILED DESCRIPTION

Static analysis of programs

A key element of automatic parallelizer (AR) is a static analyzer of the algorithmic essence (semantics) of programs implemented on the basis of the analytical components of the universal technology of optimizing compilation [1]. The analytical part contains new (see below) algorithms for control flow analysis, data flow analysis, interprocedural analysis, cycle dependency analysis, etc. The algorithms have been tested in industrial compilers and have proven their high efficiency. The analyzer includes the following analytical components:

- analysis of the data stream by the method of numbering values;

- analysis of the control flow (construction of a graph of the control flow, construction of trees of dominators / postdominators, construction of a tree of cycles, search for the iterative front of dominance, determination of equivalence for control);

- analysis of variables in the cycle (recognition of invariants, inductances, recurrences, reductions);

- analysis of cyclic dependencies;

- analysis of dependencies on acyclic sites;

- interprocedural data flow analysis.

The main task that the methods of static analysis of programs in optimizing compilers solve is the determination of the relationship of data dependencies and control between different groups of program calculations [1-8]. Efficient (accurate) calculation of these relations is crucial in carrying out optimizing transformations of the program.

Therefore, in modern optimizing compilers, the analytical phase of compilation plays a crucial role. In the analysis phases, redundant calculations, dependencies between memory access operations, control dependencies, control reachability, etc., are determined. Within the framework of these phases, the control flow in the program, the data flow are analyzed, systems of linear diophantine equations and inequalities are solved in order to determine the dependencies in the cyclic regions of the program.

After analysis of data flows and control, the compiler can use the results to get answers to questions about dependencies between any pairs of program calculations [2, 5, 25-28]. By calculations here we mean such factors of factorization of any level, such as operations, linear sections, cycles, procedures. Any request for a dependency relationship has two dimensions of complexity that determine the structure of the response. One of them considers the complexity of the calculations, for which the relationship of dependence is determined from the point of view of factorization for management, and the second determines the level of complexity of the program objects that participate in the analyzed calculations.

If the objects are elementary, then the results of the intra-procedural flow analysis of control and data are enough to answer. As the complexity of the objects increases, so does the complexity of the analysis algorithms, the results of which are necessary to obtain the least conservative answer to the question of dependence. For objects - arrays it is often necessary to apply the analysis of dependencies in the nests of loops, and for the objects that the pointer was taken, the results of the interprocedural analysis of the data stream will be claimed.

The methods of static analysis of programs are especially important in the construction of the analyzer and automatic parallelizer, for the detection of independent sections of the program (analyzer) and their further design in the form of parallel blocks (parallelizer).

Substitution of the intermediate representation of procedures in the places of their calls

The classic inline is that instead of a call operation, an intermediate representation of the called procedure is substituted. Thanks to this transformation, dependency analysis is simplified, since all the operations of the substituted procedure can be explicitly analyzed by analysis algorithms. When substituting calls, it is important to determine the criteria by which this transformation should be applied. In this paper, the criterion is chosen so as to maximize the number of cycles that do not contain calls. If the substitution of the call does not lead to the appearance of new cycles without calls, then the substitution is not carried out.

During compilation, the program is converted from the original representation (for programming languages, this is the text of the program) into an internal intermediate representation of the compiler. Any intermediate representation used in compilers primarily preserves the semantics of the original program. Semantics of a program is understood to mean its algorithmic nature. In terms of fragmentation, programs written in the most common programming languages (C, C ++, Fortran, etc.) are organized into modules and procedures. The module corresponds to the file organization of the programs. In the form of procedures, fragments of programs are executed inside the modules. The structures of these programs are represented by objects with fixed or dynamically defined sizes and a description of their internal structure using types. The most common way to save the algorithmic component of the program in compilers is the operational representation (figure 1).

The operational view is a list of operations. An operation may have an input context and an output context. The input and output contexts are specified by lists of arguments and results. Arguments can be literals, objects, or references to other operations. The mapping of the relationship between the result of one operation and the argument of another through objects is more general than the representation of this relationship as a reference to the operation. The operation itself is a set of attributes that define the semantic action on the input context to obtain the output context. Almost any known intermediate representation can be reduced to such an operational representation, starting with the syntax trees of the frontends (gcc, edg) and ending with the representations closest to the assemblers of the target architecture.

To perform optimizations in accordance with the selected criterion, a sequence of transformations of the intermediate representation is performed.

The above algorithm presents a sequence of steps that allows you to effectively parallelize the cycles in the program. The algorithm is run on an intermediate representation of the program. In the process of performing transformations of the intermediate representation. At the intermediate representation, when applying transformations, analytic data structures are built (if already built, then used): control flow graph, dominator tree, loop tree, data flow graph.

Interprocedural analysis of pointers - the solution described in [22, 23, 24] was used.

Interprocedural analysis of pointers is necessary in order to determine at the stage of compilation of the program the possible values of pointers contained in variables in various places of the program. The presence of such information helps in determining which groups of operations can be performed in parallel, which values have already been calculated and can be reused, optimizing access to objects in memory, and folding constant calculations. The presence of the results of such an analysis with a high degree of detail allows us to effectively apply many optimizing transformations of the program both internally and interprocedurally.

On a more formal level, the task of interprocedural analysis of pointers is to calculate a function that at each point in the program for each variable allows you to get many values of one of the types listed above that a variable can contain at this point. The task of interprocedural analysis can be described by constructing such an approximation of the semantics of a program that would display an interesting property of the behavior of this program at the execution stage.

The approach proposed here to the problem of interprocedural analysis of data flow is described by such characteristics as sensitivity to the control flow (flow-sensitivity) and sensitivity to the context of the procedure call (context-sensitivity). The first means that the algorithm takes into account the control inside the procedure, which leads to an increase in its accuracy. The second is that he seeks to distinguish between information coming into the procedure along various paths during execution. But since the number of such paths can be significant, it is necessary to combine those that are supposedly closest (and combining which will introduce the least possible conservatism in its results). The main mechanism that is usually used to provide contextual dependence properties is the partially transfer function (CTF) mechanism. It allows you to very effectively choose the ratio between the speed of the analysis and its accuracy, because, in the general case, the interprocedural analysis of the data stream is a rather resource-intensive process both from the point of view of the required memory and from the point of view of its time.

Data flow analysis by numbering method

The method is described in the thesis [36]. An analysis of the data flow in a program by way of numbering values is to assign the same equivalence classes to the results of operations if the operations write equivalent values to these results. Two operations are considered equivalent if they have equivalent arguments and the operations perform the same semantic action. In streaming analysis, a data flow graph is constructed that links the results and arguments of operations. The data flow graph allows for arguments to obtain operations that produce the value of the argument. In addition to the data flow graph for analysis, a method is used that uses the single assignment form. The program text translated into this form contains pseudo-operations at the points of control convergence. As a result, taking into account these pseudo-operations, for each argument for which a translation is made in the form of a single assignment, there is a single record. In the data flow graph for such arguments there will be only one input arc from a single record. Figure 2 shows a graph of a data stream in the form of a single assignment. In the program shown for the example in figure 2, there are two entries in the variable A and one read. A record is designated as 'A = ...', a reading is designated as '... = A'. Rectangles and arrows connecting them represent the control flow in the program. From BLOCK 1, it is possible to transfer control to BLOCK 2 or BLOCK 3. From BLOCK 2 and BLOCK 3, control is transferred to BLOCK 4. Black circles and arrows connecting them form a data flow graph for this program fragment. On a data flow graph, each node corresponds to an operation, and each arc corresponds to an argument-result pair. The pseudo-operation corresponding to the convergence of the control flow is denoted as 'φ (A)'.

Analysis of cycle variables for invariance, inductance and reduction

The search for loop variables is performed by the data flow graph. The analysis consists in finding subgraphs satisfying the properties of invariance, inductance, reduction [2, 5, 7, 8].

Analysis of array access operations

A significant improvement in the quality of stream analysis by the method of numbering values can be obtained by using the canonical form of representing expressions in the form of sums of products. This form is one way of representing a linear expression as a polynomial

s ₀ + s ₁ * x ₁₁ * x ₁₂ * ... * x _1k1 + c ₂ * x ₂₁ * x ₂₂ * ... * x _2k2 + ... + c _n * x _n1 * x _n2 * ... * x _nkn ,

where c ₀ , c ₁ , c _n are some constants; X _ij are factors.

The effect of using the canonical form is to reduce the linear expressions to a single (canonical) form, which allows you to define equivalent calculations, even if the original form of the expression is different. As part of the reduction of arithmetic expressions to the canonical form, convolutions of constants are performed (the execution of arithmetic operations on constants), the ordering of commutative operations, and the reduction of such terms. For example, the expression (a + b) * c and the expression a * c + b * c will be reduced to a single form a * c + b * c and defined as equivalent.

Figure 3 shows the structure of the method for implementing the specified canonical form. The rectangles represent the elements corresponding to the terms. The ovals show the elements corresponding to the factors.

The mechanism for using the canonical form during the operation of the numbering algorithm is to build the sum of products for the arguments of this operation for addition, subtraction and multiplication. The canonical form factors will be equivalence classes (for example, see “Analysis of the data stream by way of numbering values” earlier). Hashing operations for which the construction of canonical forms is possible is performed on the basis of these forms.

Figure 4 shows an example of the construction of the canonical form for the operations of addition and multiplication. The symbols V1, V2, and V3 denote equivalence classes for read operations from variables A, C, and B, respectively.

The way to represent the addresses of memory access operations is the canonical form of the sums of the products, the factors of which are the equivalence classes calculated as a result of stream analysis by the method of numbering the values. The analysis of dependencies in cyclic regions mainly reduces to the analysis of conflicts in memory access operations. The most famous way of working with memory is to access arrays by linear indexes. The following is a snippet of a program written in C. In line 1, an array A of 10 elements in size is declared. Array A in line 5 is specified by the indices 'i + 1' and 'j-1'. Assign read operations from variable i to some equivalence class V. For the index 'i + 1', the canonical form 1 + V is constructed. Reading from the variable j sets the same equivalence class V, since the values of the variables i and j contain the same values. For the index of access to the array 'j-1', the canonical form -1 + V is built. To determine the dependencies solve the equation 1 + V = -1 + V ', where for the variables V and V' there are restrictions 0 <V <10 and 0 <V '<10. Variables V and V 'are loop iteration numbers. As a result of solving the system of equations and inequalities, iterations are determined at which the access to the same element of array A occurs.

Merge loops

Optimization by fusion of cycles (fusion) [5, 6] to increase the number of calculations per iteration of the cycle and reduce the required resources for parallelization. The following is an example of merging loops. The resources required for parallelization after applying the conversion are halved, as they only parallelize one cycle instead of two.

Removal of invariant conditions

Optimization of the removal of invariant conditions from the cycle (unswitching) [5, 6] allows you to remove operations that are performed under these conditions from the cycle. Remote operations may include operations that prevent parallelization. These include, in particular, call operations. Therefore, this conversion increases the number of parallel loops.

Change the iterative space traversal order

These optimizations are aimed both at increasing the number of parallel cycles, and at increasing the efficiency of parallelization. Another name for these transformations is “unimodular transformations”. They are described in detail in [5, 7, 8].

Analysis of inter-iteration dependencies

The classical method is given in [5, 7, 8]

The task of finding the interiterational dependences consists in solving a system of linear Diophantine equations and inequalities. The equations are the result of comparing the access indices in the array, and the inequalities are formed from the representation of the upper and lower bounds of the variable cycles in mathematical form. The number of equations is determined by the dimension of the arrays, the operations of access to which are considered when setting the problem.

After the task is set, perform the following sequence of steps.

Solve a system of linear diophantine equations. If the system of equations has no solution, then the dependence does not exist. If the system of equations has a solution, investigate the system of linear Diophantine inequalities. If the system of Diophantine inequalities has a solution, this means that the dependence exists. If it has no solution, this means that the dependency does not exist. If the dependence exists, then we study the direction vectors and the distance vectors.

The classical approach to solving systems of linear Diophantine inequalities consists in applying the Fourier method.

Locality analysis of arrays

If the array at each iteration of the cycle is overwritten with new values before use and is not used after the cycle, then for each iteration you can create a local copy of such arrays. This transformation is called localization and it allows you to remove the inter-iteration dependencies of the original array. Thus, in order to localize arrays, you need to make sure that there are write operations to the same elements of the array along all paths from the beginning of the cycle to reads from arrays. In addition, you need to check that the array is not used after the loop.

This action eliminates the inter-iteration dependences in the cycle, thereby increasing the possibilities for parallelization.

Loop duplication

To verify the effectiveness of the use of parallelization using the method of duplication of cycles. One copy is not left parallelized, and the other parallelized. Check before the cycles determines the feasibility of switching to a parallel copy or leaving the original version of the cycle. They check for the execution time of iterations and compare this time with the cost of resources for launching a parallel loop.

Figure 5 shows an example of such a conversion.

The inventive method consists in the following.

At the stage of the intermediate presentation of the program, at least the following analytical data structures are built (if already built, then used): control flow graph, dominator tree, loop tree, data flow graph by any known means.

Substitute procedure bodies at their call points. In the case of parallelization, this action is aimed at analyzing cycles in which there are calls of other procedures. In the presence of calls, known methods for analyzing dependencies in cycles are not applicable.

Perform interprocedural data flow analysis. For the analysis of pointers, the method of partial transfer functions is mainly used [22, 23, 24]. It is also possible to use various alternative methods of analysis [9-21].

Intra-procedural analysis of the data stream is performed. Advantageously, a known method of numbering values is used. The purpose of the analysis is to determine equivalent operations. It is also possible to use classical iterative algorithms for distributing the streaming properties of a program [5, 6].

Perform loop variable analysis. Define invariant variables, inductive variables, and reductions. For example, analyzing a data flow graph with the definition of subgraphs corresponding to inductive and / or invariant variables.

Perform an analysis of access operations to arrays. They build access indexes into arrays in the form of canonical forms of sums of products.

Perform loop transformations that increase the effect of subsequent parallelization. These include transformations by merging cycles, by removing invariant conditions, by changing the order of traversal of the iterative space of cycles.

Perform parallel loop analysis. The loop tree is bypassed recursively from the root node with a check for the ability to parallelize the current loop. Perform at least the following types of analysis.

but. Analysis of the structure of the cycle. You can parallelize cycles with one output, which are controlled by an inductive variable with invariant upper and lower boundaries, as well as an invariant step.

b. Analysis of cycle reductions. Recognized reductions are excluded in the analysis of inter-iteration dependencies.

from. Analysis of inter-iteration dependencies in a cycle. The interiterational dependences are revealed by the classical method by solving Diophantine equations.

d. Analysis of arrays for locality. In case of localization of arrays, inter-iteration dependencies can be removed.

For parallel loops, a copy of the loop is constructed, since a parallelized loop does not always work faster than the original loop. Under some conditions, the need for additional resources to run the loop in parallel can lead to reduced performance. They dynamically check for the execution time of iterations and compare this time with additional resources for launching a parallel loop.

For parallel loops, operations are constructed that provide parallel execution of loops. In parallel execution, several threads are launched, each of which performs part of the loop iterations. The body of the loop is allocated into a new procedure, the parameters of which are nonlocal data of loop iterations. Local data structures of the created procedure are assigned local data structures of iterations of the original cycle.

The described method was implemented on the basis of CTOT [1]. The results published in this work were obtained by parallelizing the cycles.

The description structure is organized in such a way that first they describe a certain level of the algorithm in an abstract language, and then provide comments on each step of the algorithm.

Algorithm 1 . Automatic parallelization procedure.

At the input serves an intermediate representation of the program, consisting of a set of intermediate representations of the procedures.

The output is a modified intermediate representation of the program, in which parallelized loops may be present.

Parallelization_programs

1. Substitution of the bodies of the procedures in place of their calls.

2. Perform interprocedural analysis of the data stream.

3. The cycle for all program procedures.

4. Parallelization_procedures.

5. The end of the cycle.

Parallelization_procedures

1. Perform intra-procedural analysis of the data stream.

2. Perform loop variable analysis.

3. Perform an analysis of access operations to arrays.

4. Perform cycle conversions that increase the effect of subsequent parallelization.

5. Parallelization of a cycle.

6. Remove auxiliary data structures.

Parallelization

1. Perform verification of the properties of the inductive variable of the cycle and either go to step 5 or go to step 2.

2. Perform a reduction analysis of the cycle.

3. Check for the presence of inter-iteration dependencies and, if they are absent, go to step 4.

4. If there are inter-iteration dependencies, an attempt is made to remove the dependencies by the method of localizing arrays. If the dependencies could not be removed, go to step 6.

5. The use of parallelization_cycle . Exit the procedure.

6. The cycle for all nested cycles in the tree of cycles.

7. Parallelization of a cycle.

8. The end of the cycle .

Loop_ parallelization

1. Creating a copy of the cycle and the conditions for the transition to a parallelized version.

2. Construction of a parallelized cycle of variables containing the value of the lower boundary, upper boundary and step.

3. Formation of a parallel loop descriptor. According to the descriptor, depending on the type of medium, operations are constructed that will ensure parallel execution of loops. In parallel execution, several threads are launched, each of which performs part of the loop iterations.

The upper level of the automatic auto-parallelization algorithm is implemented in the program_ Parallelization procedure.

At the 1st and 2nd steps, algorithms of interprocedural analysis and optimizations are performed. First, the intermediate representations of the procedures are substituted into the places of their calls, and then the interprocedural analysis of the data flow is performed.

In steps 3-5 perform the cycle of program procedures, wherein in step 4 is started algorithm parallelization Rasparallelivanie_protsedury procedure.

In steps 1-4 of the Parallelization_procedure procedure, preliminary steps are performed before parallelization, namely: they analyze the data stream by the method of numbering the values, analyze the loop variables, analyze the operations of accessing the array, and also conduct a series of loop optimizations aimed at increasing the number of parallel loops and / or enhancing the effect of parallelization.

In step 5, run a recursive algorithm parallelization Rasparallelivanie_tsikla cycles. This procedure recursively traverses the loop tree and tries to parallelize the current loop. The procedure starts from the head of the tree of cycles.

In step 6, all auxiliary data structures are deleted.

The next level of implementation of the parallelization algorithm is loop parallelization. The Cycle_ parallelization procedure checks the properties of the cycle for possible parallelization and, if these properties are available, the cycle parallelizes it. In step 1, the loop structure is checked. You can parallelize cycles with one output, which is controlled by an inductive variable with invariant upper and lower boundaries, as well as an invariant step.

The analysis of cycle reductions is performed in step 2. Recognized reductions are excluded when analyzing inter-iteration dependencies (dependencies between iteration of the cycle) in step 3.

At step 3, the presence of inter-iteration dependencies in the cycle is checked. To do this, use the analyzer. If there are no inter-iteration dependencies in the cycle, then it can be parallelized.

If there are inter-iteration dependencies in step 4, an attempt is made to remove the dependencies by the method of localizing arrays.

If the checks were successfully completed in steps 1, 3, and 4 in step 5, the application Cycle_Parallelization_Application procedure is launched, which performs the necessary actions to parallelize the cycle.

If the decision on parallelization was not made, then at step 7, a recursive call of the procedure Parallelization of a cycle for all nested cycles of the current cycle is performed.

The Cycle_Parallelization_Application procedure performs actions to parallelize a cycle for which parallelization is possible. In step 1, a copy of the cycle and a condition that checks the effectiveness of parallelization are built. The fact is that the required resources for creating a new stream are large and if the cycle is not long enough, then its parallelization can lead to a decrease in productivity. They dynamically check for the execution time of iterations and compare this time with the required resources to start a new thread. The calculation of the execution time of loop iterations is heuristic. The estimate of this time is based on the values of the counters of the executed cycles and the heuristic times of execution of individual commands in the body of the cycle. Nested loop counters are not always known at the level of the enclosing loop. In this case, their value is set heuristically. It is estimated that the average cycle contains 10 iterations.

At step 2, the variables are initialized with the values of the lower and upper bounds, as well as with the step of the inductive variable.

In step 3, the intermediate representation of the parallelized loop is modified. The view is embedded in operations that ensure the parallel launch of the loop body. The body of the cycle is isolated in a new procedure. Depending on the locality of the data structures in relation to the iterations of the cycles, some of them are passed as a parameter to the new procedure, and some (which are local) become data structures of the new procedure.

Literature

1. Drozdov A.Yu., Features and prospects of the Universal technology of optimizing compilation. // Collection of scientific papers of ITMiVT im. S.A. Lebedeva RAS, Issue No. 1, Materials of the All-Russian Conference "Prospects for the Development of High-Performance Architectures. History, Present and Future of Russian Computer Engineering", 2008, P.62-74.

2. Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, "Compilers: Principles, Techniques, and Tools", Addison-Wesley, Reading, 1986.

3. John R. Ellis. Bulldog: A compiler for VLIW Architectures. MIT Press, 1985.

4. Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs and Koen G. Langendoen, Modern Compiler Design, by John Wiley & Sons, Ltd, 2000.

5. Randy Alien, Ken Kennedy, Optimizing Compilers for Modern Architectures. 2002 by Academic Press.

6. Steven S. Muchnick, "Advanced Compiler Design and Implementation", Morgan Kauffman, San Francisco, 1997.

7. Utpal Banerjee, Loop Transformations for Restructuring Compilers. Kluwer academic Publishers, 1993.

8. Utpal Banerjee. Dependence Analysis. Kluwer Acadmic Publishers. 1997.

9. [29] Kwangkeun Yi and Williams Ludwell Harrison III, Interprocedural Data Flow Analysis for Compile-time Memory Management. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign.

10. Evelyn Duesterwald, Rajiv Gupta, Mary Lou Soffa, Demand-driven Computation of Interprocedural Data Flow. Department of Computer Science, University of Pittsburg, POPL'95 1/95 San Francisco, CA USA.

11. Evelyn Duesterwald, Rajiv Gupta, and Mary Lou Soffa, A Practical Framework for Demand-Driven Interprocedural Data Flow Analysis. University of Pittsburg, ASM SISPLAN-SIGACT Symposium on Principles of Programming Languages, 1995.

12. Susan Horwitz, Thomas Reps, and Mooly Sagiv, Demand Interprocedural Dataflow Analysis. University of Wisconsin, Proceedings of the Third ASM SIGSOFT Symposium on Foundations of Software Engineering, Washington DC, October 10-13, 1995.

13. V.V. Voevodin, Vl.V. Voevodin, Parallel computing. St. Petersburg "BHV-Petersburg", 2002.

14. David R. Chase, Mark Wegman, F. Kenneth Zadeck, Analysis of Pointers and Structures. ASM SIGPLAN'90 PLDI, June 20-22, 1990.

15. Yuan-Shin Hwang, Joel Saltz, Compile-Time Analysis on Programs with Dynamic Pointer-Linked Data Structures. Depatment of Computer Science, University of Maryland, Nobember 8, 1996.

16. Rakesh Ghiya and Laurie J. Hendren, Connection Analysis: A Practical Interprocedural Heap Analysis for C. School of Computer Science, McGill University, Proceedings of the Eigth Workshop on Languages and Compilers fo Parallel Computing, Columbus, Ohio, August 10-12 1995.

17. Xinan Tang, Rakesh Ghiya, Laurie J. Hendren, Guang R. Gao, Heap Analysis and Optimizations for Threaded Programs. School of Computing Science, McGill University, 1997.

18. Rakesh Ghiya, Practical Techniques for Interprocedural Heap Analysis. School of Computing Science, McGill University, Montreal, January 1996.

19. Keith D. Cooper, Ken Kennedy, Fast Interprocedural Alias Analysis. Rice University, 1989.

20. Bjarne Steensgaard, Points-to Analysis in Almost Linear Time, Microsoft Research, 1996.

21. Keith D. Cooper, Ken Kennedy, Interprocedural Side-Effect Analysis in Linear Time. Rice University, 1988.

22. Robert P. Wilson, Monika S. Lam. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language and Implementation, pages 1-12, June 1995.

23. Drozdov A.Yu., Vladislavlev V.E. Interprocedural analysis of pointers // Information Technologies. Appendix No. 2, February 2005

24. [44] Drozdov A.Yu., Syrkin A.G. Methods of contextual interprocedural distribution of properties of values of program variables // Information Technologies. Appendix No. 2, February 2005

25. [46] Drozdov A.Yu., Kornev P.M., Bohanko A.S. Index analysis of dependencies according to data // Information Technologies and Computing Systems, No. 3, 2004

26. Kleanthis Psarris and Konstantinos Kyriakopoulos, Data Dependence Testing in Practice. Division of Computer Science, The University of Texas at San Antonio, San Antonio, TX 78249.

27. [48] Paul M. Petersen and David A. Padua, Experimental Evaluation of Some Data Dependence Tests (Extended Abstract), Center for Super computing Research and Development, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801.

28. [49] Paul M. Petersen, David A. Padua, Static and Dynamic Evaluation of Data Dependence Analysis. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign.

29. [54] Wen-mei Hwu, Shane Ryoo, Sain-Zee Ueng, John H. Kelm, Isaac Gelado, Sam S. Stone, Robert E. Kidd, Sara S. Baghsorkhi, Aqeel A. Mahesri, Stephanie C. Tsao , Nacho Navarro, Steve S. Lumetta, Matthew I. Frank, and Sanjay J. Patel, Implicit Parallel Programming Models for Thousand-Core Microprocessors, Proceedings of the 44th Annual Design Automation Conference, June 2007.

30. www.mpi-forum.org [56].

31. www.openmp.org [57].

32. www.intel.com [58].

33. www.pgroup.com [59].

34. www.gnu.org [63].

35. www.rapidmind.com [64].

36. [72] Loren Taylor Simson, Value-Driven Redundancy Elimination, Thesis, Rice University, Houston, Texas, April 1996.

Claims (1)

A method for automatic parallelization of cyclic areas in the algorithmic part of the program, which allows to maximize the number of parallel cycles by applying interprocedural and intraprocedural optimizations, characterized by embedding dynamic checks for parallelization efficiency in the program, including the following steps:
preliminary, at the stage of intermediate presentation of the program, when performing the transformations, they build using any known methods, and if they are already built, then at least the following analytical data structures are used: control flow graph, dominators tree, cycle tree, data flow graph;
perform substitution of the intermediate representation of procedures in the place of calls;
perform interprocedural analysis of the data stream,
to detect equivalent operations, an analysis of the data stream is performed, preferably by a method of numbering the values;
perform an analysis of cycle variables for invariance and inductance;
analyze access operations in arrays, build access indices in arrays in the form of canonical forms of sums of products;
merge loops;
carry out the removal of invariant conditions;
change the order of traversal of the iterative space of loops,
perform parallel loop analysis,
moreover, when performing interprocedural analysis of the data stream, a method is used that is sensitive to the context and sensitive to the control flow,
moreover, the substitution is carried out in cyclic areas to obtain the maximum number of cycles that do not contain procedure calls,
moreover, the method of numbering the values is additionally checked by analysis that clarifies the equivalence for memory access operations,
moreover, when constructing canonical forms, the results of the analysis of the data flow by the method of numbering values are used,
moreover, when analyzing parallel loops, the loop tree is bypassed recursively from the root node with a check for the possibility of parallelizing the current loop, and the following types of analysis are performed:
analysis of the structure of the cycle for the presence of a single output, since it is possible to parallelize only cycles with one output, which are controlled by an inductive variable with invariant upper and lower boundaries, as well as an invariant step;
analysis for the presence of cycle reductions; recognized reductions are excluded in the analysis of inter-iteration dependencies;
analysis of inter-iteration dependences in a cycle, mainly by solving diophantine equations;
analysis of arrays for locality,
moreover, for parallel loops, they build a copy of the loop and dynamically check for the execution time of iterations and compare this time with the cost of resources for starting a parallel loop,
moreover, for parallel loops, operations are constructed that will ensure parallel execution of loops; when executed in parallel, several threads are launched, each of which performs part of the loop iterations,
moreover, the body of parallel loops is allocated into a new procedure, the parameters of which are assigned non-local data of loop iterations, and the local data structures of loop iterations are assigned as local data structures of the created procedure.

Images