# Efficient out-of-place arbitrary rank GPU transpose

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:

https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/transpose_functor_gpu.cu.cc#L27

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?

• 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/…) – Kirill Nov 16 '16 at 16:41