The order that has a depth

The same table, filled two ways established that a recurrence says what a cell depends on and does not say when to compute it, that at least three orders satisfy the dependencies, and that all three produce a table agreeing cell for cell. It ended with a sentence it could not measure: that a bottom-up fill in anti-diagonal order can be run in parallel and a top-down one cannot.

Every count on this site is a total. Comparisons, swaps, cells, transfers, random bits — each is a sum over everything the algorithm did, and a sum is silent about what had to wait for what. A table is the one place where the missing quantity is exact, needs no model of a machine, and is the same integer on every computer that has ever run the computation.

It is exact because a table’s dependencies are written down. Nothing has to be inferred about which operations could overlap: cell $(i,j)$ reads three named cells, those three read three each, and the whole structure is a directed acyclic graph that the recurrence spells out. The quantity this page adds is the longest path in that graph, and the reason it can be added now rather than earlier is that it is the first place in this collection where the dependency structure is a datum rather than a guess.

Three numbers where there was one #

The quantities separate cleanly and each deserves its own name.

The cells are what this field has counted since its first plate: how many subproblems were given a value. It is a property of the recurrence and the input, and no fill order changes it.

The span is the length of the longest chain of cells, each depending on the one before. For edit distance it is exactly $n + m + 1$: cell $(i, j)$ depends on cells whose index sum is smaller, so the sum increases by at least one along any chain, and a chain from $(0,0)$ to $(n,m)$ can increase it by exactly one each step. It is a property of the recurrence alone. No schedule can finish in fewer rounds than this, whatever hardware is available, and it is computable by looking at the arrows.

The steps are what a given order achieves: how many rounds the fill takes when cells the order has already placed together are allowed to run together. It sits between the span and the cells, and it is the only one of the three that the order controls.

The gap between the cells and the span is the parallelism the recurrence contains. The gap between the span and the steps is how much of it an order throws away.

It is worth checking the definition against the null case, because a measure that reported something interesting about a computation with no parallelism in it would be measuring itself. An insertion sort’s dependency chain runs through every element it moves; a binary search’s runs through every probe; both have a span equal to their work, and both should. Here row order’s span-per-order is 91 against 100 cells, which is nearly equal and not exactly — the small gap is real and is explained two plates below — and anti-diagonal order’s is 19 against 100. A measure that gave 100 and 19 would have been suspiciously tidy.

Why row order is sequential and diagonal order is not #

The reason is one dependency arrow and it is easy to lose.

Cell $(i, j)$ reads $(i-1, j-1)$, $(i-1, j)$ and $(i, j-1)$. Two of those are in the row above. The third is the cell immediately to the left, in the same row. So a row is not a set of independent cells; it is a chain of them, and filling a row is $m$ sequential steps however many processors are watching.

Anti-diagonal order groups cells by $i + j$. Every dependency of a cell on diagonal $d$ has index sum $d-1$ or $d-2$, and no cell on diagonal $d$ depends on another cell on diagonal $d$ — because two cells with the same index sum cannot be one step apart in the required direction. So a diagonal is genuinely a set, all of it can go at once, and there are $n + m + 1$ diagonals.

Column order is the transpose of row order and behaves identically: ninety-one steps on the same hundred cells, for the same reason with the arrow rotated.

The last column is the one that says what the parallelism is worth: under anti-diagonal order the widest round holds ten cells, so ten workers can be busy at the peak and rather fewer at the ends. The average is a hundred cells over nineteen rounds, about five.

The general rule those three orders are instances of is worth extracting, because it is what carries to other recurrences. An order permits a round exactly where it groups cells that are mutually independent. Row order groups by $i$, and cells sharing an $i$ are chained by the left-neighbour arrow. Anti-diagonal order groups by $i+j$, and cells sharing $i+j$ have no arrow between them. So the question for any recurrence is which linear function of the indices its arrows all increase, and the level sets of that function are the rounds. For edit distance that function is $i+j$; for a recurrence whose arrows reached two rows back it would still be $i+j$ but the rounds would be two diagonals apart; for a recurrence with an arrow inside a diagonal there would be no such function and no parallel schedule at all.

What the three numbers say about three familiar algorithms #

The measure is worth taking outside this table for a moment, because its value is in the comparisons it makes possible and a single computation cannot show them.

A scan — summing an array, finding a maximum — has work $n$ and span 1 if the combining operation is associative, because the elements can be added in any grouping. That is the extreme case: all of the work is available at once, and a tree of additions finishes in $\log n$ rounds with $n$ workers.

A binary search has work $\log n$ and span $\log n$. Every probe’s address is computed from the previous probe’s outcome, so the chain is the whole computation and there is no parallelism at any width. It is the opposite extreme, and it is the reason a search is a poor fit for a machine with many workers however cheap each probe is.

A merge sort has work $n \log n$ and a span dominated by the final merge, which is sequential in the standard implementation and $n$ long. Its ratio is therefore about $\log n$ — genuinely parallel, and far less so than the $n/2$ this table offers, which is the sort of comparison the two numbers exist to make.

Placing an edit-distance table beside those three puts it near the useful end: work $nm$, span $n+m$, ratio about $n/2$. What makes it worth measuring rather than asserting is that the ratio depends on the shape of the table as well as its size — a long string against a short one has span dominated by the long one and work by the product, so a pattern of twenty characters against a text of a million has a ratio of about twenty rather than of half a million. The parallelism available is a property of the inputs’ proportions, and no statement of the algorithm’s class mentions them.

What the span is a bound on, and what it is not #

The span is a lower bound on rounds, and it is worth being exact about what a round is, because the temptation to read it as time is strong and wrong.

A round here is one layer of the dependency graph: a set of cells, none of which needs anything another member of the set produces. Saying the computation takes nineteen rounds says that nineteen layers must happen in order. It does not say that a machine with ten processors finishes in nineteen units of anything, because a round’s cells have to be distributed, the results have to be visible to the next round, and both of those cost something this counter does not model.

What the pair of numbers does support is a ratio. Work over span — 100/19 here, and $nm/(n+m)$ in general, which is about $n/2$ on a square table — is the maximum number of workers that could be usefully employed, and it is a property of the problem. On two strings of a thousand characters the ratio is about five hundred, so a machine with five hundred workers could in principle be kept busy and one with five thousand could not. That is a real and useful statement, it is exact, and it required no clock.

It is also the honest limit of the measurement, and this field’s version of the standing caution: the count is not the time, and a round is no more a duration than a comparison or a block transfer is.

There is a second use for the pair that has nothing to do with parallel machines, and it is the one a sequential programmer should care about. The span is also the length of the longest chain of dependent memory reads, and a dependent read is the one thing a modern processor cannot hide: it can execute out of order, issue several loads at once and predict branches, but it cannot fetch a value whose address it does not yet have. So the ratio of work to span is, roughly, how much instruction-level parallelism the computation offers a single core — and the anti-diagonal fill offers a great deal more of it than the row fill, on one processor, with no threads involved. That effect is real, it is what makes vectorised alignment implementations diagonal rather than row-major, and it is invisible in every count on this site including this one.

The order was already load-bearing, and now it carries a third thing #

This is the third distinct property the choice of fill order has turned out to decide, and setting the three beside each other is the point of this rung.

The order decides what can be released. The table nobody has to keep showed that row order permits a two-row frontier, column order permits two columns, and anti-diagonal order permits three diagonals — which on a square table is the smallest of the three. The space an algorithm needs is a property of a decision the recurrence does not record.

The order decides what can be skipped. A top-down recursion computes only the cells some later cell will ask for, which on a knapsack is a small fraction of the table; a bottom-up fill computes them all because it has no way to know. That is a property of the same decision, seen from the other side.

And the order decides the depth. Which is this page, and which is the one that costs nothing to have. Row order and anti-diagonal order compute the same cells with the same dependencies; anti-diagonal order takes a fifth of the rounds.

Three properties, one decision, and the decision appears nowhere in a statement of the recurrence. A recurrence is a specification and an order is an implementation, and the collection has now measured three separate consequences of confusing them.

There is a fourth that this field has met without naming it as one. A band as wide as the answer computes a strip of anti-diagonals, and the reason a band is walkable at all is that the band is a set of consecutive diagonals in this ordering — so the technique that prunes the table by a bound is expressed in the coordinate system this page is about, and could not be expressed in row order without care. The order was doing work there too, silently, three rungs before anybody measured it.

Why a top-down fill has no useful depth at all #

A memoised recursion computes the same cells and cannot be laid out in layers, and the reason is structural rather than incidental.

The recursion’s control flow is its dependency order: it asks for a subproblem, waits, asks for the next. A schedule that ran two of its calls at once would have to know in advance that neither needs the other’s answer, and knowing that is exactly the analysis a bottom-up fill has already done by choosing an order. So the top-down version’s step count is its call count, its span is the recursion depth, and the two are separated by the branching factor rather than by anything about the table’s shape.

That is the same trade the same table, filled two ways already measured in another unit — a top-down fill asks the table half a million questions and recurses four hundred frames deep — and the depth measurement puts a third column beside those two. The strategy that skips unreachable cells is the one that cannot be laid out in rounds, and the strategy that computes everything is the one that can. Neither dominates, which is the position that essay reached from the space side and this page reaches from the depth side.

What this does not measure #

Three things, and the first is the one that would change an implementation’s behaviour.

Nothing here is charged for communication. Nor for the memory the schedule needs: the frontier a rolling fill can keep is defined by the order, and the table nobody has to keep measured three diagonals for the anti-diagonal order against two rows for row order — so the order with the best depth is not the order with the best space on every table shape, and the two have to be traded rather than optimised separately. A round’s worth of cells has to be given to workers and its results made visible to the next round, and on any real parallel machine that cost is the whole difficulty. The measurement here is of an idealised schedule with free coordination, which makes it a bound rather than a prediction — the same status every floor on this site has.

The band is not swept. A banded fill computes a strip of cells rather than a rectangle, so its cell count falls to $O(nk)$ while its span stays at $n+m+1$, and the ratio between them collapses. Cutting the work does not cut the depth, so a banded computation has less parallelism available than a full one, which is a genuine and slightly perverse consequence: the cheaper algorithm is the harder one to spread out. That is measurable with what is already here and is not on any plate.

The rounds are counted, and their contents are not. Nineteen rounds of unequal width is not the same computation as nineteen rounds of equal width, and the plate reports the widest but not the distribution. On a square table the diagonal lengths rise linearly to the middle and fall again, so half the rounds have fewer than half the peak’s cells, and a machine sized for the peak is idle for most of the run. That is a real inefficiency with an exact description available from what is already computed, and it is the sort of thing on average is not a number is about — a mean over rounds hides a shape that decides the answer.

And the word machine is a different question. A column computed in machine words computes sixty-four cells in one machine word, which is parallelism of a kind this counter cannot see at all — it is inside the operation rather than between operations, and the span of a Myers column is the number of columns whatever the word size. Two kinds of parallelism, one visible here and one visible in that essay’s count of word operations, and no single number holds both.

Where this ladder goes next: the cells that were never worth having #

Everything on this page takes the cell count as given and asks what can be done about the order. The other question is whether the cells were the right cells.

The recurrence’s subproblem set — every pair of prefixes — is a choice, and it is the obvious choice rather than a forced one. For a longest common subsequence, only the cells where the two characters agree can lengthen anything; there are $r$ of those and $r$ is about $nm/\sigma$ for an alphabet of $\sigma$ symbols. A method that enumerates exactly those pairs and places each one by a search over the answers found so far computes $r$ subproblems rather than $nm$, which on English text is a twenty-fifth of the rectangle.

Two things make that the right next rung. It is a change to the first factor of the cost — the one this field has treated as fixed since it started counting cells — where the previous two rungs both attacked the second. And it fails informatively: on a two-letter alphabet $r$ is about half of $nm$ and the method is strictly worse than the grid it replaces, by the logarithm it added. A technique whose losing case is as easy to exhibit as its winning one is worth having on a site that measures rather than recommends.