Performance Evaluation of Parallel Branch and Bound Search with the Intel iPSC (Intel Personal SuperComputer) Hypercube Computer.
AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING
Pagination or Media Count:
With the recent availability of commercial parallel computers, researchers are examining new classes of problems for benefits from parallel processing. This report presents results of an investigation of the set of problems classified as search intensive. The specific problems discussed in this report are the backtracking search method of the N-queens problem and the Least-Cost Branch and Bound search of deadline job scheduling. The object-oriented design methodology was used to map the problem into a parallel solution. While the initial design was good for a prototype, the best performance resulted from fine tuning the algorithms for a specific computer. The experiments of the N-queens and deadline job scheduling included an analysis of the computation time to first solution, the computation time to all solutions, the speed up over a VAX 11785, and the load balance of the problem when using an Intel Personal SuperComputeriPSC. The iPSC is a loosely couple multiprocessor system based on a hypercube architecture. Results are presented which compare the performance of the iPSC and VAX 11785 for these classes of problems. Thesis
- Computer Hardware