[llvm-dev] Static Analysis for GPU Program Performance in LLVM

Tue Nov 16 17:53:59 PST 2021

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>