Algorithms For Static Task Assignment And Symmetric Contraction In Distributed Computing Systems

Loading...
Thumbnail Image

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

Citation