Accession Number:

ADA256564

Title:

Implementation and Analysis of NP-Complete Algorithms on a Distributed Memory Computer

Descriptive Note:

Master's thesis

Corporate Author:

AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING

Personal Author(s):

Report Date:

1992-03-01

Pagination or Media Count:

190.0

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 iPSC2 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.

Subject Categories:

  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE