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: Chapter in Book/Report/Conference proceedingConference contribution

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 (including data transfers costs), and improving current multithreaded implementations of in-place transposition on CPU.

Original languageEnglish (US)
Title of host publicationPPoPP 2014 - Proceedings of the 2014 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
Pages207-218
Number of pages12
DOIs
StatePublished - Mar 10 2014
Event2014 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2014 - Orlando, FL, United States
Duration: Feb 15 2014Feb 19 2014

Publication series

NameProceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP

Other

Other2014 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2014
CountryUnited States
CityOrlando, FL
Period2/15/142/19/14

Fingerprint

Particle accelerators
Program processors
Throughput
Data storage equipment
Data transfer
Tile
Graphics processing unit
Fast Fourier transforms
Algebra
Costs

Keywords

  • GPU
  • In-place
  • Transposition

ASJC Scopus subject areas

  • Software

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. In PPoPP 2014 - Proceedings of the 2014 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp. 207-218). (Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP). https://doi.org/10.1145/2555243.2555266

In-place transposition of rectangular matrices on accelerators. / Sung, I. Jui; Gómez-Luna, Juan; González-Linares, José María; Guil, Nicolás; Hwu, Wen-Mei W.

PPoPP 2014 - Proceedings of the 2014 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2014. p. 207-218 (Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Sung, IJ, Gómez-Luna, J, González-Linares, JM, Guil, N & Hwu, W-MW 2014, In-place transposition of rectangular matrices on accelerators. in PPoPP 2014 - Proceedings of the 2014 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, pp. 207-218, 2014 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2014, Orlando, FL, United States, 2/15/14. https://doi.org/10.1145/2555243.2555266
Sung IJ, Gómez-Luna J, González-Linares JM, Guil N, Hwu W-MW. In-place transposition of rectangular matrices on accelerators. In PPoPP 2014 - Proceedings of the 2014 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2014. p. 207-218. (Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP). https://doi.org/10.1145/2555243.2555266
Sung, I. Jui ; Gómez-Luna, Juan ; González-Linares, José María ; Guil, Nicolás ; Hwu, Wen-Mei W. / In-place transposition of rectangular matrices on accelerators. PPoPP 2014 - Proceedings of the 2014 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2014. pp. 207-218 (Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP).
@inproceedings{bc38a1275ba6486e8e8483ddab7bf74d,
title = "In-place transposition of rectangular matrices on accelerators",
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 (including data transfers costs), and improving current multithreaded implementations of in-place transposition on CPU.",
keywords = "GPU, In-place, Transposition",
author = "Sung, {I. Jui} and Juan G{\'o}mez-Luna and Gonz{\'a}lez-Linares, {Jos{\'e} Mar{\'i}a} and Nicol{\'a}s Guil and Hwu, {Wen-Mei W}",
year = "2014",
month = "3",
day = "10",
doi = "10.1145/2555243.2555266",
language = "English (US)",
isbn = "9781450326568",
series = "Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP",
pages = "207--218",
booktitle = "PPoPP 2014 - Proceedings of the 2014 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming",

}

TY - GEN

T1 - In-place transposition of rectangular matrices on accelerators

AU - Sung, I. Jui

AU - Gómez-Luna, Juan

AU - González-Linares, José María

AU - Guil, Nicolás

AU - Hwu, Wen-Mei W

PY - 2014/3/10

Y1 - 2014/3/10

N2 - 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 (including data transfers costs), and improving current multithreaded implementations of in-place transposition on CPU.

AB - 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 (including data transfers costs), and improving current multithreaded implementations of in-place transposition on CPU.

KW - GPU

KW - In-place

KW - Transposition

UR - http://www.scopus.com/inward/record.url?scp=84896819561&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84896819561&partnerID=8YFLogxK

U2 - 10.1145/2555243.2555266

DO - 10.1145/2555243.2555266

M3 - Conference contribution

AN - SCOPUS:84896819561

SN - 9781450326568

T3 - Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP

SP - 207

EP - 218

BT - PPoPP 2014 - Proceedings of the 2014 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

ER -