Automatic Generation of Warp-Level Primitives and Atomic Instructions for Fast and Portable Parallel Reduction on GPUs

Simon Garcia De Gonzalo, Sitao Huang, Juan Gomez-Luna, Simon Hammond, Onur Mutlu, Wen-Mei W Hwu

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

Abstract

Since the advent of GPU computing, GPU hardware has evolved at a fast pace. Since application performance heavily depends on the latest hardware improvements, performance portability is extremely challenging for GPU application library developers. Portability becomes even more difficult when new low-level instructions are added to the ISA (e.g., warp shuffle instructions) or the microarchitectural support for existing instructions is improved (e.g., atomic instructions). Library developers, besides re-tuning the code for new hardware features, deal with the performance portability issue by hand-writing multiple algorithm versions that leverage different instruction sets and microarchitectures. High-level programming frameworks and Domain Specific Languages (DSLs) do not typically support low-level instructions (e.g., warp shuffle and atomic instructions), so it is painful or even impossible for these programming systems to take advantage of the latest architectural improvements. In this work, we design a new set of high-level APIs and qualifiers, as well as specialized Abstract Syntax Tree (AST) transformations for high-level programming languages and DSLs. Our transformations enable warp shuffle instructions and atomic instructions (on global and shared memories) to be easily generated. We show a practical implementation of these transformations by building on Tangram, a high-level kernel synthesis framework. Using our new language and compiler extensions, we implement parallel reduction, a fundamental building block used in a wide range of algorithms. Parallel reduction is representative of the performance portability challenge, as its performance heavily depends on the latest hardware improvements. We compare our synthesized parallel reduction to another high-level programming framework and a hand-written high-performance library across three generations of GPU architectures, and show up to 7. 8 \times speedup (2 \times on average) over hand-written code.

Original languageEnglish (US)
Title of host publicationCGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization
EditorsTipp Moseley, Alexandra Jimborean, Mahmut Taylan Kandemir
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages73-84
Number of pages12
ISBN (Electronic)9781728114361
DOIs
StatePublished - Mar 5 2019
Externally publishedYes
Event17th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2019 - Washington, United States
Duration: Feb 16 2019Feb 20 2019

Publication series

NameCGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization

Conference

Conference17th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2019
CountryUnited States
CityWashington
Period2/16/192/20/19

Fingerprint

Portability
Shuffle
Hardware
Domain-specific Languages
Programming
Tangram
Computer systems programming
Handwriting
Application programming interfaces (API)
Computer programming languages
Shared Memory
Tuning
Leverage
Compiler
Building Blocks
Programming Languages
Data storage equipment
Speedup
High Performance
Graphics processing unit

ASJC Scopus subject areas

  • Software
  • Control and Optimization

Cite this

Gonzalo, S. G. D., Huang, S., Gomez-Luna, J., Hammond, S., Mutlu, O., & Hwu, W-M. W. (2019). Automatic Generation of Warp-Level Primitives and Atomic Instructions for Fast and Portable Parallel Reduction on GPUs. In T. Moseley, A. Jimborean, & M. T. Kandemir (Eds.), CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization (pp. 73-84). [8661187] (CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CGO.2019.8661187

Automatic Generation of Warp-Level Primitives and Atomic Instructions for Fast and Portable Parallel Reduction on GPUs. / Gonzalo, Simon Garcia De; Huang, Sitao; Gomez-Luna, Juan; Hammond, Simon; Mutlu, Onur; Hwu, Wen-Mei W.

CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization. ed. / Tipp Moseley; Alexandra Jimborean; Mahmut Taylan Kandemir. Institute of Electrical and Electronics Engineers Inc., 2019. p. 73-84 8661187 (CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization).

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

Gonzalo, SGD, Huang, S, Gomez-Luna, J, Hammond, S, Mutlu, O & Hwu, W-MW 2019, Automatic Generation of Warp-Level Primitives and Atomic Instructions for Fast and Portable Parallel Reduction on GPUs. in T Moseley, A Jimborean & MT Kandemir (eds), CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization., 8661187, CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization, Institute of Electrical and Electronics Engineers Inc., pp. 73-84, 17th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2019, Washington, United States, 2/16/19. https://doi.org/10.1109/CGO.2019.8661187
Gonzalo SGD, Huang S, Gomez-Luna J, Hammond S, Mutlu O, Hwu W-MW. Automatic Generation of Warp-Level Primitives and Atomic Instructions for Fast and Portable Parallel Reduction on GPUs. In Moseley T, Jimborean A, Kandemir MT, editors, CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization. Institute of Electrical and Electronics Engineers Inc. 2019. p. 73-84. 8661187. (CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization). https://doi.org/10.1109/CGO.2019.8661187
Gonzalo, Simon Garcia De ; Huang, Sitao ; Gomez-Luna, Juan ; Hammond, Simon ; Mutlu, Onur ; Hwu, Wen-Mei W. / Automatic Generation of Warp-Level Primitives and Atomic Instructions for Fast and Portable Parallel Reduction on GPUs. CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization. editor / Tipp Moseley ; Alexandra Jimborean ; Mahmut Taylan Kandemir. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 73-84 (CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization).
@inproceedings{1bcbe01bfe884eb8b87a1f7a79a8d377,
title = "Automatic Generation of Warp-Level Primitives and Atomic Instructions for Fast and Portable Parallel Reduction on GPUs",
abstract = "Since the advent of GPU computing, GPU hardware has evolved at a fast pace. Since application performance heavily depends on the latest hardware improvements, performance portability is extremely challenging for GPU application library developers. Portability becomes even more difficult when new low-level instructions are added to the ISA (e.g., warp shuffle instructions) or the microarchitectural support for existing instructions is improved (e.g., atomic instructions). Library developers, besides re-tuning the code for new hardware features, deal with the performance portability issue by hand-writing multiple algorithm versions that leverage different instruction sets and microarchitectures. High-level programming frameworks and Domain Specific Languages (DSLs) do not typically support low-level instructions (e.g., warp shuffle and atomic instructions), so it is painful or even impossible for these programming systems to take advantage of the latest architectural improvements. In this work, we design a new set of high-level APIs and qualifiers, as well as specialized Abstract Syntax Tree (AST) transformations for high-level programming languages and DSLs. Our transformations enable warp shuffle instructions and atomic instructions (on global and shared memories) to be easily generated. We show a practical implementation of these transformations by building on Tangram, a high-level kernel synthesis framework. Using our new language and compiler extensions, we implement parallel reduction, a fundamental building block used in a wide range of algorithms. Parallel reduction is representative of the performance portability challenge, as its performance heavily depends on the latest hardware improvements. We compare our synthesized parallel reduction to another high-level programming framework and a hand-written high-performance library across three generations of GPU architectures, and show up to 7. 8 \times speedup (2 \times on average) over hand-written code.",
author = "Gonzalo, {Simon Garcia De} and Sitao Huang and Juan Gomez-Luna and Simon Hammond and Onur Mutlu and Hwu, {Wen-Mei W}",
year = "2019",
month = "3",
day = "5",
doi = "10.1109/CGO.2019.8661187",
language = "English (US)",
series = "CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "73--84",
editor = "Tipp Moseley and Alexandra Jimborean and Kandemir, {Mahmut Taylan}",
booktitle = "CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization",
address = "United States",

}

TY - GEN

T1 - Automatic Generation of Warp-Level Primitives and Atomic Instructions for Fast and Portable Parallel Reduction on GPUs

AU - Gonzalo, Simon Garcia De

AU - Huang, Sitao

AU - Gomez-Luna, Juan

AU - Hammond, Simon

AU - Mutlu, Onur

AU - Hwu, Wen-Mei W

PY - 2019/3/5

Y1 - 2019/3/5

N2 - Since the advent of GPU computing, GPU hardware has evolved at a fast pace. Since application performance heavily depends on the latest hardware improvements, performance portability is extremely challenging for GPU application library developers. Portability becomes even more difficult when new low-level instructions are added to the ISA (e.g., warp shuffle instructions) or the microarchitectural support for existing instructions is improved (e.g., atomic instructions). Library developers, besides re-tuning the code for new hardware features, deal with the performance portability issue by hand-writing multiple algorithm versions that leverage different instruction sets and microarchitectures. High-level programming frameworks and Domain Specific Languages (DSLs) do not typically support low-level instructions (e.g., warp shuffle and atomic instructions), so it is painful or even impossible for these programming systems to take advantage of the latest architectural improvements. In this work, we design a new set of high-level APIs and qualifiers, as well as specialized Abstract Syntax Tree (AST) transformations for high-level programming languages and DSLs. Our transformations enable warp shuffle instructions and atomic instructions (on global and shared memories) to be easily generated. We show a practical implementation of these transformations by building on Tangram, a high-level kernel synthesis framework. Using our new language and compiler extensions, we implement parallel reduction, a fundamental building block used in a wide range of algorithms. Parallel reduction is representative of the performance portability challenge, as its performance heavily depends on the latest hardware improvements. We compare our synthesized parallel reduction to another high-level programming framework and a hand-written high-performance library across three generations of GPU architectures, and show up to 7. 8 \times speedup (2 \times on average) over hand-written code.

AB - Since the advent of GPU computing, GPU hardware has evolved at a fast pace. Since application performance heavily depends on the latest hardware improvements, performance portability is extremely challenging for GPU application library developers. Portability becomes even more difficult when new low-level instructions are added to the ISA (e.g., warp shuffle instructions) or the microarchitectural support for existing instructions is improved (e.g., atomic instructions). Library developers, besides re-tuning the code for new hardware features, deal with the performance portability issue by hand-writing multiple algorithm versions that leverage different instruction sets and microarchitectures. High-level programming frameworks and Domain Specific Languages (DSLs) do not typically support low-level instructions (e.g., warp shuffle and atomic instructions), so it is painful or even impossible for these programming systems to take advantage of the latest architectural improvements. In this work, we design a new set of high-level APIs and qualifiers, as well as specialized Abstract Syntax Tree (AST) transformations for high-level programming languages and DSLs. Our transformations enable warp shuffle instructions and atomic instructions (on global and shared memories) to be easily generated. We show a practical implementation of these transformations by building on Tangram, a high-level kernel synthesis framework. Using our new language and compiler extensions, we implement parallel reduction, a fundamental building block used in a wide range of algorithms. Parallel reduction is representative of the performance portability challenge, as its performance heavily depends on the latest hardware improvements. We compare our synthesized parallel reduction to another high-level programming framework and a hand-written high-performance library across three generations of GPU architectures, and show up to 7. 8 \times speedup (2 \times on average) over hand-written code.

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

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

U2 - 10.1109/CGO.2019.8661187

DO - 10.1109/CGO.2019.8661187

M3 - Conference contribution

T3 - CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization

SP - 73

EP - 84

BT - CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization

A2 - Moseley, Tipp

A2 - Jimborean, Alexandra

A2 - Kandemir, Mahmut Taylan

PB - Institute of Electrical and Electronics Engineers Inc.

ER -