Efficient parallel sparse tensor contraction
Contraction efficace et parallèle des tenseurs creux
Résumé
We investigate the performance of algorithms for sparse tensor-sparse tensor multiplication (SpGeTT).
This operation, also called sparse tensor contraction, is a higher order analogue of the sparse matrix-sparse
matrix multiplication (SpGeMM) operation. Therefore,
SpGeTT can be performed by first converting the input tensors into matrices, then invoking high performance
variants of SpGeMM, and finally reconverting the resultant matrix into a tensor.
Alternatively, one can carry out the scalar operations underlying SpGeTT in the realm of tensors without
matrix formulation.
We discuss the building blocks in both approaches and formulate a hashing-based method to avoid costly search
or redirection operations.
We present performance results with the current state-of-the-art SpGeMM-based approaches, existing SpGeTT approaches,
and a carefully implemented SpGeTT approach with a new fine-tuned hashing method, proposed in this paper.
We evaluate the methods on real world tensors, contracting a tensor with itself along various dimensions.
Our proposed hashing-based method for SpGETT consistently outperforms the state-of-the-art method, achieving a 25% reduction in sequential execution time on average and a 21% reduction in parallel execution time on average across a variety of input instances.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|---|
| licence |
