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


Assume that the largest piece of work at any point is W



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

Assume that the largest piece of work at any point is W.

  • After V(p) requests, the maximum work remaining at any processor is less than (1 - α)W; after 2V(p) requests, it is less than (1 - α)2W.

  • After (log1/1(1- α )(W/ε))V(p) requests, the maximum work remaining at any processor is below a threshold value ε.

  • The total number of work requests is O(V(p)log W).



  • Analyzing DFS

    • If tcomm is the time required to communicate a piece of work, then the communication overhead is given by

    • T0 = tcommV(p)log W (1)

    • The corresponding efficiency E is given by



    Analyzing DFS: for Various Schemes

    • Asynchronous Round Robin: V(p) = O(p2) in the worst case.

    • Global Round Robin: V(p) = p.

    • Random Polling: Worst case V(p) is unbounded. We do average case analysis.



    for Random Polling

    • Let F(i,p) represent a state in which i of the processors have been requested, and p - i have not.

    • Let f(i,p) denote the average number of trials needed to change from state F(i,p) to F(p,p) (V(p) = f(0,p)).    




    Yüklə 0,99 Mb.

    Dostları ilə paylaş:
    1   ...   12   13   14   15   16   17   18   19   ...   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