NOTE: This item is not available outside the Texas A&M University network. Texas A&M affiliated users who are off campus can access the item through NetID and password authentication or by using TAMU VPN. Non-affiliated individuals should request a copy through their local library's interlibrary loan service.
Mapping onto mesh connected multiprocessors
Abstract
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.
Description
Due to the character of the original source materials and the nature of batch digitization, quality control issues may be present in this document. Please report any quality issues you encounter to digital@library.tamu.edu, referencing the URI of the item.Includes bibliographical references.
Collections
Citation
Hangal, Prashant L (1993). Mapping onto mesh connected multiprocessors. Master's thesis, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /ETD -TAMU -1993 -THESIS -H239.
Request Open Access
This item and its contents are restricted. If this is your thesis or dissertation, you can make it open-access. This will allow all visitors to view the contents of the thesis.