It is possible for two or more processors to request work from same processor. Global Round Robin Use a single global variable called target stored at processor . When a processor needs work, it requests and receives value of target from . Then increments the value of target modulo p before responding to another request. GRR ensures that successive work request are distributed evenly across processors.
Difficulty is in centralized bottleneck processor .
Analysis of Parallel Search Assume a parameter which states that after work requests, each processor receives at least one work request. The communication overhead for parallel DFS is where W is amount of search work, is cost of communication for one piece of work. Imagine the p processors to be connected in a ring, . Processor initiates a token when it becomes idle, sends to . At any stage, token is held in processor until that processor completes.