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

Assume that the largest piece of work at any point is W.

After V(p) requests, the maximum work remaining at any processor is less than (1 - α)W; after 2V(p) requests, it is less than (1 - α)2W.

After (log1/1(1- α )(W/ε))V(p) requests, the maximum work remaining at any processor is below a threshold value ε.

The total number of work requests is O(V(p)log W).

Analyzing DFS

• If tcomm is the time required to communicate a piece of work, then the communication overhead is given by

• T0 = tcommV(p)log W (1)

• The corresponding efficiency E is given by

Analyzing DFS: for Various Schemes

• Asynchronous Round Robin: V(p) = O(p2) in the worst case.

• Global Round Robin: V(p) = p.

• Random Polling: Worst case V(p) is unbounded. We do average case analysis.

for Random Polling

• Let F(i,p) represent a state in which i of the processors have been requested, and p - i have not.

• Let f(i,p) denote the average number of trials needed to change from state F(i,p) to F(p,p) (V(p) = f(0,p)).