Compiler Design Lab

Automatic Parallelization in the Polyhedral Model Seminar

People

Organization

Language English
Participants 10
Preparatory Meeting Friday, October 26, 14:15 pm, Rm. 401 in E 1.3
Weekly Meeting Tuesday, 12:15 pm, Rm. 401 in E 1.3, starting Dec 11
Availability Registration is closed. All participants should remember to register in the LSF to get a certificate for the seminar.

Modus Operandi

Each paper will be assigned to one participant. We will have weekly meetings during the semester in which we will discuss one of the papers. The discussion will be managed by the student to whom the paper was assigned. She/He is responsible for giving a short summary on the paper and for structuring the following discussion.

Every week each student has to write a summary (max. 450 words) on the week's paper. This summary should include open questions and is to be submitted to Kevin (streit@cs.uni-saarland.de) two days before the corresponding meeting (11:59 pm). The summaries of all participants will be made available and can be used by the moderator to structure the discussion in the following meeting.

At the end of the semester each participant will give a presentation about her/his paper.

Each participant is allowed to drop two summaries without any particular reason. In case you drop a summary, please send a short mail telling so.

Dates

The preparatory meeting for this seminar took place on Friday, October 26, 14:15 pm, Rm. 401 in E 1.3.

Sessions

Date Moderator Notes Talk Summaries
Friday, Nov 23 Hack/Hammacher/Streit Introductory discussion: "Dependence: Theory and Practice". Please read [I1] as introduction to the topic.
Also, please make yourself familiar with the following set of standard loop optimizations:
  • Loop distribution
  • Loop fusion
  • Loop interchange
  • Loop skewing
  • Loop splitting and peeling
  • Loop unrolling
  • Loop tiling and blocking
  • Loop vectorization

Using Wikipedia or the like is enough to get an idea of these loop transformations. 		none Download
tba Hack/Hammacher/Streit Introductory discussion: "Polyhedral Program Optimization". Please read [I2] as introduction to the topic. none Download
Tuesday, Dec 11 David Pfaff Paper: [C1] "The Omega Test: a fast and practical integer programming algorithm for dependence analysis" Tuesday, March 12 Download
Tuesday, Dec 18 Johannes Doerfert Paper: [O1] "Index Set Splitting" Tuesday, March 12 Download
Tuesday, Jan 8 Vikrant Saxena Paper: [P2] "Some efficient solutions to the affine scheduling problem. I. One-dimensional time"
Please skip sections 2 and 3.3.4 for the final talk. 		Tuesday, March 12 Download
Tuesday, Jan 15 Tobias Frey Paper: [P3] "Some efficient solutions to the affine scheduling problem. II. Multidimensional time"
We will discuss the first 4 sections of this paper only. 		Wednesday, March 13 Download
Tuesday, Jan 29 Hack/Hammacher/Streit Paper: [O3] "Code Generation in the Polyhedral Model Is Easier Than You Think" (Please read [O2] as background) n/a Download
Tuesday, Feb 5 Steven Schäfer Paper: [L1] "A Practical Automatic Polyhedral Parallelizer and Locality Optimizer". You should read parts of [L1.1] for important background information. Wednesday, March 13 Download
Tuesday, Feb 12 All Paper: [M1] "Multi-dimensional rankings, program termination, and complexity bounds of flowchart programs". n/a n/a

Talks

The final talks and discussion will be held on March 12th and March 13th from 13:00 to approximately 16:00. Each talk should be planned to take 25 minutes plus discussion.

Papers

[I] Introductory Material

We will prepare three lectures on the foundations for the first meetings. These will be roughly based on the following works:

  1. Allen, R. & Kennedy, K. 2001. Optimizing Compilers for Modern Architectures, Chapter 2: Dependence, Theory & Practice. Morgan Kaufmann Publishers Inc. (2001)
  2. Pouchet, L. N. 2010. PhD Thesis, Chapter 2: Polyhedral Program Optimization. University of Paris-Sud 11. (2010)
    1. Bastoul, C. 2004. PhD Thesis, Chapter 2: Program Model. (2004)
    2. Bastoul, C. 2004. PhD Thesis, Chapter 3: Program Transformations. (2004)

[C] Classical Parallelization and Dependence Testing

  1. Pugh, W. 1991. The Omega Test: a fast and practical integer programming algorithm for dependence analysis. ACM/IEEE Conference on Supercomputing (1991).
    1. Different view on the problem: Pugh, W. 1992. A Practical Algorithm for Exact Array Dependence Analysis. Communications of the ACM. 35, 8 (1992).
  2. Darte et al. 2001. Loop Parallelization Algorithms. Compiler Optimizations for Scalable Parallel Systems. LNCS 1808/2001 (2001).

[P] Polyhedral Seminal Papers

  1. Feautrier, P. 1991. Dataflow Analysis of Array and Scalar References. International Journal of Parallel Programming. 20, 1 (1991).
  2. Feautrier, P. 1992. Some efficient solutions to the affine scheduling problem. I. One-dimensional time. International Journal of Parallel Programming. 21, 5 (1992).
  3. Feautrier, P. 1992. Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time. International Journal of Parallel Programming. 21, 6 (1992).

[O] Optimization and Code Generation

  1. Griebl M. et al. Index Set Splitting. International Journal of Parallel Programming. 28, 6 (2000).
  2. Quilleré, F. et al. 2000. Generation of Efficient Nested Loops from Polyhedra. International Journal of Parallel Programming. 28, 5 (2000).
  3. Bastoul, C. 2004. Code Generation in the Polyhedral Model Is Easier Than You Think. PACT (2004).
    1. Related: Vasilache, N. et al. 2006. Polyhedral Code Generation in the Real World. CC (2006).

[L] Locality and Communication

  1. Bondhugula, U. et al. 2008. A Practical Automatic Polyhedral Parallelizer and Locality Optimizer. PLDI (2008).
    1. Bondhugula, U. 2008. Effective Automatic Parallelization and Locality Optimization using the Polyhedral Model
  2. Bondhugula, U. 2011. Automatic Distributed-Memory Parallelization and Code Generation using the Polyhedral Framework. Unpublished.

[M] Misc

  1. Vasilache, N. et al. 2012. Joint Scheduling and Layout Optimization to Enable Multi-Level Vectorization. IMPACT (2012).
  1. Alias, C. et al. 2010. Multi-dimensional rankings, program termination, and complexity bounds of flowchart programs. SAS (2010).