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.

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