Parallel Performance Modeling Flashcards
What is parallel speedup?
Sp = T1 / Tp
The measure of performance improvement achieved by using multiple processors in parallel.
What is ideal speedup?
SIp = 1 / p
The theoretical maximum parallel speedup that could be achieved.
What is parallel efficiency?
Ep = Sp / p
Measure how far we are from the ideal speedup.
What is the serial fraction?
The fraction of the program cannot be parallelized.
What is Brent’s Theorem?
Tp <= t + (m-t) / p
m = number of tasks
t = critical path
p = number of processors
What is PRAM Model?
Parallel Random Access Machine: Every memory location is accessible to any processor.
What is an EREW PRAM model?
Exclusive read, exclusive write PRAM.
Only one processor at a time can read or write.
Limitations of the PRAM model?
Unrealistic and Perform poorly.
What is Bulk Synchronous Parallel Model?
Orders the program into a sequence of supersteps, each ending with a barrier synchronization.
What are the 3 components of a super-step in the BSP model?
Local Computation
Global Communication
Barrier Synchronization
How is the execution time of a super-step in the BSP model calculated?
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.
What is an h-relation
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.
How is the execution time of a super-step in the BSP model calculated?
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.
What 3 architectural parameters are used to describe the BSP model?
P = number of processors,
G = bandwidth parameter
L = barrier synchronization latency
What is super-linear speedup?
When the speedup is larger than the number of processors
What is parallel overhead?
The time to coordinate and manage the program on multiple processors in parallel.
The time difference between experimental and ideal speedup.
What are the reasons that superlinear speedup is sometimes observed?
Net cache increases with more processors, thus decreasing cache miss rate which is responsible for a superlinear speedup.
