Implementation and Analysis of NP-Complete Algorithms on a Distributed Memory Computer
AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING
Pagination or Media Count:
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.
- Computer Systems