Difference between revisions of "Benchmarking & Scaling Tutorial/Introduction"
(Created page with " == 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...") |
|||
| Line 2: | Line 2: | ||
== 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 [ | + | 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. |
| Line 24: | Line 24: | ||
</math> | </math> | ||
| − | <math>t_p/P</math> is the speed up amount of time due to the usage of multiple CPUs. The total | + | <math>t_p/P</math> is the speed up amount of time due to the usage of multiple CPUs. The total '''speedup''' <math>S</math> is defined as the ratio of the sequential to the parallel runtime: |
<math> | <math> | ||
| Line 30: | Line 30: | ||
</math> | </math> | ||
| − | The | + | The '''efficiency''' is the speedup per processor, i.e. |
<math> | <math> | ||
| Line 37: | Line 37: | ||
| − | == Amdahl's Law == | + | === Amdahl's Law === |
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 | 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 49: | Line 49: | ||
</math> | </math> | ||
| − | This places an upper limit on the | + | 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''. |
| + | |||
| + | ---- | ||
| + | |||
| + | Knowing about speedup and efficiency we can now try to measure this ourselves. | ||
| + | |||
| + | Next: [[Benchmarking_%26_Scaling_Tutorial/Manual_Benchmarking | Interactive Manual Benchmarking ]] | ||
Revision as of 11:09, 10 September 2021
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 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.
Speedup and Efficiency
We assume that the total execution time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} of a program is comprised of
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_s} , a part of the code which can only run in serial
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_p} , a part of the code which can be parallelized
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_o} , parallel overheads due to, e.g. communication
The execution time of a serial code would then be
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(1) = t_s + t_p }
The time for a parallel code, where the work would be perfectly divided by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} processors, would be given by
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(P) = t_s + \frac{t_p}{P} + t_o(P) }
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_p/P} is the speed up amount of time due to the usage of multiple CPUs. The total speedup Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is defined as the ratio of the sequential to the parallel runtime:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = \frac{T(1)}{T(P)} }
The efficiency is the speedup per processor, i.e.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E = \frac{S}{P} = \frac{T(1)}{P \cdot T(P)} }
Amdahl's Law
Knowing that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_o > 0} , and writing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F = \frac{t_s}{t_s + t_p}} as the fraction of the serial code, we can rewrite this to
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S \leq \frac{1}{F+(1-F)/P} }
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E \leq \frac{1}{PF+(1-F)} }
This places an upper limit on the strong scalability i.e. how quickly can we solve a problem of fixed size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} by increasing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} . It is known as Amdahl's Law.
Knowing about speedup and efficiency we can now try to measure this ourselves.