Iteration space slicing and its application to communication optimization
William White Tison Pugh, Evan Rosser · 1997
Program slicing is an analysis that answers questions such as "Which statements might affect the computation of variable v at statement s?" or "Which statements depend on the value of v computed in statement s?". The answers computed by program slicing are generally a set of statements. We introduce the idea of iteration spacing slicing: we refine program slicing to ask questions such as "Which iterations of which statements might effect the computation in iterations I of statement s?" or "Which iterations of which statements depend on the value computed by iterations I of statement s?". One application of this general-purpose technique is optimization of interprocessor communication in data-parallel compilers. For example, we can separate a code fragment into 1) those iterations that must be done before a send, 2) those iterations that don't need to be done before a send and don't depend on non-local data and 3), those iterations that depend on non-local data. We examine application...