Optimal Dynamic Remapping of Data Parallel Computations

David M. Nicol, Paul F. Reynolds

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)206-219
Number of pages14
JournalIEEE Transactions on Computers
Issue number2
StatePublished - Feb 1990
Externally publishedYes


  • Data parallel computations
  • Markov decision process
  • dynamic remapping
  • load balancing
  • parallel processing
  • performance analysis

ASJC Scopus subject areas

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


Dive into the research topics of 'Optimal Dynamic Remapping of Data Parallel Computations'. Together they form a unique fingerprint.

Cite this