Optimal Periodic Remapping of Bulk Synchronous Computations on Multiprogrammed Distributed Systems

For bulk synchronous computations that have nondeterministic behaviors, dynamic remapping is an effective approach to ensure parallel efficiency. There are two basic issues in remapping: when and how to remap. This paper presents a formal treatment of the first issue for dynamic computations with a priori known statistical behaviors. We have formulated the problem as two complement sequential stochastic optimization, with an objective of finding optimal remapping frequencies for a given tolerance of load imbalance on multiprogrammed distributed systems. We have developed analytical approaches to precisely characterize the transient statistical behaviors of the workload process and derived optimal remapping frequencies for various random workload change processes. 1 Introduction A bulk synchronous computation proceeds in phases. During each phase, its processes perform calculations independently and then communicate new results with their datadependent peers. Due to the need of synchr..