Optimal remapping in dynamic bulk synchronous computations via a stochastic control approach

Gang Yin, Chengzhong Xu, Le Yi Wang

Abstract

A bulk synchronous computation proceeds in phases that are separated by barrier synchronization. For dynamic bulk synchronous computations that exhibit varying phase-wise computational requirements, remapping at run-time is an effective approach to ensure parallel efficiency. This paper introduces a novel remapping strategy for computations whose workload changes can be modeled as a Markov chain. It is shown that optimal remapping cart be formulated as a binary decision process: remap or not at a given synchronizing instant. The optimal strategy is then developed for long lasted computations by employing optimal stopping rules in a stochastic control framework. The existence of optimal controls is established. Necessary and sufficient conditions for the optimality are obtained. Furthermore, a policy iteration algorithm is devised to reduce computational complexity and enhance fast convergence to the desired optimal control.
BibTeX
@article{yin2003optimal,
  author = {Gang Yin and Chengzhong Xu and Le Yi Wang},
  title = {{Optimal remapping in dynamic bulk synchronous computations via a stochastic control approach}},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  year = {2003},
  doi = {10.1109/tpds.2003.1167370},
}

Loading related content...

Figure