Back To Schedule
Thursday, October 29 • 4:00pm - 5:00pm
Polly - Optimistic Loop Nest Optimizations with Schedule Trees

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

Polly is an advanced LLVM loop nest optimizer that provides precise memory access analyses and implements on top of them advanced loop optimizations based on a memory-access focused program model.

In the first part of this tutorial we introduce the audience to  integer set based schedule trees as a way to model loop programs. We explain how we statically model program behavior on the granularity of individual dynamic computations and discuss different program analyses (memory accesses, data-dependences, computational complexity).

We then learn how to perform complex loop transformations using simple per-node operations on an abstract program schedule tree. Such transformations include most classical loop transformations, but also full/partial tile separation, outer-loop vectorization and other more complex transformations. At the end of the first part of this tutorial, the audience understands the general concepts used in Polly.

The second part of this tutorial is focused on Polly's new optimistic optimization infrastructure that enables non-statically provable transformations to be performed optimistically. Discussing optimization blocking issues such as exception handling code, infinite loops, integer wrapping or out-of-bound memory accesses we introduce the concept of optimistic assumptions. We then discuss how such assumptions can be described in general, how Polly can collect assumptions, how redundant assumptions are eliminated and how a (close to) minimal run-time check to verifying them are generated. At the end of the second part of this tutorial the audience will be able to create optimistic loop optimizations even for cases that lack sufficient static information.

avatar for Johannes Doerfert

Johannes Doerfert

Researcher/PhD Student, Saarland University

Tobias Grosser

ETH Zurich

Thursday October 29, 2015 4:00pm - 5:00pm PDT
Salon I & Salon II

Attendees (0)