Skip to Main content Skip to Navigation
Conference papers

Efficient and effective sparse tensor reordering

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.
Complete list of metadatas

Cited literature [49 references]  Display  Hide  Download

https://hal.inria.fr/hal-02306569
Contributor : Bora Uçar <>
Submitted on : Thursday, October 24, 2019 - 4:53:16 PM
Last modification on : Tuesday, November 19, 2019 - 2:41:26 AM
Long-term archiving on: : Saturday, January 25, 2020 - 5:28:25 PM

File

li-ics.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jiajia Li, Bora Uçar, Umit Catalyurek, Jimeng Sun, Kevin Barker, et al.. Efficient and effective sparse tensor reordering. ICS 2019 - ACM International Conference on Supercomputing, Jun 2019, Phoenix, United States. pp.227-237, ⟨10.1145/3330345.3330366⟩. ⟨hal-02306569⟩

Share

Metrics

Record views

94

Files downloads

500