Which algorithm is best when running with parallel processors?

Question

If I had a machine with multiple processors and trying to solve a huge problem, which algorithm would be best for solving this problem?

Dynamic Programming, Greedy or the Divide and Conquer algorithm?

Answer 1

This is an extremely broad question, and many things will depend on the specific problem you're trying to solve, but what you're looking for is whether an algorithm can run its steps in parallel. This can only be done if the result of one step does not depend on the result of another.

• We can't say anything about greedy algorithms here. They're only defined as taking the locally best next step.
• Divide and conquer divides the problem into separate parts, each of which can be individually solved, so this is often a good candidate for running things in parallel.
• Dynamic programming could be viewed as a sort of divide and conquer, but now, you're solving a small part of the problem, and then using that to solve a bigger part, and so on. For example, the knapsack problem is often used as a use case for dynamic programming. You can solve the problem starting with a trivially small knapsack, and building up your solution from there. The problem here is that each solution depends on the solution of the smaller problem. Unless individual steps can be divided among threads, this cannot be parallelized.

So generally, divide and conquer seems to be your best bet for running things in parallel.

Answer 2

The Dynamic programming it use an array, which has to be synchronized between threads, which are searching for individual solutions.

The Greedy is kind of single threaded. Can be made multi threaded, but not a huge advantage imo. Anyway, you can use a pool of threads to shot with the best 5 matches...This would be the easiest to implement.

The Divide and Conquer is a recursive. If you would spawn a new thread still need a synchronization, but it can take the advantage clearly of multiple processor. I think it would be the second easier method to implement multithreaded.

The nature of the problem, which you need to solve it will decide which programming method should you use, not the processor core numbers.

Please take in considerations the time costs for switching the contexts between threads also!