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!):
Complete list of metadata

Cited literature [49 references]  Display  Hide  Download
Contributor : Bora Uçar Connect in order to contact the contributor
Submitted on : Thursday, October 24, 2019 - 4:53:16 PM
Last modification on : Friday, September 30, 2022 - 4:12:22 AM
Long-term archiving on: : Saturday, January 25, 2020 - 5:28:25 PM


Files produced by the author(s)




Jiajia Li, Bora Uçar, Ümit V. Çatalyürek, 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⟩



Record views


Files downloads