Skip to Main content Skip to Navigation
Journal articles

A multi-dimensional Morton-ordered block storage for mode-oblivious tensor computations

Abstract : Computation on tensors, treated as multidimensional arrays, revolve around generalized basic linear algebra subroutines (BLAS). We propose a novel data structure in which tensors are blocked and blocks are stored in an order determined by Morton order. This is not only proposed for efficiency reasons, but also to induce efficient performance regardless of which mode a generalized BLAS call is invoked for; we coin the term mode-oblivious to describe data structures and algorithms that induce such behavior. Experiments on one of the most bandwidth-bound generalized BLAS kernel, the tensor–vector multiplication, not only demonstrate superior performance over two state-of-the-art variants by up to 18%, but additionally show that the proposed data structure induces a 71% less sample standard deviation for tensor–vector multiplication across d modes, where d varies from 2 to 10. Finally, we show our data structure naturally expands to other tensor kernels and demonstrate up to 38% higher performance for the higher-order power method.
Document type :
Journal articles
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-02082524
Contributor : Equipe Roma <>
Submitted on : Thursday, March 28, 2019 - 12:06:39 PM
Last modification on : Wednesday, November 20, 2019 - 3:18:43 AM
Long-term archiving on: : Saturday, June 29, 2019 - 1:51:43 PM

File

pawlowskiUcarYzelman-jocs.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Filip Pawlowski, Bora Uçar, Albert-Jan Yzelman. A multi-dimensional Morton-ordered block storage for mode-oblivious tensor computations. Journal of computational science, Elsevier, In press, pp.1-35. ⟨10.1016/j.jocs.2019.02.007⟩. ⟨hal-02082524⟩

Share

Metrics

Record views

138

Files downloads

426