# Iteration Space Slicing and Its Application to Communication Optimization

 dc.contributor.author Pugh, William en_US dc.contributor.author Rosser, Evan en_US dc.date.accessioned 2004-05-31T22:43:27Z dc.date.available 2004-05-31T22:43:27Z dc.date.created 1997-04 en_US dc.date.issued 1998-10-15 en_US dc.identifier.uri http://hdl.handle.net/1903/869 dc.description.abstract 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 {\em 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 applications of iteration space slicing to communication optimizations in parallel executions of programs such as stencil computations and block-cyclic Gaussian elimination with partial pivoting. (Also cross-referenced as UMIACS-TR-97-02) en_US dc.format.extent 446650 bytes dc.format.mimetype application/postscript dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-3737 en_US dc.relation.ispartofseries UMIACS; UMIACS-TR-97-02 en_US dc.title Iteration Space Slicing and Its Application to Communication Optimization en_US dc.type Technical Report en_US dc.relation.isAvailableAt Digital Repository at the University of Maryland en_US dc.relation.isAvailableAt University of Maryland (College Park, Md.) en_US dc.relation.isAvailableAt Tech Reports in Computer Science and Engineering en_US dc.relation.isAvailableAt UMIACS Technical Reports en_US
﻿