Virginia Tech
    • Log in
    View Item 
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Masters Theses
    • View Item
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Masters Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Processor and link assignment using simulated annealing

    Thumbnail
    View/Open
    LD5655.V855_1988.B644.pdf (3.804Mb)
    Downloads: 177
    Date
    1988-05-17
    Author
    Bollinger, S. Wayne
    Metadata
    Show full item record
    Abstract
    Advances in VLSI technology have made possible a new generation of multicomputer systems that contain hundreds or thousands of processors and offer a combined processing power far beyond that possible in a single processor machine. Multicomputers can be used to solve a variety of computationally intensive applications, but they introduce the problem of handling communication between concurrent processes. In the design of multicomputer systems, the scheduling and mapping of a parallel algorithm onto a host architecture has a critical impact on overall system performance. The problem of how to best assign the resources of a host multicomputer system to the cooperating tasks of a parallel application program is known as the mapping problem. In this research we develop a graph-based solution to both aspects of the mapping problem using the simulated annealing optimization heuristic. A two phase mapping strategy is formulated: I) process annealing assigns parallel processes to processing nodes, and 2) connection annealing schedules traffic connections on network data links so that interprocess communication conflicts are minimized. To evaluate the quality of generated mappings, cost functions suitable for simulated annealing are derived that accurately quantify communication overhead. Communication efficiency is formulated to measure the quality of assignments when the optimal mapping is unknown. Application examples are presented using the hypercube as a host architecture, with host graphs containing up to 512 nodes. The influence of various parameters on the annealing algorithms is investigated, and results for several image graphs are presented.
    URI
    http://hdl.handle.net/10919/43836
    Collections
    • Masters Theses [19687]

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us
     

     

    VTechWorks

    AboutPoliciesHelp

    Browse

    All of VTechWorksCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Log inRegister

    Statistics

    View Usage Statistics

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us