Table 1: Messages per processor (15-puzzle,
)
Table 1: Messages per processor (15-puzzle, )
Table 1 shows the total messages and
work messages received by a single node
while computing a hard 15-puzzle problem
on a 128-processor ring.
The total message count includes all message transfers through that specific
node, while the work message count represents only work packets received
by the node.
As can be seen, PIDA*'s total message flow increases from one iteration to the next. AIDA*'s communication overhead, on the other hand, decreases after a couple of iterations. This is caused by our adaptive load balancing method that constantly improves the global work-load by keeping the transferred nodes at the new processor for the next iteration.
Moreover, the absolute number of messages is by an order of magnitude lower for AIDA*. Similar results have been obtained for the larger 1024-node system and also for the more time-consuming 19-puzzle. The communication overhead does not significantly increase with growing system size because most work requests are satisfied in the nearest neighborship.