cs598dhp Parallel Processing
Spring 2008
Machine Problem 5
Due Tuesday, April 15
The objective of this machine problem is to evaluate different work-splitting strategies.
To this end, you are asked to develop a parallel program that implements a depth-first search for the best sequence of moves to solve the 8-puzzle problem discussed in chapter 11 of Introduction to Parallel Programming by A. Grama et al. (distributed in class).
The program is to be implemented in OpenMP. Please observe that dues to the dynamic characteristics of the algorithm we need to use the parallel for construct of OpenMP only to initiate parallelism. That is, the program should probably consist of a single parallel for executing omp_get_num_procs() iterations (one iteration per processor). The body of the loop should be a while loop that “steals” work from other processors (the work splitting strategies) using locks to avoid errors.
For the Load balancing scheme (i.e. the process of deciding from which processor to “steal work” once a processor becomes idle) you should use the global round robin strategy. You are asked to implement two versions of the work-splitting strategy: ‘steal” nodes near the bottom, and (2) steal nodes as near to the cutoff depth as possible. You should experiment with the cutoff depth and to determine the effect of changing it. You can use any termination detection strategy you want.
As in the past, programs should be run on one of the machines csil-polaris02 thru csil-polaris07. The language should be C, C++, or Fortran.
You are asked to hand in your evaluation including a discussion (no more than three pages) of the result you obtain including speedups, the relative performance of the near-the-bottom and the cutoff strategies, as well as the effect of changing the cutoff point. Your interpretation of the result are also requested.