Efficient and effective sparse tensor reordering

Jiajia Li, Bora Uçar, V. Çatalyürek, Jimeng Sun, Kevin Barker, Richard Vuduc

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

Abstract

This paper formalizes the problem of reordering a sparse tensor to improve the spatial and temporal locality of operations with it, and proposes two reordering algorithms for this problem, which we call BFS-MCS and Lexi-Order. The BFS-MCS method is a Breadth First Search (BFS)-like heuristic approach based on the maximum cardinality search family; Lexi-Order is an extension of doubly lexical ordering of matrices to tensors. We show the effects of these schemes within the context of a widely used tensor computation, the CANDECOMP/PARAFAC decomposition (CPD), when storing the tensor in three previously proposed sparse tensor formats: coordinate (COO), compressed sparse fiber (CSF), and hierarchical coordinate (HiCOO). A new partition-based superblock scheduling is also proposed for HiCOO format to improve load balance. On modern multicore CPUs, we show Lexi-Order obtains up to 4.14× speedup on sequential HiCOO-Mttkrp and 11.88× speedup on its parallel counterpart. The performance of COO- and CSF-based Mttkrps also improves. Our two reordering methods are more effective than state-of-the-art approaches. The code is released as part of Parallel Tensor Infrastructure (ParTI!): https://github.com/hpcgarage/ParTI.

Original languageEnglish (US)
Title of host publicationICS 2019 - International Conference on Supercomputing
PublisherAssociation for Computing Machinery
Pages227-237
Number of pages11
ISBN (Electronic)9781450360791
DOIs
StatePublished - Jun 26 2019
Externally publishedYes
Event33rd ACM International Conference on Supercomputing, ICS 2019, held in conjunction with the Federated Computing Research Conference, FCRC 2019 - Phoenix, United States
Duration: Jun 26 2019 → …

Publication series

NameProceedings of the International Conference on Supercomputing

Conference

Conference33rd ACM International Conference on Supercomputing, ICS 2019, held in conjunction with the Federated Computing Research Conference, FCRC 2019
CountryUnited States
CityPhoenix
Period6/26/19 → …

Keywords

  • HiCOO
  • Hierarchical coordinate
  • Reordering
  • Sparse tensor
  • Tensor decomposition

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient and effective sparse tensor reordering'. Together they form a unique fingerprint.

  • Cite this

    Li, J., Uçar, B., Çatalyürek, V., Sun, J., Barker, K., & Vuduc, R. (2019). Efficient and effective sparse tensor reordering. In ICS 2019 - International Conference on Supercomputing (pp. 227-237). (Proceedings of the International Conference on Supercomputing). Association for Computing Machinery. https://doi.org/10.1145/3330345.3330366