General in-situ matrix transposition algorithm for massively parallel environments

Matrix transposition is an essential mathematical operation broadly used in many scientific and engineering domains. In this paper, we present a new approach to the matrix transposition problem in massively parallel computing environments. We propose to utilize recursive functions to translate worker (thread) coordinates on a grid so that they can be used to locate and transpose matrix elements. In principal, it is possible to define a grid of threads in such a way that, based on their uniquely assigned index, we can decompose it using above mentioned functions so that each individual thread can exchange two relevant matrix elements across the main diagonal. Currently, our in-place method can be applied to arbitrary square matrices. In addition, we present a basic implementation of our algorithm for CUDA. Finally, we demonstrate initial performance tests performed on GPU and compare our results with naive versions of the in-place and out-of-place algorithms for CUDA.