This paper proposed two reordering schemes for sparse tensors: BFS-MCS and LEXI-ORDER. BFS-MCS 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. CANDECOMP/PARAFAC decomposition (CPD) is taken as an example to show their effect on existing three sparse tensor formats for CPUs: coordinate (COO), compressed sparse fiber (CSF), and hierarchical coordinate (HICOO). LEXI-ORDER obtains up to 4.14× speedup on sequential HICOO-MTTKRP and 11.88× speedup on its parallel case. COO- and CSF-MTTKRP also achieves performance improvement in different degree. Our two reordering methods are more efficient and effective than other state-of-the-art reordering methods used in SPLATT.
Revised: November 21, 2019 |
Published: June 26, 2019
Citation
Li J., B. Ucar, U. Catalyurek, J. Sun, K.J. Barker, and R. Vuduc. 2019.Efficient and Effective Sparse Tensor Reordering. In Proceedings of the ACM International Conference on Supercomputing (ICS 2019), June 26-28, 2019, Phoenix, AZ, 227-237. New York, New York:ACM.PNNL-SA-138751.doi:10.1145/3330345.3330366