Performance Evaluation of Parallel Branch and Bound Search with the Intel iPSC (Intel Personal SuperComputer) Hypercube Computer.

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 11/785, and the load balance of the problem when using an Intel Personal SuperComputer(iPSC). 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 11/785 for these classes of problems. (Thesis)