Abstract
Sparse tensors are foundational to modern computational fields, yet they present significant optimization challenges due to the "curse of dimensionality" and irregular memory access patterns. This paper introduces PASTA, a comprehensive benchmark suite for sparse tensor computations. PASTA provides standardized implementations of five essential tensor kernels across CPU and GPU platforms, utilizing both traditional Coordinate (COO) and modern Hierarchical Coordinate (HiCOO) data formats to establish a consistent baseline for high-performance computing research.
Introduction
Sparse tensors—multi-dimensional arrays where the vast majority of entries are zero—are critical in domains such as machine learning, quantum chemistry, and social network analysis. Optimizing these structures is notoriously difficult. Unlike dense matrices, sparse tensors suffer from irregular memory access patterns and "mode orientation," where a specific data layout may favor some dimensions while penalizing others. As hardware becomes increasingly heterogeneous, the lack of standardized reference implementations makes it difficult to compare algorithms and data formats across CPUs and GPUs. PASTA addresses this gap by providing a diverse, consistent benchmark suite.
Methodology and Data Formats
The PASTA suite implements five core tensor kernels: Tew (element-wise), Ts (tensor-scalar), Ttv (tensor-times-vector), Ttm (tensor-times-matrix), and Mttkrp (matricized tensor-times-Khatri-Rao product). The latter is often the computational bottleneck in CP decompositions.
To manage these kernels, the researchers utilized two primary data formats. The Coordinate (COO) format serves as the standard "entry-list" baseline.
To improve cache locality and reduce storage overhead, the suite also includes the Hierarchical Coordinate (HiCOO) format, which compresses indices into blocks. Beyond the standard HiCOO, the paper introduces gHiCOO and sHiCOO variants to handle more flexible and semi-sparse scenarios, respectively. These hierarchical formats are designed to mitigate the memory-bound nature of sparse operations by boosting data locality.
Experimental Setup and Datasets
The suite includes 30 diverse tensors to ensure robust testing:
- Real-World (15): Sourced from the FROSTT repository, covering healthcare (choa), web data (flickr), and crime statistics (crime4d).
- Synthetic (15): Generated using Kronecker and Power Law models to test specific properties like "small world" characteristics common in real-world data.
Performance was analyzed using Roofline Models, which visualize how closely a kernel approaches theoretical hardware limits for memory bandwidth and peak compute.
Key Insights
- Memory-Bound Reality: Sparse tensor kernels are primarily limited by memory bandwidth rather than raw computational power. Consequently, data layout (like HiCOO) is more critical for performance than raw FLOP counts.
- Predictable Sparsity: For operations like Ttv and Ttm, the output sparsity pattern is predictable, allowing for pre-allocation and avoiding expensive dynamic memory management or data races during parallel execution.
- Hardware Trade-offs: While HiCOO significantly improves performance on CPUs by boosting locality, it can hinder GPUs. The blocking nature of HiCOO can lead to load imbalances, where some GPU threads are overworked while others remain idle.
- Cache Effects: Small tensors can appear to exceed 100% efficiency in Roofline models when they fit entirely within the CPU's Last Level Cache (LLC), bypassing DRAM bandwidth limits.
Results and Discussion
Performance across the suite varied significantly, from 0.8 GFLOPS to 81 GFLOPS, depending on the tensor and platform. On CPUs, HiCOO generally outperformed COO for Tew, Ts, and Ttv. For Mttkrp, HiCOO showed better memory efficiency but required more careful tuning to surpass the simplicity of COO.
Comparing hardware, NVIDIA Tesla V100 GPUs demonstrated a 3–7x advantage in peak performance and bandwidth over CPUs. However, the efficiency (percentage of peak utilized) was often lower on GPUs due to the inherent irregularity of sparse data.
Conclusion and Future Work
PASTA provides a vital reference for the community, but it remains an evolving project. Future work includes expanding the suite to include the Compressed Sparse Fiber (CSF) format, adding more complex operations like "TTM-chain" for Tucker decomposition, and extending support to distributed systems and FPGA architectures.
Summary updated