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



Yüklə 0,99 Mb.
səhifə17/23
tarix26.12.2016
ölçüsü0,99 Mb.
#3369
1   ...   13   14   15   16   17   18   19   20   ...   23

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

1   ...   13   14   15   16   17   18   19   20   ...   23




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin