next up previous
Next: Testing Your Code Up: No Title Previous: No Title

Extending Eureka

On the class home page, you will find a compressed tar file that contains the EUREKA search algorithm described in class. I would like you to extend this system by adding a non-synchronized version of distributed tree search (also can be used by the Kumar and Rao algorithm). In this non-synchronized version, processors who reach the end of an IDA* iteration do not load balance to get more work, and do not wait for other processors to finish before starting the next iteration. Instead, they increment their own cost threshold and start a new IDA* iteration. To ensure optimality, processors inform the host of the cost threshold they are initiating.

Your program should be able to find a first (possibly non-optimal) or optimal solution. Remember, if you are looking for an optimal solution, the host must wait, even if a solution has been found, for processors that are searching to a smaller cost limit.

Diane J. Cook
Mon Jan 20 13:39:38 CST 1997