Benchmarking & Scaling Tutorial/Introduction - Revision history

Sebastian-potthoff-3c73@uni-muenster.de at 08:59, 3 June 2022

2022-06-03T08:59:12Z

Kamil-braschke-0d3e@uni-wuppertal.de: /* Gustafson's Law */

2022-04-08T10:39:49Z

Gustafson's Law

Sebastian-potthoff-3c73@uni-muenster.de at 10:27, 3 November 2021

2021-11-03T10:27:19Z

Sebastian-potthoff-3c73@uni-muenster.de at 09:47, 3 November 2021

2021-11-03T09:47:53Z

Sebastian-potthoff-3c73@uni-muenster.de at 09:40, 3 November 2021

2021-11-03T09:40:06Z

Sebastian-potthoff-3c73@uni-muenster.de at 12:16, 22 October 2021

2021-10-22T12:16:05Z

Sebastian-potthoff-3c73@uni-muenster.de at 10:46, 22 October 2021

2021-10-22T10:46:24Z

Sebastian-potthoff-3c73@uni-muenster.de at 10:40, 24 September 2021

2021-09-24T10:40:09Z

Sebastian-potthoff-3c73@uni-muenster.de at 09:59, 24 September 2021

2021-09-24T09:59:43Z

Sebastian-potthoff-3c73@uni-muenster.de at 10:01, 14 September 2021

2021-09-14T10:01:43Z

← Older revision		Revision as of 08:59, 3 June 2022
Line 87:		Line 87:

	[[File:Gustafson.png\|1200px]]		[[File:Gustafson.png\|1200px]]
−
−	~~=== Consequences ===~~

@@ Line 79: / Line 79: @@
   <math>
-  S = F + (1-F) \cdot N
+  S = F + (1-F) \cdot P
   </math>

@@ Line 35: / Line 35: @@
   </math>
-The '''efficiency''' is the speedup per processor, i.e.
+The '''efficiency''' <math>E</math> is the speedup per processor, i.e.
   <math>
@@ Line 82: / Line 82: @@
   </math>
-where P is the number of processes, F is again the fraction of the serial part of the code and therefore (1-F) the fraction of the parallel part.
+where <math>P</math> is the number of processes, <math>F</math> is again the fraction of the serial part of the code and therefore <math>(1-F)</math> the fraction of the parallel part. Here the speedup increases linearly with respect to the number of processors (with a slope smaller than one).
 ==== Speedup and Efficiency ====

@@ Line 56: / Line 56: @@
 This places an upper limit on the '''strong scalability''' i.e. how quickly can we solve a problem of fixed size <math>N</math> by increasing <math>P</math>. It is known as ''Amdahl's Law''.
-=== Consequences ===
+[[File:amdahl.png|1200px]]
-* The speedup is never linear in P, therefore the efficiency is never 100%
+We can see that the speedup is never linear in P, therefore the efficiency is never 100%:
-* Examples:
+* Some Examples:
 ** For P=2 processors, to achieve E=0.9, you have to parallelize 89% of the code
 ** For P=10 processors, to achieve E=0.9, you have to parallelize 99% of the code
 ** For P=10 processors, to achieve E=0.5, you have to parallelize 89% of the code
+In the second figure terms for parallel overhead (e.g. communication between nodes) were added. This yields an even worse, but more realistic, behavior when increasing the number of processors:
 [[File:amdahl_overhead.png|1200px]]

← Older revision		Revision as of 09:40, 3 November 2021
Line 5:		Line 5:
	== Scalability ==		== Scalability ==

−	Often users who start running applications on an HPC system tend to assume the more resources (compute nodes / cores) they use, the faster their code will run (i.e. they expect a linear behaviour). Unfortunately this is not the case for the majority of applications. How fast a program runs with different amounts of resources is referred to as scalability. For parallel programs a limiting factor is defined by [https://en.wikipedia.org/wiki/Amdahl%27s_law Amdahl's law]. It takes into account the fact, that a certain amount of work of your code is done in parallel but the speedup is ultimately limited by the sequential part of the program.	+	Often users who start running applications on an HPC system tend to assume the more resources (compute nodes / cores) they use, the faster their code will run (i.e. they expect a linear behaviour). Unfortunately this is not the case for the majority of applications. How fast a program runs with different amounts of resources is referred to as scalability. For parallel programs a limiting factor is defined by [https://en.wikipedia.org/wiki/Amdahl%27s_law Amdahl's law]. It takes into account the fact, that a certain amount of work of your code is done in parallel but the speedup is ultimately limited by the sequential part of the program. However, next to different amount of resources, we can also vary the problem size we want to solve - its behavior is described by [https://en.wikipedia.org/wiki/Gustafson%27s_law Gustofson's law]. In this introduction we want to give a you a brief overview about the two models and their consequences for running code on a cluster.

@@ Line 66: / Line 66: @@
-[[File:amdahl.png|600px]]
+[[File:amdahl.png|1200px]]
-[[File:amdahl_overhead.png|600px]]
 == Weak Scaling ==

@@ Line 1: / Line 1: @@
 {{DISPLAYTITLE:Introduction & Theory}}<nowiki />
 {{Syllabus Benchmarking & Scaling}}<nowiki />
 __TOC__
 == Scalability ==
@@ Line 7: / Line 8: @@
-== Speedup and Efficiency ==
+== Strong Scaling ==
 We assume that the total execution time <math>T</math> of a program is comprised of
 * <math>t_s</math>, a part of the code which can only run in serial
@@ Line 39: / Line 42: @@
-=== Amdahl's Law ===
+==== Speedup and Efficiency ====
 Knowing that <math>t_o > 0</math>, and writing <math>F = \frac{t_s}{t_s + t_p}</math> as the fraction of the serial code, we can rewrite this to
@@ Line 65: / Line 68: @@
 [[File:amdahl.png|600px]]
 [[File:amdahl_overhead.png|600px]]
 Knowing about speedup and efficiency we can now try to measure this ourselves.

@@ Line 52: / Line 52: @@
 This places an upper limit on the '''strong scalability''' i.e. how quickly can we solve a problem of fixed size <math>N</math> by increasing <math>P</math>. It is known as ''Amdahl's Law''.
 [[File:amdahl.png|600px]]
@@ Line 59: / Line 69: @@
 Knowing about speedup and efficiency we can now try to measure this ourselves.
-Next: [[Benchmarking_%26_Scaling_Tutorial/Manual_Benchmarking | Interactive Manual Benchmarking ]]
+'''Next''': [[Benchmarking_%26_Scaling_Tutorial/Manual_Benchmarking | Interactive Manual Benchmarking ]]