# Automatic Parallelization in the Polyhedral Model Seminar

## 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

## 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:

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

### [C] Classical Parallelization and Dependence Testing

- Pugh, W. 1991. The Omega Test: a fast and practical integer programming algorithm for dependence analysis. ACM/IEEE Conference on Supercomputing (1991).
- Different view on the problem: Pugh, W. 1992. A Practical Algorithm for Exact Array Dependence Analysis. Communications of the ACM. 35, 8 (1992).

- Darte et al. 2001. Loop Parallelization Algorithms. Compiler Optimizations for Scalable Parallel Systems. LNCS 1808/2001 (2001).

### [P] Polyhedral Seminal Papers

- Feautrier, P. 1991. Dataflow Analysis of Array and Scalar References. International Journal of Parallel Programming. 20, 1 (1991).
- Feautrier, P. 1992. Some efficient solutions to the affine scheduling problem. I. One-dimensional time. International Journal of Parallel Programming. 21, 5 (1992).
- 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

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

### [L] Locality and Communication

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

### [M] Misc

- Vasilache, N. et al. 2012. Joint Scheduling and Layout Optimization to Enable Multi-Level Vectorization. IMPACT (2012).

- Alias, C. et al. 2010. Multi-dimensional rankings, program termination, and complexity bounds of flowchart programs. SAS (2010).