search-icon
Paper
:
HiCOO: Hierarchical Storage of Sparse Tensors
Event Type
Paper
Registration Categories
TP
Tags
Algorithms
Graph Algorithms
Linear Algebra
Machine Learning
Sparse Computation
Finalists
BSP Finalist
TimeTuesday, November 13th3:30pm - 4pm
LocationC141/143/149
DescriptionThis paper proposes a new storage format for sparse tensors, called Hierarchical COOrdinate (HiCOO; pronounced: “haiku”). It derives from coordinate (COO) format, arguably the de facto standard for general sparse tensor storage. HiCOO improves upon COO by compressing the indices in units of sparse tensor blocks, with the goals of preserving the “mode-agnostic” simplicity of COO while reducing the bytes needed to represent the tensor and promoting data locality. We evaluate HiCOO by implementing a single-node, multicore-parallel version of the matricized tensor-times-Khatri-Rao product (MTTKRP) operation, which is the most expensive computational core in the widely used CANDECOMP/PARAFAC decomposition(CPD) algorithm. This MTTKRP implementation achieves up to 23.0× (6.8× on average) speedup over COO format and up to 15.6× (3.1× on average) speedup over another state-of-the-art format, compressed sparse fiber (CSF), by using less or comparable storage of them. When used within CPD, we also observe speedups against COO- and CSF-based implementations.
Archive
Back To Top Button