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


Parameters in Parallel DFS: Work Splitting



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

Parameters in Parallel DFS: Work Splitting

  • Splitting the DFS tree: the two subtrees along with their stack representations are shown in (a) and (b).



Load-Balancing Schemes

  • Who do you request work from? Note that we would like to distribute work requests evenly, in a global sense.

  • Asynchronous round robin: Each processor maintains a counter and makes requests in a round-robin fashion.

  • Global round robin: The system maintains a global counter and requests are made in a round-robin fashion, globally.

  • Random polling: Request a randomly selected processor for work.



Analyzing DFS

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