Optimal dynamic remappping of data parallel computations

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 fu...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1990-02, Vol.39:2
Main Authors: Nicol, D.M., Reynolds, P.F.
Format: Article
Language:English
Subjects:
990200 - Mathematics & Computers
ARRAY PROCESSORS
COMPUTERIZED SIMULATION
DECISION MAKING
DYNAMICS
FLUID MECHANICS
GENERAL AND MISCELLANEOUS//MATHEMATICS, COMPUTING, AND INFORMATION SCIENCE
MARKOV PROCESS
MECHANICS
OPTIMIZATION
PARALLEL PROCESSING
PERFORMANCE TESTING
PROBABILISTIC ESTIMATION
PROGRAMMING
SIMULATION
STOCHASTIC PROCESSES
TESTING
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. The authors 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.
ISSN:0018-9340
1557-9956
DOI:10.1109/12.45206