When Should I Use Parallel Programming? Amdhal’s Law Explained

Writing a parallel program is such a daunting task. See how Amdhal’s Law can help you determine if the benefits are worth the pain

6 min readMar 23, 2023

For the longest time, parallel programming has been infamous for being hard and challenging.

This is because most of our programs have sequential and parallel parts. As a software developer, you must ensure synchronization among these parts.

Unfortunately, you may go through this hustle of parallelizing your programs while, in essence, you did not have to.

If a large program can be divided into smaller independent tasks, these individual tasks can be executed concurrently and independently. These tasks can be executed in any order, and the absolute result will be the same. This type of program can take advantage of parallel computing.

A program for finding prime numbers between a given range can benefit from parallel computing since we can divide the work into batches and split the batches among the different processing resources. The batches can be executed in any order our result would be the same.

If a program cannot be decomposed into independent tasks, then the program cannot be converted into a parallel program.

The 3 types of programs

Purley Sequential — Cannot be broken down into independent tasks. Every piece of the program relies on previously executed tasks. e.g. Traversing a linked list.
Embarrassingly Parallel — Can easily be broken down into independent tasks that can be executed independently from start to finish. e.g. Finding prime numbers from a range of numbers.
Sequential and Parallel — Made up of sequential and parallel parts. Some tasks can be independent, and some cannot. Software developers synchronize different program pieces, e.g. A computer program that processes files. A part of that program may scan the disk’s directory and create a list of files internally in memory (sequential). After that, another part of the program passes each file to a separate thread for processing (parallel)

In the real world, most of our programs are made of sequential and parallel parts. How much efficiency we can get from parallel programming can be determined by calculating the theoretical speedup using Amdahl’s Law.

Using Amdahl's Law to predict theoretical speedup

Admdahl's Law is named after the computer scientist Gene Amdahl and states that.

The overall performance improvement gained by optimizing a single part of a system is limited by the fraction of time that the improved part is actually used

Imagine we have 1 processor that takes 1 unit of time to complete a task. If we add another processor, we now have two processors. The total time taken to complete a single piece of task is now ½ = 0.5

To calculate the speedup

speedup = Time taken by one processor / Time taken by n processors
        = 1/0.5 = 2

As simple as it may seem, this is not true in the real world as the majority of our programs comprise sequential and parallel parts.

Let's use S to denote our sequential part of the program, P to denote the parallel part, and N to denote the number of processors.

The time taken by 1 processor, T1, to complete a task is

T1 = S + P

The time taken by N processors, TN, is

TN = (S + P) / N

Assuming that the unit of time taken by 1 processor is 1

1 = S + P

Then

S = 1 - P

We can re-write

TN = (S + P) / N

TN = 1 - P + P/N

Hence speedup is

speedup = Time taken by one processor / Time taken by n processors 
        = 1 / (1 - P + P/N)

The above equation is the equation for Amdahl's Law

Amdhal’s Law in Action

Let's now see Amdhal's Law in action. We are going to calculate the speedups for the following scenarios.

Suppose we have a program that is 70% parallel and 30% sequential, and we have 10 processors

speedup = 1 / (1 - P + P/N)
        = 1 / ((1 - 0.7) + 0.7/10)
        = 2.7

Suppose for the program above, and we now have 200,000 processors

speedup = 1 / (1 - P + P/N)
        = 1 / ((1–0.7) + 0.7/200000)
        = 3.33

Suppose we have a program that is 95% parallel and 5% sequential, and we have 10 processors

speedup = 1 / (1 - P + P/N)
        = 1 / ((1–0.95) + 0.95/10)
        = 6.89

Suppose for the program above, and we now have 200,000 processors

speedup = 1 / (1 - P + P/N)
        = 1 / ((1–0.95) + 0.95/200000)
        = 19.99

Surprisingly, with 30% of our program being sequential, there is little increase in speedup even after bumping up our processors from 10 to 200,000. A ⅓ of the program is sequential, and the performance gain is limited.

Consequently, if 50% of the execution time is sequential, the maximum speedup is 2, no matter how many processors you use.

Adding processors increases the performance up to some point, but after that, the advantages diminish quickly.

Sounds familiar? This is similar to the Law of diminishing returns.

What does this mean for software developers?

The advantages of parallel computing using multiple processors are only beneficial if the program is highly parallelizable.

A highly parallelizable program like finding prime numbers can benefit from parallel computing since we can divide the work into batches and split the batches among the different processing resources.

Writing a program with sequential and parallel parts means the developer has to handle synchronization between these parts. This is not an easy task and is what has made parallel programming infamous for being difficult.

Even though we can convert parts of our sequential programs into parallel programs (the parts that can be decomposed into independent tasks), it does not mean we should.

Using Amdahl's Law, we can determine if we shall benefit by going through the pain of parallelizing our program.

Amdahl's Law Caveat

If you are keen, you may have noticed Amdahl's Law assumes the size of the problem remains constant.

The constant is not the size of the problem but rather the time the user wants to wait for the result; given a faster machine, the user will increase the problem's size or the solution's accuracy rather than solve the same problem faster.

In our next article, When Should I Use Parallel Programming? Gustafson’s Law Explained, we'll look into how potential speedup can be measured in terms of an increase in the size of the problem.

Thanks for reading this article! Leave a comment below and tell me what you think. If you would like this article and would like to support my writing, you can buy me a coffee at https://ko-fi.com/kelvinmuchiri

Related articles by the author

When Should I use parallel programming? Gustafson’s Law Explained

An optimistic perspective on Amdhal’s Law

medium.com

What Is the Difference Between Concurrency and Parallelism?

Concurrency is about dealing with a lot of things at once, parallelism is about doing a lot of things at once