Optimal Dynamic Remapping of Data Parallel Computations

A large class of data parallel computations are characterized by a sequence of phases, with phase changes occurring unpredictably. Dynamic remapping of the workload to processors may be required to maintain good performance. The problem considered here arises when the utility of remapping and the future behavior of the workload is uncertain, phases exhibit stable execution requirements during a given phase, but requirements may change radically between phases. For these situations, a workload assignment generated for one phase may hinder performance during the next phase. This problem is treated formally for a probabilistic model of computation with at most two phases. We address the fundamental problem of balancing the expected remapping performance gain against the delay cost, and derive the optimal remapping decision policy. The promise of the approach is shown by application to multiprocessor implementations of an adaptive gridding fluid dynamics program, and to a battlefield simulation program.