Work and critical path
Tag: work-critical-path
Aliases: T1 and T-infinity, average parallelism
Work T1 is the time to run a computation on one processor; critical path T_inf is its dependence-graph depth (time on infinitely many processors). Average parallelism is T1/T_inf, and a p-wide machine takes at least max(T1/p, T_inf) time.