Mapping onto mesh connected multiprocessors /
typically consist of several computationally intensive modules that are designed to execute in parallel while communicating amongst themselves. When such a program is to be executed on a parallel computer, it would be desirable to place pairs of modules that communicate with each other on processor...
| Main Author: | |
|---|---|
| Format: | Thesis eBook |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
1993.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy |
| Summary: | typically consist of several computationally intensive modules that are designed to execute in parallel while communicating amongst themselves. When such a program is to be executed on a parallel computer, it would be desirable to place pairs of modules that communicate with each other on processors such that the messages between them would have to traverse as few communication links as possible before reaching the destination processor. In addition, since one of the objectives of a parallel program is to exploit the concurrency involved in the problem, the modules would have to be distributed among the processors in such a way that the processor utilization is high. The task allocation problem or the mapping problem is one of assigning the tasks of a parallel program among the processors of a distributed memory multiprocessor (DMM) in a manner that minimizes the interprocessor communication costs while simultaneously maintaining computational load balance among the processors. The mapping problem can be shown to be equivalent to the problem of graph z'somorphism which is known to be NP-complete. Hence, satisfactory suboptimal solutions obtainable in a reasonable amount of time are generally sought. In this research., we explore heuristic solutions to the problem of task allocation in the context of a mesh connected parallel computer. We propose a mapping algorithm that is based on the Kernighan-Lin heuristic of vertex movement to reduce the cost of graph partition coupled with repeated partitioning of the task graph in order to determine the processor assignment of a task incrementally. Since the mesh architecture lends itself well to a recursive definition, a recursive divide-and-conquer strategy, is used to map the partitioned task graph onto the mesh. We shall also show that such a recursive approach, however, has shortcomings that can be addressed effectively using a nonrecursive approach to the partitioning and mapping. In addition, we shall demonstrate the partitioning process with a initial configuration obtainedadvantages of starting the using a greedy clustering technique, instead of a random initial configuration. In mapping the task graph onto a mesh architecture, the suitability of a four-partition approach over bipartitioning is explored. A number of test task graphs arising in molecular dynamics applications are used to evaluate the effectiveness of the proposed mapping heuristic. The mappings obtained by the proposed heuristic are compared with those obtained by the well known probabilistic optimization technique of simulated annealing. |
|---|---|
| Item Description: | "Major subject: Computer Science". Vita. |
| Physical Description: | xi, 64 leaves : illustrations ; 28 cm. Also available online. |
| Bibliography: | Includes bibliographical references. |