CS 380C: Lecture schedule

Lecture Schedule

August

30	Course overview: slides

September

4	Program representations for analysis and transformation: slides
6	Optimization and dataflow analysis slides
11	Constant propagation: see Sept 6th slides
13	Formalisms for dataflow analysis: monotonicity etc. slides
18	Classification of dataflow problems: see Sept 6 slides
20	Strength reduction: slides
25	Partial redundancy elimination Dreschler and Stadel, SIGPLAN Notices, May 1993 Implementation Notes by Rolaz, March 2003
27	Partial redundancy elimination (contd.)

October

2	Exploiting structure in dataflow analysis: see Sept 6th slides
4	Dominance,postdominance,control-dependence,data-dependence: slides Optimal Control Dependence Computation, Pingali and Bilardi, TOPLAS 1997
9	SSA form and optimizations using SSA form slides Efficient SSA Computation, Cytron et al TOPLAS 1994 Algorithms for SSA computation, Bilardi and Pingali, JACM 2003 Constant Propagation with Conditional Branches, Wegman and Zadeck, POPL 1984
11	Register allocation slides Register allocation and spilling via graph coloring, Chaitin, PLDI 1982
16	Instruction scheduling slides
18	Software pipelining slides Iterative Modulo Scheduling, Bob Rau, 1995 Fine-grain scheduling under resource constraints, Feautrier, LCPC 1994
23	Optimizing array programs: cache models and loop transformations Introduction Cache performance modeling
25	Array dependence analysis and integer linear programming: slides
30	Solving Diophatine equalities and inequalities: slides The Omega Test: Bill Pugh, CACM August 1992

November

1

Array dependence abstractions:slides

6

Synthesizing loop transformations for parallelism and locality enhancement: slides
A Data Locality Optimizing Algorithm, Wolf and Lam, PLDI 1991
Access Normalization: Loop Restructuring for NUMA Computers, Li and Pingali, ACM TOCS 1993

8

Fractal symbolic analysis: slides
Fractal Symbolic Analysis, Menon and Pingali, TOPLAS 2003

13

Optimistic parallelization of irregular programs: slides
Optimistic Parallelism Requires Abstractions, Kulkarni et al, PLDI 2007

15

Points-to analysis: slides
Points-to analysis in almost linear time, Steensgard, PLDI 1995
Fast and accurate flow-insensitive points-to analysis, Shapiro and Horowitz, POPL 97
The Ant and the Grasshopper, Hardekopf and Lin, PLDI 2007

20

Shape analysis
Parametric shape analysis via 3-values logic, Sagiv, Reps, Wilhelm, POPL 1999

22

Thanksgiving

27

Shape analysis (contd.)

29

Optimizing irregular programs using points-to and shape analysis
Detecting parallelism in C programs with recursive data structures, Ghiya et al, CC'98

December

4	Self-optimizing programs and empirical search slides Is search really necessary to generate high-performance BLAS? Yotov et al, Proceedings of IEEE, Feb 2005. FFTW website
6	Research directions