A dataflow recalculation has many independent cells but barely speeds up on more workers — what explains that?
answer
- independence permits, it does not cause
- graph depth bounds the gain
- the chain is the serial fraction
- tiny cells lose to scheduling
- hidden edges serialise silently
basics
~20 sIndependence licenses concurrency; it does not create it. Speedup is bounded by the longest dependency chain through the graph, by per-cell work too small to repay scheduling, and by hidden edges that serialise cells the engine believed were independent.
solid answer
~40 sThe count of independent cells is the wrong number to look at. What bounds you is the graph's **critical path** — the most expensive chain of cells, each waiting on the previous one. Total work divided by the cost of that chain is the best speedup any scheduler can reach, however many workers you add; Amdahl's law is the same statement with the chain as the serial fraction. Two things eat what remains: cells whose own work is smaller than the cost of dispatching them, so coordination dominates; and edges the engine cannot see, where two supposedly independent cells touch the same outside state and must be serialised — or are not, and interfere. Measure the critical path before adding workers.
go deeper
Know that cells with no path between them may be evaluated in any order, and that this is a permission the notation gives rather than a speedup it delivers.
Explain why the longest dependency chain caps the gain, and why very small cells can make a pass slower rather than faster once workers are added.
Diagnose a real pass: measure total work against critical-path cost, hunt for hidden edges into outside state, and reshape a chain into a tree where the operation is associative.
Decide whether the model, not the machine, is the thing to change. Reshaping a graph for width costs modelling and testing effort; sometimes accepting a sequential ceiling is the cheaper call.
## What independence actually licenses A dataflow graph is often sold as parallel "for free", and the claim has a precise, limited meaning: if no path runs between two cells, evaluating them in either order, or simultaneously, produces the same values. That is a **permission**. It says the notation will not stop a scheduler from running them together. It does not say a scheduler exists, that it will choose to, or that doing so will be faster. Turning that permission into speed needs three separate things to hold: the graph must be **wide** (many cells ready at once), each cell's work must be **large enough** to be worth handing to another worker, and the engine's picture of the edges must be **complete**. ## The critical path is the ceiling Define two numbers over one pass: - **Total work** — the sum of the evaluation cost of every cell in the stale set. - **Critical path** — the most expensive chain of cells where each reads the one before it. The ratio of the two is the maximum speedup, because no scheduler can begin a cell before its input exists. A chain of 1,000 cells, each reading the previous, has total work equal to its critical path, so the ratio is one and extra workers buy nothing. A sheet of 1,000 cells that each read one source and nothing else has a critical path of two, so it parallelises almost perfectly. This is Amdahl's law wearing dataflow clothes: the chain *is* the serial fraction. The practical consequence is to measure the graph's depth before buying workers, because the depth is a property of how the sheet was modelled, not of the machine it runs on. ## Three reasons the width never arrives 1. **Granularity.** If a cell's evaluation costs less than the bookkeeping to schedule, dispatch and collect it, adding workers makes the pass slower. This is the common surprise in a fine-grained graph: thousands of trivial cells, each a net loss. 2. **Hidden edges.** A cell whose definition reads or writes something outside the graph — a shared counter, a device, a log — has a real dependency the engine did not record. Either you serialise those cells by hand, which removes the width, or you do not, and two of them interfere. 3. **A narrow shape.** Many graphs are long chains without anyone noticing: a running total defined as the previous total plus this reading is a chain of length n, even though the underlying operation is associative and could have been a tree. | symptom | likely cause | what to measure | |---|---|---| | flat speedup past two workers | the critical path dominates | total work divided by chain cost | | the pass slows as workers grow | per-cell work below scheduling cost | mean cell evaluation time | | results vary between runs | an edge outside the graph | which cells touch outside state | | one worker busy, the rest idle | a narrow graph shape | ready-cell count over the pass | ## Widening the graph The fixes are restructurings of the model, not scheduler settings: - **Rebuild a chain as a tree.** A running total over n readings, defined cell by cell, has depth n. The same sum as a balanced tree of partial sums has depth about log2 n — for 1,024 readings, ten levels instead of a thousand. This works only when the combining operation is associative, so check that before reshaping. - **Coarsen the cells.** Merge many trivial definitions into fewer substantial ones so scheduling cost stops dominating. The trade is some of the fine-grained recomputation you were paying for. - **Make hidden inputs into real cells.** Once the outside value is a cell the engine knows about, the edge is recorded, ordering becomes the engine's problem again, and the remaining independence is genuine. ## The judgment an interviewer is listening for The weak answer is "add more workers" or "the engine should parallelise it". The strong one names the ceiling first and only then reaches for the machine: measure the critical path, ask whether the model's shape can change, check granularity against scheduling cost, and confirm that the independence the engine believes in is real. Be willing to conclude that a pass is already at its ceiling — some graphs are honestly sequential, and then the right move is to change what is modelled, not how it is run.
- How would you estimate the ceiling before changing anything?Measure two numbers over one pass: total work across the stale set, and the cost of the critical path — the most expensive chain in which each cell reads the one before it. Their ratio is the best speedup any scheduler can reach at any width. Compare it with the speedup you were hoping for; if the ratio is near one, no amount of concurrency helps and the model itself has to change.
- What restructuring genuinely widens a graph?Turning a deep chain into a shallow tree where the operation allows it: a running total defined as previous-plus-current over n readings has depth n, while a balanced tree of partial sums has depth about log2 n. That requires an associative combining operation. Coarsening very small cells so scheduling stops dominating, and turning hidden inputs into modelled cells, are the other two levers.
saying these in an interview costs you the question
- Says a dataflow graph parallelises itself with no ceiling.
- Counts independent cells and predicts speedup from that count.
- Ignores the longest dependency chain when estimating the gain.
- Assumes per-cell work always repays the cost of scheduling it.
- Calls a cell that touches outside state independent of the rest.