Modeling Utilization to Identify Shared-memory Atomic Bottlenecks
Rongcui Dong, Sreepathi Pai · 2025
Read Modeling Utilization to Identify Shared-memory Atomic Bottlenecks by Rongcui Dong, Sreepathi Pai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-17893.txt.
Introduction
Rongcui Dong and Sreepathi Pai wrote this 2025 computing paper on finding a hidden bottleneck in GPU programs. Programs whose behavior depends on data are hard to profile: simple models miss the mark, and raw counters take long to read. The authors target one suspect, shared-memory atomic operations, where many threads update the same spot.
Their model treats the atomic unit as a single-server queue. Its inputs are the hardware counters a run already produces. The model captures load effects such as pipelining, parallel work, and varied access patterns. It covers fetch-and-op and compare-and-swap instructions on two NVIDIA chip families. Built into a tool, the model predicts how busy the atomic unit is, so a user can tell at once whether atomics are the bottleneck. No earlier tool, the authors note, offered that check.
Catalog record
| CREATOR | Rongcui Dong, Sreepathi Pai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-17893
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Modeling Utilization to Identify Shared-memory Atomic Bottlenecks Rongcui Dong, Sreepathi Pai Abstract . Performance analysis is critical for GPU programs with data-dependent behavior, but models like Roofline are not very useful for them and interpreting raw performance counters is tedious. In this work, we present an analytical model for shared memory atomics ( fetch-and-op and compare-and-swap instructions on NVIDIA Volta and Ampere GPU) that allows users to immediately determine if shared memory atomic operations are a bottleneck for a program’s execution. Our model is based on modeling the architecture as a single-server queuing model whose inputs are performance counters. It captures load-dependent behavior such as pipelining, parallelism, and different access patterns. We embody this model in a tool that uses CUDA hardware counters as parameters to predict the utilization of the shared-memory atomic unit. To the best of our knowledge, no existing profiling tool or model provides this capability for shared-memory atomic operations. We used the model to compare two histogram kernels that use shared-memory atomics. Although nearly identical, their performance can be different by up to 30%. Our tool correctly identifies a bottleneck shift from shared-memory atomic unit as the cause of this discrepancy. Conference: GPGPU’2025; March 1; Las Vegas, NV 1. Introduction The GPU is known for its ability to execute massively data-parallel programs efficiently ( Owens et al., 2008 ; Navarro et al., 2014 ) . This makes it indispensable for problems such as machine learning ( Awan et al., 2017 ; Li et al., 2017 ) , physical simulation ( Hermann et al., 2010 ; Liang et al., 2018 ; Jespersen, 2010 ) , bioinformatics ( Vouzis and Sahinidis, 2011 ) , and many others. To achieve high performance, programs must effectively use the GPU’s memory hierarchy. In particular, making good use of the on-chip scratchpad memory known as shared memory on NVIDIA GPUs is key to avoid the high latency cost imposed by other parts of the GPU memory hierarchy. A common use of shared memory is to optimize algorithms in tight loops ( Egielski et al., 2014 ; GPU, 2015 ; Harris, 2007 ; CUD, 2014 ; Nyland and Jones, 2013 ) , but using shared memory effectively for programs with irregular parallelism or those that have data-dependent access patterns is hard. Of particular interest to us in this work are programs with irregular and data-dependent parallelism that use shared memory atomics to reduce the cost of global memory atomics, such as histogram ( Konstantinidis and Cotronis, 2015 ; Egielski et al., 2014 ; Gómez-Luna et al., 2013 ) , sorting ( NVIDIA, 2024 ) , sparse matrix multiplication ( Wang et al., 2010 ) , non-deterministic finite automata ( Liu et al., 2020 ) , etc. In these programs, a large problem is divided so that each sub-problem fits inside shared memory to compute partial results, which are then combined in global memory. Using shared-memory atomics leads to lower contention and higher performance. Since shared-memory atomic operations can also become the bottleneck of a GPU program, it is desirable to understand how much time is spent on these operations. Unfortunately, no existing GPU profiler or performance model currently measures this time. The CUDA toolkit provides call graph timing, performance counters, memory analysis, and Roofline charts ( Corporation, 2022d ) . Performance counters for shared-memory atomic operations include count, peak throughput, and peak parallelism. However, these values do not easily translate to the actual cost, because the time required for shared-memory atomic operations is not publicly documented and is also load dependent. For instance, as we will show in experiments, the average time required for atomic operations can vary more than ten times depending on their launch and access patterns. The Roofline charts only analyze bottlenecks for arithmetic and memory operations and do not analyze atomic operations ( Corporation, 2022d ; Corporation, 2022c ) . Therefore, no current tools or models reveal the utilization of shared-memory atomic units for programs that are data-dependent with irregular access patterns. In this work, we contribute: (1) an operational single-server queue-based performance model; (2) a tool that uses the performance model to estimate utilization of shared-memory atomic units in real programs using quantities derived from hardware performance counters. (3) a case study of two histogram variants on two different GPUs that reveals bottlenecks which cause up to 30% performance difference. This paper is organized as follows. In Section 2 , we describe the atomic instructions of the NVIDIA Titan V GPU and the Ampere A6000 GPU that we model in this work. In Section 3 , we give a brief introduction to the operational method of queuing analysis, build a single-server queuing model for these instructions, and find hardware performance counters for obtaining basic quantities used as parameters to the model. In Section 4 , we perform a case study on two histogram kernels using our performance model. In Section 5 , we describe some related works and compare them with our work. We conclude in Section 6 . 2. Shared Memory Atomic Instructions Atomic operations allow data to be read, modified, and written in a single step. These operations are critical in multithreaded programming models, because they prevent intermediate states from being observed by other threads. An example of fetch-and-op (FAO) would be fetch-and-add, which performs the memory read, adds a constant, and store the sum in one operation. Other operations are subtraction, exchange, minimum, maximum, increment, decrement, bitwise AND, bitwise OR, and bitwise XOR. The compare-and-swap (CAS) operation conditionally replaces a value if it matches a specified value, returning the old value. FAO is a cheaper arithmetic operation and is used whenever possible. CAS instructions may be generated when FAO is insufficient, such as floating point atomic operations. In the Ampere architecture, NVIDIA introduced a new atomic instruction, ATOMS.POPC.INC , to conditionally replace ATOMS.ADD instructions. ATOMS.POPC.INC remain undocumented, but experiments show that it increments a shared memory variable by the number of active threads in a warp (i.e. population count increment , or POPC.INC ). This instruction is generated when an atomic increment does not use its return value, and it is cheaper to execute than FAO instructions. As we show later in Section 4 , histogram kernels generate this instruction. 3. Single-Server Queuing Model Queuing models are used to analyze the performance of computer systems ( Denning and Buzen, 1978 ; Thomas, 1976 ) by modeling it as a network of servers servicing jobs . A job is a unit of work. Each server is an abstract entity with an input queue and services jobs sequentially with some service time S . If there are multiple servers in the network, a job requests service from only one server at a time. We analyze our queuing network using the operational approach ( Denning and Buzen, 1978 ) because we found that most (but not all) of the quantities required can be measured directly using GPU performance counters. Importantly, our model does not have to exactly represent the internal architecture of the shared memory atomic unit. Even though we know through microbenchmarking that it is pipelined and can process multiple instructions, we found it sufficient to model the performance of the shared-memory atomic unit using a load-dependent,