www/index.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2           "http://www.w3.org/TR/html4/strict.dtd">
   3 <!-- Material used from: HTML 4.01 specs: http://www.w3.org/TR/html401/ -->
   4 <html>
   5 <head>
   6   <META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   7   <title>Polly - Polyhedral optimizations for LLVM</title>
   8   <link type="text/css" rel="stylesheet" href="menu.css">
   9   <link type="text/css" rel="stylesheet" href="content.css">
  10   <script src="video-js/video.js" type="text/javascript" charset="utf-8"></script>
  11   <script type="text/javascript">
  12     VideoJS.setupAllWhenReady();
  13   </script>
  14
  15   <!-- Include the VideoJS Stylesheet -->
  16   <link rel="stylesheet" href="video-js/video-js.css" type="text/css" media="screen" title="Video JS">
  17 </head>
  18 <body>
  19 <div id="box">
  20 <!--#include virtual="menu.html.incl"-->
  21 <div id="content">
  22   <!--*********************************************************************-->
  23   <h1>About Polly</h1>
  24   <!--*********************************************************************-->
  25
  26   <p> Polly is a high-level loop and data-locality optimizer and optimization
  27   infrastructure for LLVM. It uses an abstract mathematical representation based
  28   on integer polyhedra to analyze and optimize the memory access pattern of a
  29   program. We currently perform classical loop transformations, especially
  30   tiling and loop fusion to improve data-locality. Polly can also exploit
  31   OpenMP level parallelism, expose SIMDization opportunities. Work has also be
  32   done in the area of automatic GPU code generation.</p>
  33
  34   For many users, however, it's not the existing optimizations in Polly that are
  35   of most interest, but the new analyses and optimizations enabled by the Polly
  36   infrastructure. At
  37   <a href="http://polyhedral.info">polyhedral.info</a> you can get an idea of
  38   what has already been done and what is possible in the context of polyhedral
  39   compilation.
  40
  41   <!--=====================================================================-->
  42   <h2>News</h2>
  43   <!--=====================================================================-->
  44
  45   <table id="news">
  46   <tr><td><b>2017</b></td></tr>
  47   <tr><td width="120"><p>September</p></td>
  48   <td>
  49     <h4>High-Performance Generalized Matrix Multiplication</h4>
  50     Polly automatically detects and optimizes generalized matrix
  51     multiplication, the computation C &larr; &alpha; &otimes; C &oplus; &beta;
  52     &otimes; A &otimes; B, where A, B, and C are three appropriately sized
  53     matrices, &oplus; and &otimes; operations are originating from the
  54     corresponding matrix semiring, and &alpha; and &beta; are constants, and
  55     beta is not equal to zero. It allows to obtain the highly optimized form
  56     structured similar to the expert implementation of GEMM that can be found
  57     in GotoBLAS and its successors.
  58     <h4>The performance evaluation of GEMM</h4>
  59     <img src="images/GEMM_double.png" /><br />
  60   </td>
  61   <tr><td><b>2017</b></td></tr>
  62   <tr><td width="120"><p>January</p></td>
  63   <td>
  64   <a href="http://impact.gforge.inria.fr/impact2017">IMPACT 2017</a> program
  65   announced. Join IMPACT 2017 on January 23rd in Stockholm <a
  66   href="https://www.hipeac.net/2017/stockholm/">@HiPEAC'17</a>.
  67   </td>
  68   </tr>
  69   <tr><td><b>2016</b></td></tr>
  70   <tr><td width="120"><p>August</p></td>
  71   <td>
  72   <a href="http://impact.gforge.inria.fr/impact2017">IMPACT 2017</a> the 7th
  73   International Workshop on Polyhedral Compilation Techniques will take place
  74   at January 23-25, 2017 together with HiPEAC 2017 in Stockholm, Sweden. It is
  75   a great opportunity to discuss and present work on Polyhedral Compilation,
  76   including work on Polly.
  77   </td>
  78   </tr>
  79   <tr><td width="120"><p>April</p></td>
  80   <td>
  81     A source checkout that contains Polly now provides Polly functionality
  82     by default in clang/opt/bugpoint without the need to load an additional
  83     module.
  84   </td>
  85   </tr>
  86   <tr><td><b>2015</b></td></tr>
  87   <tr><td width="120"><p>July</p></td>
  88   <td>
  89     <h4>AST Generation Paper published in TOPLAS</h4>
  90     The July issue of TOPLAS contains a 50 page discussion of the AST
  91     generation techniques used in Polly. This discussion gives not only an
  92     in-depth description of how we (re)generate an imperative AST from our
  93     polyhedral based mathematical program description, but also gives
  94     interesting insights about:
  95     <ul>
  96       <li><b>Schedule trees:</b> A tree-based mathematical program description
  97       that enables us to perform loop transformations on an abstract level,
  98       while issues like the generation of the correct loop structure and loop
  99       bounds will be taken care of by our AST generator.
 100       <li><b>Polyhedral unrolling:</b> We discuss techniques that allow the
 101       unrolling of non-trivial loops in the context of parameteric loop bounds,
 102       complex tile shapes and conditionally executed statements. Such unrolling
 103       support enables the generation of predicated code e.g. in the context of
 104       GPGPU computing.
 105       <li><b>Isolation for full/partial tile separation:</b> We discuss native
 106       support for handling full/partial tile separation and -- in general --
 107       native support for isolation of boundary cases to enable smooth code
 108       generation for core computations.
 109       <li><b>AST generation with modulo constraints:</b> We discuss how modulo
 110       mappings are lowered to efficient C/LLVM code.
 111       <li><b>User-defined constraint sets for run-time checks</b> We discuss how
 112       arbitrary sets of constraints can be used to automatically create run-time
 113       checks that ensure a set of constrainst actually hold. This feature is
 114       very useful to verify at run-time various assumptions that have been taken
 115       program optimization.
 116     </ul>
 117
 118    <a href="http://www.grosser.es#pub-polyhedral-AST-generation">
 119    <em>Polyhedral AST generation is more than scanning polyhedra</em></a><br />
 120     Tobias Grosser, Sven Verdoolaege, Albert Cohen<br />
 121     ACM Transations on Programming Languages and Systems (TOPLAS), 37(4),
 122     July 2015
 123
 124     <br>
 125     <br>
 126     <br>
 127     <br>
 128   </td>
 129   </tr>
 130   <tr><td width="120"><p>February</p></td>
 131   <td>
 132     <h4>Polly allows now non-affine subregions</h4>
 133     Data-dependent or floating point conditionals inside a SCoP can now be
 134     overapproximated in order to increase the applicability on general purpose
 135     code.
 136   </td>
 137   </tr>
 138   <tr><td><b>2014</b></td></tr>
 139   <tr><td width="120"><p>August</p></td>
 140   <td>
 141   <h4>Polly drops the support of ScopLib and the external optimizer PoCC</h4>
 142   The support for ScopLib as an exchange format has been removed as recent
 143   versions of clan, candl and pluto all support the OpenScop exchange format.
 144
 145   The support of the external optmizer PoCC has been dropped in favor of the
 146   isl optimizer (default) and the still available pluto support.
 147   </td>
 148   </tr>
 149   <tr><td><b>2014</b></td></tr>
 150   <tr><td width="120"><p>June</p></td>
 151   <td>
 152   <h4>Polly can be built without GPL licensed software</h4> After Sebastian
 153   Pop's
 154   and David Peixotto's (both Qualcomm) recent <a
 155   href="http://repo.or.cz/w/isl.git/commit/60703e3ee89b9d5d4d1afb6a3f611292c0884574">commit</a>
 156   to isl, isl's latest development version can be built with imath instead of
 157   GMP. With both CLooG and gmp having become optional, the last obilgatory
 158   dependency to GPL licensed software has been removed. Now Polly only depends
 159   on isl (and the included imath), which are both MIT licensed.
 160   </td>
 161   </tr>
 162   <tr><td width="120"><p>April</p></td>
 163   <td>
 164   <h4>Polly Phone Call - 23April</h4>
 165   We had a polly phone call about delinearizing array accesses (II)<a
 166   href="https://docs.google.com/document/d/1IZewI8Up0iEkCNIPr6gVtwJxF7RV6KmXkdwOBM_Q5Cs/edit?usp=sharing ">Meeting notes</a> are available online.
 167   <h4>Polly Phone Call - 17th April</h4>
 168   We had a polly phone call about delinearizing array accesses <a
 169   href="https://docs.google.com/document/d/14d3ehkH2MsvBdqsEOSYjysH0Ztyzb75Lp843hnxh2IA/edit?usp=sharing">Meeting notes</a> are available online.
 170   <h4>Polly Phone Call - 10th April</h4>
 171   We had a polly phone call. <a
 172   href="https://docs.google.com/document/d/12W-qZjiZGEQ_lVrob4OzvKJI3EooonC-ap1b9f9KCUE/edit?usp=sharing">Meeting notes</a> are available online.
 173   <h4>Polly Phone Call - 4th April</h4>
 174   We had a polly phone call. <a
 175   href="https://drive.google.com/folderview?id=0B7OMOXTgCYIUWkpJbWVJcW04ams&usp=sharing">Meeting notes</a> are available online.
 176   </td>
 177   </tr>
 178   <tr><td width="120"><p>March</p></td>
 179   <td>
 180   <h4>Static link Polly into tools</h4> Polly can now be configured with 'cmake
 181   -D LINK_POLLY_INTO_TOOLS:Bool=ON' to be statically linked in the tools (opt,
 182   bugpoint, and clang.) This makes it easier to use polly without having to load
 183   a shared library, and it also reduces the complexity of compiling Polly on
 184   Windows.
 185   </td>
 186   </tr>
 187   <tr><td width="120"><p>February</p></td>
 188   <td>
 189   <h4>Polly presentation at FOSDEM 2014</h4> Polly was <a
 190   href="https://fosdem.org/2014/schedule/event/polly/">presented</a> at the
 191   FOSDEM LLVM developer's meeting.
 192   <h4>New LLVM test-suite buildbots</h4>
 193   The set of <a href="http://lab.llvm.org:8011/console?category=polly">Polly
 194   buildbots</a> has been extended. We now have 16 new blades that track
 195   correctness and performance when compiling the LLVM test-suite. For now five
 196   of them are used to provide <a
 197   href="http://llvm.org/perf/db_default/v4/nts/22463">fine granularity
 198   reports</a> (almost per-commit)
 199   for 'clang -O3' (no polly). We also have six machines that track different
 200   configurations of polly.
 201   </td>
 202   </tr>
 203   <tr><td width="120"><p>January</p></td>
 204   <td>
 205   <h4>islplot released</h4>
 206   <a href="https://github.com/tobig/islplot">islplot</a> is a library that
 207   generates illustrations of integer sets and maps. It relies on <a
 208   href="http://repo.or.cz/w/isl.git">isl</a> to model the integer sets and uses the <a
 209   href="https://pypi.python.org/pypi/islpy">islpy</a> Python bindings to access
 210   them. Plotting is performed with <a
 211   href="http://matplotlib.org">matplotlib</a>. The following <a
 212   href="http://nbviewer.ipython.org/github/tobig/islplot/blob/master/notebooks/islplot-examples.ipynb">
 213   Examples</a> show its use.
 214   </td>
 215   </tr>
 216   <tr><td><b>2013</b></td></tr>
 217   <tr><td width="120"><p>November</p></td>
 218   <td>
 219   <h4>Loop optimization BoF at upcoming LLVM conference</h4>
 220   At the upcoming <a href="http://llvm.org/devmtg/2013-11/#bof5">LLVM conference
 221   </a> there will be a loop optimization BoF discussing Polly and other high
 222   level loop optimizers.
 223   </td>
 224   </tr>
 225   <tr><td width="120"><p>October</p></td>
 226   <td>
 227   <h4>Automatic code coverage and static analysis tests</h4>
 228   Sylvestre Ledru set up automatic tests for <a
 229   href="http://buildd-clang.debian.net/coverage/">code coverage</a> and
 230   <a href="http://buildd-clang.debian.net/scan-build/">static analysis</a>
 231   which run at least once a day and which include results for Polly.
 232   <h4>Move to CLooG 0.18.1 and isl 0.12.1</h4>
 233   With the move to an isl 0.12 version Polly can be compiled without the
 234   need to link directly to GMP (if isl is used for code generation). Currently
 235   isl is still internally using GMP, but private patches exist to also remove
 236   this dependency. Without the use of GMP, a <b>GPL free</b> version of Polly
 237   is possible.
 238   </td></tr>
 239
 240   <tr><td><b>2012</b></td></tr>
 241   <tr><td width="120"><p>December</p></td>
 242   <td>
 243   <h4> New publication in the PPL Journal
 244      </h4>
 245
 246       We published a journal version of the Polly paper named
 247       <em>
 248       Polly - Performing polyhedral optimizations on a low-level intermediate
 249       representation</em> in the Parallel Processing Letters 2012.
 250   </td></tr>
 251   <tr><td width="120"><p>September</p></td>
 252   <td>
 253   <h4>Experimental support for the <b>new isl code generator</b></h4>
 254      The code generator can be parameterized on a fine-grained
 255      level. It gives direct control for example over unrolling, the amount of
 256      control overhead and the code size. It can also be used to
 257      create loops to handle border conditions or to perform full-partial tile
 258      separation.<br />
 259      We also relicensed isl under the <b>MIT license</b>. This means, with the
 260      exception of GMP (LGPL), there is no other (L)GPL licensed software used in
 261      Polly. The
 262      use of GMP is limited to a well defined interface. Replacing it with
 263      a BSD licensed replacement is a tractable engineering project we would
 264      be very interested in. For more information about isl see the <a
 265      href="http://www.kotnet.org/~skimo/isl/manual.pdf">isl manual</a>.
 266      </p>
 267   </td></tr>
 268   <tr><td width="120"><p>July</p></td>
 269   <td>
 270   <p> Polly can now be directly linked to the <a
 271 href="http://pluto-compiler.sourceforge.net/">Pluto optimizer</a>. We were
 272 already able to perform Pluto-like optimizations with Polly, as a similar
 273 algorithm was added to isl half a year ago. However, being able to directly
 274 compare with the original implementation will not only bring in competition in
 275 the optimizer field. It will also allow new experiments with a cutting edge
 276 research tool.<br \>
 277   This support was on of the outcomes of the 1-day Polly workshop and the
 278   following week of joint work at IISC Bangalore and in cooperation with
 279   AMD India.
 280   </td></tr>
 281   <td>
 282   </td></tr>
 283   <tr><td width="120"><p>February</p></td>
 284   <td>
 285   <p>Polly is an official LLVM project, reachable at <a
 286   href="http://polly.llvm.org">http://polly.llvm.org</a></p>
 287   </td></tr>
 288   <tr><td width="120"><p>January</p></td>
 289   <td>
 290   <p>Improved support for the isl scheduling optimizer</p>
 291   Polly can now automatically optimize all <a
 292   href="http://www.cse.ohio-state.edu/~pouchet/software/polybench/">polybench
 293   2.0</a> kernels without the help of
 294   an external optimizer. The compile time is reasonable and we can show
 295   notable speedups for various kernels.
 296   </td></tr>
 297
 298   <tr>
 299   <tr><td><b><br/>2011</b></td></tr>
 300   <tr><td width="120"><p>November</p></td>
 301   <td>
 302   <p>
 303   Talk at the <a href="http://llvm.org/devmtg/2011-11/">
 304       LLVM Developer Meeting 2011</a></p>
 305   New SCEV parser<br>
 306   (Allows parameters in array subscript and max/signextend)
 307   </td></tr>
 308
 309   <tr>
 310   <td><p>October</p></td>
 311   <td>
 312   <p>Polly can use the isl schedule optimizer<br>
 313     (The optimizer is similar to the one in Pluto, but it is part of isl)
 314   </p>
 315   </td></tr>
 316
 317   <tr>
 318   <td><p>August</p></td>
 319   <td>
 320   <p>
 321   <a href="example_load_Polly_into_clang.html">Use Polly as
 322   clang plugin</a></p>
 323   </td>
 324   </tr>
 325
 326   <tr>
 327   <td><p>July</p></td>
 328   <td>
 329   <p> Polly builder as part of the <a
 330   href="http://lab.llvm.org:8011/console">LLVM Buildbots</a>
 331   </p>
 332   </td>
 333   </tr>
 334
 335   <tr>
 336   <td><p>June</p></td>
 337   <td>
 338   <p><a href="http://www.grosser.es">Tobias</a> is founded for
 339   three years by a <a
 340   href="http://research.google.com/university/relations/fellowship_recipients.html">
 341   Google Europe Fellowship in Efficient Computing</a>.
 342   </p>
 343   </td>
 344   </tr>
 345
 346   <tr>
 347   <td><p>May </p></td>
 348   <td><p><a href="http://www.grosser.es">Tobias</a>' diploma thesis and
 349   Raghesh's master thesis. See our <a
 350   href="publications.html">list of publications</a>.</p></td>
 351   </tr>
 352
 353   <tr>
 354   <td><p>April</p></td>
 355   <td><p>Polly moves to the LLVM infrastructure (svn, bugtracker)</p></td>
 356   </tr>
 357
 358   <tr>
 359   <td><p>March</p></td>
 360   <td><p>Presentation at <a
 361   href="http://impact2011.inrialpes.fr/">CGO/IMPACT</a></p>
 362   <p>Polly can compile
 363   polybench 2.0 with vectorization and OpenMP code generation</p>
 364   </td>
 365   </tr>
 366   <tr>
 367   <td><p>Februar</p></td>
 368   <td><p>pollycc - a script to automatically compile with
 369   polyhedral optimizations </p></td>
 370   </tr>
 371
 372   <tr>
 373   <td><p> Januar</p></td>
 374   <td><p> Basic OpenMP support, Alias analysis integration,
 375   Pluto/POCC support </p></td>
 376   </tr>
 377
 378   <tr><td><b><br>2010</b></td></tr>
 379   <tr>
 380   <td><p> Dezember </p></td>
 381   <td><p>Basic vectorization support </p></td>
 382   </tr>
 383
 384   <tr>
 385   <td><p> November </p></td>
 386   <td><p>Talk at the <a
 387   href="http://llvm.org/devmtg/2010-11/">LLVM Developer Meeting</a> </p></td>
 388   </tr>
 389
 390   <tr>
 391   <td><p>October</p></td>
 392   <td><p>Dependency analysis </p>
 393   <p>Finished Phase 1 - Get something working </p>
 394   <p>Support scalar dependences and sequential SCoPs </p>
 395   </td>
 396   </tr>
 397
 398   <tr>
 399   <td><p>August</p></td>
 400   <td><p>RegionInfo pass committed to LLVM</p>
 401   <p>llvm-test suite compiles </p>
 402   </td>
 403   </tr>
 404
 405   <tr>
 406   <td><p>July</p></td>
 407   <td><p>Code generation works for normal SCoPs.  </p></td>
 408   </tr>
 409
 410   <tr>
 411   <td><p>May</p></td>
 412   <td><p>The CLooG AST can be parsed.</p>
 413   </td>
 414   </tr>
 415
 416   <tr>
 417   <td><p>April</p></td>
 418   <td><p>SCoPs can automatically be detected. </p></td>
 419   </tr>
 420
 421   <tr>
 422   <td><p>March</p></td>
 423   <td><p>The RegionInfo framework is almost completed.  </p></td>
 424   </tr>
 425
 426   <tr>
 427   <td><p>February</p></td>
 428   <td><p>Translate a simple loop to Polly-IR and regenerate a loop structure
 429          with CLooG works.  </p>
 430   <p>ISL and CLooG are integrated.  </p></td>
 431   </tr>
 432
 433   </tr>
 434
 435   <tr>
 436   <td><p>January</p></td>
 437   <td><p>The RegionInfo pass is finished.  </p></td>
 438   </tr>
 439
 440   <tr><td><b><br>2009</b></td></tr>
 441   <tr>
 442   <td><p>End of the year</p></td>
 443   <td><p>Work on the infrastructure started.  </p></td>
 444   </tr>
 445   </table>
 446   </ul>
 447 </div>
 448 </div>
 449 </body>
 450 </html>