Frameworks supporting the polyhedral model

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). Two of the most common frameworks are (a) the [http://www.cs.umd.edu/projects/omega Omega Library] (with source code now hosted as [http://github.com/davewathaverford/the-omega-project/tree/master the-omega-project] on github) and (b) a combination of [http://www.piplib.org/ piplib] Paul Feautrier. "Parametric Integer Programming." 1988] , [http://icps.u-strasbg.fr/polylib/ Polylib] Doran K. Wilde. "A Library for Doing Polyhedral Operations." 1993. [ftp://ftp.irisa.fr/techreports/1993/PI-785.ps.gz tech report] ] , the [http://www.cloog.org/ cloog polyhedral code generator] Cedric Bastoul. "Code Generation in the Polyhedral Model Is Easier Than You Think." PACT'13 IEEE International Conference on Parallel Architecture and Compilation Techniques (2004)] , and the [http://www.freshmeat.net/projects/barvinok barvinok library for counting integer solutions] . The latter combination is sometimes referred to as "Polylib"; the term "Polylib etc." is used to refer to this combination here. The "Polylib etc." tools are collected together in gcc as GraphiteSebastian Pop, Albert Cohen , Cedric Bastoul , Sylvain Girbal, Pierre Jouvelot, Georges-Andr Silber et Nicolas Vasilache. "Graphite: Loop optimizations based on the polyhedral model for GCC." 4th GCC Developper's Summit. Ottawa, Canada, June 2006.] .

Common Strengths

Both libraries 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). Both 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. Both allow the use of symbolic expressions.

Both 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 dependences. Both can also be used to represent code transformation, and provide features to generate the transformed code in a high-level language. For both libraries, the transformation and generation systems can handle imperfectly nested loops.

An example to contrast both 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 dependences 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 dependences 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 dependences 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 either Polylib etc. or the Omega Library.

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 both frameworks have explored the simple 1-dimensional finite difference 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

A re-cap here, of the two approaches on this example, might be nice, but for now see the individual papers of WonnacottDavid Wonnacott. "Achieving Scalable Locality with Time Skewing." International Journal of Parallel Programming 30.3 (2002)] David Wonnacott. " [http://doi.ieeecomputersociety.org/10.1109/IPDPS.2000.845979 Using Time Skewing to Eliminate Idle Time due to Memory Bandwidth and Network Limitations.] " 14th International Parallel and Distributed Processing Symposium (IPDPS'00)] , and Sadayappan et alUday Bondhugula, Muthu Manikandan Baskaran, Sriram Krishnamoorthy, J. Ramanujam, Atanas Rountev, P. Sadayappan. "Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model." CC 2008 - International Conference on Compiler Construction] , as well as others who have studied this code using different frameworks, such as Song and LiYonghong Song, Zhiyuan Li. " [http://portal.acm.org/citation.cfm?id=301618.301668&coll=portal&dl=ACM&type=series&idx=SERIES363&part=series&WantType=Proceedings&title=PLDI&CFID=36310011&CFTOKEN=72120731 New Tiling Techniques to Improve Cache Temporal Locality] ." Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)] .

Differences in approach or implementation status

The "Polylib etc." toolchain saw more more extensive development than the Omega Library in the early 2000's, 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 (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 two frameworks differ, specifically:

Precision and speed

Integer programming is N-P 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 William Pugh. " [http://portal.acm.org/citation.cfm?id=125848 The Omega test: a fast and practical integer programming algorithm for dependence analysis] ." Proceedings of the 1991 ACM/IEEE conference on Supercomputing] , Robert Seater, David Wonnacott. " [http://www.springerlink.com/content/w2exje48bmv41b99/ Polynomial Time Array Dataflow Analysis] .", Languages and Compilers for Parallel Computing 2003] .

Outside of this domain, the Omega Library emphasizes the production of an exact result (except in the cases of certain uses of uninterpreted function symbols), despite the high complexity. In some cases, such as variable elimination ("projection"), Polylib primarily uses algorithms for the rational domain, and thus produces an approximation of the result for integer variables. It may the 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 etc. has some operations to produce exact results for Z-polyhedra (integer points bounded by polyhedra), but at the time of this writing, [http://lipforge.ens-lyon.fr/tracker/index.php?func=detail&aid=3171&group_id=52&atid=296 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 Sven Verdoolaege, Rachid Seghir, Kristof Beyls, Vencent Loechner, Maurice Bruynooghe. " [https://lirias.kuleuven.be/bitstream/123456789/124371/1/algorithmica.pdf Counting Integer Points in Parametric Polytopes using Barvinok's Rational Functions] ." Section 6.1 discusses Pugh's method and splintering.] (and thus exponentially in terms of input size, despite fixed dimension, unless there is some limit on coefficient sizes).

Vertex enumeration

Polylib provides algorithms for enumerating the vertices of a polytope. This functionality is not present in the Omega Library.

Indication of an approximate result

In some parts of a compiler, an approximate result is acceptable in certain cases. For example, when dependence analysis is used to guide loop transformation, it is generally acceptable to use a superset of the true dependences --- 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, both 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. The Omega Library provides a transitive closure operation that is exact for many cases that arise in programs with simple dependence patterns. In other cases, it produces an approximate result (appropriately tagged). Note that adding an exact transitive closure would make the Omega Library undecidableWayne Kelly, William Pugh, Evan Rosser, Tatiana Shpeisman. "Transitive Closure of Infinite Graphs and Its Applications." Languages and Compilers for Parallel Computing, 8th International Workshop (LCPC 1995)] .

ee Also

*Loop nest optimization
*Jean-Francois Collard's "Reasoning About Program Transformations," Jean-Francois Collard, "Reasoning About Program Transformations,", 2003 Springer-Verlag] covers some of the shared philosophy of these projects.
*Cedric Bastoul's thesis Cedric Bastoul. "Improving Data Locality in Static Control Programs" [http://www.prism.uvsq.fr/~cedb/bastools/download/bastoul_thesis.pdf pdf] ] gives an introduction to the polyhedral model.
*Links to relevant open-source libraries are given in the first paragraph of this article.
* [http://www.reservoir.com/ 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.

References