HiCOO: Hierarchical storage of sparse tensors

Jiajia Li, Jimeng Sun, Richard Vuduc

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This 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.

Original languageEnglish (US)
Title of host publicationProceedings - International Conference for High Performance Computing, Networking, Storage, and Analysis, SC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages238-252
Number of pages15
ISBN (Electronic)9781538683842
DOIs
StatePublished - Mar 11 2019
Externally publishedYes
Event2018 International Conference for High Performance Computing, Networking, Storage, and Analysis, SC 2018 - Dallas, United States
Duration: Nov 11 2018Nov 16 2018

Publication series

NameProceedings - International Conference for High Performance Computing, Networking, Storage, and Analysis, SC 2018

Conference

Conference2018 International Conference for High Performance Computing, Networking, Storage, and Analysis, SC 2018
CountryUnited States
CityDallas
Period11/11/1811/16/18

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'HiCOO: Hierarchical storage of sparse tensors'. Together they form a unique fingerprint.

  • Cite this

    Li, J., Sun, J., & Vuduc, R. (2019). HiCOO: Hierarchical storage of sparse tensors. In Proceedings - International Conference for High Performance Computing, Networking, Storage, and Analysis, SC 2018 (pp. 238-252). [8665782] (Proceedings - International Conference for High Performance Computing, Networking, Storage, and Analysis, SC 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SC.2018.00022