Adaptive Matrix Transpose Algorithms for Distributed Multicore Processors

Abstract An adaptive parallel matrix transpose algorithm optimized for distrib-uted multicore architectures running in a hybrid OpenMP/MPI configuration is pre-sented. Significant boosts in speed are observed relative to the distributed transpose used in the state-of-the-art adaptive FFTW library. In some cases, a hybrid config-uration allows one to reduce communication costs by reducing the number of MPI nodes, and thereby increasing message sizes. This also allows for a more slab-like than pencil-like domain decomposition for multidimensional Fast Fourier Trans-forms, reducing the cost of, or even eliminating the need for, a second distributed transpose. Nonblocking all-to-all transfers enable user computation and communi-cation to be overlapped. 1 The matrix transpose The matrix transpose is an essential primitive of high-performance parallel comput-ing. In contrast to the situation on serial and shared-memory parallel architectures, where the use of memory strides in linear algebra and Fast Fourier Transform (FFT) libraries allows matrices to be accessed in transposed order, many distributed com-puting algorithms rely on a global matrix transpose. This requires so-called all-to-all communication, where every process must communicate with all of the other processes to swap each matrix column with its corresponding row. For example, multi-dimensional FFT algorithms use a matrix transpose to localize the compu-tation within individual processes. For efficiency, all data corresponding to a give