Load balancing significantly affects the performance of a majority of parallel algorithms. When work is divided evenly among processors, no load balancing is necessary. Heuristic search frequently creates highly irregular search spaces, which results in load imbalance between processors. EUREKA permits load balancing operations during iterations of IDA*. A processor with nodes available on its open list may donate some or all of the nodes to a requesting processor. Decisions that affect system performance include deciding when to balance the load, identifying a processor from which to request work, and deciding how much work to donate.
In the first load balancing experiment we test EUREKA's ability to select the appropriate processor polling strategy. We have implemented the asynchronous round robin and the random polling approaches. On the nCUBE 2, a processor's D neighbors are polled for work (using the nCUBE's hypercube topology, D corresponds to log2 P) whereas in the PVM environment, a processor's right and left neighbors are polled (D = 2 because the workstations are connected with a ring topology). The results of this experiment are listed in Table 9.
Table 9 shows that once again C4.5 yields the best speedup in most cases and always yields the best speedup on filtered data sets. Among the fixed results, no single approach outperforms the others on all data sets.
Table 10 summarizes the classification results of the fixed
strategies in comparison to the C4.5 classifications. For each of the
filtered data sets, C4.5 outperforms any fixed strategy with a significance
of p
0.04 or better.
The second load balancing experiment demonstrates EUREKA's ability to determine the optimal amount of work to donate upon request. If too little work is donated, the requesting processor will soon return for more work. If too much work is donated, the granting processor will soon be in danger of becoming idle. Table 11 lists the results of this experiment, demonstrating once again that the learning system is capable of effectively selecting load balancing strategies, except when the unfiltered test cases from the fifteen puzzle are used (on the nCUBE and on the distributed network of workstations). The combined results are generated using training cases from the fifteen puzzle and robot arm motion planning nCUBE examples.
Table 12 lists the classification accuracy results. C4.5 does not
perform significantly better than the fixed strategies for the unfiltered data,
but does perform significantly better (p0.04) than the fixed
strategies for the filtered data.