Performance Comparison of Strategies for Static Mapping of Parallel Prgorams

摘要

We address the problem of efficient strategies for mapping arbitray parallel programs onto distributed memory message-passing parallel computers. An efficient task assignment stragey based on two phases (task clustering and task reasigment) is prosed. This strategy is suitable for applications which could be partitioned into parallel executable tasks and its design is a trade-off between solution quality and computational complexity. It is evaluated by comparison with some representative heuristics from the literature that cover the range of different complexity categories: two simple greedy algorithms (Largest Processing Time Frist and Largest Global Cost First) with low complexity, two iterative heuristics (Simulated Annealing and Tabu Search) with the highest complexity and a mixed heuristic (Even Distribution and Task Reassignment) with an intermediate complexity between the other two. It is shown to be very effective for comptuations whose communciation topology matches some well-known regular graph families such as trees, rings and meshes, as well as for arbitrary computations with irregular communications patterns. Its solution quality is better than that produced by the other mixed heuristic and as good as (and sometimes better than) that produced by Simulated Annealing.