Efficient Parallel Processing Methods for Transposing Matrices on Symmetric Multiprocessors

摘要

In this paper, we introduce two efficient algorithms (the transpose algorithm and the butterfly algorithm) of transposing matrices on symmetric multiprocessors (SMP). By employing hierarchical transposing, our algorithms allow overlapping between computation and communication and create more opportunities for parallelism. Simulation results show that our algorithms have less overhead than transposing matrices using the existing built-in collective communication function MPI Alltoall() (version MPICH 1.2.4). Simulation results also show that the relation between the overhead associated with our algorithms and the data size is approximately linear. As a comparison between the two proposed algorithms, the transpose algorithm is better than the butterfly algorithm when the data size is greater than a threshold, which is derived theoretically for the SMP. On the other hand, the butterfly algorithm requires more memory space than the transpose algorithm.