Algorithms For Static Task Assignment And Symmetric Contraction In Distributed Computing Systems
Loading...
Date
1988-05-05
Authors
Lo, Virginia M.
Journal Title
Journal ISSN
Volume Title
Publisher
University of Oregon
Abstract
In this paper, we look at the mapping problem, which was posed within the domain of parallel
processing, and we redefine that problem for use in distributed computing systems whose underlying
communication medium is a broadcast medium such as ethernet. We describe an efficient algorithm
which can be utilized to find optimal assignments of tasks to processors for a wide variety of
distributed algorithms when symmetric contraction of the algorithm is necessary. 'Ne also describe
a heuristic algorithm for use in finding suboptimal assignments of tasks to processors for arbitrary
distributed computations. Both algorithms model the mapping problem as the Graph Partitioning
Problem. Our algorithms utilize an efficient algorithm for finding maximum weight matchings to
find an assignment of tasks to processors which minimizes the total interprocessor communication
cost while meeting a constraint on the number of tasks assigned to each processor.
Description
14 pages
Keywords
symmetric contraction, Graph Partitioning Problem, heuristic algorithm