Critical Path

The critical path is the longest chain of dependent work in a task graph. It sets the minimum runtime given dependencies, and no amount of parallelism shortens it. Covered in ECE459 L13.

Why draw the DAG?

It makes parallel opportunities visible: tasks with no mutual dependency can run concurrently. It’s also useful for explaining parallelism to non-technical stakeholders.

Example from L13: B depends on A; D depends on B and C; C depends on nothing. C can run in parallel with A→B, but the path Start → A → B → D → Finish bounds the total time.

Related concepts

• Work ($T_1$): total time on one processor
• Span / Depth ($T_{\infty }$): critical-path length; runtime with infinitely many processors
• Brent’s theorem: $T_P\le T_1/P+T_{\infty }$. Theoretical max speedup is $T_1/T_{\infty }$

Shortening the critical path

• break long RAW dependency chains (parallel prefix sum, reduction trees)
• hoist loop-invariant work out
• use speculation to start dependent work early

Related

• Data Dependency
• Amdahl’s Law