An efficient heuristic scheme for dynamic remapping of parallel computations

Alok N. Choudhary, Bhagirath Narahari*, Ramesh Krishnamurti

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


In applications where a sequence of different tasks is to be performed, the computational load of a task varies dynamically and can become severely imbalanced between successive tasks. These dynamic changes in the load suggest that a remapping of the load must be performed before the next task in the sequence is executed. A remapping scheme must: (1) estimate load measures for each task and dynamically compute load distribution, then (2) compute a remapping and (3) remap the load according to the mapping generation in (2). This paper presents an experimental analysis of a heuristic remapping scheme applied to a motion estimation system in computer vision, and implemented on an Intel iPSC/2 machine. We discuss a fast heuristic mapping algorithm to compute the remapping that compares favorably with the slower optimal algorithm. Our experiments show that the heuristic remapping scheme results in significant performance gains, of over 3 times improvement in speedup, while incurring low overheads.

Original languageEnglish (US)
Pages (from-to)621-632
Number of pages12
JournalParallel Computing
Issue number6
StatePublished - Jun 1993


  • Intel iPSC
  • Mapping algorithm
  • computation load
  • distributed memory system
  • dynamic remapping scheme
  • experimental results

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'An efficient heuristic scheme for dynamic remapping of parallel computations'. Together they form a unique fingerprint.

Cite this