Parallel Performance Modeling

Question 1

What is parallel speedup?

Answer 1

Sp = T1 / Tp

The measure of performance improvement achieved by using multiple processors in parallel.

Question 2

What is ideal speedup?

Answer 2

SIp = 1 / p

The theoretical maximum parallel speedup that could be achieved.

Question 3

What is parallel efficiency?

Answer 3

Ep = Sp / p

Measure how far we are from the ideal speedup.

Question 4

What is the serial fraction?

Answer 4

The fraction of the program cannot be parallelized.

Question 5

What is Brent’s Theorem?

Answer 5

Tp <= t + (m-t) / p

m = number of tasks
t = critical path
p = number of processors

Question 6

What is PRAM Model?

Answer 6

Parallel Random Access Machine: Every memory location is accessible to any processor.

Question 7

What is an EREW PRAM model?

Answer 7

Exclusive read, exclusive write PRAM.

Only one processor at a time can read or write.

Question 8

Limitations of the PRAM model?

Answer 8

Unrealistic and Perform poorly.

Question 9

What is Bulk Synchronous Parallel Model?

Answer 9

Orders the program into a sequence of supersteps, each ending with a barrier synchronization.

Question 10

What are the 3 components of a super-step in the BSP model?

Answer 10

Local Computation
Global Communication
Barrier Synchronization

Question 11

How is the execution time of a super-step in the BSP model calculated?

Answer 11

tStep = max(wi) + mg * max(hi) + l

Wi = time for local work on processor i
Hi = number of incoming or outgoing messages for processor i
M = message size
G = BSP bandwidth parameter.
L = BSP latency parameter.

Question 12

What is an h-relation

Answer 12

A communication pattern whose properties are summarized by the parameter h.

h is the larger number of incoming or outgoing interactions in a communication step.

Question 13

How is the execution time of a super-step in the BSP model calculated?

Answer 13

tStep = max(wi) + mg * max(hi) + l

Wi = time for local work on processor i
Hi = number of incoming or outgoing messages for processor i
M = message size
G = BSP bandwidth parameter.
L = BSP latency parameter.

Question 14

What 3 architectural parameters are used to describe the BSP model?

Answer 14

P = number of processors,
G = bandwidth parameter
L = barrier synchronization latency

Question 15

What is super-linear speedup?

Answer 15

When the speedup is larger than the number of processors

Question 16

What is parallel overhead?

Answer 16

The time to coordinate and manage the program on multiple processors in parallel.

The time difference between experimental and ideal speedup.

Question 17

What are the reasons that superlinear speedup is sometimes observed?

Answer 17

Net cache increases with more processors, thus decreasing cache miss rate which is responsible for a superlinear speedup.