Loop Parallelization in the Polyhedron Model - Just in Time.

In the past two decades, the polyhedron model [1] has been equipped with a technology that enables its use in the automatic parallelization and optimization of loop programs for high-performance computing [2]. PolyJIT strives to apply the polyhedron model not only at compile time, but at also run time. The additional run-time information will be used to achieve two main goals.

Wider range of applications: The polyhedron model shall become applicable to a variety of real-world codes that are not amenable to state-of-the-art polyhedral optimization due to a lack of knowledge at compile time. The run-time information used includes actual parameter values, actual control flow and more detailed aliasing information.

New analysis and optimization methods: The amount of time spent on program optimization is especially painful at run time, because it reduces the potential benefit. Existing polyhedral optimization algorithms, which tend to have a high execution time complexity, shall be transformed into versions that are suitable for run-time optimization. Furthermore, concurrent program analysis and transformation (on unused cores) and the exploitation of knowledge of the execution context shall enable dynamic and adaptive optimizations.

  1. Christian Lengauer. Loop Parallelization in the Polytope Model. In Eike Best, editor, CONCUR’93, number 715 in Lecture Notes in Computer Science, pages 398–416. Springer-Verlag, 1993.

  2. Paul Feautrier and Christian Lengauer. Polyhedron Model. In David Padua et al., editors, Encyclopedia of Parallel Computing, pages 1581–1592. Springer-Verlag, September 2011.


Project PolyJIT is funded by the German Research Foundation (Deutsche Forschungsgemeinschaft--DFG) , project numbers LE 912/14-1 and GR 4253/1-1 (funding period 2013–2015) and LE 912/14-2 (funding period 2016–2018).


Dagstuhl-Seminar 18111 on 11-16 March 2018 will cover issues around project PolyJIT.






  • Andreas Simbürger, Sven Apel, Armin Größlinger, and Christian Lengauer. The Potential of Polyhedral Optimization: An Empirical Study. In Proceedings of the IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 508–518. IEEE Computer Society, November 2013. Acceptance rate (full papers): 16% (51 / 317).
  • Andreas Simbürger, Sven Apel, Armin Größlinger, and Christian Lengauer. The Potential of Polyhedral Optimization. Technical Report MIP-1301, Department of Informatics and Mathematics, University of Passau, March 2013. 10 pages.

Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these publications may not be reposted without the explicit permission of the copyright holder.