Efficient Adaptive Algorithms for Transposing Small and Large Matrices on Symmetric Multiprocessors

Article type: Research Article

Authors: Na'mneh, Rami Al | Pan, W. David | Yoo, Seong-Moo

Affiliations: Department of Electrical and Computer Engineering, University of Alabama in Huntsville, 301 Sparkman Drive, Huntsville, Alabama 35899, USA, e-mail: dwpan@ece.uah.edu

Abstract: Matrix transpose in parallel systems typically involves costly all-to-all communications. In this paper, we provide a comparative characterization of various efficient algorithms for transposing small and large matrices using the popular symmetric multiprocessors (SMP) architecture, which carries a relatively low communication cost due to its large aggregate bandwidth and low-latency inter-process communication. We conduct analysis on the cost of data sending / receiving and the memory requirement of these matrix-transpose algorithms. We then propose an adaptive algorithm that can minimize the overhead of the matrix transpose operations given the parameters such as the data size, number of processors, start-up time, and the effective communication bandwidth.

Keywords: matrix transpose, SMP, MPI, all-to-all communication

Journal: Informatica, vol. 17, no. 4, pp. 535-550, 2006