Phase 2: Generating Fine Grained Work Packets

In the second phase, processor takes its nodes from the frontier node array to get a wide-spread distribution of search frontier nodes. The nodes are expanded by applying two IDA* iterations, giving a new search frontier, , as shown in Figure 1. At the end of the second phase, the local node arrays of the individual processors contain about 3000 frontier nodes each. These nodes make up the work packets used in dynamic load balancing in the third phase. As before, there is neither synchronization nor communication involved in this phase.