diff options
| -rw-r--r-- | polly/lib/CodeGen/IslAst.cpp | 10 | ||||
| -rw-r--r-- | polly/lib/Transform/ScheduleOptimizer.cpp | 43 | ||||
| -rw-r--r-- | polly/www/index.html | 43 | ||||
| -rw-r--r-- | polly/www/publications.html | 6 |
4 files changed, 94 insertions, 8 deletions
diff --git a/polly/lib/CodeGen/IslAst.cpp b/polly/lib/CodeGen/IslAst.cpp index 3c17517c923..c86b4b7c49e 100644 --- a/polly/lib/CodeGen/IslAst.cpp +++ b/polly/lib/CodeGen/IslAst.cpp @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// // -// The isl code generator interface takes a Scop and generates a isl_ast. This +// The isl code generator interface takes a Scop and generates an isl_ast. This // ist_ast can either be returned directly or it can be pretty printed to // stdout. // @@ -17,6 +17,14 @@ // bb2(c2); // } // +// An in-depth discussion of our AST generation approach can be found in: +// +// Polyhedral AST generation is more than scanning polyhedra +// Tobias Grosser, Sven Verdoolaege, Albert Cohen +// ACM Transations on Programming Languages and Systems (TOPLAS), +// 37(4), July 2015 +// http://www.grosser.es/#pub-polyhedral-AST-generation +// //===----------------------------------------------------------------------===// #include "polly/CodeGen/CodeGeneration.h" diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp b/polly/lib/Transform/ScheduleOptimizer.cpp index 26b9668d972..1e063093033 100644 --- a/polly/lib/Transform/ScheduleOptimizer.cpp +++ b/polly/lib/Transform/ScheduleOptimizer.cpp @@ -7,14 +7,43 @@ // //===----------------------------------------------------------------------===// // -// This pass the isl to calculate a schedule that is optimized for parallelism -// and tileablility. The algorithm used in isl is an optimized version of the -// algorithm described in following paper: +// This pass generates an entirey new schedule tree from the data dependences +// and iteration domains. The new schedule tree is computed in two steps: +// +// 1) The isl scheduling optimizer is run +// +// The isl scheduling optimizer creates a new schedule tree that maximizes +// parallelism and tileability and minimizes data-dependence distances. The +// algorithm used is a modified version of the ``Pluto'' algorithm: +// +// U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan. +// A Practical Automatic Polyhedral Parallelizer and Locality Optimizer. +// In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language +// Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008. +// +// 2) A set of post-scheduling transformations is applied on the schedule tree. +// +// These optimizations include: +// +// - Tiling of the innermost tilable bands +// - Prevectorization - The coice of a possible outer loop that is strip-mined +// to the innermost level to enable inner-loop +// vectorization. +// - Some optimizations for spatial locality are also planned. +// +// For a detailed description of the schedule tree itself please see section 6 +// of: +// +// Polyhedral AST generation is more than scanning polyhedra +// Tobias Grosser, Sven Verdoolaege, Albert Cohen +// ACM Transations on Programming Languages and Systems (TOPLAS), +// 37(4), July 2015 +// http://www.grosser.es/#pub-polyhedral-AST-generation +// +// This publication also contains a detailed discussion of the different options +// for polyhedral loop unrolling, full/partial tile separation and other uses +// of the schedule tree. // -// U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan. -// A Practical Automatic Polyhedral Parallelizer and Locality Optimizer. -// In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language -// Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008. //===----------------------------------------------------------------------===// #include "polly/ScheduleOptimizer.h" diff --git a/polly/www/index.html b/polly/www/index.html index c4ca186d934..97d6d190811 100644 --- a/polly/www/index.html +++ b/polly/www/index.html @@ -44,6 +44,49 @@ <table id="news"> <tr><td><b>2015</b></td></tr> + <tr><td width="120"><p>July</p></td> + <td> + <h4>AST Generation Paper published in TOPLAS</h4> + The July issue of TOPLAS contains a 50 page discussion of the AST + generation techniques used in Polly. This discussion gives not only an + in-depth description of how we (re)generate an imperative AST from our + polyhedral based mathematical program description, but also gives + interesting insights about: + <ul> + <li><b>Schedule trees:</b> A tree-based mathematical program description + that enables us to perform loop transformations on an abstract level, + while issues like the generation of the correct loop structure and loop + bounds will be taken care of by our AST generator. + <li><b>Polyhedral unrolling:</b> We discuss techniques that allow the + unrolling of non-trivial loops in the context of parameteric loop bounds, + complex tile shapes and conditionally executed statements. Such unrolling + support enables the generation of predicated code e.g. in the context of + GPGPU computing. + <li><b>Isolation for full/partial tile separation:</b> We discuss native + support for handling full/partial tile separation and -- in general -- + native support for isolation of boundary cases to enable smooth code + generation for core computations. + <li><b>AST generation with modulo constraints:</b> We discuss how modulo + mappings are lowered to efficient C/LLVM code. + <li><b>User-defined constraint sets for run-time checks</b> We discuss how + arbitrary sets of constraints can be used to automatically create run-time + checks that ensure a set of constrainst actually hold. This feature is + very useful to verify at run-time various assumptions that have been taken + program optimization. + </ul> + + <a href="http://www.grosser.es#pub-polyhedral-AST-generation"> + <em>Polyhedral AST generation is more than scanning polyhedra</em></a><br /> + Tobias Grosser, Sven Verdoolaege, Albert Cohen<br /> + ACM Transations on Programming Languages and Systems (TOPLAS), 37(4), + July 2015 + + <br> + <br> + <br> + <br> + </td> + </tr> <tr><td width="120"><p>February</p></td> <td> <h4>Polly allows now non-affine subregions</h4> diff --git a/polly/www/publications.html b/polly/www/publications.html index bee01c00523..7793342f26e 100644 --- a/polly/www/publications.html +++ b/polly/www/publications.html @@ -38,6 +38,12 @@ Parallel Processing Letters 2012 22:04<br /> <h2> Publications involving Polly </h2> <h3> 2015 </h3> <ul> + <li><em>Polyhedral AST generation is more than scanning polyhedra</em><br /> + Tobias Grosser, Sven Verdoolaege, Albert Cohen<br /> + ACM Transations on Programming Languages and Systems (TOPLAS), 37(4), July + 2015<br /> + <a href="http://www.grosser.es#pub-polyhedral-AST-generation">Paper</a> + </li> <li><em>On recovering multi-dimensional arrays in Polly</em><br /> Tobias Grosser, Sebastian Pop, J. Ramanujam, P. Sadayappan <br /> Impact2015 at HiPEAC, Amsterdam, The Netherlands<br /> |
