Factors affecting parallel performance

Question 1

What are the SLOW factors affecting parallel performance?

Answer 1

1. Starvation
2. Latency
3. Overhead
4. Waiting

Question 2

How does Starvation affect parallel performance?

Answer 2

Insufficient parallel work to keep the processors busy sometimes, due to an uneven distribution of work.

Question 3

How does Latency affect parallel performance?

Answer 3

The time taken for information to travel from one part of the system to another slows down the entire system.

Question 4

How does Overhead affect parallel performance?

Answer 4

The work required in addition to the computation such as starting and stopping OpenMP parallel regions.

Question 5

How does Waiting affect parallel performance?

Answer 5

When multiple threads/processes are accessing a shared resource they are in contention for memory or network bandwidth.

Question 6

What is parallel speedup?

Answer 6

How much faster the parallel program is than the linear version.

Question 7

How is parallel speedup calculated?

Answer 7

SN = T0/TN

where T0 is the time for the serial program to run and TN is the time taken for the parallel program to run on N processors

Question 8

How is parallel efficiency calculated?

Answer 8

EN = SN/N

Where SN is the speedup on N processors

Question 9

What is strong scaling?

Answer 9

When the total problem size is fixed and the number of processors is increased to reduce run time.

Question 10

What is Amdahl’s law?

Answer 10

The idea that parallel speedup is limited by the fraction of the program that can be parallelised.

Question 11

How is parallel speedup calculated using Amdahl’s Law?

Answer 11

SN = 1/(s + p/N)

Where SN is the parallel speed up, s is the fraction that can not be parallelised, and p is the fraction that can be parallelised.

Question 12

What did Gustafson observe?

Answer 12

He observed that in practice the problem size scales with the number of processors.

Question 13

What is weak scaling?

Answer 13

The idea that speed up increases linearly with the number of processors so the run time remains constant and it is easier to make use of a large number of processors.

Question 14

What is the equation for weak scaling?

Answer 14

Sn = s + pN

Question 15

How are parallel regions kept synchronised?

Answer 15

There is an implied barrier after parallel regions and work share constructs which acts as a synchronisation point.

Question 16

How is the implicit synch point removed?

Answer 16

Using the nowait command.

Question 17

How does nowait improve performance?

Answer 17

It can improve performance by avoiding unnecessary waiting but you need to be careful the program still works correctly.

Question 18

How is synchronisation added?

Answer 18

Using the command barrier

Question 19

What are the three loop scheduling options?

Answer 19

1. Static
2. Dynamic
3. Guided

Question 20

How does static loop scheduling work?

Answer 20

Iterations are divided into pieces of size chunk and distributed round-robin between threads.

Question 21

How does dynamic loop scheduling work?

Answer 21

iterations divided into pieces of size chunk, when a thread finishes its chunk it is given another to work on.

Question 22

How does guided loop scheduling work?

Answer 22

Dynamic scheduling with decreasing chunk size. for chunk=1 chunk size is proportional to the number of unassigned iterations divided by the number of threads in the team. chunk=k sets minimum chunk size.

Question 23

What is interconnect?

Answer 23

Compute nodes are linked by an interconnect which carries these messages. the time spent communicating needs to be minimised to achieve high parallel efficiency and scale to large numbers of processors.

Question 24

What are two types of interconnect?

Answer 24

1. Gigabit ethernet
2. Infiniband

Question 25

How do network topologies affect latency?

Answer 25

The number of hops between nodes affects latency. Ideally, every node is connected to every other node, but this only works for smaller networks. Bus or ring are simple but don't provide enough connectivity. More sophisticated topologies are used.

Question 26

What network topology is common im HPC systems?

Answer 26

Fat Tree

Question 27

How does MPI process placement affect overhead?

Answer 27

MPI processes within the same node can communicate faster than processes on different nodes. The speed of communication between processes on different nodes depends on network connectivity. The placement of MPI processes can be optimised to reduce communication time.

Question 28

What are the main transmission time factors?

Answer 28

1. Number of hops between nodes 2. Blocking factor of the network 3. Other network traffic

Question 29

How is transmission time calculated?

Answer 29

t = L + (M/B) where L is the latency, M is the message length, B is the bandwidth.

Question 30

What is super-linear speed up?

Answer 30

While applying domain decomposition, an important data structure becomes small enough to fit into memory cache, resulting in a sudden performance increase.

Question 31

How do the ration of halo points to domain points scale?

Answer 31

1/N

Question 32

What are parallel overheads?

Answer 32

They are the extra work required to run a program in parallel. MPI has explicit overheads but they are less obvious in OpenMP.

Question 33

How are parallel overheads incorporated into Amdahl's Law?

Answer 33

An overhead (np)v is added to the parallel run time