Parallel Programming Patterns: Part 4
By Hardik Dave on Apr 02, 2008
As promised, we will see the divide and conquer pattern implemented in MPI Plugin for Netbeans.
This pattern is employed in solving many sequential problems where a problem can be split into number of smaller problems which can be solved independently. The intermediate solutions are merged to get the final solution. The sub problems are generally independent of each other and structured such that they can not be further sub divided. Also if the program correctness is independent of whether the subproblems are solved sequentially or concurrently, a hybrid system can be designed that sometimes solves them sequentially and sometimes concurrently, based on which approach is likely to be more efficient. With this strategy, the subproblems can be solved directly, or they can in turn be solved using the same divide-and-conquer strategy, leading to an overall recursive program structure.In summary program following this pattern should have a recursive process creation, base case solving mechanism, and merging the result. Maintaining the right level or recursion depth and problem size may need to be tuned.
The final pattern of our series would be the ring pattern, for more information, please see MPI Plugin design patterns.