Dynamic Remapping of Parallel Computations with Varying Resource Demands

David M. Nicol, Joel H. Saltz

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1073-1087
Number of pages15
JournalIEEE Transactions on Computers
Volume37
Issue number9
DOIs
StatePublished - Sep 1988
Externally publishedYes

Keywords

  • Adaptive computation
  • dynamic load balancing
  • multiprocessors
  • optimal partitioning
  • parallel computation
  • remapping

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Dynamic Remapping of Parallel Computations with Varying Resource Demands'. Together they form a unique fingerprint.

Cite this