ALTO: Adaptive Linearized Storage of Sparse Tensors

Abstract

The analysis of high-dimensional sparse data is becoming increasingly popular in many important domains. However, real-world sparse tensors are challenging to process due to their irregular shapes and data distributions. We propose the Adaptive Linearized Tensor Order (ALTO) format, a novel mode-agnostic (general) representation that keeps neighboring nonzero elements in the multi-dimensional space close to each other in memory. To generate the indexing metadata, ALTO uses an adaptive bit encoding scheme that trades off index computations for lower memory usage and more effective use of memory bandwidth. Moreover, by decoupling its sparse representation from the irregular spatial distribution of nonzero elements, ALTO eliminates the workload imbalance and greatly reduces the synchronization overhead of tensor computations. As a result, the parallel performance of ALTO-based tensor operations becomes a function of their inherent data reuse. On a gamut of tensor datasets, ALTO outperforms an oracle that selects the best state-of-the-art format for each dataset, when used in key tensor decomposition operations. Specifically, ALTO achieves a geometric mean speedup of 8X over the best mode-agnostic (coordinate and hierarchical coordinate) formats, while delivering a geometric mean compression ratio of 4.3X relative to the best mode-specific (compressed sparse fiber) formats.

arXiv commentAccepted to ICS 2021

References in corpus (8)

• Tensor Decomposition for Signal Processing and Machine Learning
• Format Abstraction for Sparse Tensor Algebra Compilers
• uops.info: Characterizing Latency, Throughput, and Port Usage of Instructions on Intel Microarchitectures
• A Unified Optimization Approach for Sparse Tensor Operations on GPUs
• Software for Sparse Tensor Decomposition on Emerging Computing Architectures
• Automatic Throughput and Critical Path Analysis of x86 and ARM Assembly Kernels
• Sparse Tensor Transpositions
• Extracting the multi-timescale activity patterns of online financial markets

Cited by in corpus (4)

• Compiler Support for Sparse Tensor Computations in MLIR
• PRISM: Processing-In-Memory Sparse MTTKRP for Tensor Decomposition Acceleration
• A Sparse Tensor Generator with Efficient Feature Extraction
• Efficient, Out-of-Memory Sparse MTTKRP on Massively Parallel Architectures