Parallel computation¶

Figure 1: CoRA, a robotic platform in which all computers (e.g. the one connected to the camera, another connected to the gripper, etc) sent messages to one receiving computer: an example of distributed parallelism

Why parallel computing is important¶

Most HPC clusters use 7-10 days as a maximum duration for a job. Your calculation may take longer than that. One technique that may work is to use parallel computing, where one uses multiple CPU cores to work together on a same calculation

HPC cluster architecture¶

Here is a simplified picture of HPC cluster architecture:

• [1] this is a pun to distributed parallelism

Types of ‘doing more things at the same time’¶

There are many types of ‘doing more things at the same time’. One way to distinguish these, is to separate these on the extent of the parallelism:

Today, we will extend your toolkit from a single-threaded calculation (you already do this) to thread parallelism.

The ideal effectiveness of parallelism¶

Before going into details, we will look at the effectiveness of parallelism in the most optimal case, with the goal that you can determine if it is worth it.

By now, you can probably guess that parallel computing spreads a calculation over multiple things that can calculate.

Imagine a calculation that takes 16 time units, represented as this:

Figure 2: a calculation of 16 time units run on 1 core, following the legend below:

Square	A unit of calculation time that …
	cannot be run in parallel
	can be run in parallel
	is spent doing nothing

This calculation time is expressed in a time unit such as seconds and hence, can be split up into smaller blocks.

Using 2 calculation units, this results in:

Figure 2: a calculation of 16 time units run on 2 cores, where square is a time unit of calculation.

This takes the calculation down from 16 to 10 time units. The so-called ‘speedup’ of using two workers is 16 / 10 = 1.6.

n = t_y / t_x

n =  performance_x / performance_y

S = s + (p * N) = N - ((N - 1) * s) = 1 + ((N - 1) * p)

However, 4 (out of 20) calculations units are spent waiting. This means that 16 / 20 = 80% of the calculation time is spent efficiently.

f = t_used_effectively / t_total`

t_used_effectively = (p + s) + (p * (N - 1))
t_total = time * N

Here one can see this calculation for more cores:

Program runtime	Number of cores	Time	Speedup	Efficiency
	1	16	16 / 16 = 100%	16 / 16 = 100%
	2	10	16 / 10 = 160%	(10 + 6) / (10 * 2) = 16 / 20 = 80%
	3	8	16 / 8 = 200%	(10 + 4 + 4) / (10 * 3) = 60%
	4	7	16 / 7 = 229%	(10 + 3 + 3 + 3) / (10 * 4) = 48%
	6	6	16 / 6 = 267%	(10 + (2^5)) / (10 * 6) = 70%
.	12	5	16 / 5 = .%	(10 + (1^11)) / (10 * 12) = 10%
.	24	4.5	16 / 4.5 = .%	(10 + (0.5^23)) / (10 * 24) = 34 / 50 = 68%
.	48	4.25	16 / 4.25 = .%	(10 + (0.25^47)) / (10 * 48) = 34 / 50 = 68%

The best possible speed gain (as shown here) is called Amdahl’s Law (inspired by [Amdahl, 1967]) and, in a general form, is plotted like this:

Exercises¶

Question -1: change your Zoom name¶

Change your Zoom name, to include your HPC cluster and favorite programming language, e.g. make Sven into Sven [Alvis, R].

You can do so by right-click on the video of yourself, then click ‘Rename’ to change your Zoom name.

Question 0: remember your Zoom room¶

Question 1¶

Which of the lines in the graph of Amdahl’s Law corresponds with the worked-out example of 16 time units?

Question 2¶

In the example of 16 time units, what is the shortest amount of time that can be spent on the calculation, given infinite resources?

Question 3¶

In the example of 16 time units, what is the maximal possible speedup?

S = t_regular / t_enhanced
S = 16 / 4
S = 4
S = 400%

Question 4¶

For your research project, you need to run a lot of calculations. Each calculation takes 10 hours. How do you make optimal use of your computational resources?

Question 5¶

For your research project, you also have a calculation that takes 11 days. Your HPC cluster allows a calculation of at most 10 days. Assume your HPC center will not extend your job (they will probably do so when asked: we are there to help!). How do you make optimal use of your computational resources?

Question 6¶

Your colleague runs many jobs with a lot of cores. ‘It is way faster!’, he/she states. That same colleague, however, also complains about long waiting times before his/her jobs start. How would you explain this situation?

Question 7¶

Your colleague has also done the exercises in this session and decided to measure the same features of her code. Below you can see the plots produced by this benchmark. What seemed to be the percentage of his/her code that could be run in parallel?

References¶

• [Amdahl, 1967] Amdahl, Gene M. “Validity of the single processor approach to achieving large scale computing capabilities.” Proceedings of the April 18-20, 1967, spring joint computer conference. 1967. Fun facts: it contains a single hand-drawn plot and no equations
• [Hennessy and Patterson, 2011] Hennessy, John L., and David A. Patterson. Computer architecture: a quantitative approach. Elsevier, 2011.