Processor and link assignment using simulated annealing

Simple item page
dc.contributor.authorBollinger, S. Wayneen
dc.contributor.committeechairMidkiff, Scott F.en
dc.contributor.committeememberArmstrong, James R.en
dc.contributor.committeememberGray, Festus Gailen
dc.contributor.departmentElectrical Engineeringen
dc.date.accessioned2014-03-14T21:40:56Zen
dc.date.adate2010-07-21en
dc.date.available2014-03-14T21:40:56Zen
dc.date.issued1988-05-17en
dc.date.rdate2010-07-21en
dc.date.sdate2010-07-21en
dc.description.abstractAdvances 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.en
dc.description.degreeMaster of Scienceen
dc.format.extentix, 114 leavesen
dc.format.mediumBTDen
dc.format.mimetypeapplication/pdfen
dc.identifier.otheretd-07212010-020233en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-07212010-020233/en
dc.identifier.urihttp://hdl.handle.net/10919/43836en
dc.publisherVirginia Techen
dc.relation.haspartLD5655.V855_1988.B644.pdfen
dc.relation.isformatofOCLC# 18354354en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V855 1988.B644en
dc.subject.lcshDigital mappingen
dc.subject.lcshMultiprocessorsen
dc.subject.lcshParallel processing (Electronic computers)en
dc.titleProcessor and link assignment using simulated annealingen
dc.typeThesisen
dc.type.dcmitypeTexten
thesis.degree.disciplineElectrical Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LD5655.V855_1988.B644.pdf
Size:
3.8 MB
Format:
Adobe Portable Document Format
Download

Collections

Masters Theses