Polyhedral Loop Parallelization: LooPo

Description

LooPo is a project of the Chair for Programming at the Department of Informatics and Mathematics of the University of Passau. Its purpose has been to develop prototype implementation of loop parallelization methods based on the polyhedral model. LooPo has been traversing a number of partially overlapping phases, which we identify by the years of their start:

1994: Implementation of space-time mapping methods for nested FOR loops [Loop Parallelization in the Polytope Model].
1996: Capability of dealing with WHILE loops, FOR loops with unknown bounds at compile time and IF conditions in the loop nest [The Mechanical Parallelization of Loop Nests Containing WHILE Loops].
1998: Optimization through index set splitting; adaption of the granularity of parallelism through tiling [Automatic Parallelization of Loop Programs for Distributed Memory Architectures ].
1999: Code optimization, on the one hand, by compiling to HPF and, on the other, by refining the polyhedron model from statements to expressions [Code Optimization in the Polyhedron Model].
2002: Capability to deal with special cases of non-linearity [The Challenges of Non-Linear Parameters and Variables in Automatic Loop Parallelization].
2005: Code generation for the Grid based on a master-worker scheme [LooPo-HOC: A Grid Component with Embedded Loop Parallelization].
2008: Code generation for multicores and GPUs [Precise Management of Scratchpad Memories for Localising Array Accesses in Scientific Codes] (on-going).
2010: Connection of polyhedral methods to the compiler infrastructure LLVM [Polly - Polyhedral Optimization in LLVM]

The LooPo team has been led by Martin Griebl for many years. Since 2010, the project is being managed by Armin Größlinger. Several dozen students were involved in the implementation of different modules. The LooPo team can be contacted by e-mail at loopo@infosun.fim.uni-passau.de.

Funding

The project has been funded by:

the German Research Foundation (Deutsche Forschungsgemeinschaft - DFG):
- RecuR (start 1994, 4 years, Le 912/1)
- LooPo/HPF (start 1999, 4 years, Le 912/3)
- CompSpread (start 2005, 4 years, GR 1762/2)
the German Academic Exchange Service (Deutscher Akademischer Austausch Dienst - DAAD) (5 exchange projects of 2-3 years each),
the EU Network of Excellence CoreGRID (start 2004, 4 years),
the EU Network of Excellence ArtistDesign (start 2008, 4 years),
the Bavarian-French University Centre (Bayerisch-Französisches Hochschulzentrum - BFHZ) (2004 and 2010).

Individual Projects related to LooPo

Polly: an infrastructure for polyhedral optimizations on the intermediate representation of LLVM
LooPo: prototypical source-to-source polyhedral compiler
The distribution contains the complete source code of LooPo, written in C++, with a front-end in Tcl/Tk and a new frontend in Java (in development). LooPo uses only freely available software to enable a wide-spread use. LooPo is known to run on Linux, Solaris and FreeBSD (and probably other *nix operating systems).

LooPo is being provided "as is" and has been put under the GNU General Public License. It contains the CLooG code generator (by Cédric Bastoul) and relies on externally installed PIPlib (required), PolyLib (required), Barvinok (optional) and Omega (optional).
CADGen: a prototype of a code generator (similar to CLooG) using cylindrical algebraic decomposition (CAD) instead of polyhedra

Publications

The following list has been generated automatically from an up-to-date publications database.

2012

Tobias Grosser, Armin Größlinger, and Christian Lengauer. Polly—Performing Polyhedral Optimizations on a Low-Level Intermediate Representation. Parallel Processing Letters, 22(4):Article 1250010, 28 pages, December 2012.

2011

Paul Feautrier and Christian Lengauer. Polyhedron Model. In David Padua et al., editors, Encyclopedia of Parallel Computing, pages 1581–1592. Springer, September 2011.
Tobias Grosser. Enabling Polyhedral Optimizations in LLVM. Master's thesis, University of Passau, April 2011.
Tobias Grosser, Hongbin Zheng, Ragesh Aloor, Andreas Simbürger, Armin Größlinger, and Louis-Noël Pouchet. Polly – Polyhedral Optimization in LLVM. In Christophe Alias and Cédric Bastoul, editors, Proceedings of the First International Workshop on Polyhedral Compilation Techniques (IMPACT). INRIA Grenoble Rhône-Alpes, April 2011. 6 pages.

2010

Soufiane Baghdadi, Armin Größlinger, and Albert Cohen. Putting Automatic Polyhedral Compilation for GPGPU to Work. In Proc. of Compilers for Parallel Computers (CPC), 2010.

2009

Armin Größlinger. Precise Management of Scratchpad Memories for Localising Array Accesses in Scientific Codes. In O. de Moor and M. Schwartzbach, editors, Proceedings of the International Conference on Compiler Construction (CC), volume 5501 of Lecture Notes in Computer Science, pages 236–250. Springer-Verlag, 2009.
Armin Größlinger. The Challenges of Non-linear Parameters and Variables in Automatic Loop Parallelisation. doctoral thesis, Department of Informatics and Mathematics, University of Passau, December 2009.

2008

Michael Claßen, Philipp Claßen, and Christian Lengauer. Extending Loop Parallelization for the Grid to Largely Decentralized Communication. In Sergei Gorlatch, Paraskevi Fragopoulou, and Thierry Priol, editors, Integrated Research in Grid Computing, CoreGRID Integration Workshop, pages 287–298. Crete University Press, 2008.
Michael Claßen, Philipp Claßen, Christian Lengauer, Jan Dünnweber, and Sergei Gorlatch. Adapting Loop Parallelization to the Grid. In Proceedings of the Programming Model Institute Technical Meeting 2008, number TR-0138 in CoreGRID Technical Reports, pages 4–10, 2008.
Johannes Tomasoni, Jan Dünnweber, Sergei Gorlatch, Michael Claßen, Philipp Claßen, and Christian Lengauer. LooPo-HOC: A Grid Component with Embedded Loop Parallelization. In Sergei Gorlatch, Paraskevi Fragopoulou, and Thierry Priol, editors, Integrated Research in Grid Computing, CoreGRID Integration Workshop, pages 241–252. Crete University Press, 2008.
Johannes Tomasoni, Jan Dünnweber, Sergei Gorlatch, Michael Claßen, Philipp Claßen, and Christian Lengauer. LooPo-HOC: A Grid Component with Embedded Loop Parallelization. In Sergei Gorlatch, Paraskevi Fragopoulou, and Thierry Priol, editors, Grid Computing: Achievements and Prospects, pages 261–274. Springer-Verlag, 2008.

2007

Peter Faber. Code Optimization in the Polyhedron Model - Improving the Efficiency of Parallel Loop Nests. doctoral thesis, Department of Informatics and Mathematics, University of Passau, 2007.
Eduardo Argollo, Michael Claßen, Philipp Claßen, and Martin Griebl. Loop Parallelization for a Grid Master-Worker Framework. In CoreGRID Workshop on Grid Programming Model Grid and P2P Systems Architecture, Grid Systems, Tools and Environments, number TR-0080 in CoreGRID Technical Reports, pages 516–527, June 2007.

2006

Michael Claßen and Martin Griebl. Automatic Code Generation for Distributed Memory Architectures in the Polytope Model. In Proceedings of the 11th International Workshop on High-Level Parallel Programming Models and Supportive Environments at the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2006), 2006.
Jan Dünnweber, Sergei Gorlatch, Martin Griebl, Christian Lengauer, and Eduardo Argollo Dias. Making a Task Farm Component Parallelize Loops for the Grid. In Sergei Gorlatch, Marian Bubak, and Thierry Priol, editors, Integrated Resarch in Grid Computing, pages 93–103. Academic Computing Centre CYFRONET AGH, 2006.
Armin Größlinger, Martin Griebl, and Christian Lengauer. Quantifier Elimination in Automatic Loop Parallelization. Journal of Symbolic Computation, 41(11):1206–1221, November 2006.

2005

Martin Griebl, Paul Feautrier, and Armin Größlinger. Forward Communication Only Placements and their Use for Parallel Program Construction. In Languages and Compilers for Parallel Computing, 15th International Workshop, LCPC'02. Revised Papers, Lecture Notes in Computer Science 2481, pages 16–30. Springer-Verlag, 2005. doi:10.1007/11596110_2.
Armin Größlinger, Martin Griebl, and Christian Lengauer. Quantifier Elimination in Automatic Loop Parallelization. In Andreas Dolzmann, Andreas Seidl, and Thomas Sturm, editors, Algorithmic Algebra and Logic (A3L 2005), pages 123–128. Books on Demand GmbH, Norderstedt, April 2005.

2004

Peter Faber, Martin Griebl, and Christian Lengauer. Polyhedral Loop Parallelization: The Fine Grain. In Michael Gerndt and Edmodf Kereku, editors, Proceedings of the 11th Workshop on Compilers for Parallel Computers (CPC 2004), Research Report Series LRR-TUM, pages 25–36. Technische Universität München, 2004.
Martin Griebl, Peter Faber, and Christian Lengauer. Space-Time Mapping and Tiling – a Helpful Combination. Concurrency and Computation: Practice and Experience, 16(2–3):221–246, 2004.
Armin Größlinger, Martin Griebl, and Christian Lengauer. Introducing Non-linear Parameters to the Polyhedron Model. In Michael Gerndt and Edmond Kereku, editors, Proceedings of the 11th Workshop on Compilers for Parallel Computers (CPC 2004), Research Report Series LRR-TUM, pages 1–12. Technische Universität München, 2004.
Martin Griebl. Automatic Parallelization of Loop Programs for Distributed Memory Architectures. habilitation thesis, Department of Mathematics and Informatics, University of Passau, 2004.

2003

Peter Faber, Martin Griebl, and Christian Lengauer. Replicated Placements in the Polyhedron Model. In Harald Kosch, Laszlo Böszörményi, and Hermann Hellwagner, editors, Euro-Par 2003: Parallel Processing, number 2790 in Lecture Notes in Computer Science, pages 303–308. Springer-Verlag, 2003.

2001

Peter Faber, Martin Griebl, and Christian Lengauer. Issues of the Automatic Generation of HPF Loop Programs. In Samuel P. Midkiff et al., editor, Languages and Compilers for Parallel Computing (LCPC 2000), number 2017 in Lecture Notes in Computer Science, pages 359–362. Springer-Verlag, 2001.
Peter Faber, Martin Griebl, and Christian Lengauer. Loop-Carried Code Replacement. In Euro-Par 2001: Parallel Processing, number 2150 in Lecture Notes in Computer Science, pages 230–234. Springer-Verlag, 2001.
Martin Griebl. The Minimal Number of Communication Startups when Tiling Space-Time Mapped Programs. In Ninth International Workshop on Compilers for Parallel Computers (CPC 2001), pages 117–126, 2001.
Martin Griebl. On Tiling Space-Time Mapped Loop Nests. In Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001), pages 322–323. ACM Press, 2001.

2000

Martin Griebl, Paul Feautrier, and Christian Lengauer. Index Set Splitting. International Journal of Parallel Processing, 28(6):607–631, December 2000. Special Issue on the International Conference on Parallel Architectures and Compilation Techniques (PACT'99).

1999

Jean-Fran cois Collard and Martin Griebl. A Precise Fixpoint Reaching Definition Analysis for Arrays. In Larry Carter and Jean Ferrante, editors, Languages and Compilers for Parallel Computing (LCPC'99), volume 1863 of Lecture Notes in Computer Science, pages 286–302. Springer-Verlag, 1999.
Nils Ellmenreich, Christian Lengauer, and Martin Griebl. Application of the Polytope Model to Functional Programs. In Larry Carter and Jeanne Ferrante, editors, Languages and Compilers for Parallel Computing (LCPC'99), number 1863 in Lecture Notes in Computer Science, pages 219–235. Springer-Verlag, 1999.
Martin Griebl, Paul Feautrier, and Christian Lengauer. On Index Set Splitting. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT'99), pages 274–282. IEEE Computer Society Press, 1999.
Max Geigl, Martin Griebl, and Christian Lengauer. Termination Detection in Parallel Loop Nests with while Loops. Parallel Computing, 25(12):1489–1510, 1999.

1998

Nils Ellmenreich, Martin Griebl, and Christian Lengauer. Applicability of the Polytope Model to Functional Programs. In Herbert Kuchen, editor, Proceedings of the 7th International Workshop on Functional and Logic Programming. Institut für Wirtschaftsinformatik, Westf. Wilhelms-Universität Münster, 1998.
Max Geigl, Martin Griebl, and Christian Lengauer. A Scheme for Detecting the Termination of a Parallel Loop Nest. In Proceedings of the GI/ITG FG PARS Workshop, PARS Mitteilungen Nr. 17, pages 166–175. Gesellschaft für Informatik e.V., 1998.
Martin Griebl, Christian Lengauer, and Sabine Wetzel. Code Generation in the Polytope Model. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT'98), pages 106–111. IEEE Computer Society Press, 1998.

1997

Jean-Fran cois Collard and Martin Griebl. Array Dataflow Analysis for Explicitly Parallel Programs. Parallel Processing Letters, 7(2):117–131, 1997.
Martin Griebl and Christian Lengauer. The Loop Parallelizer LooPo – Announcement. In David Sehr, editor, Languages and Compilers for Parallel Computing (LCPC'96), number 1239 in Lecture Notes in Computer Science, pages 603–604. Springer-Verlag, 1997.
Christian Lengauer, Martin Griebl, and editors Sergei Gorlatch. Euro-Par'97: Parallel Processing, volume 1300 of Lecture Notes in Computer Science. Springer-Verlag, 1997.

1996

Albert Cohen, Jean-Fran cois Collard, and Martin Griebl. Data Flow Analysis of Recursive Structures. In Michael Gerndt, editor, Proceedings of the Sixth Workshop on Compilers for Parallel Computers (CPC'96), volume 21 of Konferenzen des Forschungszentrums Jülich, pages 181–192. Forschungszentrum Jülich, 1996.
Jean-Fran cois Collard and Martin Griebl. Array Dataflow Analysis for Explicitly Parallel Programs. In Luc Bougé, Pierre Fraigniaud, Anne Mignotte, and Yves Robert, editors, Euro-Par'96: Parallel Processing. Vol. I, volume 1123 of Lecture Notes in Computer Science, pages 406–413. Springer-Verlag, 1996.
Martin Griebl and Christian Lengauer. The Loop Parallelizer LooPo. In Michael Gerndt, editor, Proceedings of the 6th Workshop on Compilers for Parallel Computers (CPC'96), number 21 in Konferenzen des Forschungszentrums Jülich, pages 311–320. Forschungszentrum Jülich, 1996.
Martin Griebl and Christian Lengauer. Classifying Loops for Space-Time Mapping. In Luc Bougé, Pierre Fraigniaud, Anne Mignotte, and Yves Robert, editors, Euro-Par'96: Parallel Processing, Volume I, number 1123 in Lecture Notes in Computer Science, pages 467–474. Springer-Verlag, 1996. Invited.
Martin Griebl. The Mechanical Parallelization of Loop Nests Containing WHILE Loops. doctoral thesis, Department of Mathematics and Informatics, University of Passau, 1996.

1995

Martin Griebl and Jean-Fran cois Collard. Generation of Synchronous Code for Automatic Parallelization of tt while Loops. In Seif Haridi, Khayri Ali, and Peter Magnusson, editors, EURO-PAR'95, volume 966 of Lecture Notes in Computer Science, pages 315–326. Springer-Verlag, 1995.
Martin Griebl and Christian Lengauer. A Communication Scheme for the Distributed Execution of Loop Nests with sf while Loops. International Journal of Parallel Processing, 23(5):471–495, 1995.
Christian Lengauer and Martin Griebl. On the Parallelization of Loop Nests Containing sf while Loops. In Nikolay N. Mirenkov, Qian-Ping Gu, Shietung Peng, and Stanislav Sedukhin, editors, Proceedings of the 1st Aizu International Symposium on Parallel Algorithm/Architecture Synthesis (pAs'95), pages 10–18. IEEE Computer Society Press, 1995.

1994

Martin Griebl and Christian Lengauer. On Scanning Space-Time Mapped while Loops. In Bruno Buchberger and Jens Volkert, editors, CONPAR 94 – VAPP VI, Lecture Notes in Computer Science 854, pages 677–688. Springer-Verlag, 1994.
Martin Griebl and Christian Lengauer. On the Space-Time Mapping of WHILE-Loops. Parallel Processing Letters, 4(3):221–232, 1994.

1993

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.

Contact

Christian Lengauer (University of Passau)
Armin Größlinger (University of Passau)
Andreas Simbürger (University of Passau)