PaperlayerView exact revision on arXiv

Source-linked AI summary

SUSpMV: A High Frequency Sparse Matrix Vector Multiplier on HBM Enabled FPGA written in SUS

Lennart Van Hirtum, David Volz, Andreas Koch, Christian Plessl

arXiv:2610.10403v1cs.ARcs.DC

TL;DR

SpMV is memory-bandwidth-bound, and prior HiHiSpMV work had already used the U280’s HBM capacity, leaving bandwidth efficiency as an opportunity. SUSpMV combines density-adaptive matrix storage with a multi-row accumulator. It reports 79% higher computational throughput than HiHiSpMV on the same Alveo U280 platform.

  • Problem

    SpMV is bandwidth-bound, and HiHiSpMV already exhausted U280 HBM bandwidth, motivating more efficient bandwidth use.

    Source: §I · p. 1

  • Method

    SUSpMV dynamically switches matrix encodings across density regions and uses a multi-row accumulator for up to six multiply-accumulates per CU per cycle.

    Source: §I · pp. 1–2

  • Results

    79% higher computational throughput than HiHiSpMV on the same Alveo U280 platform.

    Source: §V · p. 8

  • Takeaways & Limitations

    Ablations show both the dynamic format and multi-row accumulator improve performance, and evaluation demonstrates scalability with more CUs for larger matrices.

    Source: §V · p. 8

Abstract

from arXiv · show

SUSpMV is a Sparse Matrix Vector multiplication (SpMV) accelerator written in the upcoming HDL SUS. By leveraging SUS's unique latency counting and inference mechanism, SUSpMV could be designed with very deep pipelines yet small design complexity overhead. This enables an efficient implementation which employs all 32 HBM channels on the Alveo U280 FPGA at 400MHz for streaming matrix data into 32 Compute Units (CUs). Input and output vectors are stored in DDR memory, which allows zero-overhead chaining of multiplications and increases overall system memory bandwidth by not sharing HBM bandwidth with the CUs. A CU processes the SpMV in tiles of width 1024 and a dynamically chosen height, up to 32768. Each CU is capable of accumulating the multiplications with up to 6 separate matrix entries per cycle, resulting in the combined theoretical peak computational throughput of 153.6 GFLOPs. The matrix storage format is designed to exploit density variation within a given matrix by dynamically switching between one representation optimized for denser regions, and a second optimized for sparser regions, allowing jumps of up to 255 rows between each entry. Evaluation demonstrates a 79% geometric mean improvement over prior work on the same platform. We achieve a peak throughput of 144.9 GFLOPs, or 94% of our theoretical computational throughput, compared to 98 GFLOPs reached by prior work.

I. INTRODUCTION

SpMV performance is constrained by matrix bandwidth, and prior work had already saturated the U280’s HBM, leaving room to improve bandwidth efficiency. SUSpMV addresses this with density-adaptive storage and multi-row accumulation.

I. INTRODUCTION

  • Its storage format dynamically switches between high- and low-density variants to handle density variation within a matrix.The format is intended to be easy to decode on FPGA and avoids filler values or other stall mechanisms.Source: §I · pp. 1–2
  • SUSpMV is implemented in the upcoming HDL SUS, while the introduction frames SpMV as bandwidth-bound because each matrix element requires one multiply and one add.The matrix bandwidth focus motivates reducing the matrix memory footprint.Source: §I · p. 1
  • SUSpMV exceeds HiHiSpMV’s effective bandwidth utilization despite lower actual bandwidth because it does not reach 450 MHz.The introduction identifies HiHiSpMV as the prior design that used all 32 U280 HBM pseudo-channels at full capacity.Source: §I · pp. 1–2
  • The accumulator handles up to six multiply-accumulates per CU per cycle, with inputs that may target the same or different rows.The design prioritizes accumulating across multiple rows in one cycle rather than leaving block slots unused or adding backpressure.Source: §I · pp. 1–2
  • The work evaluates throughput against HiHiSpMV and uses ablations to assess the matrix format and accumulator contributions.The introduction lists both throughput comparison and ablation study among the contributions.Source: §I · p. 2

II. BACKGROUND & RELATED WORK

Sparse matrices vary widely in density, so storage formats must balance compression with access behavior and accelerator resources. Prior formats and tiling strategies address these trade-offs in different ways.

II. BACKGROUND & RELATED WORK

  • Sparse-matrix density can range from 10^-1 to 10^-6, making dense storage often impractical.The text defines density as the portion of nonzero entries.Source: §II · p. 2

A. Data Format

  • COO stores value-row-column triplets, CSR stores value-column tuples with row pointers, and CSC applies the CSR arrangement with axes transposed.These are identified as common sparse-matrix storage formats.Source: A. Data Format · p. 2
  • R3COO and OCOO compress index or control information, while CoSpMV’s density-adaptive SCDF uses separate control, value, and coordinate segments.SCDF’s references across segments make its accelerator resource-intensive and prevent it from using all external-memory bandwidth.Source: A. Data Format · p. 2
  • Format choices affect vector access patterns: CSR makes X accesses random and Y accesses linear, while CSC reverses this and COO makes both random.Random external-memory accesses negatively affect available bandwidth; DRC groups entries sharing X values to reduce buffer needs.Source: A. Data Format · p. 2
  • Matrices larger than local SRAM buffers are split into tiles processed separately, often in parallel across CUs with results merged afterward.Available SRAM limits tile size.Source: A. Data Format · p. 2

B. Accumulation

The accumulator combines products into output-vector values, and its design depends on how the matrix format distributes entries across rows. Prior approaches handle row assignment and imbalance through different mechanisms.

B. Accumulation

  • The accumulator receives parallel products of X-vector and matrix values and adds them to the corresponding Y values.It is described as the main computational component of an SpMV accelerator.Source: B. Accumulation · p. 2
  • The matrix format determines whether products arrive for the same row or different rows, and a single-row accumulator may need stalls or routing.Uneven entry distributions can leave parts of the accumulator idle.Source: B. Accumulation · p. 2
  • R3COO assigns multiple adders per HBM channel to separate rows and fills unused accumulator slots with zeros.Incoming values are reordered so each accumulator receives one value per cycle.Source: B. Accumulation · p. 2
  • HiHiSpMV accumulates hierarchically within a row, while HiSpMV can split an imbalanced row across CUs and combine its results afterward.The HiSpMV approach addresses rows with several times the average number of entries.Source: B. Accumulation · p. 2

C. Platform and Implementation

The implementation combines SUS’s latency-aware pipelining with matrix encoding and accumulation designed for sparse regions. It connects the accelerator to the U280’s HBM channels while using DDR for vector data.

C. Platform and Implementation

  • Prior SpMV implementations commonly use HLS, while the authors chose SUS to gain more control over generated hardware.The authors characterize SpMV as a critical application that could benefit from that control.Source: C. Platform and Implementation · p. 3
  • SUS’s Latency Counting automatically adds registers to synchronize parallel paths, accommodating 11-cycle fp32 adders in the accumulator.Latency Inference lets modules adapt to the latency of surrounding modules.Source: C. Platform and Implementation · p. 3

III. IMPLEMENTATION

  • The 5xFloat/6xFloat encoding addresses bandwidth waste by packing dense-region values and indices or sparse-region values, indices, and delta-Y values.Blocks can mark transitions to new rows at multiple positions, allowing contributions to up to six rows per block.Source: §III · p. 3
  • Each Y repeat is a full matrix pass that reads the X vector from DDR again; the example uses two repeats for three CUs and six tile rows.The figure’s example reads X once for each set of three tile rows.Source: Figure 1 · p. 3, §III · p. 3

A. The Matrix Format

The matrix is partitioned into bounded tiles and streamed as blocks whose encoding adapts to density. The format supports multirow contributions, with a small but measurable set of cases that 6xFloat cannot represent.

A. The Matrix Format

  • Tiles are 1024 X values wide and at most 32768 Y values high; variable heights balance work, and exceeding the limit requires additional Y repeats.Each Y repeat is a full pass over the matrix and a corresponding read of the X vector from DDR.Source: A. The Matrix Format · p. 3
  • Each tile streams 256-bit blocks at one block per cycle, encoding values and positions with 10-bit X positions and relative Y positions.5xFloat supports Y advances up to 255; 6xFloat trades that capacity for an additional value and X position.Source: A. The Matrix Format · p. 3
  • 6xFloat fits six weights and six 10-bit indices for denser regions, while 5xFloat trades one weight for delta-Y values and tile-end encoding.The caption identifies 5xFloat by its four “lasts” bits.Source: A. The Matrix Format · p. 3, Figure 2 · p. 4
  • The illustrated tile stores 16 sparse values in three blocks: row 0, then rows 0, 3, 4, and 5, then rows 5 through 7.The first and third blocks are 6xFloat, and the middle block is 5xFloat.Source: Figure 3 · p. 4
  • 6xFloat cannot represent every combination of multirow coverage and X ordering; this constraint prohibited its use in 0.17% of cases geomean and 3.4% worst-case.The format uses a last mask or a descending X position to indicate a Y increment, but those mechanisms do not cover every combination.Source: A. The Matrix Format · p. 4

B. A single Compute Unit

  • Within a CU, decoded weights pair with X-vector lookups and products feed partial-sum computation, leaving zero to six partial row sums for collection.After all tiles in a row finish, accumulated row totals are streamed out and the banks reset for the next Y repeat.Source: B. A single Compute Unit · p. 4
  • The decoder unpacks six X indices, weights, and delta-Y values, inserting a zero weight for 5xFloat and deriving delta-Y signals from 6xFloat last signals.It also emits tile-end control signals; flow control tracks X and Y buffer use.Source: B. A single Compute Unit · p. 4

2) X vector memory:

The CU buffers X-vector tiles for reuse and overlaps loading with computation. It then multiplies decoded matrix values and accumulates row sums across blocks.

2) X vector memory:

  • The X memory stores the 1024 fp32 values for a tile, reads them once, and reuses them for all matrix entries in that tile.An 8-way double buffer lets the next seven tiles load asynchronously while the current tile is in use; a fast CU may still wait for a slower one on highly unbalanced matrices.Source: 2) X vector memory · p. 4

1) Reading from HBM and Block Decoding:

  • Six replicated X-memory banks support maximum-throughput reads, and the looked-up values are multiplied by six matrix weights.Each bank is 512 bits wide to store incoming X values at the full DDR-interface bandwidth.Source: 1) Reading from HBM and Block Decoding · p. 4

3) Partial Sums & Accumulation:

  • Delta-Y values determine whether terms continue the same row or start a new sum; cross-block row sums pass through adjacent-pair stages to cover the 11-cycle fp32-add latency.Partial sums that do not need the cascading accumulator bypass it before routing to their Y sum buckets.Source: 3) Partial Sums & Accumulation · p. 5

4) Y Collector:

The Y Collector maintains partial row totals across tiles and streams completed results out. Multiple CUs connect to separate HBM channels, with shared vector paths and resource-aware floorplanning.

4) Y Collector:

  • The Y Collector routes up to six partial sums per cycle into 16 banks assigned by the row index’s lower four bits.Bank conflicts, such as simultaneous writes to rows 0 and 16, are resolved statically by moving a conflicting row to the next data block.Source: 4) Y Collector · p. 5
  • Double-buffering each Y bank lets one half accumulate while the other streams results to external memory and resets during idle cycles.The 16 output streams are recombined before being forwarded to external memory.Source: 4) Y Collector · p. 5

C. Integrating 32 SpMV Units

  • Each of 32 CUs connects to one HBM pseudo-channel; a shared DDR reader broadcasts X data, and a round-robin writer joins CU outputs in order.The X reader tracks CU progress to avoid overwriting local buffers before their values are consumed.Source: C. Integrating 32 SpMV Units · pp. 5–6

1) Floorplanning:

  • Per-CU BRAM and URAM requirements fit eight CUs on each SLR’s left half and six on its right half, prompting pblock-based floorplanning.The halves have complementary BRAM/URAM constraints; long shared X and Y buses use 8–24 pipeline stages depending on SLR crossings.Source: 1) Floorplanning · p. 6

D. Compute Unit Load Balancing & Shuffling

SUSpMV balances work by varying tile heights and can shuffle rows and columns to address larger imbalances. Its evaluation compares against HiHiSpMV and measures kernel runtime and matrix footprint on 59 shared benchmark matrices.

D. Compute Unit Load Balancing & Shuffling

  • Tile heights vary so each CU processes roughly the same number of matrix elements; extra Y repeats handle tiles above 32k or imbalanced distributions.Large column imbalances can still make CUs wait for one another, so row-and-column shuffling is optionally used to alleviate them.Source: D. Compute Unit Load Balancing &… · p. 6

IV. EVALUATION

  • The evaluation compares SUSpMV with HiHiSpMV using its published results and includes ablations of the matrix format and multi-row accumulator.The performance table reports GFLOPs for SuiteSparse matrices sorted by descending nonzero count; HiHi denotes HiHiSpMV, while NoSh and Sh denote SUSpMV without and with shuffling.Source: §IV · p. 6, Table II · p. 7

A. Setup

  • Kernel runtime is measured while preprocessing and data transfer are excluded, using the same 59 SuiteSparse matrices as HiHiSpMV.The study also measures matrix memory footprint and reports GFLOPs and effective bandwidth.Source: A. Setup · p. 6

B. Throughput

SUSpMV outperforms HiHiSpMV in geometric-mean throughput, while its bandwidth and resource results expose trade-offs in the implementation. It also exceeds prior reported peak throughput on the same platform in many tests.

B. Throughput

  • 79% geomean speedup with shuffling and 45% without, compared with HiHiSpMV; small matrices can be slower because pipeline and Y-writer arbitration overheads dominate.Speedups are more pronounced for matrices with higher nonzero counts.Source: B. Throughput · p. 7
  • 214.8 GB/s mean and 387 GB/s peak bandwidth are achieved against a 409.6 GB/s theoretical limit; matrix-value-only effective bandwidth is 155.2 GB/s.Measurements are at 400 MHz.Source: B. Throughput · p. 7

C. Resource Utilization

  • SUSpMV uses significantly more logic and memory resources than HiHiSpMV, except for DSPs; its 256-bit HBM interfaces limit maximum bandwidth despite higher fmax.Storing vectors in separate DDR memory provides additional bandwidth and mitigates this drawback.Source: C. Resource Utilization · p. 7
  • Per HBM channel, SUSpMV and HiSpMV use similar combined SRAM resources, measured as BRAM+URAM*8.Source: C. Resource Utilization · p. 7
  • In 24 tests, SUSpMV exceeds the reported peak computational throughput of any previous work on the same platform.Source: C. Resource Utilization · p. 7

D. CU Scaling

Performance scales mostly linearly with CU count except on very small matrices. The data-format ablation finds gains from 6xFloat, while sparse regions can still incur dummy values and constrain alternative encodings.

D. CU Scaling

  • Performance scaling is mostly linear across 1, 2, 4, 8, 16, and 32 CUs, except for very small matrices.Other CUs were disabled by assigning them zero Y values, leaving constant-time synchronization overhead on the Y return channel.Source: D. CU Scaling · p. 7, Figure 7 · p. 7

E. Data Format

  • 16% geomean fewer blocks and 12% geomean speedup result from enabling 6xFloat; larger matrices approach its 20% maximum improvement.The ablation disables 6xFloat blocks and measures total blocks issued and runtime.Source: E. Data Format · pp. 7–8, Figure 8 · p. 8
  • 6xFloat reduces index bits to fit another float in denser regions, while 5xFloat needs dummy entries only below one entry per 255 rows; empty sections can therefore add dummy-block overhead.The threshold is about 4 * 10^-6 density, and none of the test matrices fell below it, though many had large empty sections.Source: E. Data Format · pp. 7–8
  • Dummy zeroes account for 0.64% geomean and 6.41% worst case across matrices, mostly because of sparse areas, though bank conflicts also contribute.Source: E. Data Format · p. 8
  • A 4xFloat format could help matrices with large empty areas, but tile skipping would desynchronize CUs and stall faster units unless X-vector reloading adapts.Source: E. Data Format · p. 8

F. Accumulator

The multi-row accumulator improves throughput and reduces matrix storage in the reported evaluation. The conclusion also identifies remaining opportunities in matrix encoding and X-vector streaming.

F. Accumulator

  • 7.9% geomean throughput improvement, with a 102% best case, follows enabling accumulation of values from different rows in the same cycle.The ablation forces same-row entries within each block to measure the accumulator's impact.Source: Figure 9 · p. 8, F. Accumulator · p. 8
  • 7.6% geomean matrix-storage reduction is reported across all matrices.For ted B, full accumulator use reduced storage from 30k to 24k blocks despite unequal row distribution across CUs.Source: F. Accumulator · p. 8

V. CONCLUSION

  • The conclusion reports 79% higher computational throughput than HiHiSpMV on Alveo U280 and says both the dynamic format and multi-row accumulator improve performance.It attributes up to 20% greater data delivery bandwidth in dense regions to the format and 7.6% lower matrix storage to the accumulator.Source: §V · p. 8
  • Further performance gains may come from improving the dynamic matrix-storage encoding and streaming the X vector more efficiently.Source: §V · p. 8
Loading 2610.10403v1…