Algorithms For Static Task Assignment And Symmetric Contraction In Distributed Computing Systems
| dc.contributor.author | Lo, Virginia M. | |
| dc.date.accessioned | 2023-06-20T20:01:49Z | |
| dc.date.available | 2023-06-20T20:01:49Z | |
| dc.date.issued | 1988-05-05 | |
| dc.description | 14 pages | en_US |
| dc.description.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. | en_US |
| dc.identifier.uri | https://hdl.handle.net/1794/28432 | |
| dc.language.iso | en | en_US |
| dc.publisher | University of Oregon | en_US |
| dc.rights | Creative Commons BY-NC-ND 4.0-US | en_US |
| dc.subject | symmetric contraction | en_US |
| dc.subject | Graph Partitioning Problem | en_US |
| dc.subject | heuristic algorithm | en_US |
| dc.title | Algorithms For Static Task Assignment And Symmetric Contraction In Distributed Computing Systems | en_US |
| dc.type | Article | en_US |