Matrix Transpose on 2D Torus Array Processor
Ahmed Sherif Zekri, Stanislav G. Sedukhin · 2006
Previously, we represented the index space of the (nxn)-matrix multiply-add problem C=C+AxB as a 3D torus, where A, B, and C are rolled along the corresponding axes of the index space. All optimal 2D data allocations (resulted from projection) to solve the problem on the nxn torus array processor in n multiply-add-roll steps were obtained. In this paper, we formulate the operations needed for aligning both the data before computing and the results after computing as matrix multiply-add problems. These alignment operations are combined with the optimal data allocations that solve the matrix multiply-add problem to propose new algorithms to transpose an nxn matrix on the nxn torus array processor in O(n) multiply-add-roll steps. Using the proposed algorithms, we showed different approaches to solve the transposed matrix multiply-add problem, C=C+ATxBT, on the 2D torus array processor.