Frameworks supporting the polyhedral model
Encyclopedia
Use of the polyhedral model
within a compiler
requires software to represent the objects of this framework (sets of integer-valued points in regions of various spaces) and perform operations upon them (e.g., testing whether the set is empty).
For more detail about the objects and operations in this model, and an example relating the model to the programs being compiled, see the polyhedral model page.
There are many frameworks supporting the polyhedral model. Some of these frameworks use one or more libraries for
performing polyhedral operations. Others, notably Omega, combine everything in a single package.
Some commonly used libraries are the Omega Library (and a more recent fork),
piplib,
PolyLib,
PPL,
isl,
the cloog polyhedral code generator, and the barvinok library for counting integer solutions.
Of these libraries, PolyLib and PPL focus mostly on rational values, while the other libraries focus on integer values.
The polyhedral framework of gcc
is called Graphite. Polly provides polyhedral optimizations for LLVM
.
Polyhedral frameworks can be used for dependence analysis for arrays, including both traditional alias analysis and more advanced techniques such as the analysis of data flow in arrays or identification of conditional dependencies. They can also be used to represent code transformation, and provide features to generate the transformed code in a high-level language. The transformation and generation systems can typically handle imperfectly nested loops.
for i := 0 to N do
A(i) := (A(i) + A(N-i))/2
Approaches that cannot represent symbolic terms (such as the loop-invariant quantity N in the loop bound and subscript) cannot reason about dependencies in this loop. They will either conservatively refuse to run it in parallel, or in some cases speculatively run it completely in parallel, determine that this was invalid, and re-execute it sequentially.
Approaches that handle symbolic terms but represent dependencies via direction vectors or distance vectors will determine that the i loop carries a dependence (of unknown distance), since for example when N=10 iteration 0 of the loop writes an array element (A(0)) that will be read in iteration 10 (as A(10-10)) and reads an array element (A(10-0)) that will later be overwritten in iteration 10 (as A(10)). If all we know is that the i loop carries a dependence, we once again cannot safely run it in parallel.
In reality, there are only dependencies from the first N/2 iterations into the last N/2, so we can execute this loop as a sequence of two fully parallel loops (from 0...N/2 and from N/2+1...N). The characterization of this dependence, the analysis of parallelism, and the transformation of the code can be done in terms of the instance-wise information provided by any polyhedral framework.
Instance-wise analysis and transformation allows the polyhedral model to unify additional transformations (such as index set splitting, loop peeling, tiling, loop fusion or fission, and transformation of imperfectly nested loops) with those already unified by the unimodular framework (such as loop interchange, skewing, and reversal of perfectly nested loops). It has also stimulated the development of new transformations, such as Pugh and Rosser's iteration-space slicing (an instance-wise version of program slicing; note that the code was never released with the Omega Library).
heat equation
stencil calculation
expressed by the following pseudocode
:
for t := 0 to T do
for i := 1 to N-1 do
new(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25 // explicit forward-difference with R = 0.25
end
for i := 1 to N-1 do
A(i) := new(i)
end
end
This code confounds many of the transformation systems of the 20th century,
due to the need to optimize an imperfect loop nest.
Polyhedral frameworks can analyze the flow of information among different executions of statements in the loop nest, and transform this code to simultaneously exploit scalable parallelism
and scalable locality
.
A re-cap here, of the two approaches on this example, might be nice, but for now see the individual papers of Wonnacott, and Sadayappan et al., as well as others who have studied this code using different frameworks, such as Song and Li.
Examples are provided below to aid in translation:
helping to capture the impact of symbolic terms,
identify conditional dependences,
and separating out the effects of memory aliasing.
The effects of memory aliasing, in particular, have been described in two ways:
many authors distinguish between "true" data dependences (corresponding to actual flow of information) from false dependences arising from memory aliasing or limited precision of dependence analysis.
The Omega Project publications use specific terms to identify specific effects on analysis.
They maintain the traditional distinction of flow-, output-, and anti-dependences,
based on the types of array access (write to read, write to write, or read to write, respectively).
Dependences can independently be classified as memory-based or value-based ---
the former corresponds to memory aliasing,
and the latter does not include dependences interrupted by intervening writes.
A dependence test may produce information that is exact or approximate,
depending on the nature of the program being analyzed and the algorithms used in the test.
Finally, the results of dependence analysis will be reported in a dependence abstraction
that provides a certain degree of precision.
For example, the "dependence relations" produced by the Omega Test,
and the "quasts" produced by the algorithms of Feautrier or Maydan and Lam,
contain precise information (though in different forms) about the loop iterations involved in a dependence.
The results of either test can be converted into the more traditional "dependence vector" form,
but since this abstraction provides less precision,
much of the information about the dependence will be lost.
Both techniques produce exact information for programs with affine control and subscript expressions,
and must approximate for many programs outside this domain (i.e., in the presence of non-affine subscripts such as index arrays).
The original work of Feautrier focused on describing true dependences,
which would be referred to as exact value-based flow dependences by the Omega Project.
The Omega Project also described the use of their algorithms for value-based output- and anti-dependences, though Feautrier's quasts could presumably be easily adapted to this as well.
Some authors depict transformations by changing the location of points on the page,
essentially aligning the picture with the coordinate axes of the transformed space;
in such diagrams, tiles appear as axis-aligned rectangles/rectangular solids containing iterations.
Examples of this approach can be found in the publications and transformation-visualization software of Michelle Mills Strout.
Other authors depict different transformations as different wavefronts of execution that move across the points of the original coordinate system at different angles.
In such diagrams, tiles appear as parallelograms/parallelepipeds.
Examples of this approach can be found in the time-skewing publications of
David G. Wonnacott.
There are several other points on which the frameworks differ, specifically:
is NP-complete
, and Maydan showed that the problem of checking array aliasing in nested loops with affine bounds and subscripts is equivalent to integer programming; other operations, such as array dataflow analysis, are even more complex (the algorithms of the Omega Library handle the full language of Presburger Arithmetic, which is O(2^2^2^n)). Thus, it is clearly unrealistic to expect exact fast results for arbitrary problems of array aliasing or array data flow, even over the affine domain. Fortunately, many problems fall into a subset of this domain where general algorithms can produce an exact answer in polynomial time ,.
Outside of this domain, the Omega Library, piplib and isl emphasize the production of an exact result (except in the cases of certain uses of uninterpreted function symbols in Omega), despite the high complexity. In some cases, such as variable elimination ("projection"), PolyLib and PPL primarily use algorithms for the rational domain, and thus produce an approximation of the result for integer variables. It may the case that this reduces the common experience with the Omega Library in which a minor change to one coefficient can cause a dramatic shift in the response of the library's algorithms.
Polylib has some operations to produce exact results for Z-polyhedra (integer points bounded by polyhedra), but at the time of this writing, significant bugs have been reported. Note that bugs also exist in the Omega Library, including reliance on hardware-supplied integer types and cases of the full Presburger Arithmetic algorithms that were not implemented in the library. Users who need exact results for integer variables may need to be wary with either library.
Barvinok's techniques for counting integer solutions require a description of the vertices (and bounding rays) of the polyhedron, but produce an exact answer in a way that can be far more efficient than the techniques described by Pugh. Barvinok's algorithm is always polynomial in the input size, for fixed dimension of the polytope and fixed degree of weights, whereas the "splintering" in Pugh's algorithm can grow with the coefficient values (and thus exponentially in terms of input size, despite fixed dimension, unless there is some limit on coefficient sizes).
vertex enumeration on (non-parametric) polytopes.
The Omega Library internally performs vertex enumeration during the computation of the convex hull.
PolyLib and isl provide vertex enumeration on parametric polytopes, which is essential for applying
Barvinok's algorithm to parametric polytopes.
is used to guide loop transformation, it is generally acceptable to use a superset of the true dependencies—this can prevent an optimization but does not allow illegal code transformations. When the Omega Library produces an approximate answer, the answer is appropriately marked as an upper bound (e.g., via "and UNKNOWN") or a lower bound (e.g., via "or UNKNOWN"). Answers not marked this way are exact descriptions of sets of integer-valued points (except in cases of bugs in the software).
In the case of the Omega Library, the subset itself may be approximate, resulting in an upper bound (tagged) of a lower bound (not tagged) of the transitive closure. Note that the computation of an exact transitive closure is undecidable.
Polytope model
The polyhedral model is a mathematical framework for loop nest optimization in program optimization. The polytope method treats each loop iteration within nested loops as lattice points inside mathematical objects called polytopes, performs affine transformations or more general non-affine...
within a compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
requires software to represent the objects of this framework (sets of integer-valued points in regions of various spaces) and perform operations upon them (e.g., testing whether the set is empty).
For more detail about the objects and operations in this model, and an example relating the model to the programs being compiled, see the polyhedral model page.
There are many frameworks supporting the polyhedral model. Some of these frameworks use one or more libraries for
performing polyhedral operations. Others, notably Omega, combine everything in a single package.
Some commonly used libraries are the Omega Library (and a more recent fork),
piplib,
PolyLib,
PPL,
isl,
the cloog polyhedral code generator, and the barvinok library for counting integer solutions.
Of these libraries, PolyLib and PPL focus mostly on rational values, while the other libraries focus on integer values.
The polyhedral framework of gcc
GNU Compiler Collection
The GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...
is called Graphite. Polly provides polyhedral optimizations for LLVM
Low Level Virtual Machine
The Low Level Virtual Machine is a compiler infrastructure written in C++ that is designed for compile-time, link-time, run-time, and "idle-time" optimization of programs written in arbitrary programming languages...
.
Common Strengths
Polyhedral frameworks are designed to support compilers techniques for analysis and transformation of codes with nested loops, producing exact results for loop nests with affine loop bounds and subscripts ("Static Control Parts" of programs). They can be used to represent and reason about executions (iterations) of statements, rather than treating a statement as a single object representing properties of all executions of that statement. Polyhedral frameworks typically also allow the use of symbolic expressions.Polyhedral frameworks can be used for dependence analysis for arrays, including both traditional alias analysis and more advanced techniques such as the analysis of data flow in arrays or identification of conditional dependencies. They can also be used to represent code transformation, and provide features to generate the transformed code in a high-level language. The transformation and generation systems can typically handle imperfectly nested loops.
An example to contrast polyhedral frameworks with prior work
To compare the constraint-based polyhedral model to prior approaches such as individual loop transformations and the unimodular approach, consider the question of whether we can parallelize (execute simultaneously) the iterations of following contrived but simple loop:for i := 0 to N do
A(i) := (A(i) + A(N-i))/2
Approaches that cannot represent symbolic terms (such as the loop-invariant quantity N in the loop bound and subscript) cannot reason about dependencies in this loop. They will either conservatively refuse to run it in parallel, or in some cases speculatively run it completely in parallel, determine that this was invalid, and re-execute it sequentially.
Approaches that handle symbolic terms but represent dependencies via direction vectors or distance vectors will determine that the i loop carries a dependence (of unknown distance), since for example when N=10 iteration 0 of the loop writes an array element (A(0)) that will be read in iteration 10 (as A(10-10)) and reads an array element (A(10-0)) that will later be overwritten in iteration 10 (as A(10)). If all we know is that the i loop carries a dependence, we once again cannot safely run it in parallel.
In reality, there are only dependencies from the first N/2 iterations into the last N/2, so we can execute this loop as a sequence of two fully parallel loops (from 0...N/2 and from N/2+1...N). The characterization of this dependence, the analysis of parallelism, and the transformation of the code can be done in terms of the instance-wise information provided by any polyhedral framework.
Instance-wise analysis and transformation allows the polyhedral model to unify additional transformations (such as index set splitting, loop peeling, tiling, loop fusion or fission, and transformation of imperfectly nested loops) with those already unified by the unimodular framework (such as loop interchange, skewing, and reversal of perfectly nested loops). It has also stimulated the development of new transformations, such as Pugh and Rosser's iteration-space slicing (an instance-wise version of program slicing; note that the code was never released with the Omega Library).
A more interesting example
Authors of polyhedral frameworks have explored the simple 1-dimensional finite differenceFinite difference method
In mathematics, finite-difference methods are numerical methods for approximating the solutions to differential equations using finite difference equations to approximate derivatives.- Derivation from Taylor's polynomial :...
heat equation
Heat equation
The heat equation is an important partial differential equation which describes the distribution of heat in a given region over time...
stencil calculation
Stencil (numerical analysis)
In mathematics, especially the areas of numerical analysis concentrating on the numerical solution of partial differential equations, a stencil is a geometric arrangement of a nodal group that relate to the point of interest by using a numerical approximation routine. Stencils are the basis for...
expressed by the following pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
:
for t := 0 to T do
for i := 1 to N-1 do
new(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25 // explicit forward-difference with R = 0.25
end
for i := 1 to N-1 do
A(i) := new(i)
end
end
This code confounds many of the transformation systems of the 20th century,
due to the need to optimize an imperfect loop nest.
Polyhedral frameworks can analyze the flow of information among different executions of statements in the loop nest, and transform this code to simultaneously exploit scalable parallelism
Scalable parallelism
Software is said to exhibit scalable parallelism if it can make use of additional processors to solve larger problems,i.e. this term refers to software for which Gustafson's law holds.Consider a program whose execution time is dominated by one or more loops,...
and scalable locality
Scalable locality
Software is said to exhibit scalable locality if it can continue to make use of processors that out-pace their memory systems, to solve ever larger problems....
.
A re-cap here, of the two approaches on this example, might be nice, but for now see the individual papers of Wonnacott, and Sadayappan et al., as well as others who have studied this code using different frameworks, such as Song and Li.
Differences in Presentation or Vocabulary
Comparison of works using different frameworks is complicated by both technical differences (discussed later) and differences in vocabulary and presentation.Examples are provided below to aid in translation:
Classification of Dependences
Polyhedral Frameworks support dependence analysis in a variety of ways,helping to capture the impact of symbolic terms,
identify conditional dependences,
and separating out the effects of memory aliasing.
The effects of memory aliasing, in particular, have been described in two ways:
many authors distinguish between "true" data dependences (corresponding to actual flow of information) from false dependences arising from memory aliasing or limited precision of dependence analysis.
The Omega Project publications use specific terms to identify specific effects on analysis.
They maintain the traditional distinction of flow-, output-, and anti-dependences,
based on the types of array access (write to read, write to write, or read to write, respectively).
Dependences can independently be classified as memory-based or value-based ---
the former corresponds to memory aliasing,
and the latter does not include dependences interrupted by intervening writes.
A dependence test may produce information that is exact or approximate,
depending on the nature of the program being analyzed and the algorithms used in the test.
Finally, the results of dependence analysis will be reported in a dependence abstraction
that provides a certain degree of precision.
For example, the "dependence relations" produced by the Omega Test,
and the "quasts" produced by the algorithms of Feautrier or Maydan and Lam,
contain precise information (though in different forms) about the loop iterations involved in a dependence.
The results of either test can be converted into the more traditional "dependence vector" form,
but since this abstraction provides less precision,
much of the information about the dependence will be lost.
Both techniques produce exact information for programs with affine control and subscript expressions,
and must approximate for many programs outside this domain (i.e., in the presence of non-affine subscripts such as index arrays).
The original work of Feautrier focused on describing true dependences,
which would be referred to as exact value-based flow dependences by the Omega Project.
The Omega Project also described the use of their algorithms for value-based output- and anti-dependences, though Feautrier's quasts could presumably be easily adapted to this as well.
Visualization of Transformations and Tiling
There are many ways to produce a visual depiction of the process of transforming and tiling an iteration space.Some authors depict transformations by changing the location of points on the page,
essentially aligning the picture with the coordinate axes of the transformed space;
in such diagrams, tiles appear as axis-aligned rectangles/rectangular solids containing iterations.
Examples of this approach can be found in the publications and transformation-visualization software of Michelle Mills Strout.
Other authors depict different transformations as different wavefronts of execution that move across the points of the original coordinate system at different angles.
In such diagrams, tiles appear as parallelograms/parallelepipeds.
Examples of this approach can be found in the time-skewing publications of
David G. Wonnacott.
Differences in Approach or Implementation Status
Some of the libraries have seen more extensive development than the Omega Library in the early 2000s, and in many places has much more sophisticated algorithms. In particular, users have reported good results with the Cloog code generator (both in terms of the code generated, and in terms of ability to control trade-offs when generating code), and with the algorithms for counting integer solutions (Alexander Barvinok's work requires a vertex description of the polytope, which is not supported in the Omega Library).There are several other points on which the frameworks differ, specifically:
Precision and speed
Integer programmingInteger programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, and Maydan showed that the problem of checking array aliasing in nested loops with affine bounds and subscripts is equivalent to integer programming; other operations, such as array dataflow analysis, are even more complex (the algorithms of the Omega Library handle the full language of Presburger Arithmetic, which is O(2^2^2^n)). Thus, it is clearly unrealistic to expect exact fast results for arbitrary problems of array aliasing or array data flow, even over the affine domain. Fortunately, many problems fall into a subset of this domain where general algorithms can produce an exact answer in polynomial time ,.
Outside of this domain, the Omega Library, piplib and isl emphasize the production of an exact result (except in the cases of certain uses of uninterpreted function symbols in Omega), despite the high complexity. In some cases, such as variable elimination ("projection"), PolyLib and PPL primarily use algorithms for the rational domain, and thus produce an approximation of the result for integer variables. It may the case that this reduces the common experience with the Omega Library in which a minor change to one coefficient can cause a dramatic shift in the response of the library's algorithms.
Polylib has some operations to produce exact results for Z-polyhedra (integer points bounded by polyhedra), but at the time of this writing, significant bugs have been reported. Note that bugs also exist in the Omega Library, including reliance on hardware-supplied integer types and cases of the full Presburger Arithmetic algorithms that were not implemented in the library. Users who need exact results for integer variables may need to be wary with either library.
Barvinok's techniques for counting integer solutions require a description of the vertices (and bounding rays) of the polyhedron, but produce an exact answer in a way that can be far more efficient than the techniques described by Pugh. Barvinok's algorithm is always polynomial in the input size, for fixed dimension of the polytope and fixed degree of weights, whereas the "splintering" in Pugh's algorithm can grow with the coefficient values (and thus exponentially in terms of input size, despite fixed dimension, unless there is some limit on coefficient sizes).
Vertex enumeration
Polyhedral libraries such as PolyLib and PPL exploit the double description of polyhedra and therefore naturally supportvertex enumeration on (non-parametric) polytopes.
The Omega Library internally performs vertex enumeration during the computation of the convex hull.
PolyLib and isl provide vertex enumeration on parametric polytopes, which is essential for applying
Barvinok's algorithm to parametric polytopes.
Indication of an approximate result
In some parts of a compiler, an approximate result is acceptable in certain cases. For example, when dependence analysisLoop dependence analysis
In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, with respect to array access and modification, induction, reduction and private variables, simplification of loop-independent code and management of conditional branches...
is used to guide loop transformation, it is generally acceptable to use a superset of the true dependencies—this can prevent an optimization but does not allow illegal code transformations. When the Omega Library produces an approximate answer, the answer is appropriately marked as an upper bound (e.g., via "and UNKNOWN") or a lower bound (e.g., via "or UNKNOWN"). Answers not marked this way are exact descriptions of sets of integer-valued points (except in cases of bugs in the software).
Handling nonlinear terms
When code contains a mixture of affine and non-affine terms, polyhedral libraries can, in principle, be used to produce approximate results, for example by simply omitting such terms when it is safe to do so. In addition to providing a way to flag such approximate results, the Omega Library allows restricted uses of "Uninterpreted Function Symbols" to stand in for any nonlinear term, providing a system that slightly improves the result of dependence analysis and (probably more significantly) provides a language for communication about these terms (to drive other analysis or communication with the programmer). Pugh and Wonnacott discussed a slightly less restricted domain than that allowed in the library, but this was never implemented (a description exists in Wonnacott's dissertation).Transitive closure operation
Some kinds of analysis, such as Pugh and Rosser's iteration space slicing, can be most easily stated in terms of the transitive closure of the dependence information. Both the Omega Library and isl provide a transitive closure operation that is exact for many cases that arise in programs with simple dependence patterns. In other cases, the Omega Library produces a subset of the transitive closure, while isl produces a superset.In the case of the Omega Library, the subset itself may be approximate, resulting in an upper bound (tagged) of a lower bound (not tagged) of the transitive closure. Note that the computation of an exact transitive closure is undecidable.
See also
- Loop nest optimizationLoop nest optimizationLoop nest optimization applies a set of loop transformations for the purpose of locality optimization or parallelization or other loop overhead reduction of the loop nests...
- Jean-Francois Collard's Reasoning About Program Transformations, covers some of the shared philosophy of these projects.
- Cedric Bastoul's thesis gives an introduction to the polyhedral model.
- The "Omega Test" entry in Springer's forthcoming Encyclopedia of Parallel Computing describes the applications and algorithms of the Omega Library, indicating the major Omega Project publications where further detail can be found. An earlier draft of this content can be found in tech report form as a Haverford College Computer Science Tech Report.
- Links to relevant open-source libraries are given in the first paragraph of this article.
- Reservoir Labs provides "Jolylib", a Java implementation of Polylib etc. that "provides improved performance, stability, and features". Jolylib is available for commercial and academic use; for further information, contact Reservoir Labs via email.