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


When processor P0 goes idle, it colors itself green and initiates a green token



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

When processor P0 goes idle, it colors itself green and initiates a green token.

  • If processor Pj sends work to processor Pi and j > i then processor Pj becomes red.

  • If processor Pi has the token and Pi is idle, it passes the token to Pi+1. If Pi is red, then the color of the token is set to red before it is sent to Pi+1. If Pi is green, the token is passed unchanged.

  • After Pi passes the token to Pi+1, Pi becomes green .

  • The algorithm terminates when processor P0 receives a green token and is itself idle.



  • Tree-Based Termination Detection

    • Associate weights with individual workpieces. Initially, processor P0 has all the work and a weight of one.

    • Whenever work is partitioned, the weight is split into half and sent with the work.

    • When a processor gets done with its work, it sends its parent the weight back.

    • Termination is signaled when the weight at processor P0 becomes 1 again.

    • Note that underflow and finite precision are important factors associated with this scheme.



    Tree-Based Termination Detection

    • Tree-based termination detection. Steps 1-6 illustrate the weights at various processors after each work transfer




    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