Effect of Different Work Packet Sizes



Next: Results on Floorplan Up: Empirical Results Previous: Communication Overhead

Effect of Different Work Packet Sizes

Work packets of dissimilar sizes make it harder to balance the global work-load, because the amount of work a processor receives with a packet is not known a priori. This is a serious problem in the 15-puzzle, where the work packet sizes vary by several orders of magnitude.

Figure 7 illustrates for various work packet sizes (measured in nodes per subtree) how many of these packets exist in the system. Note that both axes are plotted logarithmical, showing packets ranging from only a handful of nodes up to 300,000 nodes for the largest subtree.

  
Figure 7: Size of work packets, 15-puzzle,

We therefore modified AIDA* to transfer only medium sized subtrees. In our implementation [16], this is done with a partial sort on the frontier nodes array. After each iteration, work packets of average size are moved to the end of the array, to be shipped to other processors during the next iteration. Further research is under way to adjust all work packets to an average size with node splitting and node contraction strategies [2].



Volker Schnecke
Fri Dec 16 11:20:32 MET 1994