Scheduling and Automatic Parallelization

Part 1 Unidimensional problems: scheduling DAGs without communications - introduction, where do task graphs come from? scheduling DAGs, solving Pb(oo), solving Pb(oo), conclusion, bibliographical notes, exercises; scheduling DAGs with communications - introduction, a model with communication costs, NP-completeness of Pb(oo), a guaranteed heuristic for Pb(oo), list heuristic for Pb(p), two-step clustering heuristics, linear clustering, conclusion, bibliographical notes, exercises; cycling scheduling - introduction, problem formulation, solving BCS(oo), solving BCS(p), bibliographical notes, exercises. Part 2 Multidimensional problems: systems of uniform recurrence equations - introduction, computability of a SURE, and linear scheduling, SURE and multidimensional scheduling, bibliographical notes exercises; parallelism detection in nested loops - introduction, dependence analysis and abstraction, Allen and Kennedy's algorithm, unimodular transformation, Darte and Vivien's algorithm, Feautrier's algorithm, optimality, bibliographical notes, exercises. Bibliography.