3 - Design and Analysis of Parallel Algorithms Flashcards
1
Q
critical path length
A
is the length of the longest series of operations that have to be performed sequentially due to data dependencies
2
Q
parallel work
A
max. number of instructions performed by all procs during executions of A, where in each (parallel) time step as many processors are available as needed to execute the step in constant time.
3
Q
parallel time
A
max. number of parallel steps needed under the same circumstances
4
Q
parallel cost
A
t(n)*p(n) where p(n) = max. number of processors used in a step of A
