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


Let W be serial work and WP be parallel work. Search overhead factor s is defined as WP/W



Yüklə 0,99 Mb.
səhifə12/23
tarix26.12.2016
ölçüsü0,99 Mb.
#3369
1   ...   8   9   10   11   12   13   14   15   ...   23

Let W be serial work and WP be parallel work. Search overhead factor s is defined as WP/W.

  • Upper bound on speedup is p×(W/WP).



  • Parallel Depth-First Search

    • How is the search space partitioned across processors?

    • Different subtrees can be searched concurrently.

    • However, subtrees can be very different in size.

    • It is difficult to estimate the size of a subtree rooted at a node.

    • Dynamic load balancing is required.



    Parallel Depth-First Search

    • The unstructured nature of tree search and the imbalance resulting from static partitioning.



    Parallel Depth-First Search: Dynamic Load Balancing

    1   ...   8   9   10   11   12   13   14   15   ...   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