M.: A decomposition for in-place matrix transposition

We describe a decomposition for in-place matrix transposi-tion, with applications to Array of Structures memory ac-cesses on SIMD processors. Traditional approaches to in-place matrix transposition involve cycle following, which is difficult to parallelize, and on matrices of dimension m by n require O(mn logmn) work when limited to less than O(mn) auxiliary space. Our decomposition allows the rows and columns to be operated on independently during in-place transposition, reducing work complexity to O(mn), given O(max(m,n)) auxiliary space. This decomposition leads to an efficient and naturally parallel algorithm: we have measured median throughput of 19.5 GB/s on an NVIDIA Tesla K20c processor. An implementation specialized for the skinny matrices that arise when converting Arrays of Struc-tures to Structures of Arrays yields median throughput of 34.3 GB/s, and a maximum throughput of 51 GB/s. Because of the simple structure of this algorithm, it is par-ticularly suited for implementation using SIMD instructions to transpose the small arrays that arise when SIMD proces-sors load from or store to Arrays of Structures. Using this algorithm to cooperatively perform accesses to Arrays of Structures, we measure 180 GB/s throughput on the K20c, which is up to 45 times faster than compiler-generated Ar-ray of Structures accesses. In this paper, we explain the algorithm, prove its correct-ness and complexity, and explain how it can be instantiated efficiently for solving various transpose problems on bot