An O(n) Time-Complexity Matrix Transpose on Torus Array Processor

Matrix transpose is an essential operation in many applications like signal processing (ex. linear transforms) etc. and an efficient matrix transpose algorithm can speed up many applications. In this paper, we propose a new algorithm for n x n matrix transposition on array processors connected in torus network. The algorithm has O(n) time complexity. The algorithm uses matrix-matrix multiply-add (MMA) operation for transposing the matrix. We show how to align data and give algorithm for generating permutation matrices. The entire n x n matrix transposition is carried out in 5n time-steps. This approach does not require any dedicated connections for matrix transposition. Both input and output matrices are in canonical (natural and not skewed) layout. We also discuss blocked matrix transposition.