Narrow Results

The combinatorial optimization problem of assigning parallel tasks onto a multiprocessor so as to minimize the execution time is termed as the mapping problem. This problem even in its simplest form is known to be NP-hard. Several heuristic solutions that have been proposed seek to obtain a 'good' sub-optimal mapping in a reasonable time. In this paper we present two randomized heuristics for the mapping problem one of which is based on Plaisted's randomized graph separator heuristic while the other is based on the principles of genetic algorithms. We empirically compare the performance of our algorithms with two other such existing randomized mapping algorithms. One of them is the recursive min-cut partitioning heuristic due to Sadayappan et al., while the other is a simple genetic algorithm for mapping of our earlier work.

This comparison of relative performance of the four randomized algorithms indicates that the genetic class of algorithms always produces better mappings than algorithms of the clustering class. In addition it is found that the recursive separator mapping algorithm performs as good as the recursive clustering algorithm while our new variant of genetic algorithm performs no better than our simple genetic algorithm.

In this paper, a heuristic mapping approach which maps parallel programs, described by precedence graphs, to MIMD architectures, described by system graphs, is presented. The complete execution time of a parallel program is used as a measure, and the concept of critical edges is utilized as the heuristic to guide the search for a better initial assignment and subsequent refinement. An important feature is the use of a termination condition of the refinement process. This is based on deriving a lower bound on the total execution time of the mapped program. When this has been reached, no further refinement steps are necessary. The algorithms have been implemented and applied to the mapping of random problem graphs to various system topologies, including hypercubes, meshes, and random graphs. The results show reductions in execution times of the mapped programs of up to 77 percent over random mapping.

The mapping problem arises when a concurrent program is executed on a parallel architecture. The goal is to devise an allocation of processes onto physical processing nodes which optimizes a global measure of system performance. In this work we analyze the complexity and the approximability of both the mapping problem in its general formulation and some of its subproblems that are interesting for massively parallel systems.

Unfortunately, it turns out that all the problems introduced are NP-Hard. Moreover, they can be solved only with approximate algorithms for which the distance between the exact and the approximate solution is not bounded.