Dynamic Remapping of Parallel Computations with Varying Resource Demands

A large class of computational problems are characterized by frequent synchronization, and computational requirements which change as a function of time. When such a problem is solved on a message passing multiprocessor machine, the combination of these characteristics leads to system performance which deteriorates in time. Performance can be improved with periodic redistribution of computational load; however, redistribution can exact a sometimes large delay cost. We study the issue of deciding when to invoke a global load remapping mechanism. Such a decision policy must effectively weigh the costs of remapping against the performance benefits, and should be general enough to apply automatically to a wide range of computations. We propose here a general remapping decision heuristic, then study its effectiveness and its anticipated behavior on two very different models of load evolution. Assuming only that the remapping cost is known, this policy dynamically attempts to minimize system degradation (including the cost of remapping) per computation step. This policy is quite simple, choosing to remap when the first local minimum in the degradation function is detected. Simulations show that our policy provides significantly better performance than that achieved by never remapping. We also observe that the average interremapping frequency is quite close to the optimal fixed remapping frequency. This phenomenon is explained, in part, analytically. We show that when performance deteriorates monotonically (in expectation), then the heuristic is well motivated. Finally, using a tractable model of load evolution, we compare our policy’s performance to provably optimal performance.