Name
Abstract | ||
|---|---|---|
Graphics processing units (GPUs) have emerged as a strong candidate for high-performance computing. While regular data-parallel computations with little or no synchronization are easy to map on the GPU architectures, it is a challenge to scale up computations on dynamically changing pointer-linked data structures. The traditional lock-based implementations are known to offer poor scalability due to high lock contention in the presence of thousands of active threads, which is common in GPU architectures. In this paper, we present a performance evaluation of concurrent lock-free implementations of four popular data structures on GPUs. We implement a set using lock-free linked list, hash table, skip list, and priority queue. On the first three data structures, we evaluate the performance of different mixes of addition, deletion, and search operations. The priority queue is designed to support retrieval and deletion of the minimum element and addition operations to the set. We evaluate the performance of these lock-free data structures on a Tesla C2070 Fermi GPU and compare it with the performance of multi-threaded lock-free implementations for CPU running on a 24-core Intel Xeon server. The linked list, hash table, skip list, and priority queue implementations achieve speedup of up to 7.4, 11.3, 30.7, and 30.8, respectively on the GPU compared to the Xeon server. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/ICPADS.2012.18 | ICPADS |
Keywords | Field | DocType |
data structures,graphics processing units,multi-threading,GPU,Intel Xeon server,Tesla C2070 Fermi GPU,addition operations,concurrent lock-free data structures,data-parallel computations,deletion operations,graphics processing units,hash table,high-performance computing,lock-based implementations,lock-free linked list,multithreaded lock-free implementations,performance evaluation,pointer-linked data structures,priority queue,search operations,skip list,CUDA,GPU,concurrent,hash table,linked list,lock-free,priority queue,skip list | Data structure,Linked list,Non-blocking algorithm,Computer science,Skip list,Parallel computing,Priority queue,Xeon,Speedup,Distributed computing,Hash table | Conference |
ISSN | Citations | PageRank |
1521-9097 | 9 | 0.61 |
References | Authors | |
12 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prabhakar Misra | 1 | 9 | 0.61 |
| Mainak Chaudhuri | 2 | 300 | 18.86 |