Date of Award

3-1992

Document Type

Thesis

Degree Name

Master of Science

Department

Department of Electrical and Computer Engineering

Abstract

The purpose of this research is to explore methods used to parallelize NP-complete problems and the degree of improvement that can be realized using different methods of load balancing. A serial and four parallel A* branch and bound algorithms were implemented and executed on an Intel iPSC/2 hypercube computer. One parallel algorithm used a global, or centralized, list to store unfinished work and the other three parallel algorithms used a distributed list to store unfinished work locally on each processor. the three distributed list algorithms are: without load balancing, with load balancing, and with load balancing and work distribution. The difference between load balancing and work distribution is load balancing only occurs when a processor becomes idle and work distribution attempts to emulate the global list of unfinished work by sharing work throughout the algorithm, not just at the end. Factors which effect when and how often to load balance are also investigated. which algorithm performed best depended on how many processors were used to solve the problem. For a small number of processors, 16 or less, the centralized list algorithm easily outperformed all others. However, after 16 processors, the overhead of all processors trying to communicate and request work from the same centralized list began to outweigh any benefits of having a global list. Now the distributed list algorithms began to perform best. When using 32 processors, the distributed list with load balancing and work distribution out performed the other algorithms. Search, Hypercube, Parallel, NP-complete.

AFIT Designator

AFIT-GE-ENG-92-M

DTIC Accession Number

ADA256564

Download

Share

COinS