|
|
səhifə | 17/23 | tarix | 26.12.2016 | ölçüsü | 0,99 Mb. | | #3369 |
|
for Random Polling
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 |
|
|