Parallel Performance Flashcards
(23 cards)
What are the main causes of performance degradation in parallel computing?
- Starvation – Not enough parallel work to keep processors busy
- Latency – Delay in transferring data between system components
- Overhead – Extra overhead work needed for parallel execution (e.g., thread management)
- Waiting – Processes waiting for shared resources
Acronym: SLOW
What is parallel speed-up? How is it defined mathematically?
- How much faster the parallel program is compared to the serial version.
- S{N} = T{N}/T{0}, where T{0} is serial execution time and T{N} is parallel execution time on N processors.
What is parallel efficiency? How is defined mathematically?
- Whether speed-up represents efficient use of the resources.
- E{N} = S{N}/N, where S{N} is speed-up on N processors.
What is strong scaling?
Keeping the total problem size fixed and increasing the number of processors to reduce execution time.
What is Amdahl’s Law? What is the formula?
The parallel speed-up is limited by the fraction of the program that cannot be parallelised.
Formula:
S{N} = 1/(s + p/N), where:
- S{N} is the parallel speed-up
- s is the serial fraction
- p is the parallel fraction
- N is the number of processors
What is the theoretical maximum speed-up if infinite processors were available?
S{max} = 1/s = 1/(1−p)
How does Gustafson’s Law challenge Amdahl’s Law?
It assumes that problem size increases with the number of processors, leading to better scaling than predicted by Amdahl’s Law.
What is Gustafson’s Law? What is the formula?
- With a more powerful processor, the problem generally expands
Formula
S{N} = s + pN, where:
- S{N} is the parallel speed-up
- s is the serial fraction
- p is the parallel fraction
- N is the number of processors
What is weak scaling?
- Keep the workload per processor constant
- Increase the number of processors
- This leads to increased total problem size
Why are barriers used in parallel programming?
To ensure all threads complete their work before proceeding to a critical section (e.g., writing output).
How can implied barriers be removed to improve performance?
Using the nowait clause
What is load balancing?
Distributing workloads across processes to prevent idle time and make better use of resources
What are the three main loop scheduling strategies in OpenMP?
- (static, chunk) – Assigns equal chunks to threads in a round-robin manner.
- (dynamic, chunk) – Assigns chunks dynamically as threads finish their work.
- (guided, chunk) – Initially large chunks that decrease in size.
Why is load balancing important in MPI programs?
To ensure all processors are utilised effectively and prevent idle time due to uneven work distribution.
What is the role of an interconnect in HPC clusters?
It facilitates communication between compute nodes by carrying MPI messages
What are common interconnect technologies used in HPC clusters?
- Gigabit Ethernet
- Infiniband
What are three key factors affecting MPI message transmission time?
- Number of hops between nodes
- Blocking factor of the network
- Other network traffic
How is message transmission time modelled/calculated?
t = L+ M/B, where:
- L is the latency
- M is the message size
- B is the bandwidth
- When is latency more important than bandwidth?
- When is bandwidth more important than latency?
- When sending many small messages.
- When sending large messages.
What is the proportion of computation to communication for domain decomposition?
- R{2D} = 4/N
- R{3D} = 6/N
As subdomain size decreases, communication overhead increases.
What are parallel overheads?
- Extra work required to run a program in parallel
- e.g., Extra code for message passing, process synchronisation, thread management, loop scheduling, etc.
How does Amdahl’s Law change when considering parallel overheads?
The speed-up formula includes the extra overhead term:
- S{N} = 1/(s + p/N + (n{p}v)/T{0})
where n{v}v represents parallel overhead as a fraction of serial runtime.
What is super-linear speed-up, and when does it occur?
When speed-up exceeds N due to improved cache utilisation at smaller problem sizes.
