The Application
Next: Parix Implementation
Up: No Title
Previous: Introduction
Our application is an algorithm from the domain of Artificial Intelligence,
the iterativedeepening search algorithm IDA* [1].
This is a heuristic DFS algorithm that simulates a bestfirst search
by a series of depthfirst searches with successively increased costbounds.
Iterativedeepening search is used in many applications
that cannot be solved with direct bestfirst searches
(like A*) because of memory restrictions.
The search tree is highly irregular,
so that efficient workpartitioning and dynamic workload balancing
schemes are required in a parallel implementation to achieve a good
overall performance.
Our Asynchronous IDA* (AIDA*) algorithm [3]
works in two phases:

In an initial task partitioning phase, the nodes of a
searchfrontier 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.

In an asynchronous search phase,
each processor expands its `own' frontier nodes in depthfirst 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 frontiernodes, but now with an increased costbound.
When a processor finds a solution,
all others are informed by a broadcast.
To avoid speedupanomalies, we search for all solutions in our implementation.
This ensures that the node count is always the
same for a given problem instance.
Volker Schnecke
Thu Dec 15 22:13:21 MET 1994