Parallel Algorithms and Sequential Algorithms

1. Overview

In the case of Sequential algorithms, It should execute the tasks one after each other. In the case of Parallel algorithms, we execute different tasks with different processors then combine the results. Some problems are easy to parallelizable, other problems are completely sequential.

2. Description

2.1 Parallel algorithms

Checking prime numbers in a range. We have to make subsets. Find the primes sequentially in the subsets then combine the results together. We are going to assign as many threads as a number of processors or the number, of course, is going to be parallel.

2.2 Sequential algorithms

Numerical methods or every algorithm where the next step relies heavily on the previous one. For example, Newton-method, Euler-method

2.3 Parallel execution and concurrent programming

If we use threads, it is not necessarily going to be executed as parallel, it depends on the concrete OS or machine. If it has a single processor, it makes time-slicing between the threads which is slower than simple sequential implementation one thread at a given time. Whereas parallel execution, we can execute more threads at the same time.

2.4 Parallel Execution Problems 

2.4.1 Communication

For serial algorithms, we have memory and time complexity. Parallel algorithms we have to take the communication between threads into consideration.

2.4.2 Load balance

We have to make sure we split the work evenly amongst the processors. For example, we want to find prime factors for [0-1000]. [0-500] and [501-1000] is not a good division. The first processor finished before the second and waits instead of making the computation.