The Application

Our application is an algorithm from the domain of Artificial Intelligence, the iterative-deepening search algorithm IDA* [1]. This is a heuristic DFS algorithm that simulates a best-first search by a series of depth-first searches with successively increased cost-bounds. Iterative-deepening search is used in many applications that cannot be solved with direct best-first searches (like A*) because of memory restrictions. The search tree is highly irregular, so that efficient work-partitioning and dynamic work-load balancing schemes are required in a parallel implementation to achieve a good overall performance. Our Asynchronous IDA* (AIDA*) algorithm [3] works in two phases:

1. In an initial task partitioning phase, the nodes of a search-frontier level in the tree are generated in parallel and stored on all processors. Each of the nodes is a root of a subtree and represents an indivisible piece of work for the next phase.

2. In an asynchronous search phase, each processor expands its `own' frontier nodes in depth-first fashion. When a processor becomes idle, it sends a work request to obtain a work packet (i.e., an unprocessed frontier node) from another processor. Work requests are forwarded on a ring topology until one processor has work to share or the request is returned to the sender. If no work is left for this iteration, the processor proceeds with the next iteration, that is, it again starts the search on its frontier-nodes, but now with an increased cost-bound. When a processor finds a solution, all others are informed by a broadcast.

To avoid speedup-anomalies, we search for all solutions in our implementation. This ensures that the node count is always the same for a given problem instance.