rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Mapping onto mesh connected multiprocessors
  name:
    name part: Hangal, Prashant L.
    role:
      role term: creator
  type of resource: text
  genre: bibliography
  origin info:
    place:
      place term: xx
    date issued: 1993
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: print
    form: remote
    extent: xi, 64 leaves : illustrations ; 28 cm.
  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 pa…
  note: by Prashant L. Hangal.
  note: "Major subject: Computer Science".
  note: Vita.
  note: Also available online.
  note: M.S. Texas A&M University 1993.
  note: Includes bibliographical references.
  subject:
    topic: Major computer science
  identifier: https://hdl.handle.net/1969.1/ETD-TAMU-1993-THESIS-H239
  related item:
    location:
      url: https://hdl.handle.net/1969.1/ETD-TAMU-1993-THESIS-H239
  record info:
    record content source: TXA
    record creation date: 960419
    record change date: 20220103114433.0
    record identifier: in00001289976