UniSparse: An Intermediate Language for General Sparse Format Customization

Jie Liu, Zhongyuan Zhao, Zijian Ding, Benjamin Brock, Hongbo Rong, Zhiru Zhang

Introduction

Sparse data structures are foundational to modern computing, appearing in diverse domains such as graph analytics, scientific simulations, and pruned deep learning models. To optimize memory usage and computational throughput, developers rely on sparse formats like Compressed Sparse Row (CSR) or Coordinate (COO). However, as hardware architectures become increasingly specialized—encompassing GPUs, FPGAs, and Processing-in-Memory (PIM) systems—standard formats often fail to exploit specific hardware strengths.

Existing sparse compilers, such as TACO, typically utilize an "attribute-based" abstraction, categorizing dimensions as either "dense" or "compressed." While effective for standard formats, this approach is too rigid to describe complex, hardware-aware, or hybrid structures. Consequently, engineers are often forced to manually implement format conversions and computational kernels, a process that is both error-prone and difficult to scale. This paper introduces UniSparse, an intermediate language (IL) and compiler designed to decouple a tensor's logical data structure from its physical memory layout, enabling general sparse format customization.

The UniSparse Abstraction

The core innovation of UniSparse lies in its expressive, language-based abstraction. Rather than relying on simple attributes, UniSparse represents sparse tensors through several key components:

  • The Metadata Tree: A hierarchical logical representation where dimensions are stacked to define the tensor's structure.
  • Index Maps: Mathematical functions that map logical coordinates (e.g., row and column) to physical locations or specialized offsets, such as diagonal indices.
  • Query and Mutation Primitives: A set of operations—including trim (to remove zeros), merge (to fuse redundant metadata), and sum (to analyze sparsity patterns)—that allow the compiler to reason about and manipulate the underlying data.
  • Layout Primitives: Operations such as pack (converting Structure-of-Arrays to Array-of-Structures) and partition (distributing data across memory banks) that define the final physical arrangement in memory.

By separating the logical definition of the data structure from its physical implementation, UniSparse allows for the expression of formats that were previously incompatible with automated compilers.

Compiler Architecture and Conversion

UniSparse is implemented as a dialect within the Multi-Level Intermediate Representation (MLIR) framework. The compiler features a formal Format Conversion Algorithm that utilizes rewrite rules to automatically transform data between arbitrary source and destination formats. This approach treats format conversion as a series of reversible mathematical transformations, ensuring that the compiler can find an optimal path from a simple representation (like COO) to a complex, hardware-specific layout.

The code generation process follows a two-step methodology. First, the compiler generates a functionally correct "exhaustive" loop nest that covers all possible iterations. Second, it applies optimization passes to prune redundant iterations based on the specific sparsity pattern and format constraints, resulting in high-performance executable code.

Evaluation and Results

The researchers evaluated UniSparse using a diverse suite of real-world datasets, including the SuiteSparse and SNAP collections for scientific computing, the Open Graph Benchmark (OGB) for machine learning, and pruned Transformer models (BERT-style) with sparsity levels ranging from 50% to 95%.

UniSparse demonstrated significant performance improvements by enabling specialized formats across various hardware targets:

  • Heterogeneous Systems: By implementing a hybrid BDIA/CSR format across a combined CPU and GPU setup, UniSparse achieved a 5.63x geomean speedup over a standard CPU-only implementation.
  • GPU Acceleration: For sparse matrix-matrix multiplication (SpMM) on an NVIDIA RTX A6000, a hybrid BELL/COO format generated by UniSparse resulted in a 2.7x speedup compared to the standard CSR format.
  • FPGA Throughput: UniSparse successfully automated the generation of the "Serpens" format for FPGAs, matching the performance of hand-optimized implementations and providing 1.91x better throughput than previous automated tools.
  • PIM Load Balancing: On simulated Processing-in-Memory hardware, the custom "CISR-plus" format mitigated load imbalances, leading to a 1.54x speedup over simpler banked formats.

Discussion and Future Work

UniSparse highlights the power of decoupling logical and physical representations in sparse computing. One of its most significant capabilities is input-adaptive customization, where the compiler analyzes the sparsity pattern of an input matrix at runtime to decompose it into sub-tensors, applying different formats to different regions (e.g., a diagonal format for a dense core and CSR for the remainder).

However, certain limitations remain. Some primitives, such as indirect maps used for load balancing, are currently non-reversible, complicating automated conversion away from those formats. Additionally, users must still provide certain tuning parameters, such as blocking sizes or sparsity thresholds. Future research may explore the integration of machine learning or heuristic search algorithms to automatically determine the optimal UniSparse format for a specific matrix and hardware target, further reducing the need for manual intervention.

Conclusion

UniSparse represents a significant step forward in sparse computing by providing a flexible, expressive intermediate language for format customization. By automating the generation of high-performance code for diverse hardware, it bridges the gap between general-purpose sparse compilers and hand-optimized, hardware-specific implementations.

Summary updated

BibTeX
@article{liu2024unisparse,
  author = {Jie Liu and Zhongyuan Zhao and Zijian Ding and Benjamin Brock and Hongbo Rong and Zhiru Zhang},
  title = {{UniSparse: An Intermediate Language for General Sparse Format Customization}},
  journal = {Proc. ACM Program. Lang.},
  year = {2024},
  doi = {10.1145/3649816},
}
Figure