Accelerating Sparse Tensor Decomposition Using Adaptive Linearized Representation
- 20 March 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 36 (5) , 1025-1041
Abstract
High-dimensional sparse data emerge in many critical application domains such as healthcare and cybersecurity. To extract meaningful insights from massive volumes of these multi-dimensional data, scientists employ unsupervised analysis tools based on tensor decomposition (TD) methods. However, real-world sparse tensors exhibit highly irregular shapes and data distributions, which pose significant challenges for making efficient use of modern parallel processors. This study breaks the prevailing assumption that compressing sparse tensors into coarse-grained structures (i.e., tensor slices or blocks) or along a particular dimension/mode (i.e., mode-specific) is more efficient than keeping them in a fine-grained, mode-agnostic form. Our novel sparse tensor representation, Adaptive Linearized Tensor Order (${\sf ALTO}$ ), encodes tensors in a compact format that can be easily streamed from memory and is amenable to both caching and parallel execution. In contrast to existing compressed tensor formats, ${\sf ALTO}$ constructs one tensor copy that is agnostic to both the mode orientation and the irregular distribution of nonzero elements. To demonstrate the efficacy of ${\sf ALTO}$ , we accelerate popular TD methods that compute the Canonical Polyadic Decomposition (CPD) model across different types of sparse tensors. We propose a set of parallel TD algorithms that exploit the inherent data reuse of tensor computations to substantially reduce synchronization overhead, decrease memory footprint, and improve parallel performance. Additionally, we characterize the major execution bottlenecks of TD methods on multiple generations of the latest Intel Xeon Scalable processors, including Sapphire Rapids CPUs, and introduce dynamic adaptation heuristics to automatically select the best algorithm based on the sparse tensor characteristics. Across a diverse set of real-world data sets, ${\sf ALTO}$ outperforms the state-of-the-art approaches, achieving more than an order-of-magnitude speedup over the best mode-agnostic formats. Compared to the best mode-specific formats, which require multiple tensor copies, ${\sf ALTO}$ achieves $5.1\times$ geometric mean speedup at a fraction (25% ) of their storage costs. Moreover, ${\sf ALTO}$ obtains $8.4\times$ geometric mean speedup over the state-of-the-art memoization approach, which reduces computations by using extra memory, while requiring 14% of its memory consumption.
Keywords
All Related Versions
This publication has 48 references indexed in Scilit:
- Computationally Efficient CP Tensor Decomposition Update Framework for Emerging Component Discovery in Streaming Data2018
- Extracting the multi-timescale activity patterns of online financial marketsScientific Reports, 2018
- A Unified Optimization Approach for Sparse Tensor Operations on GPUs2017
- Accelerating the Tucker Decomposition with Compressed Sparse Tensors2017
- Tensorlab 3.0 — Numerical optimization strategies for large-scale constrained and coupled matrix/tensor factorization2016
- A survey of techniques for designing and managing CPU register fileConcurrency and Computation: Practice and Experience, 2016
- Tensor-based anomaly detection: An interdisciplinary surveyKnowledge-Based Systems, 2016
- Newton-based optimization for Kullback–Leibler nonnegative tensor factorizationsOptimization Methods and Software, 2015
- Efficient and scalable computations with sparse tensors2012
- Sur une courbe, qui remplit toute une aire planeMathematische Annalen, 1890