Summary: Is there an efficient out-of-place GPU tensor transpose operation that scales as $O(n)$ for tensors with $n$ total elements, regardless of the rank $d$? The naive algorithm costs $O(dn)$, since it requires $O(d)$ worth of index manipulation per entry.

Here is the current implementation of high rank tensor transpose in TensorFlow:


It does a flat 1-D loop, deconstructs the index using $O(d)$ divisions by strides, and reconstructs the transposed index. Is there any index trickery / precomputation that would avoid the $O(d)$ cost per entry?

  • 1
    $\begingroup$ I wonder if it's dominated by uncoalesced memory accesses or by the $O(d)$ index computation? I would've guessed uncoalesced loads are more expensive by far. It's worth checking that first I'd say. (e.g., devblogs.nvidia.com/parallelforall/…) $\endgroup$ – Kirill Nov 16 '16 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.