GUST: Graph Edge-Coloring Utilization for Accelerating Sparse Matrix Vector Multiplication

Accelerators for multiplying a mostly-empty matrix by a vector bind each arithmetic unit to one row of the matrix, so a unit whose row has run out of work sits idle while a busier row queues — utilisation on real matrices lands near a tenth of one percent; GUST (Maryland) unbolts the multipliers from the adders and puts a crossbar between them so any multiplier can feed any adder, then avoids the resulting collisions by noticing that the sparsity pattern is known in advance and the whole scheduling question is a textbook graph-colouring problem.

Why this problem is worth solving

The number nobody quotes is the one that matters.

The scheduling question turns out to have a textbook answer.

What people did before, and where it broke

• Stream the matrix through a one-dimensional systolic array. A strip of processing elements, each holding a running sum for one row, with values flowing along and results dumped at the end. The classical design, dating to 1978. Where it broke. Every element occupies a unit for a cycle whether or not it is a real value, and the majority of the stream is zeros, so utilisation measures 0.08 percent on real matrices.
• Repurpose a two-dimensional matrix engine. Recent work maps only the non-zeros onto a grid and inserts marker elements to track where one row ends and the next begins. Where it broke. Units idle whenever their stored column index does not match the vector element passing by, and each pass through the grid costs three phases — loading, calculating, dumping — so the measured utilisation is 1.45 percent.
• Feed a balanced adder tree. Multipliers across the top, halving layers of adders beneath, computing one dot product per pass. Where it broke. Each element still occupies a multiplier and an adder for a cycle, and most elements are zero, so it lands at the same 0.08 percent as the systolic array.
• Reduce opportunistically in a tree of matching units. A tree design forwards partial products upward with their row indices, accumulating whenever indices happen to match and passing the rest along. Where it broke. The upper layers must be provisioned for the worst case, which caps achievable utilisation at a quantity that shrinks as the tree grows; measured, it reaches 4.67 percent — the best of the prior designs and still under a twentieth.
• The gap. Every one of these successfully removes the zeros from the stream, and every one keeps a static allocation underneath: a unit belongs to a row, or to a column, for the duration. Sparsity is irregular precisely in that some rows have far more work than others, so a fixed allocation guarantees that some units are starved while others queue, no matter how well the zeros are compressed away.

How a crossbar and a colouring replace a stalled pipeline

The idea

The units were never the scarce thing; the permission to use them was. Every prior design attacks the same symptom, which is that zeros occupy hardware, and every one leaves the underlying arrangement untouched: a processing element belongs to a row, a multiplier belongs to a column, a layer of an adder tree belongs to a fixed group of them. That arrangement is what converts irregular sparsity directly into idleness, because sparsity being irregular means exactly that some rows carry many times the work of others, and a unit bound to a light row has nowhere to lend itself. Splitting the multiplication from the accumulation and putting a crossbar between the two banks removes the binding: a product computed anywhere can be steered to the adder that owns its row, so a dense row can consume as many multipliers as are free. The result on real matrices is 33.67 percent of units busy against 4.67 for the best prior design, an improvement of roughly seven times in the metric that everything else was already trying to improve. Breaking a fixed one-to-one pairing so that provisioned hardware stops idling is the same move the reconfigurable array work covered elsewhere on this site makes when it stops giving every arithmetic unit a private router and has three of them share one.

The collisions look like a runtime arbitration problem and are not one. Sharing creates a hazard immediately: two elements of the same row reaching the crossbar together both want the same adder, and one is lost. Handling that by stalling is the obvious response and it is a disaster — the paper reports that with stalling, this hardware is slower than the plain systolic array once density passes eight in a thousand. What rescues it is that nothing about the hazard is dynamic. The positions of the non-zeros are fixed properties of the matrix, known long before any vector arrives, so the order can be decided in advance. Written as a graph with rows on one side, columns on the other, and an edge per non-zero, the constraint is that no two edges meeting at a vertex may be processed together — which is the definition of a proper edge colouring, a problem studied since the 1960s. The theory hands over more than an algorithm: it gives the exact schedule length, since for a bipartite graph the colours required equal the largest number of edges at any single vertex. Recasting a cost that looks unavoidable into a structure whose mathematics is already understood is the same manoeuvre the causal-ordering data structure work covered elsewhere on this site performs when it replaces a flat array scanned in full with a tree shaped like the dependencies themselves.

Because the cost is a maximum rather than a sum, the enemy is variance. This is the consequence that decides how well the idea actually works. The schedule for a group of rows takes as many cycles as the busiest row or column group within it has entries, so a group containing one very heavy row and several light ones wastes almost all of its width. Reducing the total number of non-zeros would not help; reducing their spread does. The fix is deliberately cheap — sort the rows by how many entries they hold, sort the column groups within each partition the same way, and reverse the ordering of alternate groups so that heavy and light are interleaved rather than stacked. That last step is the kind of trick that looks arbitrary until you notice it is pairing the largest with the smallest. It is worth 1.8 times on top of the colouring alone, and it explains the paper’s most honest result: performance is markedly better on uniformly distributed matrices than on power-law ones, because power-law is the distribution whose entire character is a few enormously heavy vertices. Discovering that skew, not volume, is what sets the cost is the same finding the near-data load-balancing work covered elsewhere on this site reports when real data turns some units into hotspots while their neighbours idle.

Following one sparse matrix from disk to output vector

Folding means several matrix columns map to one vertex of the graph, which is why the graph can have more than one edge between the same pair of vertices.

Why it works

• Sparsity is irregular in exactly the way a fixed allocation cannot absorb. Compressing the zeros out of the stream still leaves rows with wildly different amounts of work → and a unit bound to a light row cannot lend itself to a heavy one → so the units starve unevenly, which is why designs that all succeed at removing zeros still measure between 0.08 and 4.67 percent utilisation.
• Separating multiply from accumulate is what makes sharing expressible. As long as one unit does both, its identity is tied to a row → but with distinct banks joined by a crossbar steered by the row index, a product computed anywhere can reach the adder that owns its row → so a dense row can consume every free multiplier, and the same hardware reaches 33.67 percent.
• The hazard is static, so it can be scheduled away rather than arbitrated. Two elements of one row arriving together would collide, and stalling on that is worse than not sharing at all → but the positions of the non-zeros are a fixed property of the matrix, fixed long before any vector arrives → so the entire order can be decided once, offline, with no runtime cost and no collisions remaining.
• The constraint is literally a graph colouring, so the theory comes free. Rows and columns as the two sides of a bipartite graph, non-zeros as edges, one colour per time slot → gives both an algorithm, repeatedly stripping off a set of edges sharing no vertex, and a cost formula, since the colours needed equal the most edges at any vertex → which turns the schedule length into a quantity that can be reasoned about analytically rather than only measured.
• A dense input stream converts idle bandwidth into throughput. The reason the systolic baseline is slow is not arithmetic but that it draws a stream mostly made of zeros → whereas a collision-free schedule presents a compact stream and pulls near the card’s full bandwidth → so the speedup tracks one over the density, and holds across a range of densities spanning four orders of magnitude.

What it costs (trade-offs and scope)

• The hardware alone is a regression. With collisions handled by stalling, the design is slower than the plain systolic array once density exceeds eight in a thousand. Scheduling supplies an average of 88 times over the naive version, so essentially all of the benefit is software.
• The headline 411 times is against a very weak baseline. A one-dimensional systolic array at 0.08 percent utilisation is not a serious sparse accelerator. The meaningful comparison is against a state-of-the-art design, where the result is far more modest: lower execution time on seven of nine matrices and lower energy on four of nine.
• The crossbar is the wall. Its area grows quadratically with array length and its power superlinearly. A length-256 instance uses 888 thousand lookup tables against 132 thousand for the systolic baseline, and the clock is set by the longest route across the crossbar — 96 megahertz, against 223 for the design it is compared to. The wins come from cycle count, not from speed.
• The shorter array is better on energy, and the proposed fix is unevaluated. A length-87 instance achieves less speedup but higher energy efficiency than length-256, because of that superlinear crossbar. The suggested remedy is several short arrays in parallel, which the paper does not build and openly notes would raise execution time, since it reduces exactly the sharing the design exists to provide.
• Most of the comparison points are modelled, not built. Only the systolic baseline and the state-of-the-art competitor were synthesised. The utilisation figures for the matrix-engine, adder-tree and tree-reducer designs come from the authors calculating each design’s dataflow per matrix, and one of them is given a different mix of units — 448 adders and 128 multipliers against 256 of each.
• The analytical bound assumes an optimal colouring the algorithm does not guarantee. The derivation takes the number of colours to equal the maximum degree, while the implementation greedily builds one matching per colour without searching for augmenting paths, so it may use more. The bound is also derived only for uniformly random matrices, which is the favourable case.
• The attribution of the bound is loose. The paper cites Vizing’s theorem for the claim that the minimum colours equal the maximum degree. Vizing’s result is the general-graph version and gives that number or one more; the exact equality for bipartite graphs is Koenig’s theorem. The claim as used is correct, by a different route.
• Real matrices are the harder case. Speedup is much better on uniformly distributed matrices than on power-law or k-regular ones, and the paper says the load balancing helps with high spread only to a degree. Power-law is what most real graphs look like.
• Bandwidth is a floor, not a headroom. A length-256 instance requires at least 224 gigabytes per second on a card that supplies 460, precisely because the point is a dense stream. Part of the advantage is spending bandwidth the baseline wastes, which bounds how far the approach scales.
• Preprocessing is thousands of times the cost of one multiplication — several seconds against under a millisecond — and is performed on a host processor. The paper argues the amortisation case well, noting that iterative solvers repeat the same sparsity pattern and that a single dense multiplication at full bandwidth would take longer than the whole preprocessing step, and it is worth noting that the competitor’s preprocessing is two to five times more expensive still.

The evaluation

Check yourself

Sources

The paper is “GUST: Graph Edge-Coloring Utilization for Accelerating Sparse Matrix Vector Multiplication” by Armin Gerami and Bahar Asgari, published at ASPLOS 2024, pages 127-141, DOI 10.1145/3622781.3674186. The authors are at the University of Maryland, College Park.

This explainer is written from the full arXiv text, arXiv:2410.09106. Everything above comes from the paper’s own sections: the definition of hardware utilisation and the survey of four prior approaches with their mechanisms, cycle counts and measured utilisations tabulated side by side; the diagnosis attributing their limits to static resource allocation; the architecture of three layers with its multiplier bank, index-steered crossbar and adder bank, the buffer filler and its double-buffered streaming, and the windowing scheme that folds columns by their index modulo the array length; the scheduling section covering the table-filling analogy, the mapping of rows and columns onto the two sides of a bipartite graph with non-zeros as edges and colours as buffer positions, the greedy matching-per-colour algorithm and the three output arrays it produces, and the note that a schedule is reusable across vectors and across value changes that preserve the pattern; the statistical analysis deriving the expected number of colours and hence the expected utilisation for uniformly random matrices; the three-step sorting procedure for load balancing; the experimental setup covering the board, the clock frequency and its cause, the bandwidth requirement, the energy model and its per-operation figures, and the resource tables for three array lengths; and the results covering the utilisation and execution time comparisons against the four prior designs, the speedup and energy comparisons against the systolic baseline for naive, coloured, and colour-plus-balanced variants, the bandwidth utilisation measurements, the nine-matrix comparison against a state-of-the-art design including preprocessing costs, the effect of density and structure, and the scalability discussion of the crossbar and the untested parallel arrangement.