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

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.

•