Masters Theses

Date of Award

5-1989

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

David C. Mutchler

Committee Members

J. R. B Cocket, Ton Dunigan

Abstract

Several classes of problems can be solved by searching a graph. The bestfirst (BF) search algorithm can be used to generate a minimum cost solution. BF search Iteratively selects the best node using heuristic information and then expands the best node. Parallel best-first (BF) search iteratively selects the K best nodes (beam search) where K is the number of processors available. These K nodes are expanded simultaneously (in parallel). The effect of the choice for how many expansions each processor should do per each iteration is investigated through experiments. The effect of different parameters on the optimal choice of number of expansions per iteration (E) is also illustrated. The parameters are number of expansions per iteration, number of slaves, heuristics, computation time (c1) and communication time(c2). A simple mathematical model is developed to estimate the computation time per each expansion (c1) and communication time (c2). Intuitively, E is directly proportional to communication time. This is discussed and results are presented. Using the traveling salesman problem as a testbed, this thesis investigates the optimal value for E as a function of communication and computation time.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS