Sparse Operator Fusion

Launching a GPU or NPU kernel involves significant fixed latency for driver calls, argument passing, and synchronization. In a naive sparse inference pipeline, each layer (e.g., sparse linear, ReLU, normalization) is a separate kernel. Fusion combines these into one kernel, amortizing this overhead. For small batch sizes or layers with low operational intensity, launch latency can dominate execution time, making fusion critical for real-time performance.

The 'memory wall' is the dominant bottleneck for sparse compute. Without fusion, the output of one sparse layer (e.g., a sparse matrix multiplication) is written to global DRAM, only to be immediately read back as input for the next layer (e.g., an activation). This store/load cycle consumes precious memory bandwidth. Fusion keeps intermediate results in fast on-chip registers or shared memory, bypassing DRAM entirely. This can reduce off-chip memory traffic by 2-4x for common layer sequences.

Individual sparse kernels skip computations where their input operands are zero. Fusion allows for more aggressive skipping based on the collective semantics of the fused operators. For example, in a fused SparseLinear + ReLU kernel, if the linear output for a neuron is negative, the subsequent ReLU will zero it. A fused kernel can skip downstream dependent computations (like writes) immediately, saving additional cycles. This creates optimization opportunities invisible to separate kernels.

Sparse computations suffer from irregular memory access patterns, leading to poor cache efficiency. Fusion improves temporal locality by ensuring that data loaded for the first operation is still hot in the cache for the second. For instance, the non-zero weight indices fetched for a sparse matmul can be reused in a subsequent fused sparse operation without a second cache miss. This maximizes the utility of every memory transaction, crucial for bandwidth-bound operations.

Fusion is not a runtime heuristic; it is a deterministic transformation applied by the model compiler (e.g., TVM, XLA, or proprietary NPU compilers) during graph lowering. The compiler:

• Identifies fusible subgraphs (e.g., linear -> activation -> normalization).
• Validates data dependencies and tensor layouts.
• Generates a single, custom fused kernel that implements the combined semantics. This kernel is often hand-tuned or auto-scheduled for the target hardware's memory hierarchy and SIMD width.

A fused kernel provides a larger, more complex workload for the hardware scheduler, enabling optimizations impossible with micro-kernels. Examples include:

• Warp-Level Pipelining: Seamlessly pipeline the gather-compute-scatter phases of consecutive sparse ops within a single warp.
• Persistent Thread Blocks: Keep thread blocks resident to process multiple elements across fused operations, reducing context-switch overhead.
• Specialized ISA Use: Leverage unique accelerator instructions (e.g., sparse tensor cores) across a compound operation. The fusion boundary defines the scope for these low-level optimizations.

A family of data structures for efficiently storing and operating on tensors where most elements are zero. Instead of storing all values, these formats encode only the non-zero values and their indices. Common formats include:

• CSR (Compressed Sparse Row): Efficient for row-wise operations.
• CSC (Compressed Sparse Column): Efficient for column-wise operations.
• COO (Coordinate Format): Simple list of (index, value) tuples. The choice of format directly impacts the efficiency of the gather-scatter patterns used in sparse operator fusion.

The fundamental computational kernel for multiplying a sparse matrix by a dense matrix. It is the core operation in sparse linear layers and the primary target for fusion. Efficient SpMM implementations avoid computations with zero weights by using:

• Gather operations to fetch the relevant dense activations.
• Scatter operations to accumulate partial results. Fusing a subsequent element-wise operation (like ReLU) into the SpMM kernel eliminates the need to write and then immediately read the large intermediate result matrix.

The compiler-level process of transforming a model's computational graph for optimal execution. This includes:

• Operator Fusion: Combining consecutive nodes (e.g., SpMM + ReLU) into a single kernel.
• Constant Folding: Pre-computing static parts of the graph.
• Dead Code Elimination: Removing unused operations. For sparse models, the graph optimizer identifies chains of sparse and element-wise operations that are candidates for fusion, analyzing data dependencies and memory access patterns to maximize locality.

Critical parallel computing primitives for sparse computation. Due to irregular data access, these operations are often the performance bottleneck.

• Gather: Reads a set of values from non-contiguous memory addresses (e.g., fetching activations corresponding to non-zero weights) into a contiguous vector for efficient computation.
• Scatter: Writes a contiguous vector of results back to non-contiguous memory addresses. Fusion minimizes the total number of expensive gather-scatter cycles by reusing fetched data across multiple operations before scattering the final result.

The additional computational cost incurred during sparse execution beyond the floating-point operations (FLOPs). This overhead includes:

• Index Decoding: Processing the CSR/COO metadata to locate non-zeros.
• Conditional Branching: Instructions to check for zero values or manage control flow.
• Memory Latency: Non-coalesced memory accesses from irregular patterns. Sparse operator fusion aims to amortize this fixed overhead across multiple logical operations. By executing two operations in one kernel launch, it pays the index decoding and launch cost only once, improving overall efficiency.

The process by which a compiler maps an abstract sparse computational graph onto the specific execution units of target hardware. This involves:

• Selecting the optimal sparse data layout (e.g., blocked formats for Tensor Cores).
• Scheduling operations to hide memory latency.
• Utilizing specialized ISA extensions for scatter/gather. For fusion, the compiler must verify that the fused kernel pattern can be efficiently expressed on the target's execution model (e.g., GPU warps, NPU vector units) without causing resource conflicts or excessive register pressure.