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


Experimental isoefficiency curves for RP for different efficiencies



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

Experimental isoefficiency curves for RP for different efficiencies.



Termination Detection

  • How do you know when everyone's done?

  • A number of algorithms have been proposed.



Dijkstra's Token Termination Detection

  • Assume that all processors are organized in a logical ring.

  • Assume, for now that work transfers can only happen from Pi to Pj if j > i.

  • Processor P0 initiates a token on the ring when it goes idle.

  • Each intermediate processor receives this token and forwards it when it becomes idle.

  • When the token reaches processor P0, all processors are done.



Dijkstra's Token Termination Detection

  • Now, let us do away with the restriction on work transfers.


  • Yüklə 0,99 Mb.

    Dostları ilə paylaş:
1   ...   15   16   17   18   19   20   21   22   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