PaperlayerView exact revision on arXiv

Source-linked AI summary

Hardware Acceleration of Sparse and Irregular Tensor Computations of ML Models: A Survey and Insights

Shail Dave, Riyadh Baghdadi, Tony Nowatzki, Sasikanth Avancha, Aviral Shrivastava, Baoxin Li

arXiv:2007.00864v2cs.ARcs.CVcs.DCcs.LGcs.NE

TL;DR

Sparse and irregular ML tensors create computation, communication, and memory-access patterns that conventional accelerators do not inherently exploit. This survey categorizes accelerator and software techniques and analyzes their costs and trade-offs. It concludes that encoding, extraction, reuse, PE design, and load balancing shape acceleration, with block sparsity offering storage and balance benefits.

  • Problem

    Unstructured sparsity and irregular tensor shapes create scattered non-zeros and irregular execution, requiring additional mechanisms and hardware or software support.

    Source: §I · p. 2

  • Method

    The paper surveys accelerator systems and software techniques, categorizes design choices, and analyzes their costs and opportunities for sparse tensor execution.

    Source: §I · p. 2

  • Results

    The survey finds that encoding, extraction, memory reuse, PE architecture, and load balancing all shape sparse-tensor acceleration, while block sparsity can improve storage efficiency and balance computations.

    Source: §XV · pp. 36–37

  • Takeaways & Limitations

    Design choices for encoding, storing, extracting, communicating, computing, and balancing non-zeros should be considered together with hardware/software/model co-design opportunities.

    Source: §I · p. 2, A. Hardware/Software/Model Co-designs · p. 34

Abstract

from arXiv · show

Machine learning (ML) models are widely used in many important domains. For efficiently processing these computational- and memory-intensive applications, tensors of these over-parameterized models are compressed by leveraging sparsity, size reduction, and quantization of tensors. Unstructured sparsity and tensors with varying dimensions yield irregular computation, communication, and memory access patterns; processing them on hardware accelerators in a conventional manner does not inherently leverage acceleration opportunities. This paper provides a comprehensive survey on the efficient execution of sparse and irregular tensor computations of ML models on hardware accelerators. In particular, it discusses enhancement modules in the architecture design and the software support; categorizes different hardware designs and acceleration techniques and analyzes them in terms of hardware and execution costs; analyzes achievable accelerations for recent DNNs; highlights further opportunities in terms of hardware/software/model co-design optimizations (inter/intra-module). The takeaways from this paper include: understanding the key challenges in accelerating sparse, irregular-shaped, and quantized tensors; understanding enhancements in accelerator systems for supporting their efficient computations; analyzing trade-offs in opting for a specific design choice for encoding, storing, extracting, communicating, computing, and load-balancing the non-zeros; understanding how structured sparsity can improve storage efficiency and balance computations; understanding how to compile and map models with sparse tensors on the accelerators; understanding recent design trends for efficient accelerations and further opportunities.

I. INTRODUCTION

The paper surveys accelerator and software support for sparse and irregular ML tensor computations, where conventional accelerators waste work on zeros and irregular patterns demand special handling. It categorizes design choices, examines their costs and effects, and identifies co-design opportunities.

I. INTRODUCTION

  • Conventional accelerators fetch and communicate zeros and cannot skip ineffectual computations, while unstructured sparsity scatters non-zeros and makes execution irregular.Efficient execution therefore requires support for storing, extracting, communicating, computing, and load-balancing non-zeros.Source: §I · pp. 1–2
  • The paper surveys accelerator systems and execution techniques for sparse ML tensors, organizing designs by hardware and software aspects.It discusses the need for system modules, design choices, and qualitative trade-offs.Source: §I · p. 2
  • The survey analyzes how sparsity and tensor shapes affect encoding storage efficiency and tensor reuse.It also covers sources of sparsity, challenges for sparse and irregular-shaped computations, and accelerator enhancements.Source: §I · p. 2
  • It outlines hardware/software/model co-design opportunities and examines recent DNN acceleration and execution bottlenecks.The survey also covers compiler support, module-specific techniques, and future directions.Source: §I · pp. 2–3

II. BACKGROUND: NEED FOR EFFICIENT EXECUTION OF ML MODELS ON HARDWARE ACCELERATORS

The background introduces the DNN workloads and spatial accelerators that motivate the survey, then explains why model compression and sparse tensors require specialized execution support. It describes sparsity sources and structures alongside the efficiency opportunities they offer.

A. Domain-Specific Machine Learning Models

  • The survey focuses mainly on supervised-learning DNNs and on accelerating MLP, CONV, and RNN operators, which are core primitives in many models.The background also describes CNN, sequence-to-sequence, GAN, graph, and recommendation workloads.Source: A. Domain-Specific Machine Learning… · p. 3

B. Hardware Accelerators for Machine Learning

  • Coarse-grained spatial accelerators use interconnected processing elements, private and shared memories, and interconnects to reuse data and reduce off-chip accesses.Structured execution and data management can keep processing elements engaged while data moves through the memory hierarchy.Source: B. Hardware Accelerators for Machine… · pp. 3–4

C. Need for Further Efficient Execution

  • Deeper and larger models increase computation and memory demands, while tensor compression can reduce computation, communication, and storage requirements.The background cites AlexNet at 61M parameters and 724 MFLOPs, versus ResNet-101 at 100+ parameter layers and about 7.6 GFLOPs per image.Source: C. Need for Further Efficient Execution · p. 4

III. ACCELERATION OPPORTUNITIES DUE TO COMPACT MODELS AND THE NEED FOR SPECIAL SUPPORT

  • Sparsity, size reduction, and quantization compact tensors, but compression can make their shapes and processing irregular.Examples include pruning, quantization, and Huffman encoding reducing AlexNet's model size from 552 MB to 11.3 MB; the survey frames efficient processing as requiring special support.Source: §III · p. 4

A. Opportunities Due to Sparse Tensors

  • Sparsity arises from model operations, pruning, and application data, and may be unstructured, block-based, or density-bounded.Structured patterns and block choices depend on task accuracy; processing non-zeros can reduce computation, storage, and communication.Source: A. Opportunities Due to Sparse Tensors · pp. 4–5

B. Opportunities Due to Size-Reduced Tensors

Size reduction and quantization reduce tensor requirements but can produce irregular shapes, variable precision, and indirect accesses. These compressed representations therefore need accelerator support tailored to their execution patterns.

B. Opportunities Due to Size-Reduced Tensors

  • Size reduction through operators, dimensionality reduction, decomposition, and ragged tensors reduces storage and computation but can produce irregular-shaped tensors.These transformations include depth-wise separation, low-rank approximations, and spatial factorization.Source: B. Opportunities Due to Size-Reduced… · pp. 5–6

C. Opportunities Due to Quantized Tensors

  • Quantization lowers precision or shares similar values, reducing storage, memory access, area, and power, while accuracy may be preserved or traded for execution efficiency.Fine-tuning or quantization-aware training can compensate for accuracy drops.Source: C. Opportunities Due to Quantized… · p. 6

D. Need for Special Support to Accelerate Sparse and Irregular Tensor Computations

  • Sparse and irregular execution needs support for handling non-zeros and flexible tensor shapes; value-shared quantization additionally needs codebook indexing and configurable bit-widths.Shape transformations and different functions can call for configurable architectures and flexible mappings.Source: D. Need for Special Support to… · p. 6

IV. ACCELERATOR DESIGN FOR EFFICIENT SPARSE AND IRREGULAR TENSOR COMPUTATIONS

The section surveys accelerator and software mechanisms for processing sparse tensors, then analyzes achievable DNN speedups and their execution overheads. Its case study finds that moderate sparsity can yield speedups near the reduction in operations, while extraction, imbalance, and communication can limit gains.

A. Overview

  • Accelerator systems add hardware or software modules to orchestrate structured computation over compressed tensors, with PE, load-balancing, write-back, post-processing, and compiler support.PE designs range from scalar to SIMD and vector architectures; load balancing may be software-based or dynamically supported by hardware.Source: A. Overview · pp. 6–8
  • Accelerators vary in whether they exploit weight sparsity, activation sparsity, or both, and in support for static versus runtime-detected sparsity.Static sparsity permits offline encoding and transformations, whereas dynamic sparsity requires runtime matching of nonzeros and often load balancing.Source: A. Overview · pp. 6–7
  • Sparse encodings store nonzero values with location metadata; extraction logic decodes tensors and finds matching operands, with indexing or intersection methods effective up to moderate activation and high weight sparsity.At high or hyper sparsity, scattered nonzeros make extraction challenging and execution is usually memory-bounded with low arithmetic intensity.Source: A. Overview · p. 7
  • Memory management and communication designs must account for sparsity-dependent reuse, memory transfers, interconnect patterns, and output reduction or collection.The survey discusses hiding miss penalties and configurable communication patterns for different sparsity, reuse, and functionality.Source: A. Overview · p. 7

B. Case Study: Acceleration of DNNs and Bottleneck Analysis

  • The case study uses data-driven latency modeling with randomly induced tensor sparsity and assumes dense peak-utilization processing for unsupported depthwise convolutions.Modeled latency includes functional-unit processing, decoding, nonzero extraction, synchronization, and off-chip transfers.Source: B. Case Study: Acceleration of DNNs… · p. 8
  • 4.8× fewer Transformer operations yielded about 4×–4.2× speedup; BERT-base-uncased on SQuAD achieved about 7.7×–8.9× speedup out of 12.2× at peak processing.The analysis compares obtained speedups with desired reductions in operations and examines execution overheads.Source: Figure 5 · p. 9, B. Case Study: Acceleration of DNNs… · p. 9
  • Cambricon-S and ZENA-IA-W achieved higher CV-model speedups by exploiting unstructured activation sparsity, but extraction, load imbalance, communication, and DMA could add overhead.ZENA's zero-aware static filter sorting and dynamic load balance addressed imbalance; its shared bus still incurred on-chip communication time, which the study disregarded.Source: Figure 5 · p. 9, B. Case Study: Acceleration of DNNs… · p. 9

V. ENCODINGS FOR COMPRESSING SPARSE TENSORS

This section explains how sparse-tensor encodings represent nonzero values and their positions, and compares their storage and processing costs. The formats trade metadata size and storage efficiency against the work needed to index and extract nonzeros.

V. ENCODINGS FOR COMPRESSING SPARSE TENSORS

  • The section also covers group-wise encoding of tensor blocks and Huffman coding of quantized values with differing frequencies.Huffman coding is described as an additional compression step after quantization or value sharing.Source: §V · p. 10, A. Encoding Formats and Implications · p. 12

A. Encoding Formats and Implications

  • COO stores each nonzero with its absolute coordinates, while CSR stores values row-wise and uses column indices and row pointers to avoid repeated row coordinates.CSR allows random access to rows, but its metadata overhead makes it efficient at high sparsity, such as 90% or higher.Source: A. Encoding Formats and Implications · pp. 10–11
  • RLC represents zero runs before nonzeros, but narrow run fields may require padding zeros; bitmap stores one flag per dense-tensor element and suits low or moderate sparsity.RLC indexing accumulates runs, while bitmap indexing requires step-processing.Source: A. Encoding Formats and Implications · p. 10
  • For 2 MB matrices, COO achieves storage efficiency at 70%+ sparsity, while its data and metadata can be directly extracted for simple indexing.Figure 8 compares storage benefits across formats and sparsities, normalized to dense matrix size.Source: A. Encoding Formats and Implications · p. 10, Figure 8 · p. 11
  • CSR decoding locates a row through pointers and then a nonzero through its column index; CSC uses the analogous column-wise organization.RLC-encoded CSR or CSC metadata can reduce index or pointer storage but may require three processing steps.Source: A. Encoding Formats and Implications · pp. 11–12
  • CSF generalizes CSR to higher-order tensors with a tree of coordinate indices, reducing duplication as dimensions and coordinate redundancy increase.Metadata processing can require up to 2n steps for an n-dimensional tensor, so CSF may suit high-dimensional, highly sparse tensors.Source: A. Encoding Formats and Implications · p. 12
  • Coarse-grain block-sparse encodings can substantially reduce metadata by indicating dense-block locations, while density-bounded blocks have overhead similar to unstructured blocks of the same size and sparsity.The section gives examples including a single bitmap bit per 1×16 dense block and a few bytes per 8×8 block.Source: A. Encoding Formats and Implications · p. 12

B. Group-wise Encoding

Sparse-tensor encoding and extraction choices are shaped by sparsity patterns and PE mappings. The section contrasts encoding strategies with mechanisms for finding matching nonzeros, including approaches that avoid runtime extraction through structured computation.

B. Group-wise Encoding

  • Group-wise encoding aligns separately encoded tensor tiles with predetermined per-PE work, making decoding and extraction easier; EIE, Cambricon-X, and CompAct use it.Unlike whole-tensor encoding, each group corresponds to execution on a distinct PE or PE-group.Source: B. Group-wise Encoding · p. 12

C. On-the-fly Encoding

  • On-the-fly encoding supports dynamically sparse activations and training tensors, whereas inference accelerators often encode static weights offline.It is often paired with assembling PE outputs after reorganizing data for the next layer's group-wise encoding and dataflow.Source: C. On-the-fly Encoding · p. 13

D. Optimization Opportunities

  • Different sparsity levels and patterns can motivate separate tensor encodings, but supporting multiple formats requires configurable decoding logic.Separate formats may support storage, PE zero-guarding, or faster extraction of intersecting nonzeros.Source: D. Optimization Opportunities · p. 13

VI. EXTRACTION OF MATCHING DATA FOR COMPUTATIONS ON NON-ZEROS

  • Extraction mechanisms locate effective nonzeros from metadata, then supply matching values to PEs for computation.The surveyed mechanisms are categorized by whether PEs perform scalar MACs, scalar-vector multiplication, or vector-vector multiplication.Source: §VI · p. 13, A. Non-Zero Detection and Extraction… · p. 13

A. Non-Zero Detection and Extraction Mechanisms

  • Indexing uses a sparse tensor's nonzero positions to look up corresponding dense values, while multi-stage indexing or comparator-based matching finds intersections between compressed tensors.In EIE, a PE may fetch another activation when no matching weight is found, leaving functional units unused for that cycle.Source: A. Non-Zero Detection and Extraction… · pp. 13–14
  • At a search length of 256, Cambricon-X supports 93.75% sparsity when fetching 16 nonzeros, while its central indexing module uses about 31% of on-chip area and 35% of power.Parallel lookup uses multiplexers to select matching vector elements; higher sparsity can require larger multiplexers.Source: A. Non-Zero Detection and Extraction… · p. 14
  • Structured sparsity can avoid runtime matching: ERIDANUS streams clustered weight blocks through a systolic array, while adaptive tiling reduced array invocations by 2×–3× for MobileNet point-wise CONVs.ERIDANUS keeps corresponding activations stationary; adaptive tiling statically combines nonzero weights across columns.Source: A. Non-Zero Detection and Extraction… · p. 14, Figure 12 · p. 14

B. Centralized vs. Distributed Management

Centralized extraction can coordinate work across PEs, while in-PE extraction supports spatial reuse; each presents different load-balancing and communication trade-offs. Sparsity lowers reuse for many tensors, though substantial reuse remains in some layers.

B. Centralized vs. Distributed Management

  • Central extraction can allocate work across PEs and enable runtime load balancing, but per-PE extraction can limit multicast of common data; SNAP shares extraction across a row and multicasts data.In-PE extraction permits tensor elements to be multicast before local extraction, but may incur unhidden extraction cycles and make inter-PE balancing costly.Source: B. Centralized vs. Distributed… · p. 15

C. Optimization Opportunities

  • Configurable extraction mechanisms can better handle varied sparsity, and integrating low-cost balancing logic into a central module may improve PE utilization.The central module already tracks data sent to PEs, which can provide information about their operation counts.Source: C. Optimization Opportunities · p. 15

A. Leveraging Data Reuse Opportunities

  • Reuse varies by layer and tensor: CNN weight reuse can exceed feature-map reuse by an order of magnitude, while MLP weight reuse increases linearly with batch size.Depthwise convolutions have low input-activation and partial-summation reuse; larger input-channel counts can increase partial-summation reuse in deeper CNNs and reduction layers.Source: A. Leveraging Data Reuse Opportunities · p. 16
  • Sparse models preserve broad reuse patterns but reduce reuse for almost all layers and tensors; reuse can still reach 1E + 04, and weight reuse is unchanged when activations are not sparse.Without batching, MLP weight reuse can fall below one when some nonzero weights lack matching nonzero input activations.Source: A. Leveraging Data Reuse Opportunities · p. 16

B. Hiding Miss Latency Behind Computations

Buffering and asynchronous communication overlap computation with memory activity, while banked memories manage concurrent accesses and their conflicts. Cross-layer reuse, power gating, and unified data-and-metadata memory are further management opportunities.

B. Hiding Miss Latency Behind Computations

  • Double-buffered scratchpads and loop tiling or ordering overlap computation with off-chip transfers; asynchronous refill lets PEs and DMA move data while computations proceed.Asynchronous communication and computation can alleviate PE work imbalance caused by unstructured sparsity.Source: B. Hiding Miss Latency Behind… · p. 17

C. Management of Multi-Bank Memory

  • Banked buffers provide simultaneous accesses to different tensors, but irregular sparse outputs can conflict at banks and require arbitration or additional banks.SCNN uses 2×N output banks for N sources; its 16×32 crossbar occupies 21% of each PE's on-chip area.Source: C. Management of Multi-Bank Memory · p. 17

D. Reusing Intermediate Tensors

  • Keeping intermediate feature maps on-chip reduces off-chip traffic, and fused-layer execution reuses tiles across layers; its tile size and layer count are bounded by memory capacity.Fused-layer CNNs reduced off-chip input-feature-map transfers by 28% for AlexNet's first two layers and 95% for VGG-19's first five layers.Source: D. Reusing Intermediate Tensors · pp. 17–18

E. Techniques for Further Energy-Efficiency

  • Look-ahead snoozing power-gates inactive SRAM banks, while EIE and Cambricon-X can bypass shared memory for data with little reuse.Banks are snoozed according to their activity periods in the data-movement schedule.Source: E. Techniques for Further… · p. 18

F. Optimization Opportunities

  • Unified memory for data and metadata is an optimization opportunity because separate metadata buffers may not suit varying sparsity and value similarity, which change storage requirements.The design space includes memory partitioning and bank management, including for FPGA implementations.Source: F. Optimization Opportunities · p. 18

VIII. INTERCONNECTS FOR DISTRIBUTING NON-ZEROS AND REDUCING PARTIAL OUTPUTS

Interconnects distribute operands according to reuse and communication needs, while partial outputs can be accumulated temporally, spatially, or through configurable combinations. Because sparsity and tensor shape make communication and reduction patterns irregular, configurable networks and reduction mechanisms can accommodate varied workloads.

A. Mechanisms for Distribution of Operands

  • Multicast and broadcast enable spatial reuse, meshes forward data between PEs, and unicast feeds distinct elements where reuse is infeasible or outputs are collected simultaneously.Unicast can reduce communication latency with high bandwidth, but may incur high area and power.Source: A. Mechanisms for Distribution of… · p. 19
  • Configurable NoCs are needed because dataflow, sparsity, and tensor shapes create varied communication patterns, including gather, scatter, forwarding, reduction, and non-uniform multi-hop traffic.EyerissV2, microswitch-NoC, and SIGMA address some of these challenges.Source: A. Mechanisms for Distribution of… · p. 19
  • EyerissV2, microswitch-NoC, and SIGMA use configurable interconnect designs to support different communication patterns and data movement.EyerissV2 uses a hierarchical mesh; microswitches enable configurable communication patterns; SIGMA uses a Benes topology with configurable switches.Source: A. Mechanisms for Distribution of… · pp. 19–20, Figure 17 · p. 19

B. Mechanisms for Reduction of Partial Outputs

  • Temporal reduction avoids inter-PE communication for sparse outputs, but requires local buffer or register reads and writes that consume more energy than integer arithmetic.It is used in EIE, ZENA, and SparTen.Source: B. Mechanisms for Reduction of Partial… · p. 20
  • Spatial reduction can avoid buffer accesses and improve energy efficiency by 2×–3× versus temporal reduction on scalar PEs, but variable partial-output counts challenge symmetric reductions.The section notes that functional units may be poorly utilized when high or hyper sparsity leaves them without enough non-zeros; structured sparsity can alleviate imbalance, but configurable mechanisms remain necessary for different dataflows, functionalities, and shapes.Source: B. Mechanisms for Reduction of Partial… · pp. 20–21
  • Spatio-temporal reduction combines spatial accumulation with temporal updates in memory, either across PEs or locally within a PE.Systolic-array columns can reduce partial outputs spatially before a bottom PE row sends them to accumulator buffers; SNAP uses configurable adder-trees before accumulating in PE memory over time.Source: B. Mechanisms for Reduction of Partial… · p. 21
  • Temporo-spatial reduction first accumulates partial outputs locally over time, then collects and reduces them across PEs.Examples include EyerissV2 cluster accumulation, SCNN exchanges among neighboring PEs, and SNAP core-level reduction.Source: B. Mechanisms for Reduction of Partial… · p. 21
  • Configurable reduction trees support asymmetric spatial reductions for unstructured sparsity and variable-sized dot-product vectors.MAERI uses configurable 3-input adder switches and forwarding links, with double bandwidth near the root; SIGMA uses 2-input adders and N:2 muxes for reduced area and power.Source: B. Mechanisms for Reduction of Partial… · p. 21, Figure 21 · p. 21

C. Optimization Opportunities

Efficient sparse and irregular computation calls for low-cost, adaptable interconnects and PE datapaths, along with compiler support to configure and map them. Functional-unit choices must account for sparsity, layer functionality, and precision while balancing utilization and hardware cost.

C. Optimization Opportunities

  • Interconnects must accommodate changing reuse, sparsity, precision, and communication patterns while managing data movement at low cost.A 24-bit EyerissV2 bus can carry three 8b uncompressed values or two pairs of 8b non-zero values and 4b metadata.Source: C. Optimization Opportunities · p. 21
  • Compilers need to program configurable interconnects, select efficient paths, and account for topology limits when mapping communication and exploring designs.Some topologies may not support dataflows that require multi-hop connectivity.Source: C. Optimization Opportunities · pp. 21–22

IX. PE ARCHITECTURE DESIGN

  • Compressed-tensor processing can require PE hardware for extraction or indexing, and one dataflow may lose acceleration across different sparsities and layer functionalities.The PE pipeline processes instructions, fetches data, computes tensor elements, and writes intermediate results; efficient pipelines also need to hide preprocessing and postprocessing latency.Source: §IX · p. 22, Figure 22 · p. 22

A. Functional Units

  • SIMD and vector PEs use multiplier arrays and adder-trees for throughput and spatial reuse, but sparse inputs can leave functional units without enough non-zeros to use them.Cambricon-X accelerated CONVs by about 8× out of 16× peak speedup for hyper W-sparsity; larger extraction modules may improve utilization but increase area and power, while fewer multipliers can support a wider sparsity range.Source: A. Functional Units · p. 22
  • Configurable functional units can process different partial-sum combinations and DNN operators, including depthwise convolutions, without high-bandwidth crossbars.SNAP uses a configurable adder-tree to process inputs from three multipliers.Source: A. Functional Units · p. 22, Figure 24 · p. 23
  • Multiplier-free PEs replace multipliers with simpler arithmetic for very low-precision or logarithmically quantized tensors, trading flexibility against hardware simplicity and potential accuracy loss.Reported top-1 and top-5 accuracy drops range from 0.1% to 5%.Source: A. Functional Units · p. 22
  • Functional-unit designs should account for sparsity and layer functionality while avoiding dense-tensor performance and energy penalties from features that are not in use.For dense tensors, SCNN achieved 79% of baseline performance and consumed 33% higher energy; added features should not increase critical-path latency and should be power-gated when unused.Source: A. Functional Units · p. 23

B. Dataflow Mechanisms

Dataflow choices determine how computation, communication, and memory accesses map onto accelerator resources, and layer characteristics can make a single mapping inefficient. The section also surveys sparsity-aware mappings and value-similarity techniques that reuse computations or skip processing.

B. Dataflow Mechanisms

  • Dataflow maps a layer's spatiotemporal execution onto accelerator resources, affecting utilization, reuse, latency hiding, execution time, and energy.Different layers vary in dimensions, functionality, and sparsity, so a single dataflow may not be effective for all of them.Source: B. Dataflow Mechanisms · pp. 23–24
  • Stationary-dataflow choices include output, weight, input, and row stationary, as well as no local reuse; each exploits different tensor reuse and spatial parallelism.Output stationary accumulates partial outputs locally over time, avoiding spatial reduction across PEs.Source: B. Dataflow Mechanisms · pp. 23–24
  • Coarse weight stationary can underutilize PEs on depthwise convolutions, while input- or output-stationary mappings can underutilize PEs in later deep-CNN layers.Analytical tools such as Timeloop, dMazeRunner, MAESTRO, and Interstellar estimate execution metrics and evaluate mappings.Source: B. Dataflow Mechanisms · p. 24, Figure 25 · p. 24, Figure 26 · p. 24
  • Sparse dataflows process compressed tensors with non-zero extraction or orchestration, which may occur in PEs, another module, or a separate controller.EyerissV2 used statically known weight sparsity to allocate more non-zero weights locally and extracted non-zeros from CSC-encoded data in each PE.Source: B. Dataflow Mechanisms · pp. 24–25
  • Dataflow optimization tools need to model the storage, communication, and extraction costs of metadata and codebooks, and account for layer-to-layer sparsity and value-similarity variation.Existing mapping tools target dense tensors, while some sparse-tensor accelerators use customized dataflows.Source: B. Dataflow Mechanisms · p. 25

C. Leveraging Value Similarity

  • Weight similarity supports codebook compression and computation reuse, but decoding shared values can add hardware costs.Value sharing compressed pruned models by up to an order of magnitude; Cambricon-S's decoder incurred 32.56% of total on-chip area and 3.98% of total on-chip power.Source: C. Leveraging Value Similarity · p. 25
  • Input or output similarity can avoid repeated computation through differential processing, memoized partial sums, or prediction-based skipping.After uniform linear quantization, about 61% of input activations matched the previous execution and 66% of computations could be avoided; UCNN reported 1.8× speedup for CNNs with up to 24% PE area overhead.Source: C. Leveraging Value Similarity · pp. 25–26
  • Frame-level similarity techniques can reuse prior outputs or skip predicted frames, while early-termination methods stop computations predicted to be ineffective for later layers.For AlexNet CONV layers, 18%–81% of computations could be reused; EVA2 identified 78%–96% of AlexNet frames and 40%–71% of Faster-RCNN frames as predicted frames on YouTube-BoundingBoxes.Source: C. Leveraging Value Similarity · p. 26

6) Optimization opportunities:

Load balancing techniques address utilization losses caused by uneven nonzero work across and within processing elements, using software reorganization, pruning, or hardware work sharing. The section also identifies co-design opportunities for balancing computations and exploiting value similarity.

6) Optimization opportunities:

  • Co-design can explore tensor value sharing jointly or use a compact differential-computing module to reduce PE-array modifications.Differential computing can condition execution on input mismatch and reuse prior results otherwise.Source: 6) Optimization opportunities · p. 26

X. LOAD BALANCING OF EFFECTUAL COMPUTATIONS

  • Software-directed balancing uses local dense regions, sorting, or structured pruning, while dynamic hardware work sharing can rebalance computations at runtime.Software approaches often require little additional hardware but are commonly limited to static weight sparsity.Source: §X · p. 27

A. Sources and Impact of Imbalance

  • Inter-PE imbalance idled up to 40% of SCNN cycles; intra-PE multiplier utilization fell below 80% across GoogLeNet layers and to 20% in its last two inception modules.SNAP multiplier utilization fell below 80% at moderate sparsity and to 20% at 90% sparsity.Source: A. Sources and Impact of Imbalance · p. 27

B. Software Directed Load Balance

  • Clustering nonzeros into dense regions can improve PE utilization, but may not work for dynamic unstructured sparsity or generic tensor operations.CCR eliminated about 79% of ineffectual computations and 51% of their storage for VGG-16, but may be difficult to extend beyond its supported operations.Source: B. Software Directed Load Balance · p. 27
  • For pruned AlexNet CONV1 on a 4×3 PE array, sorting weights filter-wise and input-channel-wise reduced workgroup allocated-NZ variation from up to 21.4× (6.09× average) before reorganization to 1.36× after.The evaluation processed 64 filters across 16 workgroups.Source: B. Software Directed Load Balance · pp. 27–28
  • ZENA’s static sorting yielded 20%–32% more acceleration for AlexNet and VGG-16 CONV layers.Sorting reduced the maximum workgroup disparity from 21.4× before reorganization to 1.36× afterward.Source: B. Software Directed Load Balance · p. 28
  • Accelerator-aware pruning can equalize work across submatrices or PEs, including k:n block-sparsity and coarse-grained weight pruning.Cambricon-S removes connections across all 16 output activations in local regions, so PEs process equal numbers of nonzero inputs and weights.Source: B. Software Directed Load Balance · p. 28

C. Load Balancing with Hardware Structures

Hardware load balancing ranges from prefetching work asynchronously to centralized runtime sharing, while write-back and data-layout choices address irregular outputs and convolution execution. The section also identifies co-design options for reducing load-balance hardware costs.

C. Load Balancing with Hardware Structures

  • FIFO prefetching in EIE reduced PE idle time from about 47% to 13%, with an NZ activation available during 87%–91% of computation cycles.A FIFO size of 8 or higher achieved this result.Source: C. Load Balancing with Hardware… · p. 28
  • ZENA’s centralized work sharing improved acceleration by about 10% for AlexNet and VGG-16 CONV layers.A leading PE-group can take an activation tile from the straggling group with the largest remaining-work count.Source: C. Load Balancing with Hardware… · p. 28
  • LNPU’s input load balancer increased PE utilization by 2%–26% across 10%–90% input sparsity.It fetches compressed elements, decodes indices, and selectively pushes nonzeros into PE-row FIFOs using bitmaps.Source: C. Load Balancing with Hardware… · p. 28

D. Optimization Opportunities

  • Most accelerators lack dedicated PE-balancing support; data reorganization mainly targets static weight sparsity, while co-design can address dynamic sparsity.Mapping, structured pruning, or operator refactoring may induce balanced computations, sometimes at modest accuracy loss.Source: D. Optimization Opportunities · p. 29

A. Write-Back from PEs

  • Simultaneous write-back can overlap communication with computation, but high-bandwidth fat-tree networks may add overhead and use bandwidth inefficiently.Common buses offer a time-shared alternative; synchronized sequential write-back can simplify programming and avoid specialized support.Source: A. Write-Back from PEs · p. 29

B. Data Assembling

  • Output assembly uses PE-produced metadata or known indices to place partial outputs, and may also transform layouts for the next layer.Some designs assemble locally, centrally, or through global accumulators.Source: B. Data Assembling · p. 29

C. Data Layout Transformations

  • NHWC data reorganization supports iterative channel-wise convolution, while Toeplitz conversion enables sparse GEMM at the cost of duplicated neighborhood data.For unit-strided convolution, the Toeplitz transform uses Fy×Fx times more memory.Source: C. Data Layout Transformations · pp. 29–30

D. On-the-fly Encoding

The section surveys on-the-fly tensor encoding and compiler support for sparse computation, including intermediate representations and their trade-offs. Polyhedral and interval-based representations differ in expressiveness and compilation cost.

D. On-the-fly Encoding

  • On-the-fly encoding reduces off-chip memory accesses and supports dynamically sparse tensors, with reported low on-chip area and power costs.The RLC encoder-decoder unit uses 2.5% and 3.06% in SqueezeFlow and 0.3% of total on-chip area in Eyeriss.Source: D. On-the-fly Encoding · p. 30
  • Sticker selects COO, bitmap, or dense encoding for high, medium, or low sparsity using two thresholds.Weights are pre-encoded offline; online activations are detected, buffered, and encoded in the selected mode.Source: D. On-the-fly Encoding · p. 30

XII. COMPILER SUPPORT

  • Compiler support covers intermediate representations, sparse-tensor challenges, compiler optimizations, accelerator ISAs, and code generation.The survey frames these areas as support for representing, optimizing, and generating code for sparse accelerator execution.Source: §XII · p. 30

A. Intermediate Representations

  • Low-level IRs may lose loop and data-layout information needed for high-level optimizations, motivating tensor- and loop-aware representations.TVM, Tiramisu, and Halide perform many optimizations on high-level IRs; MLIR is also motivated as a high-level IR for low-level compilers.Source: A. Intermediate Representations · p. 30
  • Polyhedral representations precisely model statement instances, support affine transformations, and express non-rectangular iteration domains.They use integer sets and maps to represent iteration domains, transformations, dependencies, and memory accesses.Source: A. Intermediate Representations · pp. 30–31
  • The classical polyhedral model is limited for non-affine code, and its computationally expensive operations make compilation slower than non-polyhedral alternatives.Recent extensions support some non-affine accesses, bounds, and conditionals; clustering statements into macro-statements can reduce compilation time.Source: A. Intermediate Representations · p. 31
  • Interval-based representations compile faster and can support some non-affine transformations, but cannot naturally express non-rectangular iteration spaces.They also make complex affine transformations such as iteration-space skewing difficult.Source: A. Intermediate Representations · p. 31
  • Many interval-based compilers assume acyclic dataflow, which can block legal loop fusions; their dependence analysis is less precise than polyhedral analysis.The cited discussion notes this limitation for Halide’s compute_with loop fusion.Source: A. Intermediate Representations · p. 31

B. Support for Sparse Tensors

Sparse tensor code challenges compilers with non-static loop bounds, accesses, and conditionals. Compiler approaches trade user control against automation, while cost models remain important to optimization quality.

B. Support for Sparse Tensors

  • Sparse tensor code uses non-static loop bounds, non-static array accesses, and conditionals that are difficult to analyze at compile time.The section illustrates this with direct convolution over sparse tensors.Source: B. Support for Sparse Tensors · p. 31
  • Tiramisu extends the polyhedral model for W-sparsity, approximating conditional accesses and representing non-static bounds and accesses as parameters.Code generation reinserts conditionals; the described techniques introduce compiler approximations,.Source: B. Support for Sparse Tensors · p. 32
  • Acorns fuses CNN operators, converts sparse layouts, and optimizes template code, while TACO generates sparse-operation code from iteration graphs and schedules.Acorns targets IA-sparsity and uses tiling, vectorization, and weight packing; it does not implement advanced iteration-space skewing.Source: B. Support for Sparse Tensors · p. 32

C. Compiler Optimizations

  • Semi-automatic compilers separate algorithms from optimization schedules, giving users control over transformations that automatic optimization may not optimize best.Halide, Tiramisu, and TVM are examples; deep-learning compilers may encode optimizations in operator libraries and automate selected choices such as fusion.Source: C. Compiler Optimizations · p. 32
  • Fully automatic compilers use algorithms such as Pluto to select statement schedules, but may lack fine-grained user control and produce suboptimal performance.The section attributes this risk to imprecise cost models; Pluto does not consider redundant computation, data layout, or generated control-flow complexity.Source: C. Compiler Optimizations · p. 32
  • Automatic optimization searches combinations of code transformations and needs a search technique and cost model to estimate execution time.Hand-tuned and machine-learning models may not precisely capture hardware complexity; Ithemal predicts x86 basic-block throughput with less than half the error of the cited hand-tuned models,.Source: C. Compiler Optimizations · p. 32

D. Accelerator ISAs and Code Generation

Accelerator ISAs and software stacks simplify execution of ML operators, while model, hardware, and compression co-designs offer avenues for compact-model acceleration. The section also identifies search-space and sparsity-support gaps in current tools.

D. Accelerator ISAs and Code Generation

  • High-level tensor instructions simplify compiler work, but compilers still manage data copies and accelerator interfaces can leave sparsity unsupported.Cambricon ISA supports common matrix and vector operations but lacks sparsity-specific instructions; Sticker configures layer execution and overlaps instruction distribution with computation.Source: D. Accelerator ISAs and Code Generation · pp. 33–34
  • SIMD/vector processing and PE control reduce instruction-delivery overhead by applying instructions across tensor blocks or repeating execution sequences.Accelerators may also configure finite-state machines before executing a model or layer.Source: D. Accelerator ISAs and Code Generation · p. 33
  • Libraries, code generation, and runtime stacks map model primitives to accelerator-specific execution, while frameworks such as TVM support custom backends and tensorization.Accelerators also benefit from integration with multiple ML-framework front ends.Source: D. Accelerator ISAs and Code Generation · p. 33

A. Hardware/Software/Model Co-designs

  • Hardware-aware compression should account for supported bit widths, sparsity patterns, and accelerator cost models when selecting pruning, precision, and tensor shapes.The section notes that unsupported bit widths may require zero padding, causing inefficient storage and processing.Source: A. Hardware/Software/Model Co-designs · p. 34
  • Joint exploration of pruning, quantization, and value similarity may compress models further, but hardware-friendly constraints and automated hyperparameter search remain important.The section notes that quantization can increase sparsity and pruning can reduce required bit widths; the exploration should account for accuracy tolerance and accelerator costs.Source: A. Hardware/Software/Model Co-designs · p. 34
  • Value-aware NAS and accelerator/model co-design span model, compression, mapping, and hardware searches, creating a large exploration space.NAS may take several GPU days, and the section identifies automated exploration of the resulting joint space as a challenge,,,,.Source: A. Hardware/Software/Model Co-designs · p. 34
  • Preprocessing can arrange structured dense regions or reorganize sparsity for existing systolic or in-memory engines when major design changes are infeasible.The section proposes host-processor or additional-hardware preprocessing, including sparsification or reorganization at almost no accuracy loss.Source: A. Hardware/Software/Model Co-designs · p. 35

B. Design Tools and Frameworks

  • Most accelerator-design frameworks target dense fixed-width tensors, while reusable sparse-data modules and configurable hardware features could support faster prototyping and design exploration.The proposed features include encoding and extraction, dynamic load balancing, data reorganization, configurable functional units, and interconnects.Source: B. Design Tools and Frameworks · p. 35

C. Accelerating Training of ML Models

The paper surveys hardware and software support for sparse and irregular ML tensors, including training and opportunities for accelerator/model co-design. It analyzes design trade-offs and identifies further acceleration opportunities.

C. Accelerating Training of ML Models

  • Training accelerators still have gaps in sparsity, irregular tensor utilization, and mixed-precision support, leaving opportunities for performance and energy-efficiency gains.Cross-layer gradient reuse and mixed-precision tensors are identified as possible training optimizations.Source: C. Accelerating Training of ML Models · p. 35

D. Applying Techniques for Sparsity to Other Domains

  • Sparsity techniques from ML may inform other processing-intensive domains, including graphs, databases, genomics, and compression.Finding intersecting non-zeros is analogous to database joins.Source: D. Applying Techniques for Sparsity to… · p. 35

XIV. RELATED WORK

  • Unlike prior surveys, this work connects sparse-tensor challenges to hardware and software support, including extraction, dataflows, memory, communication, load balancing, and compilers.It also covers mixed-precision and value-shared sparse tensors.Source: §XIV · p. 36

XV. SUMMARY

  • The survey analyzes accelerator designs and recent-DNN speedups, finding that moderate sparsity can be exploited while high or hyper sparsity leaves further opportunities.High or hyper sparsity requires efficient extraction and load balancing; configurable NoCs, functional units, and buffers are also identified as needed.Source: §XV · p. 36
  • Block-sparse tensors can improve storage efficiency, especially at hyper sparsity, and simplify extraction while supporting balanced computation.Existing extraction mechanisms may not extract enough non-zeros at high or hyper sparsity in large tensors.Source: §XV · p. 36
  • Sparsity lowers data reuse, but compressed tensors can fit more data on-chip; at high sparsity, execution may become bandwidth-bounded.Configurable interconnects support diverse communication patterns and asymmetric spatial accumulation of partial outputs.Source: §XV · pp. 36–37
  • The survey identifies load balancing, configurable processing, and compiler support as needs for efficient sparse execution across layers and sparsity patterns.It discusses hardware for asynchronous computation or work sharing, structured sparsity, operator transformations, and compiler support for sparse intermediate representations.Source: §XV · p. 37
  • Accelerator/model co-design and automated joint exploration of compression, quantization, shape reduction, and dataflow remain opportunities for further innovation.The conclusion characterizes efficient compact-model processing as an active research frontier.Source: §XV · p. 37

APPENDIX HARDWARE ACCELERATORS CAN

Unstructured sparsity is difficult to exploit on CPUs and GPUs, where irregularity can limit or reverse performance gains. Accelerators designed for sparse tensors can achieve substantial speedups, particularly at hyper sparsity.

EXPLOIT SPARSITY BETTER

  • 15.5× for CONV and 48.5× for FC: Cambricon-X reported these speedups at hyper sparsity over dense execution.The design reported performance gains at 5% or more sparsity.Source: EXPLOIT SPARSITY BETTER · p. 37
  • Below 1.4× or even slowdowns: AlexNet GPU experiments with CSR-encoded matrices found limited speedups at high sparsity.Scattered non-zeros can impair locality and make skipping work and balancing threads difficult.Source: EXPLOIT SPARSITY BETTER · p. 37
  • At 90.94% average sparsity, GPU geomean speedup was 23.34%, while CPU execution took 110% more time.The cited CPU and GPU comparisons used sparse BLAS or cuSPARSE against dense Caffe execution.Source: EXPLOIT SPARSITY BETTER · p. 37

Related papers

Loading 2007.00864v2…