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 journalArticle

12 Scopus citations

Abstract

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
Volume19
Issue number6
DOIs
StatePublished - Jan 1 1993

Keywords

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

ASJC Scopus subject areas

  • Computer Science Applications
  • Hardware and Architecture
  • Control and Systems Engineering

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