Time Comparisons


next up previous
Next: Parallel Optimization Up: Parallel Implementation and Optimization Previous: Parallelism

Time Comparisons

While this is only a rudimentary implementation of parallelism in searching the game tree, open to many optimizations, it demonstrates speedups over the sequential alpha-beta version. Figure 8 compares the parallel algorithm using alpha-beta on 4 processors with both version of the sequential program. As with the initial alpha-beta and minimax, the rest of the program management is identical. The main difference is the parallelization. As can be seen with this graph, which represents a fairly easy problem at all depths, the parallel version has the same times as the alpha-beta version, with a 2 second offset. I attribute this offset to process spawning and communication overhead necessary for parallelization.

Figure 9 shows the time per node evaluation for the same set of trials and shows that while the parallel version may be slower overall, it is actually performing more computations in that time than the sequential version.

Figure 10 shows the overall time for a more involved computation searching a greater set of nodes at each level. At level 5, the parallel version is faster than either sequential version. For an extremely involved search the parallel version is actually faster than either sequential version.

Looking at the time per node evaluation for each of these runs, in Figure 11, we can see that not only is the parallel version faster than the sequential versions, but as previously demonstrated, it is also making better use of it's time.

 
Figure 8: Search Time for a Simple problem

 
Figure 9: Time per Node evaluations for a Simple problem

 
Figure 10: Search Time for a Complex problem

 
Figure 11: Time per Node evaluations for a Complex problem


next up previous
Next: Parallel Optimization Up: Parallel Implementation and Optimization Previous: Parallelism


abierman@cs.caltech.edu