[Pl-seminar] 9/11: Justin Slepak, "Polyhedral Scheduling"

[Vincent St-Amour]

NEU Programming Languages Seminar presents

Justin Slepak
NEU PRL

Wednesday, 9/11
11:45-1:30
Room 366 WVH (http://www.ccs.neu.edu/home/wand/directions.html)

Polyhedral Scheduling

The polyhedral model is an IR for describing loop nests in first-order
programs. Each loop nest is represented as a polyhedron whose points
correspond to vectors of loop indices. Source-level transformations of
the loop nest, such as loop interchange and tiling, can be described as
geometric operations on the polyhedron. The polyhedral IR remains small
even when composing a long series of transformations which would produce
a large target program.

I will begin with a review of related linear algebra material and then
show typical source-level loop transformations in geometric form. I will
then give a procedure for generating code to traverse the polyhedra,
producing the transformed loop nest. Finally, I will show modifications
to this procedure to address the possibility of emitting an unacceptably
large program and to take advantage of a parallel target machine.