An ordering that buys processors, not time

The order decides the memory put nested dissection third of four orderings on the grid Laplacian, behind the heuristic with no guarantee at all, and said the crossover where its asymptotics would pay lay beyond the largest grid it could draw. The least fill there is then found minimum degree’s factor to be the smallest possible on every grid small enough to search. Between them they leave nested dissection looking like an ordering whose only virtue is a proof about grids nobody draws.

That reading measures the wrong resource. Nested dissection was never mainly an ordering for serial memory. It numbers each separator after both halves it separates, so the two halves can be factorised independently, and the halves of the halves, down to the leaves. The quantity that describes that independence is not the fill and not the total work. It is the shape of the elimination tree, the structure a factorisation that runs subtrees in parallel works along, and its most expensive path from a leaf to the root.

Read that way, the comparison changes and does not reverse. Nested dissection is not faster on unbounded processors at these sizes — its critical path is about minimum degree’s, sometimes shorter and sometimes longer. It does substantially more work to arrive at the same time. What it buys with the extra work is room for processors: the ratio of total work to critical path, which bounds the speedup a parallel factorisation can reach, grows with the grid under nested dissection and stays flat under minimum degree.

The elimination tree, and the path that sets the time #

The elimination tree of a Cholesky factorisation has one vertex per column, and column j’s parent is the first row below the diagonal in which column j of the factor has an entry. The tree says which columns must wait for which: column j can only be eliminated once every column in its subtree has been, and columns in disjoint subtrees never need each other. A factorisation that gives each subtree its own processor finishes when the most expensive chain of dependent columns finishes.

The work of eliminating column j is taken, as in the first essay, as the square of its column count $c_j$ — the arithmetic of the rank-one update it applies to the columns below it — so the total work is Σ$c_j^2$. The critical path is the largest sum of $c_j^2$ along a path from a leaf to the root: on unbounded processors, with nothing charged for moving data between them, it is the time. Total work divided by the critical path is the largest speedup any schedule on that tree can reach.

Two things are left out of that model and both favour the claim being tested. It charges nothing for communication, which on a real machine is the cost the message and the word measures; and it treats a column as indivisible, where a real code splits the arithmetic of one heavy column across processors too. The first makes every parallel ordering look better than it is; the second makes a tree with one very heavy root column look worse. The comparison between two orderings on the same model is what the measurement is for.

Nested dissection does more work to finish at the same time #

The five grids from 8 to 24 points a side give one consistent picture.

Nested dissection’s total work is 44 to 78 per cent larger at every size — 1.44 times at k = 8, 1.78 at 12, 1.44 at 16, 1.68 at 20 and 1.53 at 24. That is the first essay’s finding in the currency of arithmetic, where it found it in entries, and the square law it found between the two holds here as well: the factors of nested dissection, 21 to 38 per cent larger, cost about the square of that in work.

Its critical path is not systematically shorter. It is 10 per cent longer at k = 8, 28 per cent longer at 12, 17 per cent shorter at 16, 6 per cent longer at 20 and 15 per cent shorter at 24. The sign changes three times in five sizes, which is what two quantities of the same size look like when each is set by one unlucky column: minimum degree’s critical path at k = 16 is longer than at k = 20 relative to its total, because its heaviest chain happens to run through a large late column at that size. On unbounded processors the two orderings finish in about the same time at every size drawn.

And what the extra work buys is a larger ratio #

Divide the two columns of each ordering and the separation that the times did not show appears.

Nested dissection’s speedup bound is 2.70, 3.18, 3.75, 4.17 and 4.52 at k = 8, 12, 16, 20 and 24: it grows at every step, by a smaller amount each time, and on this range it rises roughly like the logarithm of the number of unknowns. Minimum degree’s is 2.07, 2.28, 2.17, 2.63 and 2.52 — no trend, and never above nested dissection’s smallest.

That is the whole of nested dissection’s case at these sizes, stated as a trade. On one processor it costs 44 to 78 per cent more arithmetic. On unbounded processors it costs about the same time. And the number of processors it can keep busy grows with the problem, where minimum degree’s stays at two or three however large the grid. A factorisation that is going to run on a few processors should be ordered by minimum degree; one that is going to run on many is paying for nested dissection’s extra work with idle processors it would otherwise have.

The mechanism is visible in what the two orderings put at the top of the tree. Nested dissection eliminates the top-level separator last, as a dense block whose columns form a chain; everything below it splits into two independent subtrees, and each of those into two more. Most of the work is in the separator blocks, and the separator blocks at each level are disjoint. Minimum degree eliminates cheap vertices first wherever they are, and its late eliminations join regions that were never separated — its tree is less a binary splitting than a long trunk with short branches, so a large share of its work lies along a single chain.

The two counts usually quoted do not separate them #

A parallel ordering is usually described by the height of its elimination tree, and a factorisation’s memory peak by its widest column. Neither tells the two orderings apart.

The tree heights are 23 against 24, 36 against 36, 54 against 48, 64 against 60 and 81 against 72. Nested dissection’s tree is shorter at the three largest sizes by 11 per cent at most, and the natural order’s — a path through all $k^2$ vertices — is seven to eight times taller than either. Height counts columns rather than work, so it treats a separator column of count thirty and a leaf column of count three as the same one step, and it is the work along the path rather than its length that the time depends on.

The widest columns are 11 and 11, 17 and 17, 24 and 23, 29 and 29, 38 and 35 — the size of the dense block each ordering must hold at its worst step, the same to within a column at four sizes of five. The natural order’s widest column is only k + 1, because its factor is banded, and it pays for that in a tree that is a single path and a factor 1.7 to 2.9 times the size of either heuristic’s. The fill that is not independent found that the dense block on a separator is compressible — its off-diagonal part has low numerical rank — which is a reason the widest column overstates what a hierarchical code must store, and a reason it is the same for both orderings here.

The fill each ordering pays for its tree #

The tree’s shape is bought with fill, and the fill is what the first essay drew. At sixteen points a side it is the whole cost of nested dissection’s larger ratio in one picture.

On the 16×16 grid minimum degree’s factor holds 2,179 entries and nested dissection’s 2,720, 25 per cent more; reverse Cuthill–McKee’s holds 3,096 and the natural order’s 4,111. Those are the same orderings whose trees the previous figures measured, and the ranking by fill is the ranking by total work: minimum degree first, nested dissection second, the two band orderings last. Where the rankings part company is the tree. Reverse Cuthill–McKee and the natural order both produce a factor that is a band, and a band’s elimination tree is a single path — every column’s parent is the next column — so their critical path is their total work and their speedup bound is exactly one. Neither can use a second processor for anything at all.

So the four orderings sort into three kinds on this reading. The band orderings buy a simple storage scheme and no parallelism. Minimum degree buys the least fill — the least possible on the grids small enough to check — and a modest, flat speedup bound of two or three. Nested dissection buys a speedup bound that grows with the grid and pays a quarter more fill and half again the work for it. Which of those is worth having depends on the machine, not on the matrix, and a single fill table cannot say.

Why the dissection’s work sits at the top of its tree #

The growth of nested dissection’s ratio has a structural reading that the separator argument gives directly, and it is worth stating because it is the reason to expect the growth to continue past the grids drawn here.

Each level of the dissection numbers a separator after the two regions it separates, and nothing in one region is coupled to anything in the other until the separator is eliminated. The factor is not sparse established that fill stays inside those regions and their separators; the elimination tree records the same fact as independence, with each region a subtree and each separator a chain of columns above them. The work of a separator’s columns is the square of their counts, and a separator’s columns are the densest in the factor, so most of the arithmetic sits in the separators, and the separators at each level are disjoint.

That makes the critical path a path through one separator per level — the heaviest at each — while the total is every separator at every level. A grid twice as wide has one more level of dissection, so its critical path gains one more separator’s work and its total gains a whole level’s. The ratio between them grows with the number of levels, which grows like the logarithm of the number of unknowns: the shape the measured bound has, 2.70 to 4.52 over a factor of nine in unknowns.

The same shape turns up wherever this field has divided a computation in halves. The recursion that was never told the memory split an elimination’s columns in half to serve every cache size at once, and a reduction that changes the order arranged a tall-skinny QR as a binary tree of small factorisations so that sixteen processors could each touch their part once. A tree of independent halves is how an algorithm makes room for hardware it was not told about, and it pays for the room in extra arithmetic every time. Memory bought with messages measured that price in the currency of communication, which is the one this model leaves out.

What the grid sizes can and cannot say about the crossover #

The first essay located nested dissection’s crossover on fill “further out than this figure reaches”. The measurement here does not locate it either, and it adds a qualification about what the crossover would be a crossover of.

Fill and total work. Nested dissection’s disadvantage in both shows no sign of closing between 8 and 24: its factor is 21, 38, 25, 38 and 37 per cent larger, and its work 44, 78, 44, 68 and 53 per cent. The irregularity is the separators: the implementation cuts at the middle row or column, and on a grid whose side is a power of two plus a little the pieces come out unevenly. A multilevel partitioner would do better on both counts, and nothing here measures one.

The critical path. No crossover to find — the two are the same size, with the sign changing.

The speedup bound. Nested dissection is ahead at every size and pulling away. If there is a crossover it is in the other direction, and it is not in sight.

So “nested dissection wins asymptotically” is a sentence with three possible subjects, and on the grids a person can factorise on one machine it is true of the one nobody reading a fill table is looking at. A block size is a property of the machine made the same point about a different elimination: the cost that decides the choice is a property of where the arithmetic runs, and a count taken for one machine chooses wrongly for another.

What the model leaves out #

Every number here is a count on a model. The work of a column is its count squared, which is the arithmetic of a right-looking update and ignores that a supernodal code runs dense blocks at a far higher rate per operation than it runs scattered updates; nested dissection’s large separator blocks are exactly where that rate is highest, so the model understates its advantage in wall-clock time on one processor. Communication is free, which overstates both orderings’ parallel speedup and nested dissection’s more, since its parallelism is spread across more processors that must exchange boundaries. Rounds and words is the collection’s measure of that cost, and folding it into the critical path is the measurement that would turn a bound into a prediction.

What was not measured #

Only grids, only square ones, and only the simple nested dissection that cuts at the middle; a graph with a small separator that is not a line, or a partitioner that finds a better one, would change nested dissection’s numbers and not minimum degree’s. Only the two heuristics; approximate minimum degree and the hybrids production codes use — nested dissection at the top levels, minimum degree below — are not drawn, and a hybrid is presumably designed to keep most of this essay’s speedup bound for less of its extra work. Only up to 24 points a side, where the dense symbolic factorisation this measurement uses is still affordable.

Still open: communication on the critical path, the hybrid ordering, and where the speedup bound levels off #

Charging for messages. A critical path that adds, at each separator, the cost of moving the boundary data between the processors on either side would turn the speedup bound into something closer to a speedup. The measurement is whether nested dissection’s growing ratio survives a cost proportional to the separator sizes, which grow with the grid too.

The hybrid. Nested dissection to a chosen depth and minimum degree on the pieces is what codes ship. Sweeping the depth at which it switches would put the two numbers measured here — total work and speedup bound — on one curve, and say whether there is a depth that keeps most of nested dissection’s ratio for most of minimum degree’s work.

The bound’s growth. From 2.70 to 4.52 over a factor of nine in unknowns is consistent with a logarithm and with a slow power. Grids past 24 need a sparse symbolic factorisation rather than the dense one used here, and with it the measurement of whether the bound keeps growing like the depth of the dissection, which is what the separator argument would predict.