In-place transposition of rectangular matrices on accelerators

I. Jui Sung, Juan Gómez-Luna, José María González-Linares, Nicolás Guil, Wen-Mei W Hwu

Research output: Contribution to journalArticle

Abstract

Matrix transposition is an important algorithmic building block for many numeric algorithms such as FFT. It has also been used to convert the storage layout of arrays. With more and more algebra libraries offloaded to GPUs, a high performance in-place transposition becomes necessary. Intuitively, in-place transposition should be a good fit for GPU architectures due to limited available on-board memory capacity and high throughput. However, direct application of CPU in-place transposition algorithms lacks the amount of parallelism and locality required by GPUs to achieve good performance. In this paper we present the first known inplace matrix transposition approach for the GPUs. Our implementation is based on a novel 3-stage transposition algorithm where each stage is performed using an elementary tiled-wise transposition. Additionally, when transposition is done as part of the memory transfer between GPU and host, our staged approach allows hiding transposition overhead by overlap with PCIe transfer. We show that the 3-stage algorithm allows larger tiles and achieves 3X speedup over a traditional 4-stage algorithm, with both algorithms based on our high-performance elementary transpositions on the GPU. We also show our proposed low-level optimizations improve the sustained throughput to more than 20 GB/s. Finally, we propose an asynchronous execution scheme that allows CPU threads to delegate in-place matrix transposition to GPU, achieving a throughput of more than 3.4 GB/s (in cluding data transfers costs), and improving current multithreaded implementations of in-place transposition on CPU.

Original languageEnglish (US)
Pages (from-to)207-218
Number of pages12
JournalACM SIGPLAN Notices
Volume49
Issue number8
DOIs
StatePublished - Aug 2014

Keywords

  • GPU
  • In-Place
  • Transposition

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'In-place transposition of rectangular matrices on accelerators'. Together they form a unique fingerprint.

  • Cite this

    Sung, I. J., Gómez-Luna, J., González-Linares, J. M., Guil, N., & Hwu, W-M. W. (2014). In-place transposition of rectangular matrices on accelerators. ACM SIGPLAN Notices, 49(8), 207-218. https://doi.org/10.1145/2555243.2555266