Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

for Random Polling

• We have:

Analysis of Load-Balancing Schemes

• If tcomm = O(1) , we have,

• T0 = O(V(p)log W). (2)

• Asynchronous Round Robin: Since V(p) = O(p2), T0 = O(p2log w). It follows that:

• W = O(p2log(p2log W)),

• = O(p2log p + p2log log W)

• = O(p2log p)

Analysis of Load-Balancing Schemes

• Global Round Robin: Since V(p) = O(p), T0 = O(plog W). It follows that W = O(plog p).

• However, there is contention here! The global counter must be incremented O(plog W) times in O(W/p) time.

• From this, we have:

• (3)

• and W = O(p2log p).

• The worse of these two expressions, W = O(p2log p) is the isoefficiency.

Analysis of Load-Balancing Schemes

• Random Polling: We have V(p) = O(plog p), To = O(plog plogW)

• Therefore W = O(plog2p).

Analysis of Load-Balancing Schemes: Conclusions

• Asynchronous round robin has poor performance because it makes a large number of work requests.

• Global round robin has poor performance because of contention at counter, although it makes the least number of requests.

• Random polling strikes a desirable compromise.

Experimental Validation: Satisfiability Problem

• Speedups of parallel DFS using ARR, GRR and RP load-balancing schemes.

Experimental Validation: Satisfiability Problem

• Number of work requests generated for RP and GRR and their expected values ( and respectively).

Experimental Validation: Satisfiability Problem

•