First Advisor
Mark Jones
Term of Graduation
January 2026
Date of Publication
6-1-2026
Document Type
Dissertation
Language
English
Subjects
compiler implementation, computer architecture, concurrent programming, data structures, group prefetching, instruction- and memory-level parallelism
Physical Description
1 online resource ( pages)
Abstract
A group operation performs multiple independent instances of the same operation on a data structure. For example, a group operation might look up 10 different keys in a binary search tree, returning 10 results. Chen et al introduced group prefetching, an optimization for group operations on linked data structures that improves throughput by overlapping memory access latencies for independent traversals. Constructing code that maximizes this throughput benefit by fully leveraging the instruction- and memory-level parallelism available on modern hardware is challenging because of overhead, interactions with the cache hierarchy, and other factors. To address these challenges, we present two new implementation techniques for group operations with group prefetching and we compare them empirically to prior work. We apply these techniques to operations on internal and external binary search trees, and focus our evaluation on shared memory concurrent programming on a multicore system. We present novel optimizations specific to these techniques, and apply optimizations from prior work in this new context. These two techniques improve on prior work in most cases.
Rights
In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
Recommended Citation
Cooper, Theodora R., "Group Operations for Concurrent Binary Search Trees" (2026). Dissertations and Theses. Paper 7117.