ALTO: Adaptive Linearized Storage of Sparse Tensors

Helal AE, Laukemann J, Checconi F, Tithi JJ, Ranadive T, Petrini F, Choi J (2021)

Publication Language: English

Publication Type: Conference contribution, Conference Contribution

Publication year: 2021

Series: ICS '21: Proceedings of the ACM International Conference on Supercomputing

Pages Range: 404 - 416

Event location: Virtual Event, USA US

ISBN: 9781450383356

URI: https://dl.acm.org/doi/10.1145/3447818.3461703

DOI: 10.1145/3447818.3461703

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.x relative to the best mode-specific (compressed sparse fiber) formats.

Authors with CRIS profile

Jan Laukemann Erlangen National High Performance Computing Center (NHR@FAU)

Involved external institutions

Intel Corporation US United States (USA) (US) University of Maryland US United States (USA) (US) University of Oregon (UO) US United States (USA) (US)

How to cite

APA:

Helal, A.E., Laukemann, J., Checconi, F., Tithi, J.J., Ranadive, T., Petrini, F., & Choi, J. (2021). ALTO: Adaptive Linearized Storage of Sparse Tensors. In Association for Computing Machinery, New York, NY, United States (Eds.), Proceedings of the ICS '21: 2021 International Conference on Supercomputing (pp. 404 - 416). Virtual Event, USA, US.

MLA:

Helal, Ahmed E, et al. "ALTO: Adaptive Linearized Storage of Sparse Tensors." Proceedings of the ICS '21: 2021 International Conference on Supercomputing, Virtual Event, USA Ed. Association for Computing Machinery, New York, NY, United States, 2021. 404 - 416.

BibTeX: Download