11.3 Search Overhead Factor
Parallel search algorithms incur overhead from several sources. These include communication overhead, idle time due to load imbalance, and contention for shared data structures. Thus, if both the sequential and parallel formulations of an algorithm do the same amount of work, the speedup of parallel search on p processors is less than p. However, the amount of work done by a parallel formulation is often different from that done by the corresponding sequential formulation because they may explore different parts of the search space.
Let W be the amount of work done by a single processor, and W_{p} be the total amount of work done by p processors. The search overhead factor of the parallel system is defined as the ratio of the work done by the parallel formulation to that done by the sequential formulation, or W_{p}/W. Thus, the upper bound on speedup for the parallel system is given by p x(W/W_{p}). The actual speedup, however, may be less due to other parallel processing overhead. In most parallel search algorithms, the search overhead factor is greater than one. However, in some cases, it may be less than one, leading to superlinear speedup. If the search overhead factor is less than one on the average, then it indicates that the serial search algorithm is not the fastest algorithm for solving the problem.
To simplify our presentation and analysis, we assume that the time to expand each node is the same, and W and W_{p} are the number of nodes expanded by the serial and the parallel formulations, respectively. If the time for each expansion is t_{c}, then the sequential run time is given by T_{S} = t_{c}W. In the remainder of the chapter, we assume that t_{c} = 1. Hence, the problem size W and the serial run time T_{S} become the same.
