ALTO: adaptive linearized storage of sparse tensors
ALTO: adaptive linearized storage of sparse tensors
复制标题
DOI：
10.1145/3447818.3461703
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Ahmed E. Helal;Jan Laukemann;Fabio Checconi;Jesmin Jahan Tithi;Teresa M. Ranadive;F. Petrini;Jeewhan Choi
中科院分区：
文献类型：
--
作者：
Ahmed E. Helal;Jan Laukemann;Fabio Checconi;Jesmin Jahan Tithi;Teresa M. Ranadive;F. Petrini;Jeewhan Choi
高维稀疏数据的分析在许多重要的领域中变得越来越流行。然而，现实世界中的稀疏张量由于其不规则的形状和数据分布而具有挑战性。我们提出了自适应线性化张量顺序（ALTO）格式，一种新的模式不可知（一般）表示，保持相邻的非零元素在多维空间中彼此接近的内存。为了生成索引元数据，ALTO使用自适应位编码方案，该方案权衡索引计算以降低内存使用率和更有效地使用内存带宽。此外，通过将其稀疏表示与非零元素的不规则空间分布解耦，ALTO消除了工作负载不平衡，并大大降低了张量计算的同步开销。因此，基于ALTO的张量操作的并行性能成为其固有数据重用的函数。在所有张量数据集上，ALTO在关键张量分解操作中使用时，优于为每个数据集选择最佳最先进格式的oracle。具体而言，ALTO在最佳模式不可知（坐标和分层坐标）格式上实现了8倍的几何平均加速，同时相对于最佳模式特定（压缩稀疏光纤）格式提供了4.x的几何平均压缩比。
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.