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

Parameters in Parallel DFS: Work Splitting

• Splitting the DFS tree: the two subtrees along with their stack representations are shown in (a) and (b).

Load-Balancing Schemes

• Who do you request work from? Note that we would like to distribute work requests evenly, in a global sense.

• Asynchronous round robin: Each processor maintains a counter and makes requests in a round-robin fashion.

• Global round robin: The system maintains a global counter and requests are made in a round-robin fashion, globally.

• Random polling: Request a randomly selected processor for work.

Analyzing DFS

• We can’t compute, analytically, the serial work W or parallel time. Instead, we quantify total overhead To in terms of W to compute scalability.

• For dynamic load balancing, idling time is subsumed by communication.

•