Identifying reordering transformations that minimize idle processor time
Wayne Kelly, William White Tison Pugh · University Libraries (University of Maryland) · 1995
this paper are important. A great deal of research has been done on deriving good layouts of data and/or computation [5, 1, 4]. In other systems such as Fortran-D and HPF [7, 6], the data decompositions are specified by the user and computation is decomposed according to an owner computes rule. In this paper, we assume that we have been given a data and computation decomposition, and an ordering of the iterations of the program. We use this information to predict whether or not processors will idle waiting for synchronization from other processors. For each statement, we specify an affine mapping (referred to as a space mapping) from that statement's iteration space to a virtual processor space. This virtual processor space is then mapped to the physical processor space in either a blocked, cyclic or blockedcyclic fashion. In this paper, we will only consider the case of one dimensional virtual and physical processor spaces. Figure 1 contains an example of a space mapping. We specify an iteration re-ordering by specifying for each statement, a one-to-one mapping (referred to as a