Implementation Details

While the above description gives a general outline of the AIDA* scheme, the actual implementation is more sophisticated:

• When a processor is done with its local nodes, it can start a new iteration when it receives an out_of_work message or detects a work_request with a higher cost threshold on the ring.

• To keep communication costs low, up to five nodes are bundled in a work packet. To avoid the donator from giving away all of its non processed nodes, only half of these are transferred.

• At the end of each iteration the nodes in are re-ordered: Medium size subtrees with are sorted to the end of the array, so that only work packets of average size will be transferred to other processors.

• In the hard problems (with many iterations), the size of work packets can differ by an order of magnitude. We therefore experimented with node splitting and node contraction strategies [Chakrabrti et al., 1989] to adjust the work packets to an average size. Our preliminary results indicate that the additional overhead does not pay off.