PaperlayerView exact revision on arXiv

Source-linked AI summary

SpArch: Efficient Architecture for Sparse Matrix Multiplication

Zhekai Zhang, Hanrui Wang, Song Han, William J. Dally

arXiv:2002.08947v1cs.ARcs.DC

TL;DR

SpGEMM suffers from redundant input fetches or poor output locality, causing expensive DRAM access. SpArch combines outer-product input reuse with pipelined on-chip merging, matrix condensing, Huffman scheduling, and row prefetching. Across 20 benchmarks, it reduces DRAM access and outperforms several CPU, GPU, and accelerator baselines in speed and energy.

  • Problem

    SpGEMM has limited data locality because inner products redundantly fetch mismatched operands while outer products generate many partial matrices requiring costly DRAM access.

  • Method

    SpArch jointly optimizes input and output reuse using outer products, a streaming merger, condensed matrix representation, Huffman scheduling, and row prefetching.

  • Results

    Across 20 real-world benchmarks, SpArch reduces DRAM access by 2.8× over OuterSPACE and achieves higher speed and energy savings than five baselines.

  • Takeaways & Limitations

    The architecture demonstrates that coordinating input reuse with on-chip partial-matrix merging can improve sparse matrix multiplication efficiency across diverse benchmarks.

Abstract

from arXiv · show

Generalized Sparse Matrix-Matrix Multiplication (SpGEMM) is a ubiquitous task in various engineering and scientific applications. However, inner product based SpGENN introduces redundant input fetches for mismatched nonzero operands, while outer product based approach suffers from poor output locality due to numerous partial product matrices. Inefficiency in the reuse of either inputs or outputs data leads to extensive and expensive DRAM access. To address this problem, this paper proposes an efficient sparse matrix multiplication accelerator architecture, SpArch, which jointly optimizes the data locality for both input and output matrices. We first design a highly parallelized streaming-based merger to pipeline the multiply and merge stage of partial matrices so that partial matrices are merged on chip immediately after produced. We then propose a condensed matrix representation that reduces the number of partial matrices by three orders of magnitude and thus reduces DRAM access by 5.4x. We further develop a Huffman tree scheduler to improve the scalability of the merger for larger sparse matrices, which reduces the DRAM access by another 1.8x. We also resolve the increased input matrix read induced by the new representation using a row prefetcher with near-optimal buffer replacement policy, further reducing the DRAM access by 1.5x. Evaluated on 20 benchmarks, SpArch reduces the total DRAM access by 2.8x over previous state-of-the-art. On average, SpArch achieves 4x, 19x, 18x, 17x, 1285x speedup and 6x, 164x, 435x, 307x, 62x energy savings over OuterSPACE, MKL, cuSPARSE, CUSP, and ARM Armadillo, respectively.

I. INTRODUCTION

SpGEMM is widely used, but sparse and irregular computation creates poor locality and costly DRAM traffic. SpArch jointly improves input and output reuse through on-chip merging, matrix condensing, Huffman scheduling, and row prefetching.

  • SpGEMM supports algorithms and applications ranging from compressed deep neural networks and triangle counting to chemical dynamics and linear solvers.
  • Sparse, irregular access patterns make SpGEMM memory bounded; Twitter’s adjacency matrix has density as low as 0.000214%.
  • OuterSPACE provides input reuse through outer products but produces many partial matrices that require DRAM storage before merging, limiting performance to 10.4% of theoretical peak.
  • SpArch pipelines multiplication and merging on chip to jointly optimize input and output data reuse.
  • Matrix condensing reduces the number of partial matrices by three orders of magnitude, while Huffman scheduling prioritizes merges with fewer nonzeros.
  • A row prefetcher with near-optimal replacement addresses increased reads from matrix condensing, and the complete design reduces DRAM access by 2.8× over OuterSPACE.

II. PROPOSED ARCHITECTURE

SpArch pipelines multiplication and merging by performing on-chip merging of partial matrices, avoiding the separate DRAM-storing workflow of previous accelerators.

  • SpArch pipelines the multiply and merge stages, merging partial matrices on chip immediately after production.Previous state-of-the-art processing stores all partial matrices in DRAM before merging.

1) Parallel Merge Unit:

The parallel merge unit accelerates sorted-array merging with comparator arrays, using sliding windows and hierarchical chunk selection to increase throughput while controlling hardware cost.

  • Parallel Merge Unit: A sliding-window comparator array compares N elements from each input and improves merge throughput by N times.The design replaces one-element pointer advancement with all-to-all comparisons between two windows.
  • Parallel Merge Unit: The comparator array outputs the sorted result of two input arrays by identifying boundary tiles between smaller and larger coordinates.Boundary tiles determine which element is emitted at each position in the merged sequence.
  • Parallel Merge Unit: A 4×4 comparator array processes eight inputs per cycle and produces results in one clock cycle without input data dependencies.New inputs are shifted into the windows as prior elements are replaced.
  • Hierarchical Parallel Merge Unit: Hierarchical merging reduces comparator resources by using a top-level array to select chunk pairs for low-level comparison.Chunks can skip comparison when the largest element of one chunk is smaller than the other chunk.

3) Merge Tree:

SpArch scales on-chip merging with a streaming merge tree and reduces partial matrices through matrix condensing, while adders and zero elimination produce compact results.

  • Merge Tree: A merge tree stacks binary streaming mergers so multiple sorted arrays can be merged, with FIFO nodes connecting leaves to the root output.Each layer shares one merger to balance throughput, and the root bounds the tree throughput.
  • Adders and Zero Eliminator: When duplicate coordinates meet after merging, adders combine their values and a zero eliminator removes resulting zeros.The zero eliminator compresses zeros and outputs dense results.
  • Matrix Condensing: Because only 64 arrays can be merged on chip, matrix condensing reduces benchmark partial matrices to 100–1,000 and limits repeated 64-way merging.Without condensing, intermediate results can contain 10,000 to 1,000,000 partial matrices.
  • Matrix Condensing: Matrix condensing merges compatible columns before multiplication, replacing expensive multiplied-result merging with a cheaper merge of the left matrix.Columns with no elements sharing a row index can be combined while preserving the original column index.
  • Matrix Condensing: The condensed representation reduces the number of partial matrices by three orders of magnitude.In real-world datasets, the number of columns can fall from 100,000 to 100–1,000.
  • Matrix Condensing: The condensed left matrix is stored in CSR format while being loaded by condensed columns for the merge tree.A data loader dispatches row-loaded elements to ports according to their condensed columns.

C. Huffman Tree Scheduler

The Huffman tree scheduler orders partial-matrix merges to minimize DRAM traffic when partial matrices exceed on-chip merger parallelism. It merges smaller partial matrices earlier and larger ones later, while higher merger parallelism further reduces modeled traffic.

  • C. Huffman Tree Scheduler: 64 matrices can be merged on-chip, but larger workloads require DRAM-based multi-round merging whose order determines repeated partial-result accesses.The merge unit’s limited parallelism makes scheduling important because early-merged matrices may be repeatedly loaded and stored.
  • C. Huffman Tree Scheduler: The scheduler models merges as a tree whose leaves are initial multiplied results, internal nodes are partial merges, and node weights represent nonzero counts.For internal nodes, weights are estimated by summing child weights because the matrices are very sparse and merge additions are relatively rare.
  • C. Huffman Tree Scheduler: Minimizing the sum of internal-node weights minimizes memory access, equivalently minimizing weighted leaf depths in the merge tree.The total memory access of partially merged results equals the sum of internal-node weights.
  • C. Huffman Tree Scheduler: A k-ary Huffman tree is optimal for this objective because it places larger leaves nearer the root and smaller leaves farther away.Each construction round selects k unmerged nodes with minimal weights and combines them into an internal node.
  • C. Huffman Tree Scheduler: In the example, a 2-way scheduler reduces total weight from 365 to 354, while a 4-way scheduler reduces it further to 228.Because weight is proportional to DRAM traffic, the example shows lower modeled traffic with greater merger parallelism, at the cost of increased area and power.
  • C. Huffman Tree Scheduler: The real implementation builds the Huffman tree online with a priority queue that repeatedly merges the smallest partial matrices.After each merge, the new weight is reinserted and the queue is resorted.

D. Row Prefetcher

Matrix condensing reduces partial matrices but disrupts reuse of the second operand because condensed columns require rows from different positions. SpArch addresses this with predictive row prefetching and near-optimal buffer replacement.

  • D. Row Prefetcher: Matrix condensing increases second-operand reads because one condensed column requires elements from different rows of the second matrix.Before condensing, a column required only one row of the second matrix in the described example.
  • D. Row Prefetcher: The row prefetcher predicts the second matrix’s access order from the top-down traversal and column indices of the first matrix.This predicted sequence lets the system load rows before the multipliers consume them.
  • D. Row Prefetcher: The prefetcher hides DRAM latency by fetching required rows ahead of time and reduces DRAM reads by caching them for future reuse.Separate fetchers overlap accesses across DRAM channels and banks.
  • D. Row Prefetcher: The buffer replaces the line with the farthest next use, achieving near-optimal reuse when the predicted access sequence is accurate.The policy exploits advance knowledge of row demand while streaming the first matrix.
  • D. Row Prefetcher: Figure 9 illustrates time-step buffer updates, including line-by-line spilling that preserves already-buffered row segments for later accesses.At one step, only R3-0 must be loaded because R3-1 and R3-2 remain in the buffer.

E. System Architecture

SpArch fetches condensed columns of the left matrix, prefetches rows of the right matrix, computes outer products, and merges partial matrices through an on-chip merge tree before writing results.

  • E. System Architecture: The left matrix is stored in CSR, fetched by condensed column, and processed by a column fetcher that sends elements to a look-ahead FIFO.The MatA Column Fetcher receives scheduler instructions, calculates addresses, and fetches selected-column elements.
  • E. System Architecture: A hash table maps row indices to buffer positions, while a next-use reduction tree selects the line to spill.The implementation keeps this control logic’s power consumption minimal because the hash table is narrower than the buffer and next-use values change infrequently.
  • E. System Architecture: After prefetching, the multiplier array generates COO partial matrices by outer product and sends them to the merge tree.The merge tree can accept data from either the multiplier array or a partial-matrix fetcher through configurable multiplexers.
  • E. System Architecture: The partial matrix writer buffers merge-tree outputs, writes partial matrices to DRAM, and converts the final result from internal COO to CSR.The fetcher can reload requested partially merged results when the corresponding FIFO is nearly empty.

A. Methodology

SpArch is evaluated with cycle-accurate simulation, synthesized hardware modeling, and comparisons against CPU, GPU, mobile-CPU, and accelerator baselines across sparse-matrix benchmarks. It consistently improves speed, energy efficiency, and robustness to sparsity, while the merge tree dominates area and power.

  • A. Methodology: The evaluation uses a C++ cycle-accurate simulator that models module state updates on every cycle.Each module is represented as a class with clock update and clock apply methods.
  • A. Methodology: Area and power are estimated from datapath logic including mergers, arithmetic units, FIFOs, the row prefetcher, and DRAM, with the merger synthesized in TSMC 40nm.RTL switching activity from real simulator inputs is used for power estimation.
  • A. Methodology: Baselines include Intel MKL on a 6-core Core-i7, cuSPARSE and CUSP on a TITAN Xp GPU, Armadillo on a 4-core ARM A53, and OuterSPACE.The comparisons use double precision and exclude memory allocation and transportation time for the software baselines.
  • B. Experimental Results: The merge tree consumes most of SpArch’s area and power, and evaluation uses SuiteSparse and SNAP datasets matching the prior accelerator study.This identifies the merge tree as the principal hardware cost in the reported breakdown.
  • B. Experimental Results: SpArch is 4×, 19×, 18×, 17×, and 1285× faster than OuterSPACE, MKL, cuSPARSE, CUSP, and ARM Armadillo, respectively, on average.It outperforms the baselines on every matrix and uses 2.8× less DRAM access than OuterSPACE.
  • B. Experimental Results: SpArch achieves 6×, 164×, 435×, 307×, and 62× energy savings over OuterSPACE, MKL, cuSPARSE, CUSP, and ARM Armadillo, respectively.The reported savings are attributed to reduced DRAM access and specialized logic without general-purpose processor components.
  • B. Experimental Results: On synthesized rMAT matrices, SpArch achieves over 10× speedup over Intel MKL while performance drops only 2.7× as matrices become sparser.The paper attributes the relative stability partly to the outer-product algorithm and partly to using one large merge tree.
  • B. Experimental Results: SpArch reaches 10.4GFlops/s versus OuterSPACE’s 2.5GFlops/s under a 0.19Flops/Byte operational intensity and a 32GFlops/s computation roof.The figure attributes the 4× performance difference to reduced redundant DRAM traffic for partial matrices.

C. Interpreting the Performance Gain

SpArch’s optimizations progressively reduce the DRAM traffic introduced by partially merged results, matrix condensing, Huffman scheduling, and input row prefetching. Together, these steps achieve a 4.2× speedup over OuterSPACE.

  • Overall: 4.2× speedup over OuterSPACE is achieved after combining the successive optimizations.Figure 16 describes the sequence as matrix condensing, Huffman scheduling, and row prefetching after the initial pipeline stage.
  • Breakdown: 5.7× higher DRAM access without condensing explains the initial performance slowdown from partially merged results.The pipeline requires roughly 6.7 reads and writes of partially merged results, producing about 13.9M accesses versus OuterSPACE’s 2.5M.
  • Breakdown: 5.5× lower DRAM access after matrix condensing reduces the average merge rounds from about 6.7 to 2.Condensing reduces the average number of columns from 140,000 to 100, while the right matrix is reread for each multiplication.
  • Breakdown: 1.7× lower DRAM access after Huffman scheduling makes partially merged-result traffic negligible.Columns with many nonzeros are scheduled near the Huffman-tree root and avoid generating partially merged results.
  • Breakdown: 62% row-prefetcher hit rate reduces total DRAM access from 1.5M to 0.88M, an additional 1.7× reduction.The prefetcher buffers right-matrix data to compensate for the input-reuse loss caused by matrix condensing.

D. Design Space Exploration

The design-space study balances computational throughput, memory bandwidth, buffer accuracy, and hardware cost. The selected configuration uses a 48-element prefetch line, 16×16 comparator arrays, an 8192-entry look-ahead FIFO, and a six-layer, 64-port merge tree.

  • Prefetch buffer: 48 elements per prefetch-buffer line is selected because extending lines beyond 48 yields comparatively small performance gains while increasing area linearly.The explored buffer configuration is 1024×48 = 49152.
  • Comparator arrays: 16×16 comparator arrays are selected because smaller arrays are computationally bounded, whereas this size reaches the memory-bandwidth-bounded regime.Below 8×8, performance rises linearly; at 16×16, additional gains are lower.
  • Look-ahead FIFO: 8192 look-ahead FIFO entries provide the highest performance by improving prefetch-buffer replacement without excessive startup fill time.Larger FIFOs improve reuse accuracy but can degrade performance when their fill overhead becomes excessive.
  • Merge tree: Six merge-tree layers and 64 ports are sufficient for good performance, while larger trees add FIFOs and comparator arrays without speedup.The chosen tree avoids wasting area and power.

IV. RELATED WORK

Prior SpMM research spans specialized accelerators, general-purpose CPU/GPU algorithms, merge and intersection hardware, sparse linear algebra, and cross-platform comparisons. SpArch distinguishes itself through a specialized merge-based architecture for sparse data.

  • Sparse Matrix-Matrix Multiplication Acceleration: Earlier FPGA and ASIC SpMM accelerators used general-purpose processing elements, whereas SpArch uses a fully specialized merge tree for sparse data.OuterSPACE is the main ASIC comparison discussed in the paper.
  • General-purpose platforms: CPU/GPU SpMM methods use hash tables, sorting, heaps, or merges, each with stated scalability, complexity, memory-utilization, or load-balance trade-offs.SpArch and BHSPARSE use merge because it is less complex than sorting and remains parallelizable.
  • Merge and intersection: GPU research also accelerates set intersection using parallel methods including unsorted-set processing, bloom filters, list intersection, index compression, and SIMD.These works target intersection-related sparse operations rather than the complete SpArch architecture.
  • Sparse linear algebra: Sparse linear-algebra research includes FPGA operator trees, separated index comparison and computation, compressed storage, and architectures for sparse deep-learning operations.The related designs cover SpMV, recurrent networks, sparse convolution, and dynamic sparsity.
  • Hardware comparison: Prior work compares performance and energy efficiency across hardware platforms by running common benchmarks, a methodology also used to evaluate SpArch.The paper states that its evaluation follows a similar methodology.
  • Systolic array: SpArch’s comparator array resembles a systolic array spatially but lacks long data dependencies between comparator blocks.Each comparator block depends only on neighboring comparison results derived from the input array.

V. CONCLUSION

SpArch accelerates SpGEMM by jointly improving input and output data reuse through on-chip merging, condensed representation, Huffman scheduling, and row prefetching. Across 20 real-world benchmarks, it reduces memory access and improves performance and energy efficiency over the previous state of the art.

  • Conclusion: 2.8× lower memory access, 4× higher performance, and 6× higher energy efficiency are demonstrated against the previous state of the art across 20 real-world benchmarks.The conclusion also reports a breakdown explaining the savings from each optimization.
  • Conclusion: SpArch combines a streaming merger, condensed matrix representation, Huffman tree scheduler, and near-optimal row prefetcher to optimize both input and output reuse.The merger pipelines outer-product multiplication and merging on chip, while later mechanisms reduce partial-result and right-matrix access.
Loading 2002.08947v1…