Divide and conquer

• One class of algorithms that are well-suited for parallel execution across multiple processors are divide and conquer algorithms.

• They work by first dividing a large problem into a number of smaller subproblems of roughly equal size.

• Next, the conquer phase recursively solves each of those subproblems and finally, the solution to the subproblems are combined together to produce the overall solution for the original problem.

• The common structure for divide and conquer code usually consists of an if/else statement. If the algorithm has reached what's called a base case, meaning the problem has been subdivided into a small enough piece to solve directly, then simply solve it. Otherwise, following the else case, divide the current problem into two smaller pieces, referred to as the left and right problems. Solve both of those problems recursively using the same divide and conquer strategy, then combine the left and right solutions.

• Consider the task of summing together a large number of elements. I have an array of shopping receipts here, and I need to add them all together to figure out how much we spent buying all those vegetables. If I were doing that alone as a sequential process, I would simply iterate through the receipts in the array and accumulate their values. Five plus 13 is 18, plus seven is 25, plus three is 28-- - That's going to take forever. Let's divide and conquer this task. You add this half of receipts, and I'll add this half. We've subdivided this task into two subtasks that each of our threads can execute. - Do you want to subdivide it into even smaller parts? - Sure. We can continue to recursively divide the receipts into smaller and smaller subgroups until we eventually reach our base case.

• For some algorithms, the base case may require you to continue recursively subdividing until you reach individual elements. But for our purpose, we can define our base case to stop when we reach a threshold amount of receipts. At that point, we'll add each of those subgroups of receipts together, then reverse or unwind the recursion to combine the results from all of the subproblems to get our final answer. - My half of the receipts add up to 41. - And mine add up to 62. So we spent a total of $103 on groceries.

• Divide and conquer algorithms lend themselves to being made to parallel because each of the subproblems are independent. So they can be executed in parallel on different processors.

• Now just because a divide and conquer algorithm can be made parallel, doesn't mean it's always advantageous to do so. Depending on the size of the problem set and the complexity of the operations involved, the cost and overhead involved in making the algorithm parallel may outweigh the potential benefits.

  Help/Feedback