llvm dev - Nov 2021 - Static Analysis for GPU Program Performance in LLVM

Hi there,

I would like to propose addition of two static analyses to LLVM framework
that can help detect performance issues in GPU programs: The first analysis
directly detects the issue with memory congestion across GPU threads; the
second analysis checks independence for block-size for synchronization-free
programs that allows performance tuning of block-size without impacting
correctness. Both these static analyses were developed as part of my PhD
thesis and are available on github. Please see the link here to see more
details:

https://github.com/upenn-acg/gpudrano-static-analysis_v1.0

We would like to upstream these analyses to LLVM. There are many advantages
of the work. These are ground-breaking analyses that allow light-weight
compile-time detection of performance and correctness issues in GPU
programs that concern *inter-thread *behavior. Being light-weight allows
them to operate efficiently at compile-time. Inter-thread behavior of the
program concerns the behaviors of the program that are observed due to the
interaction between threads and are not local to individual threads. Such
analysis is difficult to perform in a generic multi-threaded program,
however due to the regularity of GPU parallelism, the analyses are feasible
at compile-time.

These analyses can be the basis for optimizations that can improve the
performance of GPU programs multifold. Given the complexity of GPU
programming and the lack of support for tools in this space, the analyses
provide the first steps towards robust tools for analysis and optimization
of GPU programs. There are two publications that have been published for
this work, which can be found in the references below. I would be happy to
answer any questions or concerns regarding this work.

Regards,
Nimit

References:
1. FMSD 2021: Static analysis for detecting uncoalesced accesses in GPU
programs, Rajeev Alur, Joseph Devietti, Omar Navarro Leija, and Nimit
Singhania.
2. SAS 2018: Block-Size Independence of GPU Programs, Rajeev Alur, Joseph
Devietti, and Nimit Singhania.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211025/7d223bcb/attachment-0001.html>

Hi Nimit,

This is interesting and promising work! I haven't seen anyone else respond
yet, so I'll just give a few "pre-review" observations/suggestions
that I noticed. As a first step, and if you haven't already, take a look at
https://llvm.org/docs/DeveloperPolicy.html and
https://llvm.org/docs/GettingStarted.html#sending-patches for concrete
information and steps for submitting your patch.

  1.  Reviewers will ask you to format your code according to LLVM Coding
Standards. I see a few issues, such as some non-standard variable naming and
code formatting. Since this is new code, you can perform blanket
"clang-format" and "clang-tidy" runs over all the code to
resolve most issues automatically before submitting your patch (or at least
before committing).
  2.  This work is billed in a way that sounds like a generic "GPU"
analysis. However, as written today, it is CUDA/NVIDIA specific. For example,
UncoalescedAnalysis::ExecuteInstruction references NVVM intrinsics (e.g.,
llvm.nvvm.read.ptx.sreg.tid.x). Also, UncoalescedAnalysis::getConstantExprValue
hardcodes NVIDIA-specific address spaces 3 and 4 for Shared and Constant,
respectively (hardcoding those values is itself another issue). That said, much
of the code is generic. Probably what makes sense here is to isolate the above
instances (and any other target dependences) into target-specific hooks.
TargetTransformInfo might be the right place for these (see similar APIs like
TTI::isSourceOfDivergence). In this way, the bulk of the code remains
target-independent, and the various GPUs only need to implement their (hopefully
very small) specific hooks/overrides to utilize the analyses. Of course, there
is still the external issues-- such as what specific vendor tools/libraries are
needed, and that would be documented separately by each GPU target.
  3.  There don't seem to be any simple unit/regression ("lit")
tests. I do see that there are the benchmark directories NVIDIA_CUDA-8.0_Samples
and rodinia_3.1, but these aren't suitable unit tests. In fact, those might
be good to add to the LLVM "test suite" (see
https://llvm.org/docs/TestSuiteGuide.html). Instead, patches are usually
required to have some way to unit-test them. Often these are small IR tests. In
some cases, C++ test cases are used when it isn't feasible to test via IR
(testing, say, operations on a new ADT). See, e.g., llvm/test/Analysis for
examples of testing analysis passes.
  4.  I wonder if it makes sense to promote the GPU Drano static analysis to a
full-fledged LLVM tool (e.g., llvm/tools/llvm-gpudrano) instead of manually
running a series of clang+opt steps? That might make it a bit more convenient to
use. Even though the tool is today CUDA specific, it could have a target flag
where only a NVIDIA/CUDA value is recognized and implemented. Just a thought and
totally optional.
  5.  Adding some documentation would be useful. At the minimum, you might add a
paragraph to llvm/docs/Passes.rst. But a more substantial write-up (like the one
for llvm/docs/Vectorizers.rst) would be even better.
  6.
  7.

________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Nimit
Singhania via llvm-dev <llvm-dev at lists.llvm.org>
Sent: Monday, October 25, 2021 2:50 PM
To: llvm-dev at lists.llvm.org <llvm-dev at lists.llvm.org>
Subject: [llvm-dev] Static Analysis for GPU Program Performance in LLVM

External email: Use caution opening links or attachments

Hi there,

I would like to propose addition of two static analyses to LLVM framework that
can help detect performance issues in GPU programs: The first analysis directly
detects the issue with memory congestion across GPU threads; the second analysis
checks independence for block-size for synchronization-free programs that allows
performance tuning of block-size without impacting correctness. Both these
static analyses were developed as part of my PhD thesis and are available on
github. Please see the link here to see more details:

https://github.com/upenn-acg/gpudrano-static-analysis_v1.0

We would like to upstream these analyses to LLVM. There are many advantages of
the work. These are ground-breaking analyses that allow light-weight
compile-time detection of performance and correctness issues in GPU programs
that concern inter-thread behavior. Being light-weight allows them to operate
efficiently at compile-time. Inter-thread behavior of the program concerns the
behaviors of the program that are observed due to the interaction between
threads and are not local to individual threads. Such analysis is difficult to
perform in a generic multi-threaded program, however due to the regularity of
GPU parallelism, the analyses are feasible at compile-time.

These analyses can be the basis for optimizations that can improve the
performance of GPU programs multifold. Given the complexity of GPU programming
and the lack of support for tools in this space, the analyses provide the first
steps towards robust tools for analysis and optimization of GPU programs. There
are two publications that have been published for this work, which can be found
in the references below. I would be happy to answer any questions or concerns
regarding this work.

Regards,
Nimit

References:
1. FMSD 2021: Static analysis for detecting uncoalesced accesses in GPU
programs, Rajeev Alur, Joseph Devietti, Omar Navarro Leija, and Nimit Singhania.
2. SAS 2018: Block-Size Independence of GPU Programs, Rajeev Alur, Joseph
Devietti, and Nimit Singhania.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20211117/b0b66ed3/attachment.html>