3 ms·

Maybe OpenMP and CUDA do more optimizations than I thought they did. Do they perform AoS->SoA reorganizations, conversions from pointer members to inline member

by zurn 9y ago

Maybe OpenMP and CUDA do more optimizations than I thought they did. Do they perform AoS->SoA reorganizations, conversions from pointer members to inline members, or range analysis to choose smaller data types? Admittedly foremost I was thinking about entirely different kinds of data and layout optimizations: Herarchical data, pointer heavy structures, and potential compressed representations. Things like converting node pointers into 16-bit indices into a node array.

jlebar 9y ago
> Maybe OpenMP and CUDA do more optimizations than I thought they did. Do they perform [...] range analysis to choose smaller data types? CUDA compiler developer here. We definitely perform range analysis on values stored in registers. This is an important optimization. Via scalar replacement of aggregates, we can sometimes also replace a struct with a set of scalars. Once we do that, we can again perform range analysis on those scalars. We can't change structs that don't get SROA'ed because of limitations of the language. For one thing, essentially any memory we write to the GPU's global memory can be read from the CPU side, and it's basically impossible to tell what is and isn't read, so we have to keep the memory layout the same.
- gcp 9y ago
  SROA'ed What does this mean? (Glad you're enjoying your time at Google, Justin!)
  - sanxiyn 9y ago
    SROA stands for Scalar Replacement Of Aggregates.
- DannyBee 9y ago
  "We can't change structs that don't get SROA'ed because of limitations of the language. For one thing, essentially any memory we write to the GPU's global memory can be read from the CPU side, and it's basically impossible to tell what is and isn't read, so we have to keep the memory layout the same. " Which is precisely a language semantic problem, since there are plenty of languages where you can change SOA to AOS. In fact, it's wildly common among high perf fortran compilers
drivebycomment 9y ago
Sun's optimizing compiler did AoS->SoA reorganization, data member inlining/ordering, and range analysis in a whole program optimization mode, even for C++(!) without any extra #pragma, when it can correctly prove no aliasing and no pointer escaping. That was nearly 15 years ago. It could also transform an array of pointers to malloc'ed arrays into a single 2d array.

by zurn 9y ago

jlebar 9y ago

> Maybe OpenMP and CUDA do more optimizations than I thought they did. Do they perform [...] range analysis to choose smaller data types? CUDA compiler developer here. We definitely perform range analysis on values stored in registers. This is an important optimization. Via scalar replacement of aggregates, we can sometimes also replace a struct with a set of scalars. Once we do that, we can again perform range analysis on those scalars. We can't change structs that don't get SROA'ed because of limitations of the language. For one thing, essentially any memory we write to the GPU's global memory can be read from the CPU side, and it's basically impossible to tell what is and isn't read, so we have to keep the memory layout the same.

gcp 9y ago
SROA'ed What does this mean? (Glad you're enjoying your time at Google, Justin!)
- sanxiyn 9y ago
  SROA stands for Scalar Replacement Of Aggregates.
DannyBee 9y ago
"We can't change structs that don't get SROA'ed because of limitations of the language. For one thing, essentially any memory we write to the GPU's global memory can be read from the CPU side, and it's basically impossible to tell what is and isn't read, so we have to keep the memory layout the same. " Which is precisely a language semantic problem, since there are plenty of languages where you can change SOA to AOS. In fact, it's wildly common among high perf fortran compilers

drivebycomment 9y ago

Sun's optimizing compiler did AoS->SoA reorganization, data member inlining/ordering, and range analysis in a whole program optimization mode, even for C++(!) without any extra #pragma, when it can correctly prove no aliasing and no pointer escaping. That was nearly 15 years ago. It could also transform an array of pointers to malloc'ed arrays into a single 2d array.