Modern designs of concurrent FIFO queues often improve their scalability through executing multiple simultaneous operations or reducing cache coherence traffic, yet their ordering semantics under contention remain inadequately characterized. While the linearizability model ensures correctness, it allows arbitrary reordering of overlapping operations, masking significant deviations from ideal FIFO behavior. We introduce fairness as a measure of how closely concurrent enqueue and dequeue operations respect their invocation order. We propose two complementary metrics, overtake depth, which quantifies the severity of per-element ordering violations and overtake percentage, which measures the frequency of such violations system-wide. We apply our metrics to benchmark several modern concurrent queues under balanced and imbalanced workloads on an 8-core AMD Ryzen processor. Our results reveal that fairness violations are pervasive: under high contention, queues exhibit overtake percentages up to 68%, with individual elements bypassed by an average of 25 others (overtake depth) in severe cases. Our analysis shows that the common causes of unfairness are 1) retrying compare-and-swap (CAS) operations, 2) combiner threads delaying their own operations, 3) delays between invocation and linearization that allow operations to be descheduled. Additionally, we observe a strong correlation ($R^{2}=0.98$) between L1 cache miss rates and overtake percentage, indicating that operations delayed by cache coherence stalls are more likely to be overtaken.

The hash table finds numerous applications in many different domains, but its potential for non-coalesced memory accesses and execution divergence characteristics impose optimization challenges on GPUs. We propose a novel hash table design, referred to as Cuckoo Node Hashing, which aims to better exploit the massive data parallelism offered by GPUs. At the core of its design, we leverage Cuckoo Hashing, one of known hash table design schemes, in a closed-address manner, which, to our knowledge, is the first attempt on GPUs. We also propose an architecture-aware warp-cooperative reordering algorithm that improves the memory performance and thread divergence of Cuckoo Node Hashing and efficiently increases the likelihood of coalesced memory accesses in hash table operations. Our experiments show that Cuckoo Node Hashing outperforms and scales better than existing state-of-the-art GPU hash table designs such as DACHash and Slab Hash with a peak performance of 5.03 billion queries/second in static searching and 4.34 billion insertions/second in static building.

GPU acceleration of hash tables in high-volume transaction applications such as computational geometry and bio-informatics are emerging. Recently, several hash table designs have been proposed on GPUs, but our analysis shows that they still do not adequately factor in several important aspects of a GPU's execution environment, leaving large room for further optimization. To that end, we present a dynamic, cache-aware, concurrent hash table named DACHash. It is specifically designed to improve memory efficiency and reduce thread divergence on GPUs. We propose several novel techniques including a GPU-friendly data structure & sizing, a reorder algorithm, and dynamic thread-data mapping schemes that make the operations of hash table more amendable to GPU architecture. Testing DACHash on an NVIDIA GTX 3090 achieves a peak performance of 8.65 billion queries/second in static searching and 5.54 billion operations/second in concurrent operation execution. It outperforms the state-of-the-art SlabHash by 41.53% and 19.92% respectively. We also verify that our proposed technique improves L2 cache bandwidth and L2 cache hit rate by 9.18× and 2.68× respectively.

The persistent thread model offers a viable solution for accelerating data-irregular workloads on Graphic Processing Units (GPUs). However, as the number of active threads increases, contention and retries on shared resources limit the efficiency of task scheduling among the persistent threads. To address this, we propose a highly scalable, non-blocking concurrent queue suitable for use as a GPU persistent thread task scheduler. The proposed concurrent queue has two novel properties: 1) The supporting enqueue/dequeue queue operations never suffer from retry overhead because the atomic operation does not fail and the queue empty exception has been refactored; and 2) The queue operates on an arbitrary number of queue entries for the same cost as a single entry. A proxy thread in each thread group performs all atomic operations on behalf of all threads in the group. These two novel properties substantially reduce thread contention caused by the GPU's lock-step Single Instruction Multiple Threads (SIMT) execution model.

Modern GPUs embrace on-chip cache memory to exploit the locality present in applications. However, the behavior and effect of the cache on GPUs are different from those on conventional processors due to the Single Instruction Multiple Thread (SIMT) thread execution model and resulting memory access patterns. Previous studies report that caching data can hurt the performance due to increased memory traffic and thrashing on massively parallel GPUs. We found that the massive parallel thread execution of GPUs causes significant resource access contention among threads, especially within a warp. This is due to excessive demands for memory resources that are not sufficient to support massively parallel thread execution when memory access patterns are not hardware friendly. In this paper, we propose a locality and contention aware selective caching based on memory access divergence to mitigate intra-warp resource contention in L1 data (L1D) cache on GPUs. To determine when and what to cache we use the following heuristics: first, we detect memory divergence degree (i.e., how the memory requests from a warp are grouped) of the memory instruction to determine whether the selective caching is needed. Second, we use cache index calculation to handle congested cache sets. %the case where accesses are congested into certain cache sets. Finally, we calculate locality degree to find a better victim cache line. These algorithmic selective caching is developed based on our observation that 1) divergent memory access incurs severe contention for cache hardware resources and 2) accesses are mapped to certain sets when set associativity is relatively small compared with the memory divergence degree. Experimental results by GPU architectural simulator show that our proposed selective caching improves the average performance by 2.25x over baseline and reduces L1D cache accesses by 71%. It outperforms recently published state-of-the-art GPU cache bypassing schemes.

The conventional OpenCL 1.x style CPU-GPU heterogeneous computing paradigm treats the CPU and GPU processors as loosely connected separate entities. At best each executes independent tasks, but, more commonly, the CPU idles while waiting for results from the GPU. No data-sharing and communications are allowed during kernel execution. This model limits the number of applications that can harness the tremendous computing power of two processors. OpenCL 2.x and compliant hardware introduce a new memory model that enables a new computing paradigm where the task-parallel CPU and data-parallel GPU are tightly coupled and can closely cooperate on shared data in a lock-based or non-blocking fashion. This new model maximizes hardware utilization and performance, and opens more applications to GPU acceleration. The most significant new OpenCL 2.x features are fine-grained data sharing and thread communication through shared virtual memory, CPU-GPU cache coherence support, and system-level atomics. However, few applications that can exploit the benefits of tightly coupled CPU-GPU heterogeneous processors have emerged. Programming and debugging in this new environment have proven challenging. The resulting lack of benchmark workloads have also left hardware architects uninformed. To facilitate truly heterogeneous workload development and hardware architecture research, this paper focuses on understanding the impact of fine-grained data sharing between the CPU and GPU for future heterogeneous workload development. To that goal, we identify three CPU-GPU cooperation paradigms, demonstrate their performance benefits on real hardware using both in-house and publicly available benchmarks, and profile their detailed behavior and characteristics using an architectural simulator. Our experiments demonstrate that truly heterogeneous implementations of our studied benchmarks outperform their corresponding conventional CPU or GPU versions by up to 59.5% and 36.6% respectively. We analyze thread contention problems, latency of synchronization operations and inter-cluster memory traffic in each cooperation paradigm using a timing architectural simulator.

Processing elements such as CPUs and GPUs depend on cache technology to bridge the classic processor memory subsystem performance gap. As GPUs evolve into general purpose co-processors with CPUs sharing the load, good cache design and use becomes increasingly important. While both CPUs and GPUs must cooperate and perform well, their memory access patterns are very different. On CPUs only a few threads access memory simultaneously. On GPUs, there is significantly higher memory access contention among thousands of threads. Despite such different behavior, there is little research that investigates the behavior and performance of GPU caches in depth. In this paper, we present our extensive study on the characterization and improvement of GPU cache behavior and performance for general-purpose workloads using a cycle-accurate ISA level GPU architectural simulator that models one of the latest GPU architectures, Graphics Core Next (GCN) from AMD. Our study makes the following observations and improvements. First, we observe that L1 vector data cache hit rate is substantially lower when compared to CPU caches. The main culprit is compulsory misses caused by lack of data reuse among massively simultaneous threads. Second, there is significant memory access contention in shared L2 data cache, accounting for up to 19% of total access for some benchmarks. This high contention remains a main performance barrier in L2 data cache even though its hit rate is high. Third, we demonstrate that memory access coalescing plays a critical role in reducing memory traffic. Finally we found that there exists inter-workgroup locality which can affect the cache behavior and performance. Our experimental results show memory performance can be improved by 1) shared L1 vector data cache where multiple compute units share a single cache to exploit inter-workgroup locality and increase data reusability, and 2) clustered workgroup scheduling where workgroups with consecutive IDs are assigned on the same compute unit.

Accurate simulation is essential for the proper design and evaluation of any computing platform. Upon the current move toward the CPU-GPU heterogeneous computing era, researchers need a simulation framework that can model both kinds of computing devices and their interaction. In this paper, we present Multi2Sim, an open-source, modular, and fully configurable toolset that enables ISA-level simulation of an x86 CPU and an AMD Evergreen GPU. Focusing on a model of the AMD Radeon 5870 GPU, we address program emulation correctness, as well as architectural simulation accuracy, using AMD's OpenCL benchmark suite. Simulation capabilities are demonstrated with a preliminary architectural exploration study, and workload characterization examples. The project source code, benchmark packages, and a detailed user's guide are publicly available at www.multi2sim.org.

The introduction of General-Purpose computation on GPUs (GPGPUs) has changed the landscape for the future of parallel computing. At the core of this phenomenon are massively multithreaded, data-parallel architectures possessing impressive acceleration ratings, offering low-cost supercomputing together with attractive power budgets. Even given the numerous benefits provided by GPGPUs, there remain a number of barriers that delay wider adoption of these architectures. One major issue is the heterogeneous and distributed nature of the memory subsystem commonly found on data-parallel architectures. Application acceleration is highly dependent on being able to utilize the memory subsystem effectively so that all execution units remain busy. In this paper, we present techniques for enhancing the memory efficiency of applications on data-parallel architectures, based on the analysis and characterization of memory access patterns in loop bodies; we target vectorization via data transformation to benefit vector-based architectures (e.g., AMD GPUs) and algorithmic memory selection for scalar-based architectures (e.g., NVIDIA GPUs). We demonstrate the effectiveness of our proposed methods with kernels from a wide range of benchmark suites. For the benchmark kernels studied, we achieve consistent and significant performance improvements (up to 11.4× and 13.5× over baseline GPU implementations on each platform, respectively) by applying our proposed methodology.

Loop vectorization, a key feature exploited to obtain high performance on Single Instruction Multiple Data (SIMD) vector architectures, is significantly hindered by irregular memory access patterns in the data stream. This paper describes data transformations that allow us to vectorize loops targeting massively multithreaded data parallel architectures. We present a mathematical model that captures loop-based memory access patterns and computes the most appropriate data transformations in order to enable vectorization. Our experimental results show that the proposed data transformations can significantly increase the number of loops that can be vectorized and enhance the data-level parallelism of applications. Our results also show that the overhead associated with our data transformations can be easily amortized as the size of the input data set increases. For the set of high performance benchmark kernels studied, we achieve consistent and significant performance improvements (up to 11.4X) by applying vectorization using our data transformation approach.