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


This is done using work requests and responses in message passing machines and locking and extracting work in shared address space machines



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

This is done using work requests and responses in message passing machines and locking and extracting work in shared address space machines.

  • On reaching final state at a processor, all processors terminate.

  • Unexplored states can be conveniently stored as local stacks at processors.

  • The entire space is assigned to one processor to begin with.



  • Parallel Depth-First Search: Dynamic Load Balancing

    • A generic scheme for dynamic load balancing.



    Parameters in Parallel DFS: Work Splitting

    • Work is split by splitting the stack into two.

    • Ideally, we do not want either of the split pieces to be small.

    • Select nodes near the bottom of the stack (node splitting), or

    • Select some nodes from each level (stack splitting).

    • The second strategy generally yields a more even split of the space.




    Yüklə 0,99 Mb.

    Dostları ilə paylaş:
    1   ...   9   10   11   12   13   14   15   16   ...   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