The Multithreaded DAG Model

Directed acyclic graph(DAG)

operations
dependence edges

PRAM
memory
Scheduling: assigning ops to procs

the span of each DAG
line: O(n)
tree: O(log n)

Work-Span Laws
W(n)/D(n): Average available parallelism

for(iy=2; iy