arXiv:2604.01811v1 [cs.DB] 2 Apr 2026
GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs Lara Kreis
Justus Henneberg
Valentin Henkys
Johannes Gutenberg University Mainz, Germany [email protected]
Johannes Gutenberg University Mainz, Germany [email protected]
Aperio Space Technologies Dieburg, Germany [email protected]
Felix Schuhknecht
Bertil Schmidt
Johannes Gutenberg University Mainz, Germany [email protected]
Johannes Gutenberg University Mainz, Germany [email protected]
ABSTRACT Range minimum queries are frequently used in string processing and database applications including biological sequence analysis, document retrieval, and web search. Hence, various data structures have been proposed for improving their efficiency on both CPUs and GPUs. Recent work has also shown that hardware-accelerated ray tracing on modern NVIDIA RTX graphic cards can be exploited to answer range minimum queries by expressing queries as rays, which are fired into a scene of triangles representing minima of ranges at different granularities. While these approaches are promising, they suffer from at least one of three issues: (a) severe memory overhead, (b) high index construction time, and (c) low query throughput. This renders these methods practically unusable on larger arrays: For example, the state-of-art GPU-based approaches LCA and RTXRMQ exceed the memory capacity of an NVIDIA RTX 4090 GPU for input arrays of size ≥ 229 . To tackle these problems, in this work, we present a new approach called GPU-RMQ which is based on a hierarchical approach. GPU-RMQ first constructs a hierarchy of range minimum summaries on top of the original array in a highly parallel fashion. For query answering, only the relevant portions of the hierarchy are then processed in an optimized massively-parallel scan operation. Additionally, GPU-RMQ is hybrid in design, enabling the use of both ray tracing cores and CUDA cores across different levels of the hierarchy to handle queries. Our experimental evaluation shows that GPURMQ outperforms the state-of-the-art approaches in terms of query throughput especially for larger arrays while offering a significantly lower memory footprint and up to two orders-of-magnitude faster index construction. In particular, it achieves up to ∼ 8× higher throughput than LCA, ∼ 17× higher throughput than RTXRMQ, and up to ∼ 4800× higher throughput compared to an optimized CPU-based approach.
Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/lakreis/GPU-RMQ.
1
INTRODUCTION
Given an array 𝑋 of 𝑛 numbers, range minimum queries (RMQs) address the problem of finding the minimum value within arbitrary contiguous sub-arrays of 𝑋 . They are fundamental operations
and can be used for finding lowest common ancestors in trees, computing longest common extensions of suffixes, or answering maximum-sum segment queries. They are featured in a wide range of application areas including biological sequence analysis, and document retrieval. Consider, for example, the state-of-the-art long read aligner Minimap2 [20], one of its key components, the chaining module, relies on solving RMQs and accounts for up to 35% of the tool’s total computational runtime [18], or state-of-the-art methods for distributed suffix array construction and querying [10]. Motivated by the importance of RMQs across such diverse range of applications, their acceleration has been explored using a variety of architectures such as CPUs [1, 5–9, 19, 27], GPUs [23, 26, 30], and even QPUs [32].
(a) Memory footprint. (b) Construction time. (c) RMQ Throughput.
Figure 1: GPU-RMQ addresses important limitations of the prior GPU-based approaches RTXRMQ and LCA, resulting in (a) lower memory footprint, (b) significantly faster index construction times, and (c) higher throughput per RMQ (results shown for the mixed datasets (see Section 5.1) on an RTX 4090 GPU). For static RMQs (i.e. batched range minima are computed without updating 𝑋 ), a data structure is typically built for the input array in a preprocessing step, which is then used to answer batches of RMQs. Prior GPU-based approaches rely on different types of tree data structures. Soman et al. [30] were the first to implement RMQs on GPUs by means of a Cartesian tree data structure, while Polak et al. [26] proposed LCA – a method to compute Euler tours on trees that can be used for both lowest common ancestor queries and RMQs. Meneses et al. [23] recently proposed RTXRMQ – a new method to leverage RT (ray tracing) cores to solve RMQs. Their key idea is to represent all values of the input array as a geometric scene. By launching multiple rays into this scene, RMQs can be solved
Lara Kreis, Justus Henneberg, Valentin Henkys, Felix Schuhknecht, and Bertil Schmidt
in parallel by taking advantage of hardware-accelerated bounding volume hierarchy (BVH) traversal capabilities on GPUs. Unfortunately, all these approaches suffer from significant memory consumption to store the corresponding data structures in GPU memory. For example, the geometric scene constructed by RTXRMQ requires at least one triangle per array element, which limits its applicability for large input arrays due to insufficient memory resources. In addition, traversing trees on GPUs can be inefficient due to irregular memory access schemes. Figure 1, which shows (a) memory footprint, (b) index construction time, and (c) RMQ throughput of the two state-of-the-art GPU approaches LCA and RTXRMQ on a NVIDIA RTX 4090 for various input array sizes, presents these problems: For an input array consisting of 𝑛 = 229 elements, the memory usage of both LCA and RTXRMQ already exceeds the capacity of the utilized RTX 4090 GPU (24 GB). Further, both LCA and RTXRMQ suffer from a high construction time, which increases heavily with an increase in input size. Also, for larger input arrays that exceed the available cache, the time per RMQ heavily increases. In this work, we address these limitations by proposing an efficient hierarchical data structure and a corresponding processing scheme called GPU-RMQ. On a high-level, GPU-RMQ creates a hierarchy of range minimum summaries on top of the original array. To answer a batch of RMQs, GPU-RMQ then scans and post-filters the relevant parts of the hierarchy via highly optimized hardwareconscious scan operations using cooperative thread groups. As we can see in Figure 1, this leads to a high RMQ throughput while consuming only a moderate amount of auxiliary memory and offering a low construction time for the data structure — enabling GPU-based processing of significantly larger arrays. Additionally, we designed GPU-RMQ as a hybrid approach in which the upper level of the hierarchy can be processed by RT cores while lower levels are handled by CUDA cores, thereby combining different hardware capabilities of modern GPUs.
which hardware-accelerated ray-triangle intersection tests are performed instead of scanning. Again, we determine the effectiveness of such a hybrid approach experimentally. (4) In an extensive experimental evaluation, we show that GPU-RMQ successfully addresses the three main disadvantages of the state-of-the-art methods LCA, RTXRMQ, and HRMQ, namely severe memory overhead, high construction time, and low query throughput for a variety of workloads. As a result, GPU-RMQ is able to handle significantly larger datasets than the baseline methods on the available GPU memory while offering a superior query throughput for a large range of dataset sizes. More specifically, our GPU memory footprint is up to ∼ 4× smaller than LCA and ∼ 10× smaller than RTXRMQ. Our construction time is up to ∼ 100× faster than LCA, ∼ 50× faster than RTXRMQ, and ∼ 2400× faster than HRMQ. Our throughput is up to ∼ 8× faster than LCA, up to ∼ 17× faster than RTXRMQ and up to ∼ 4800× faster than HRMQ. The rest of the paper is organized as follows. After providing background in Section 2 and reviewing related work in Section 3, we present the core design of GPU-RMQ as well as the applied optimizations in Section 4. We then perform an extensive experimental evaluation in Section 5, which we kick off by identifying the optimal configuration for GPU-RMQ for a variety of relevant array sizes. After that, we compare GPU-RMQ against a set of state-of-the-art CPU and GPU baselines in terms of (i) memory footprint, (ii) construction time, and (iii) RMQ throughput. Additionally, we (iv) analyze the performance across different GPU generations. Finally, we conclude in Section 6.
1.1
We consider an array 𝑋 = [𝑥 0, 𝑥 1, . . . , 𝑥𝑛−1 ] of 𝑛 numbers. Range Minimum Queries (RMQs) answer queries consisting of pairs of positions (𝑙, 𝑟 ), 0 ≤ 𝑙 ≤ 𝑟 < 𝑛, by either returning the minimal value within the range from 𝑙 to 𝑟 :
2
BACKGROUND
Let us first discuss all necessary background on RMQs as well as on the hardware on which they will be executed.
2.1 Contributions and Structure of the Paper
In summary, we make the following contributions in this work: (1) We propose GPU-RMQ, a highly efficient GPU-based acceleration structure for answering RMQs. On a high-level, GPU-RMQ builds a hierarchy of range minimum summaries of varying granularity. For query answering, GPURMQ identifies and scans the relevant parts of this hierarchy in a highly parallel fashion to compute the actual minimum. (2) GPU-RMQ integrates a set of carefully designed optimizations that aim at exploiting the characteristics of the highlyparallel hardware. This includes vector loading and coalesced loading to speed up scanning, as well as multiloading and warp-local queuing for assigning queries to hardware threads. As these optimization techniques are configurable, we experimentally determine their impact and configuration of choice. (3) We designed GPU-RMQ from ground up as a hybrid acceleration structure, which supports the efficient usage of not only CUDA cores, but also RT cores. As such, the top-most level of the hierarchy can be expressed as a triangle scene in
Range Minimum Queries (RMQs)
RMQvalue (𝑙, 𝑟 ) = min 𝑥𝑘 𝑙 ≤𝑘 ≤𝑟
or by associated with minimum: 4 returning 20 18 18 an 23index 8 35 43 43 36 68 a63 22 51 81 75 9 0 1 2 3 4 RMQ 5 6 7 𝑟 )8 = arg 9 10 11𝑥 12 13 14 15 16 (𝑙, min 𝑘. index 𝑙 ≤𝑘 ≤𝑟
An example for answering the RMQ for (𝑙, 𝑟 ) = (3, 14) on an array of 17 entries via a simple scan is shown in Figure 2. 4 20 18 18 23 8 35 43 43 36 68 63 22 51 81 75 9 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Figure 2: Scanning the interval (3, 14) in a 17-element input array for an RMQ. The query would return RMQvalue (3, 14) = 8 or RMQindex (3, 14) = 5 (blue highlight). Note that we focus on the answering of a batch of RMQs on a static input array, as it is the typical scenario [7, 9, 21, 23] for RMQs.
GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs
Tensor Core
Registers Registers Registers Registers
Tensor Core Tensor Core Tensor Core
RT Core
L1 cache (128 KB) including up to 100 KB scratch
SM
32 cores 32 cores 32 cores 32 cores
Registers Registers Registers Registers
L1 cache (128 KB) including up to 100 KB scratch
L2 Cache (72 MB)
60
Tensor Core Tensor Core Tensor Core Tensor Core
RT Core
Total time [ms]
32 cores 32 cores 32 cores 32 cores
+ 126 more SMs
SM
same entry
40
20
0
GPU Chip
neighboring entries
1
2
4
8 16 32 Thread group size
64
128
256
(Global) Main Memory (24 GB)
Figure 4: Execution time for a batch of coalesced accesses. Figure 3: Architecture of the NVIDIA RTX 4090. This allows for the preprocessing of 𝑋 to build a data structure upfront that can be used to speed up the RMQs. Thus, approaches can be categorized by a space-time trade-off; i.e., the time complexity for solving a single RMQ and the space complexity for storing the additional data structure. The two extreme cases are: • Full preprocess: A data structure of size O (𝑛 2 ) is built that stores the results for all possible ranges. Each RMQ is then solved in constant time O (1) by a simple lookup. • Full scan: No preprocessing is done and each RMQ is performed by scanning all elements within the corresponding range in time O (𝑛). While the former case requires too much memory, the latter is too slow for practical applications that frequently have to compute the minimum for large ranges. As a consequence, existing approaches focus on finding solutions between these two extremes.
2.2
Modern GPU Architectures
As our main testbed, we use a recent high-end consumer GPUs: NVIDIA RTX 4090 (Ada architecture) with 24GB of main memory. The architecture is visualized in Fig. 3. Processing on the 4090 is distributed across 128 streaming multiprocessors (SMs) containing 4 vector units of 32 cores as well as one RT core each. Typically, one unit of work is assigned to one thread. When running a multithreaded task, the GPU distributes small batches of threads (thread blocks) across SMs, which then schedule even smaller batches of 32 threads (warps) onto the 32-core vector units. Each SM has its own L1 cache (128 KB), which can be partially (up to 100 KB) reconfigured to serve as fast user-programmable scratch memory, allowing for fast data movement and storage within a thread block. Similarly, each SM contains 256 KB worth of 32-bit registers, which can be cross-referenced by threads within a warp using special instructions (warp intrinsics) to exchange data on-the-fly (warp shuffling). Additionally, the GPU has a global L2 cache (100 MB). To ensure scalability, direct communication across SMs is restricted to communication though the GPU global main memory. Note that in Section 5.9, we will also investigate the performance for two other GPU generations, namely (1) an NVIDIA RTX PRO 6000 (Blackwell architecture) with 96GB of global memory and 188 SMs and (2) an NVIDIA RTX 3090 (Ampere architecture) with 24GB of global memory and 82 SMs. A notable feature of GPU memory is access coalescing: When multiple neighboring threads within a warp load neighboring entries at the same time, the GPU performs a single, larger memory access instead. To demonstrate this effect with a micro-benchmark,
we set up an array containing 228 entries of 32 bits each, populated with random data. Then, a total of 225 GPU threads are launched, organized into groups of 2𝑚 adjacent threads, yielding 225−𝑚 nonoverlapping groups. Each group carries out 1024 lookup iterations: At every iteration, the group selects a random array index 𝑝 to read from, which simulates divergent access patterns for widely separated reads. Within a given group, thread 𝑖 reads from index 𝑝 + 𝑖, meaning the group collectively accesses 2𝑚 consecutive but distinct entries. The overall number of load operations stays the same across configurations, only the access pattern varies. Figure 4 shows the total runtime of these lookup iterations across different group sizes. The results reveal that doubling the group size cuts execution time roughly in half, up to a size of 16. Increasing to 32 threads per group still helps, though to a lesser degree, while going beyond 32 provides no additional speedup. For reference, Figure 4 also includes timings for the case where every thread in a group reads only the single entry at position 𝑝. The performance gain is even more pronounced there, as the hardware can cache and reuse that one value.
3
RELATED WORK
Before presenting GPU-RMQ, we discuss the related work on GPU-based data structures in general, and on RMQ approaches in particular.
3.1
GPU-based Data Structures
In recent years, various well-known CPU-based data structures have been transitioned successfully to GPUs. These works share with ours that they also base their design around the specifics of the hardware architecture, in particular the extremely high parallelism offered by the card. We believe that fundamental optimization techniques employed by our work, such as coalesced scanning and warp-local queuing, can also be utilized to enhance other scanheavy general-purpose data structures. For instance, Awad et al. [4] proposed a flexible concurrent B-tree implementation for GPUs, supporting point- and range-lookups as well as an efficient on-card bulk-loading mechanism. Apart from parallelizing across lookups, it further exploits the high parallelism of the GPU by having groups of 16 threads inspect the content of a node concurrently within a single lookup in order to determine the next node respectively the key of interest in the leaves. Unfortunately, it is currently limited to 32-bit keys and values. In a similar style, Ashkiani et al. [3] propose a GPU-based LMS-tree implementation, which focuses on supporting efficient updates. It utilizes the parallelism of the GPU to sort and merge the individual levels of
Lara Kreis, Justus Henneberg, Valentin Henkys, Felix Schuhknecht, and Bertil Schmidt
the LSM-tree. If range-lookups are not required and point-lookups dominate, hash tables are to be preferred. Again, Ashkiani et al. [2] proposed in form of slab-hash an update-focused implementation for that. Further, Jünger et al. [16] proposed Warpcore, a highly efficient lookup-focused open-addressing hash table, which combines warp-wide linear probing with outer-layer double hashing to minimize clustering. In the presence of static datasets, Henneberg et al. [15] question the need for sophisticated data structures altogether, and proposed to use an highly optimized variant of 𝑘-ary search on a sorted array instead. To efficiently scan for qualifying entries during range-lookups, they also effectively utilize coalesced scanning, where neighboring threads handle the scanning neighboring memory regions. Further successful examples of GPU-based general-purpose data structures include Bloom filters [17], skiplists [24], and FIFO-stacks [31]. While the original application of RT cores is the production of real-time photorealistic graphics, recent work has examined their utility for non-rendering problems. A typical approach to adapt a considered task to RT cores consists of two phases: (i) encoding the input data as 3D geometric objects in a scene and building the corresponding BVH to serve as an auxiliary index structure; (ii) casting a large number of rays to perform lookups; i.e., if a ray intersects with an object, the lookup returns an identifier associated with the object as a search result. Examples of applications following this approach include scans [22], database queries [13, 14, 29], nearest neighbor search [25, 29], or spatial joins [11, 12]. To our knowledge we are the first to investigate the collaborative usage of CUDA cores and RT cores for non-rendering problems with a single data structure.
3.2
State-of-the-Art RMQ Approaches
One option to answering RMQs is to reduce it to the problem of finding the LCAs in the Cartesian tree of the input array. This approach offers a space complexity of O (𝑛 · log(𝑛)) at O (log(𝑛)) query time. The Inlabel algorithm [28] improved this by achieving constant-time LCA queries with linear space consumption. HRMQ. Ferrada et al. [5] introduced a CPU-based approach for answering RMQs, building upon the design of Fischer and Heun [6]. Instead of the previously used Depth-First Unary Degree Sequence (DFUDS), they use a balanced parentheses representation. Their algorithm keeps the asymptotically optimal size of 2𝑛 + 𝑜 (𝑛) and maintains constant query time. While being considered one of the fastest CPU-based implementation, its performance is limited by the low degree of parallelism available on multi-core CPUs in comparison to massively-parallel GPUs architectures. LCA. Soman et al. [30] were the first to solve RMQs on GPUs by introducing a succinct representation based on DFUDS designed for efficient usage on the GPU. They report a speedup ranging from 25× to 35× compared to a CPU-based method provided by Fischer and Heun [8]. By employing the Euler tour technique, Polak et al. [26] proposed LCA which adapts the Inlabel algorithm for GPUs. Their evaluation reports speedups ranging from 22× to 55× compared to a single-threaded CPU implementation of the Inlabel algorithm. However, the algorithm has to materialize (a) the order of nodes visited on the Euler tour over its Cartesian tree, (b) the depth of each node visited, as well as (c) the first occurrence of each
R 5
4
3
X
2 1
4
3
2
1
5
7
6
1 2 3 4 5
L
Figure 5: RTXRMQ solving two RMQs on 𝑋 = [2, 6, 7, 4, 1, 3] with RT cores.
node on the tour. This leads to high memory consumption; e.g. e.g. for 𝑛 = 229 it exceeds the memory capacity of an RTX4090 GPU (24GB). RTXRMQ. Recently, RTXRMQ [23] has been proposed to leverage hardware-accelerated BVH of RT cores on modern RTX video cards for solving RMQs. It launches one ray for each RMQ. The ray for RMQ(𝑙, 𝑟 ) is launched from the coordinate (−∞, 𝑙, 𝑟 ) in direction (1, 0, 0). It can only intersect with geometric primitives corresponding to array elements 𝑥𝑖 with 𝑙 ≤ 𝑖 ≤ 𝑟 . To achieve this one geometric primitive for each array element is created in a preprocessing step and positioned along the X-axis according to the element’s value. By launching rays along the X-axis, the first intersection of the ray will identify the triangle corresponding to the range minimum of the array (illustrated in Fig. 5). A major limitation of RTXRMQ is its excessive memory consumption since its data structure consists of a large number of geometric primitives stored in a BVH; e.g. for 𝑛 = 228 it already exceeds the memory capacity of an RTX4090 GPU (24GB). Additionally, the construction of the BVH is an expensive operation. In summary, there already exist a number of RMQ algorithms for both CPU and GPU. Although CPU-based approaches can be asymptotically efficient they often suffer from slow runtimes due to limited parallelism. While GPU-based methods expose massive parallelism they operate on tree data structures, posing challenges for efficient global memory access. In addition, the GPU global memory can be a scarce resource and is typically much smaller than CPU main memory. Thus, memory consumption of the auxiliary data structure becomes a bottleneck. This establishes the need for a new approach that can exploit the fast speed of GPUs for RMQs while consuming significantly less memory than prior approaches.
4
GPU-RMQ
We first introduce the core GPU-RMQ data structure and its algorithms, and then describe the GPU-specific optimizations we have applied to improve its performance.
4
18
8
35
36
63
22
75
9
4 20 18 18 23 8 35 43 43 36 68 63 22 51 81 75 9 GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs
4
18
8
35
36
63
22
75
followed by a few random but cache-aligned chunk accesses on the lower layers. The shape of the structure is determined by two parameters: The chunk size 𝑐, and a threshold 𝑡, which defines the maximum number of chunks allowed on the topmost layer. Theoretically, we have to scan at most 𝑐𝑡 + 2𝑐 log𝑐 (𝑛) ∈ O (log(𝑛)) entries to answer a query. In Section 5.3, we will identify the best choices for both parameters 𝑐 and 𝑡.
9
4 20 4 18 18 23 8 8 35 43 43 363668 63 22 512281 75 9 9 4
18
8
35
36
63
22
75
9
Figure 6: Running RMQvalue (3, 14) on a two-layer minima 4 20 18 18 23 8 35 43 43 36 68 63 22 51 81 75 9 hierarchy. 4 4
8 18
8
36 35
36
22 63
22
75
9
4.2
9
Apart from the parameter choices, it is critical how to implement the scan. GPU-RMQ supports the following two options in maximizing scan throughput on a GPU: (1) Vector loading. Instead of sequentially accessing single entries, a thread can issue an explicit vector load instruction, which loads multiple neighboring entries from memory into the thread’s registers, but costs the same as a single-entry access. Vector loads require the data to be aligned to the vector size, and are only available for up to four entries. Applied to our RMQ problem, scanning performance can be improved by fixing the chunk size to a multiple of the vector size, and access the chunk using a sequence of vector loads. After each vector load, we sequentially compute the minimum across the vector entries (now stored in registers), ignoring the entries that do not fall within the range of positions covered by the RMQ. An individual vector load can be skipped altogether if none of the vector entries qualify for the query. (2) Coalesced loading. Alternatively, we can use a multithreaded strategy: We assign a group of 𝑔 ≤ 32 neighboring threads to the same RMQ, and use them to load neighboring entries within the same chunk. This results in coalesced memory accesses, greatly increasing memory throughput. We re-use this group across all lower-layer chunks, and also for the top-layer scan. A thread skips the load operation if its entry is outside the RMQ bounds. In contrast to the vector load strategy, each thread now independently tracks the minimum of the (qualifying) entries it accesses. After the last traversal step, we compute the minimum across the thread group using warp shuffles (or by atomic aggregation when shuffling is unavailable).
4 20 18 18 23 8 35 43 43 36 68 63 22 51 81 75 9
Figure 7: Running RMQvalue (3, 14) on a three-layer minima hierarchy.
4.1
Core Data Structure
In theory, every RMQ can be answered by sequentially traversing the query range of the input array and computing the minimum. We visualized this in our introductory example in Figure 2, where 12 entries have to be traversed to find the minimum between positions 3 and 14 of the input array. However, while GPUs excel at sequential array traversals (aka scans), the cost for analyzing larger ranges becomes prohibitively high. To drastically reduce this cost, we can pre-compute the minima of fixed-size chunks of size 𝑐 (typically a power of two) and store them in a separate array as an additional layer. This reduces the problem to a coarse-granular RMQ in the significantly smaller minima array, followed by searching the minimum in the two chunks on the bottom layer that are not fully covered by the query. We illustrate this in Figure 6, where 𝑐 = 2 neighboring entries form a chunk (separated by dashed lines). Here, the query can be answered by scanning two entries in the bottom layer, and five pre-computed minima in the new layer, almost halving the amount of scanned entries. Of course, this pre-computation step can be applied recursively, producing a multi-level hierarchy of minima arrays. A three-layer hierarchy is shown in Figure 7, where we only have to traverse five entries in total to answer the RMQ. In theory, building a four-layer hierarchy would be possible for our example, but it would not be beneficial to our query since the query does not fully contain any third-layer chunk. This approach is efficient in terms of both construction and storage overhead: Generating the upper layers can be parallelized efficiently on a GPU by constructing each auxiliary layer of the hierarchy from bottom to top in parallel, where a group of adjacent threads reduces a chunk of 𝑐 adjacent entries to a single minimum summary. The resulting size of the hierarchy is only a small fraction of the input array’s memory footprint, as the number of additional elements 𝐸 in the hierarchy is bounded by 𝐸≤
log 𝑐 (𝑛) ∑︁ 𝑖=1
∞ 𝑖 𝑛 𝑛 ∑︁ 1 𝑛 1 𝑛 𝑐 𝑛 ≤ = = = . 𝑐𝑖 𝑐 𝑖=0 𝑐 𝑐 1 − 𝑐1 𝑐 𝑐 −1 𝑐 −1
To further reduce allocation complexity, we store all precomputed layers in a single, contiguous buffer. Answering a query only requires a sequential scan of the topmost qualifying layer,
1 2 3 4 5 6 7 8 9 10 11 12
Scan: Vector Loading vs Coalesced Loading
float scan ( group , l , r , array , m ) { uint my_rank = group . thread_rank () ; // align accesses to multiples of g uint offset = l - l % g ; for (; offset < r ; offset += g ) { uint my_offset = offset + my_rank ; if ( l <= my_offset && my_offset < r ) { m = min (m , array [ my_offset ]) ; } } return m ; }
Listing 1: Coalesced scan algorithm. Listing 1 shows the code for scanning a section of an array using coalesced loading and computing the thread-local minima. Listing 2 shows the full RMQ subroutine, which determines the bounds for the individual scans up the hierarchy, and performs the intra-group reduction. Note that both code snippets assume some information to be globally available, such as the chunk size c, thread group size g, and the two arrays base_array for the bottommost layer as well as upper_array for the remaining layers.
4 20 18 18 23 8 35 43
4 20 18 18 23 8 35 43
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ Lara Kreis, Justus Henneberg, Valentin Henkys, T0 FelixT1Schuhknecht, and Bertil Schmidt T0 T1 T2 T3 T4 T5 T6 T7 T2 T3 T0‘ T1‘ T2‘ T3‘
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
float rmq ( group , l , r ) { uint level = 0; float m = + INFINITY ; r += 1;
4 20 18 18 23 8 35 43 ▲ T0
▲ T1
▲ T2
▲ T3
▲ T4
▲ T5
▲ T6
▲ T7
▲ T1
▲ T2
▲ T3
▲ T0‘
▲ T1‘
▲ T2‘
▲ T3‘
Figure 8: Scanning a chunk with 6 entries in the RMQ range using larger (left) and smaller (right) thread groups.
for (; level < num_levels - 1; ++ level ) { if (r - l <= 2 * c ) { break ; } // next multiple of c larger or equal to l uint32_t next_l = ( l + c - 1) - ( l + c - 1) % c ; // next multiple of c smaller or equal to r uint32_t prev_r = r - r % c ;
4 20 18 18 23 8 35 43
4 20 18 18 23 8 35 43
▲ T0
▲ T0
▲ T1
▲ T2
▲ T3
▲ T4
▲ T5
▲ T6
▲ T7
▲ T1
▲ T2
▲ T3
▲ T0‘
▲ T1‘
▲ T2‘
▲ T3‘
Figure Scanning in the 4 209: 18 18 23 a8 chunk 35 43 with 43 entries 20 18 18 23 RMQ 8 35 range 43 using larger (left) smaller (right) ▲ ▲ ▲ ▲ ▲ and ▲ ▲ ▲ ▲ ▲ thread ▲ ▲ groups. ▲ ▲ ▲ ▲
// layer zero is the original array auto array = level == 0 ? base_array : upper_array + level_offset [ level ]; // scan left and right chunks m = scan ( group , l , next_l , array , m ) ; m = scan ( group , prev_r , r , array , m ) ;
T0
T1
T2
T3
T4
T5
T6
T7
T0
T1
T2
T3
T0‘
T1‘
T2‘
T3‘
bandwidth in this example. Overall, setting 𝑔 is non-trivial, which is why we evaluate it experimentally in Section 5.3.
4.3
l = next_l / c ; r = prev_r / c ;
Query Assignment: Multi-load vs Warp-local Queuing (WLQ)
Remember that our main workload consist of batch-solving 𝑚 RMQs concurrently, where each RMQ 𝑗 is defined by its two bounds, 𝑙 𝑗 and 𝑟 𝑗 . Our previously discussed scan mechanisms require all participating threads of a group to work on the same RMQ. There are two strategies for achieving this: (1) Multi-load. We spawn 𝑔 ·𝑚 threads in total. The thread with index 𝑡𝑖𝑑 is assigned to the query at position 𝑗 = ⌊𝑡𝑖𝑑/𝑔⌋ within the batch, and therefore acquires 𝑙 𝑗 and 𝑟 𝑗 from main memory. This approach is easy to implement and does not require communication between threads. (2) Warp-local queuing (WLQ). We spawn only 𝑚 threads, rounded up to the next multiple of 𝑔. The thread with index 𝑡𝑖𝑑 loads 𝑙𝑡𝑖𝑑 and 𝑟𝑡𝑖𝑑 . Each group now performs 𝑔 many rounds: For the first round, the first thread in the group uses warp shuffles to scatter its local values for 𝑙 and 𝑟 across the group. The threads then proceed with processing the query together, just like we described in the previous section. Finally, the computed result is sent back to the first thread. In the second round, the second thread in the group scatters its RMQ to the other threads, and receives the result, and so on. This essentially repurposes some of the threads’ registers as a queue for the queries and results. In the end, all threads write their results to some output buffer. We provide a reference implementation for warp-local queuing in Listing 3 and illustrate the process in Figure 10. Assuming 𝑔 ≤ 16, Strategy (1) performs 𝑔 · 𝑚 memory accesses, which the hardware coalesces into only 𝑚 actual transfers, while strategy (2) performs 𝑚 accesses, which the hardware coalesces into 𝑚/𝑔 many. In summary, Strategy (2) has noticeable better memory efficiency at the cost of increased register usage and requiring cross-thread communication.
} auto array = level == 0 ? base_array : upper_array + level_offset [ level ]; // scan last layer m = scan ( group , l , r , array , m ) ; return cg :: reduce ( group , m , cg :: less < float >() ) ; }
Listing 2: Scanning the hierarchy. The group size 𝑔 can be chosen independently from the chunk size 𝑐. Choosing a large group size increases the memory access efficiency of a single RMQ, but reduces the number of RMQs that we can process concurrently, as only a fixed number of threads is active at any given time. In addition, choosing 𝑔 close to 𝑐 can lead to poor thread usage: Figure 8 shows an RMQ with 6 entries in its range in a chunk of size 𝑐 = 8 being answered using a single access with group size 𝑔 = 8 (left) or two accesses with 𝑔 = 4 (right). Each thread in the group only loads and processes an entry it is assigned to if the entry falls into the range of the RMQ. In the figure, these qualifying entries are highlighted in orange, while non-qualifying entries are shown with a gray backdrop. When 𝑔 = 8, threads 0 and 1 stay idle during the scan because they are assigned to non-qualifying entries, and the remaining six threads in the group process the remaining entries. With 𝑔 = 4, there are only four active threads, and they perform the scan in two steps. In the first step, threads 0 and 1 stay idle again. However, in the second step, all four threads can do useful work, since all entries in the second half of the chunk fall into the range of the query. It is evident that choosing 𝑔 = 4 leads to higher thread utilization in this example. The effect is even more exaggerated in Figure 9: Choosing 𝑔 = 8 results in five idle threads. In contrast, when 𝑔 = 4, the first of the two loads is skipped altogether (since no entries in the first half fall into the range), and only one thread remains idle during the second step. In addition to higher thread utilization, choosing a smaller 𝑔 also saved memory
4 20 18 18 23 8 35 43 ▲ T0
1 2 3 4 5 6 7 8
uint my_id = my_thread_id () ; auto group = my_thread_group ( my_id ) ; uint my_rank = group . thread_rank () ; float result ; uint l , r ; bool find ;
GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4
20
18
18
23
8
35
43
43
36
68
63
22
52
81
75
9
3
1
9
6
3
1
9
6
3
1
9
6
3
1
9
6
3
1
9
6
14
7
12
11
14
7
12
11
14
7
12
11
14
7
12
11
14
7
12
11
3
3
3
3
1
1
1
1
9
9
9
9
6
6
6
6
14
14
14
14
7
7
7
7
12
12
12
12
11
11
11
11
legend thread with RMQ to be processed
indices
active thread shuffle operation rmq(group, active_l, active_r)
8
8
8
8
8
8
8
8
8
8
22
22
22
8
8
22
22
35
35
35
35
8
8
22
35
values 8
initial
iterations
Figure 10: Example of WLQ in GPU-RMQ with group size 4. Each thread in the group has a distinct RMQ. To process them cooperatively, one thread is designated as active and shuffles its RMQ indices to the remaining threads. Each thread then calls the function rmq (see Listing 2), which returns the group-wide minimum computed with coalesced memory accesses. The active thread stores the final result, after which the next thread becomes active to process its RMQ. 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
if ( my_id < num_queries ) { l = queries_l [ my_id ]; r = queries_r [ my_id ]; find = true ; } auto queue = group . ballot ( find ) ; while ( queue ) { auto active_rank = __ffs ( queue ) - 1; auto active_l = group . shfl (l , active_rank ) ; auto active_r = group . shfl (r , active_rank ) ; auto active_result = rmq ( group , active_l , active_r ) ; if ( active_rank == my_rank ) { result = active_result ; find = false ; } queue = group . ballot ( find ) ; } if ( my_id < num_queries ) { result_buffer [ my_id ] = result ; }
Listing 3: Warp-local queuing
4.4
Returning the Index
So far, we have only discussed how to answer RMQvalue . Solving RMQindex , which returns the index of the minimum, requires two small modifications: (1) When building the minima hierarchy, in addition to the minimum itself, we also store the position of the minimum in the original array. (2) When traversing the minima hierarchy, we return the stored position. If the minimum occurs multiple times between 𝑙 and 𝑟 , one can implement additional logic to guarantee we always return the rightmost or leftmost position.
4.5
Using Ray Tracing in the Hierarchy
Note that the scan on the topmost layer in GPU-RMQ corresponds to a regular RMQ, albeit on a summarized version of the original dataset. We can therefore introduce another dimension to our data structure: Following the design of RTXRMQ, we can replace the topmost layer with a triangle scene, and use the hardware ray 4 pipeline 18 to answer 8 35 36 63 22 still 75applying 9 tracing the top-layer RMQ, while our optimized scan strategy to the lower layers. 4 20 18 18 23 8 35 43 43 36 68 63 22 51 81 75 9
4
18
8
35
36
63
22
75
9
4 20 18 18 23 8 35 43 43 36 68 63 22 51 81 75 9
Figure 11: Three-layer minima hierarchy with the top layer replaced by a triangle scene. We visualize this in Figure 11, where the five triangles on the topmost layer replace the five array entries, and a ray-triangle intersection test replaces the scan. This has the following theoretical implications: (1) We can choose a larger value for the reduction cutoff threshold 𝑡 because the complexity of the ray tracing job scales better with input size than a linear scan of the topmost layer, resulting in fewer overall layers. (2) Since RT cores and CUDA cores are physically separate resources, the searches in the topmost layer and the remaining layers can be run concurrently within the same SM. To the best of our knowledge we are the first to exploit the combined usage of these different resources for a non-rendering problem with a single data structure.
Lara Kreis, Justus Henneberg, Valentin Henkys, Felix Schuhknecht, and Bertil Schmidt
However, this combination also requires addressing a number of technical challenges. In particular, the hardware ray tracing pipeline can only be accessed using the OptiX API, which is similar to CUDA, but introduces some restrictions to GPU programs. Most significantly, warp shuffling is not available in OptiX, forcing us to use less efficient implementations for intra-group minimum reduction (Section 4.2) and query assignment (Section 4.3). Our OptiX implementation first triggers the ray tracing job, then performs the linear scan down the hierarchy. Since there is no explicit dependency between the two parts, and GPUs heavily interleave warp execution anyway, this leaves plenty of leeway for the hardware to run ray tracing and scanning in parallel.
5
EXPERIMENTAL EVALUATION
In the following, we first empirically identify the best parameter configuration for GPU-RMQ (Section 5.3), as well as the different options regarding query assignment and the usage of ray tracing (Section 5.4). Then, we compare GPU-RMQ against a set of state-ofthe-art baseline methods in terms of memory footprint (Section 5.5), construction time (Section 5.6), and query time (Section 5.7). Additionally, we analyze the behavior of GPU-RMQ across different GPU architectures (Section 5.9).
5.1
Full GPU Scan: A naive CUDA-based GPU implementation where each thread processes one RMQ using a full scan of the corresponding values in the input array. LCA: A state-of-the-art GPU-based approach for solving LCA queries by Polak et al. [26], where Meneses et al. added the reduction from RMQ to LCA instances1 . RTXRMQ: The baseline that leverages RT cores exclusively to solve RMQs. 2 . We tested an OptiX 8-adapted version of RTXRMQ. RTXRMQ partitions the dataset with a user-configurable block size. We tested a large number of block sizes for each value of 𝑛 and always report the result with the highest throughput. Thus, the numbers serve as an upper bound for RTXRMQ’s performance. HRMQ: A CPU-based approach based on the paper Improved Range Minimum Queries [6]3 . We use the OpenMP-parallelized version by Meneses et al. and evaluate it with 128 CPU threads.
5.3
Tuning Parameters of GPU-RMQ
As explained in Section 4, GPU-RMQ supports both vector loading and coalesced loading, which we differentiate as GPU-RMQ (VL) and GPU-RMQ (CL) in the following. As both variations provide several tunable parameters, namely the group size 𝑔, the chunk size 𝑐, and the build cutoff threshold 𝑡, we will in the following empirically identify the best configuration for different array sizes 𝑛.
Experimental Setup
As described earlier, we run the main line of experiments on an NVIDIA GeForce RTX 4090 (Ada) with 24GB of GPU memory, and use an AMD Ryzen Threadripper 3990X with 64 cores and 128 threads for GPU-CPU comparisons. Furthermore, the evaluation is conducted using CUDA 12.9.1 and OptiX 8. To evaluate query performance, we test batches of three different range sizes in the following evaluation, namely large, medium, and small ranges, to study how much the range size impacts the performance of each method. These range sizes are defined as follows: • Large ranges: Uniformly distributed in [1, 𝑛] with a mean of ≈ 𝑛2 . • Medium ranges: Log-Normal distributed with mean 𝜇 = log(𝑛 0.6 ) and standard deviation 𝜎 = 0.3. • Small ranges: Log-Normal distributed with 𝜇 = log(𝑛 0.3 ) and 𝜎 = 0.3. • Mixed ranges: Randomly sampled from the three previous types (large, medium, small) with equal probability. The left border 𝑙 of a range is always drawn uniformly from [0, 𝑛−𝑠], where 𝑠 is the randomly chosen range size. To saturate the GPU, we fire a batch of 226 RMQs in total unless mentioned otherwise. The input array consists of independently sampled floating-point values from a uniform distribution on [0, 1]. The queries are sent to the GPU as a buffer of (𝑙, 𝑟 ) 32-bit integer pairs. We switch to 64-bit integers once the array size reaches 231 , to ensure every position in the array can be represented.
5.2
Baseline Methods
We evaluate our GPU-RMQ against the following baselines, which have been described in detail in Section 3.2:
Figure 12: Query time comparison using different group sizes (𝑔) and chunk sizes (𝑐) on mixed ranges for GPU-RMQ (VL) and GPU-RMQ (CL). For each 𝑛, the values are normalized relative to the best runtime. We observed that smaller values for 𝑡 always yield better performance, and therefore, we reduce the number of tests by always selecting 𝑡 as small as possible. For GPU-RMQ (CL), this minimal 𝑡 is required to be at least twice the chunk size 𝑐, whereas for GPU-RMQ (VL), 𝑡 must be greater than or equal to 𝑐. 1 The original implementation of LCA and the adapted one can be found at https: //github.com/stobis/euler-meets-cuda and https://github.com/temporal-hpc/eulermeets-cuda-rmq, respectively. 2 The implementation of RTXRMQ is available at https://github.com/temporal-hpc/ rtxrmq. 3 The code of HRMQ can be found here: https://github.com/hferrada/rmq.
GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs
(a) Large (l, r) range.
(b) Medium (l, r) range.
(c) Small (l, r) range.
Figure 13: Step-wise evaluation of the impact of integrating ray tracing into GPU-RMQ. To identify the best-performing parameter combinations of chunk size 𝑐 and group size 𝑔, we evaluate a large number of reasonable configurations in Figure 12 for both GPU-RMQ (CL) and GPU-RMQ (VL) while varying the array size 𝑛 from 220 to 231 . For each individual array size, we show the slowdown of each configuration with respect to the best observed configuration of that size. We can observe that no single parameter configuration is optimal for all array sizes 𝑛. However, for array sizes of up to 224 , GPURMQ (VL) consistently achieves the best performance, with an optimal chunk size of 𝑐 = 23 . Note that GPU-RMQ (VL) does not allow adjustment of the group size, as it employs vectorized float4 loads by default, resulting in an implicit group size of 4. For 𝑛 > 224 , GPU-RMQ (CL) outperforms GPU-RMQ (VL), with slightly varying optimal parameter combinations. Still, the experiments confirm our prediction from Section 4.1 that choosing the same value for group size and chunk size results in worse performance most of the time. Overall, a group size of 𝑔 = 24 combined with a chunk size of 𝑐 = 25 yields near-optimal performance across all large array sizes, and therefore, we use this configuration for GPU-RMQ (CL) in the remainder of the evaluation. Also note that this aligns the size of a chunk with the size of a GPU cache line, as both are 128 bytes wide. Unless stated otherwise, we collectively refer to both variants as GPU-RMQ. For array sizes smaller than 225 , the reported results correspond to GPU-RMQ (VL), while for larger arrays they correspond to GPU-RMQ (CL). In addition to these algorithm-specific parameters, we evaluated different CUDA thread block sizes. Because their impact on execution time was negligible, we use a block size of 1024 for all GPU-based algorithms throughout the evaluation.
5.4
Evaluating Optimizations of GPU-RMQ
After having tuned the parameters of GPU-RMQ, we experimentally evaluate the best choices for the remaining optimization aspects, namely (a) whether query assignment should happen via multi-loading or via warp-local queuing (WLQ) and (b) whether it
Figure 14: Execution time of GPU-RMQ (CL) for mixed ranges using WLQ compared to the multi-load approach we explained in Subsection 4.3
is beneficial to replace the topmost layer of the hierarchy with the raytracing-based RMQ algorithm. Regarding (a), Figure 14 compares both query assignment strategies for a batched RMQ task with queries of mixed size. We vary the size of the input array on the horizontal axis and report the time per RMQ on the vertical axis. The query batch size, i.e., the number of WLQs to be assigned to threads, remains constant. As discussed in Section 4.3, multi-loading performs more memory accesses than WLQ, resulting in higher execution time. The gap slightly shrinks as the size of the input (and the cost of answering the query) increases, but remains visible. Consequently, GPU-RMQ defaults to using WLQ. Unfortunately, WLQ cannot be combined with ray tracing: NVIDIA requires us to run GPU-RMQ in an OptiX kernel to utilize hardware ray tracing, but because OptiX’ programming model can move threads to different processing cores during execution, it might break warp locality guarantees, which is why NVIDIA does
Lara Kreis, Justus Henneberg, Valentin Henkys, Felix Schuhknecht, and Bertil Schmidt
not allow warp intrinsics in OptiX. Consequently, whenever OptiX is involved, we have to rewrite WLQ to a less efficient variant, and switch from warp reductions to atomic aggregation. We therefore have to investigate whether it is worth losing WLQ and warp aggregation in order to utilize ray tracing, which we integrate into our evaluation of (b). The relevant results are shown in Figure 13: Alongside GPURMQ, we evaluate a version without any warp intrinsics (GPURMQ w/o warp intrinsics) and then also run the identical code in an OptiX kernel without using ray tracing (GPU-RMQ w/o warp intrinsics in OptiX w/o RT) to determine the amount of overhead introduced by having to switch to OptiX. Lastly, we include the hybrid variant where the scan on the topmost layer is replaced by a ray tracing task (GPU-RMQ w/o warp intrinsics in OptiX w/ RT), alongside RTXRMQ, which relies on ray tracing exclusively. From the results we can see that executing the code in an OptiX kernel already adds significant overhead, especially for array sizes larger than 230 . Unfortunately, we can also observe that this overhead is not compensated by utilizing hardware ray tracing. This shows that using ray tracing for the top layer in the style of RTXRMQ is currently not recommended, and also explains why RTXRMQ itself is not competitive against our more traditional data structure. Ultimately, all following plots do not include the ray tracing variant of RTXRMQ.
5.5
Memory Footprint
Let us first inspect the memory footprint of GPU-RMQ in comparison to the GPU-resident baseline methods while varying the array size from 220 to 231 . Figure 15 shows the total amount of used GPU memory when executing the respective program, including the original array.
for RTXRMQ, an array size of 228 already exceeds the available GPU memory (24GB), rendering it unusable for larger arrays. In comparison, LCA has a higher memory footprint for 220 elements than RTXRMQ, which however, increases significantly less with an increase in array size. Nevertheless, array sizes of 229 or larger also exceed the available GPU memory. In contrast, the memory footprint of GPU-RMQ scales gracefully with an increase in array size and positions itself closely above the minimal memory footprint of Full GPU Scan, since its auxiliary data structure remains small for the configured choices of the chunk size 𝑐. Specifically, GPURMQ requires at most 30% more GPU memory than Full GPU Scan, whereas LCA consumes up to 5× more and RTXRMQ up to 13× more. As a consequence, GPU-RMQ remains feasible for array size of up to 231 , being limited by the RTX 4090’s main memory size. Even on GPUs with larger memory, GPU-RMQ always reaches the same limits as Full GPU Scan, thanks to its very low memory overhead.
5.6
5.7 Figure 15: Total memory footprint of all GPU-resident methods. Naturally, Full GPU Scan has the minimal memory footprint as it does not build any auxiliary data structures on top of the input array. While RTXRMQ also shows a competitive memory footprint for an array size of 220 , its memory footprint starts to increase drastically at an array size of 225 due the large number of heavyweight primitives that must be indexed in its BVH. As a result,
Construction Time
Next, we inspect the construction time of the auxiliary data structure of all methods. As Full GPU Scan does not incur any construction time, we do not show it here. Instead, we include the CPU-based variant HRMQ as a baseline. Figure 17 shows the construction time in milliseconds on a logarithmic scale for varying input array size. From a distance, we can already observe that the construction time of all baseline methods is significantly affected by an increase in array size. In contrast, our GPU-RMQ shows a very stable construction time, worsening only slightly for very large arrays. Moreover, GPU-RMQ archieves the fastest construction time among all methods, outperforming the GPU-resident baselines RTXRMQ and LCA, which perform very similarly. Specifically, GPU-RMQ builds its data structure up to ∼ 50× faster than RTXRMQ and up to ∼ 100× faster than LCA. The CPU-based variant HRMQ has the slowest construction time for all input sizes, up to ∼ 2400× slower than GPU-RMQ. While the construction algorithms of RTXRMQ and LCA scale poorly with an increase in array size, GPU-RMQ naturally utilizes the available parallel resources of the GPU. RTXRMQ suffers from the expensive BVH construction on a large number of primitives, while LCA has to construct a Cartesian tree and perform an Euler tour on it to generate its lookups tables. In contrast, GPU-RMQ constructs each auxiliary layer of its hierarchy from bottom to top in parallel, where a group of 𝑔 adjacent threads reduces a chunk of 𝑐 adjacent entries via warp reductions to a single summary.
RMQ Throughput
After having analyzed the memory footprint and the construction time, let us now inspect the performance for answering RMQs. Figure 16 shows the results, where we report for each method the average time of a single RMQ from the respective batch. First of all, we can see that the CPU-based method HRMQ is several orders-of-magnitude slower than the optimized GPU-based methods for all range sizes. Of all GPU-based methods, Full GPU Scan consistently performs the worst, whereas its performance predictably depends on the range size: The smaller the range, the
GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs
(a) Large (l, r) range.
(b) Medium (l, r) range.
(c) Small (l, r) range.
Figure 16: Average time per RMQ for a batch of 226 queries.
Figure 17: Total construction time for the data structures.
better it performs. For large and medium ranges and larger array sizes, the runtime per RMQ reaches 10ms and more, which is not competitive against the remaining methods4 . Still, in the best observed case, Full GPU Scan is around one order-of-magnitude slower than the sophisticated GPU-based methods. RTXRMQ overall performs worse than LCA and GPU-RMQ, especially for large ranges where it performs between ∼ 12 to ∼ 17× worse than GPU-RMQ. Additionally, it is affected the most by the range size, where handling larger ranges significantly slows it down. In comparison, both LCA and GPU-RMQ remain relatively unaffected by the range size. While LCA performs the best for small input arrays, its throughput significantly drops at an array size of 224 , resulting in up to ∼ 8× lower performance than GPURMQ. This is because LCA performs a small number of random, uncoalesced accesses for processing each query, which results in a memory bottleneck as soon as the working set no longer fits into the GPU’s L2 cache. In contrast, the performance of GPU-RMQ decreases gracefully with an increase in array size, showing the best query performance for the more relevant larger array sizes of 224 and larger. 4 For Full GPU Scan, we stopped the experiment for large and medium ranges and
large array sizes as the runtime exceeds any acceptable time frame.
Figure 18: Average time per RMQ for a batch of 226 mixed queries, comparing the competitive GPU algorithms across different GPUs.
5.8
Profiling
To analyze the throughput results in more detail, in the following, we perform a profiling run for the two best methods, namely LCA and GPU-RMQ, in NVIDIA Nsight Compute. Nsight Compute allows for kernel-level profiling of CUDA applications, showing metrics like occupancy, memory transfer rates, instruction throughput, and warp stalls. We run our analysis with 𝑛 = 228 on an RTX 4090 and focus on three reported metrics: (1) The amount of memory transferred between global memory and L2 cache. (2) The cache hit rates. (3) The average number of warp cycles between issued instructions, i.e., the timespan in which the GPU cannot do meaningful work due to memory latency. In Figure 16, all methods show different behavior for the three RMQ sizes, but GPU-RMQ behaves almost identical across all sizes once 𝑛 reaches a certain size (around 224 ). This is surprising at first, given that we would expect small queries to traverse around three layers of the hierarchy, and large ones to traverse five or
Lara Kreis, Justus Henneberg, Valentin Henkys, Felix Schuhknecht, and Bertil Schmidt
six, resulting in additional memory loads. The profiler reveals a 0% L1 hit rate and 16% L2 hit rate for small queries, while large queries yield hit rates of 34% and 61%, respectively. Remember that the uppermost layers in the hierarchy have a very low memory footprint, and can easily fit into L2 cache. As the uppermost layers are cache-resident most of the time while answering large queries, only the lower levels have to be loaded using slow main-memory accesses, resulting in a similar number of main-memory accesses for both large and small RMQs. Curiously, the profiler also underpins another interesting observation: LCA actually performs better when dealing with larger ranges compared to smaller ranges. For 𝑛 = 228 , the LCA loads a total of 21.6 GB from the GPU’s main memory when processing the small-range workload, but only 9.8 GB when processing the large-range workload, and the execution time halves accordingly. As evidenced by Figure 16, this behavior is not an isolated incident, as it repeats across all choices of 𝑛. Investigating this effect will be part of future research. Finally, note that profiling LCA yields between 2500 (large) and 4800 (small) warp cycles per instruction, depending on the range size, meaning that most of the time is spent waiting for random memory accesses, despite the total number of accesses performed by LCA being constant (i.e., independent of the range size). For comparison, GPU-RMQ exhibits between 18 and 34 average warp cycles per instruction, implying better GPU utilization.
5.9
Different GPU Generations
So far, we have evaluated all methods on a NVIDIA RTX 4090 GPU from the Ada generation, with 24GB of global memory. Let us now see whether the results look different on an NVIDIA RTX 3090 GPU from the (older) Ampere generation and a NVIDIA RTX 6000 Pro from the (newer) Blackwell generation. Further, an RTX 6000 Pro has 96GB of global memory, and we are interested in seeing how effectively the methods utilize the additional space and which array sizes they can practically handle. Figure 18 shows the average time per RMQ for RTXRMQ, LCA, and GPU-RMQ on all three GPU generations for the mixed workload. First of all, we can see that naturally, the time per RMQ improves for all methods when going from older to newer GPUs. Within each GPU generation, we can see that the relative order between the individual methods remains the same: RTXRMQ is clearly the slowest, LCA performs second best, and GPU-RMQ outperforms the competitors for all array sizes. Let us investigate the results for the two newly investigated GPU generation more closely: For the RTX 3090, which only has 6MB of L2 cache, the smallest tested array size of 220 elements (4MB) already almost fully occupies the cache. Consequently, for relevant array sizes, all methods suffer from a significant amount of cache misses. However, we can also see that GPU-RMQ can utilize the available cache a bit longer than the competitors, with its performance drop only at 222 elements (16MB). For the RTX 6000 Pro, which has 96GB of global memory, we can first of all see that all methods can handle larger arrays. However, while RTXRMQ and LCA are only able to double the amount of elements they can index, GPU-RMQ is able to actually handle arrays four times the size. This resembles the increase in available global memory in comparison to the RTX 3090
and RTX 4090. By this, GPU-RMQ is able to handle datasets up to 233 elements (64GB), while RTXRMQ and LCA run out of memory already at 228 elements (1GB) and 229 elements (2GB), respectively.
6
CONCLUSION
In this work, we presented GPU-RMQ, a publicly available opensource highly-parallel hierarchical acceleration structure for answering RMQs on GPUs. We showed that it is able to outperform the state-of-the-art CPU and GPU-based alternatives in three essential aspects, namely (a) memory footprint (up to ∼ 4× smaller than LCA and ∼ 10× smaller than RTXRMQ), (b) construction time (up to ∼ 50× faster than RTXRMQ, ∼ 100× faster than LCA and ∼ 2400× faster than HRMQ), and (c) throughput (up to ∼ 8× faster than LCA, ∼ 17× faster than RTXRMQ and ∼ 4800× faster than HRMQ) — enabling RMQ acceleration on GPUs especially for previously not feasible very large datasets. We further demonstrated that GPU-RMQ is highly robust across a variety of different workloads, array sizes, and GPU generations. This new level of acceleration can be beneficial to a wide range of applications in areas including biological sequence analysis, pattern matching, and document retrieval. In addition, our presented techniques can also provide insights for enhancing other scan-heavy general-purpose data structures on GPUs. We have also investigated the exploitation of heterogeneous resources by combining the usage of CUDA cores and RT cores. Our performance evaluation shows that the associated overheads overshadow potential performance benefits on current generation GPU architectures. However, since RT cores are evolving rapidly, this approach might become more efficient in the near future.
REFERENCES [1] Mai Alzamel, Panagiotis Charalampopoulos, Costas S Iliopoulos, and Solon P Pissis. 2017. How to answer a small batch of RMQs or LCA queries in practice. In International Workshop on Combinatorial Algorithms. Springer, 343–355. [2] Saman Ashkiani, Martin Farach-Colton, and John D. Owens. 2018. A Dynamic Hash Table for the GPU. In 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018. IEEE Computer Society, 419–429. https://doi.org/10.1109/IPDPS.2018.00052 [3] Saman Ashkiani, Shengren Li, Martin Farach-Colton, Nina Amenta, and John D. Owens. 2018. GPU LSM: A Dynamic Dictionary Data Structure for the GPU. In 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018. IEEE Computer Society, 430–440. https://doi.org/10.1109/IPDPS.2018.00053 [4] Muhammad A. Awad, Saman Ashkiani, Rob Johnson, Martin Farach-Colton, and John D. Owens. 2019. Engineering a high-performance GPU B-Tree. In Proceedings of the 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019, Washington, DC, USA, February 16-20, 2019, Jeffrey K. Hollingsworth and Idit Keidar (Eds.). ACM, 145–157. https://doi.org/ 10.1145/3293883.3295706 [5] Niklas Baumstark, Simon Gog, Tobias Heuer, and Julian Labeit. 2017. Practical Range Minimum Queries Revisited. In 16th International Symposium on Experimental Algorithms (SEA 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, and Rajeev Raman (Eds.), Vol. 75. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 12:1–12:16. https://doi.org/10.4230/LIPIcs.SEA.2017.12 [6] Héctor Ferrada and Gonzalo Navarro. 2017. Improved Range Minimum Queries. Journal of Discrete Algorithms 43 (2017), 72–80. https://doi.org/10.1016/j.jda. 2016.09.002 [7] Paolo Ferragina and Filippo Lari. 2025. FL-RMQ: A Learned Approach to Range Minimum Queries. In Proc. 36th Annual Symposium on Combinatorial Pattern Matching. [8] Johannes Fischer and Volker Heun. 2007. A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array. (2007), 459–470. [9] Johannes Fischer and Volker Heun. 2011. Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays. SIAM J. Comput. 40 (01 2011), 465–492. https://doi.org/10.1137/090779759
GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs
[10] Patrick Flick and Srinivas Aluru. 2019. Distributed enhanced suffix arrays: efficient algorithms for construction and querying. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–17. [11] Liang Geng, Rubao Lee, and Xiaodong Zhang. 2024. Rayjoin: Fast and precise spatial join. In Proceedings of the 38th ACM International Conference on Supercomputing. 124–136. [12] Liang Geng, Rubao Lee, and Xiaodong Zhang. 2025. LibRTS: A Spatial Indexing Library by Ray Tracing. In Proceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 396–411. [13] Justus Henneberg and Felix Schuhknecht. 2023. RTIndeX: Exploiting HardwareAccelerated GPU Raytracing for Database Indexing. Proceedings of the VLDB Endowment 16 (12 2023), 4268–4281. https://doi.org/10.14778/3625054.3625063 [14] Justus Henneberg, Felix Schuhknecht, Rosina Kharal, and Trevor Brown. 2025. More Bang For Your Buck (et): Fast and Space-efficient Hardware-accelerated Coarse-granular Indexing on GPUs. In 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, 1320–1333. [15] Justus Henneberg and Felix Martin Schuhknecht. 2025. All You Need Is Binary Search! A Practical View on Lightweight Database Indexing on GPUs. CoRR abs/2506.01576 (2025). https://doi.org/10.48550/ARXIV.2506.01576 arXiv:2506.01576 [16] Daniel Jünger, Robin Kobus, André Müller, Christian Hundt, Kai Xu, Weiguo Liu, and Bertil Schmidt. 2020. WarpCore: A Library for fast Hash Tables on GPUs. In 27th IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2020, Pune, India, December 16-19, 2020. IEEE, 11–20. https://doi.org/10.1109/HIPC50609.2020.00015 [17] Daniel Jünger, Kevin Kristensen, Yunsong Wang, Xiangyao Yu, and Bertil Schmidt. 2025. Optimizing Bloom Filters for Modern GPU Architectures. CoRR abs/2512.15595 (2025). https://doi.org/10.48550/ARXIV.2512.15595 arXiv:2512.15595 [18] S. Kalikar, C. Jain, M. Vasimuddin, and S. Misra. 2022. Accelerating minimap2 for long-read sequencing applications on modern CPUs. Nat Comput Sci 2 (2022), 78–83. https://doi.org/10.1038/s43588-022-00201-8 [19] Tomasz M Kowalski and Szymon Grabowski. 2018. Faster range minimum queries. Software: Practice and Experience 48, 11 (2018), 2043–2060. [20] Heng Li. 2018. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics 34, 18 (05 2018), 3094–3100. https://doi.org/10.1093/ bioinformatics/bty191 arXiv:https://academic.oup.com/bioinformatics/articlepdf/34/18/3094/48919122/bioinformatics_34_18_3094.pdf
[21] Mingmou Liu and Huacheng Yu. 2020. Lower bound for succinct range minimum query. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 1402–1415. [22] Yangming Lv, Kai Zhang, Ziming Wang, Xiaodong Zhang, Rubao Lee, Zhenying He, Yinan Jing, and X Sean Wang. 2024. Rtscan: Efficient scan with ray tracing cores. Proceedings of the VLDB Endowment 17, 6 (2024). [23] Enzo Meneses, Cristóbal A Navarro, Héctor Ferrada, and Felipe A Quezada. 2024. Accelerating range minimum queries with ray tracing cores. Future Generation Computer Systems 157 (2024), 98–111. [24] Nurit Moscovici, Nachshon Cohen, and Erez Petrank. 2017. A GPU-Friendly Skiplist Algorithm. In 26th International Conference on Parallel Architectures and Compilation Techniques, PACT 2017, Portland, OR, USA, September 9-13, 2017. IEEE Computer Society, 246–259. https://doi.org/10.1109/PACT.2017.13 [25] Vani Nagarajan, Durga Mandarapu, and Milind Kulkarni. 2023. RT-kNNS Unbound: Using RT Cores to Accelerate Unrestricted Neighbor Search. In Proceedings of the 37th ACM International Conference on Supercomputing (Orlando, FL, USA) (ICS ’23). Association for Computing Machinery, New York, NY, USA, 289–300. https://doi.org/10.1145/3577193.3593738 [26] Adam Polak, Adrian Siwiec, and Michał Stobierski. 2021. Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees. In 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 233–244. https://doi.org/10.1109/IPDPS49936.2021.00032 [27] Luís MS Russo. 2022. Range minimum queries in minimal space. Theoretical Computer Science 909 (2022), 19–38. [28] Baruch Schieber and Uzi Vishkin. 1988. On finding lowest common ancestors: Simplification and parallelization. In VLSI Algorithms and Architectures, John H. Reif (Ed.). Springer New York, New York, NY, 111–123. [29] Xuri Shi, Kai Zhang, X Sean Wang, Xiaodong Zhang, and Rubao Lee. 2025. RayDB: Building Databases with Ray Tracing Cores. Proceedings of the VLDB Endowment 19, 1 (2025), 43–55. [30] Jyothish Soman, Kishore Kothapalli, and P. J. Narayanan. 2012. Discrete range searching primitive for the GPU and its applications. ACM J. Exp. Algorithmics 17, Article 4.5 (Oct. 2012), 17 pages. https://doi.org/10.1145/2133803.2345679 [31] Noah South and Byunghyun Jang. 2023. Scan Stack: A Search-based Concurrent Stack for GPU. In Proceedings of the 2023 ACM Southeast Conference, ACMSE 2023, Virtual Event, USA, April 12-14, 2023, Kuang-Nan Chang, Eric Gamess, and Chi Shen (Eds.). ACM, 10–19. https://doi.org/10.1145/3564746.3587018 [32] Qisheng Wang, Zhean Xu, and Zhicheng Zhang. 2026. Quantum Data Structure for Range Minimum Query. J. Comput. System Sci. (2026), 103756.