Title :
Lock-free Hash Table on Graphics Processors
Author :
Moazeni, Maryam ; Sarrafzadeh, Majid
Author_Institution :
Comput. Sci. Dept., Univ. of California, Los Angeles, Los Angeles, CA, USA
Abstract :
Lock-free data structures guarantee higher throughput than lock-based implementations in parallel architectures. This paper presents the first CAS-based lock-free hash table that is based on chaining on GPUs. We achieve an improvement of about 2-8X over lock-free OpenMP implementation. We also achieve over 2-25X speed up over GPU lock-based implementation. We achieve 1.3X to 3.5X increase on throughput with combined Insert and Search workloads over the counterpart OpenMP implementation.
Keywords :
data structures; graphics processing units; parallel architectures; CAS-based lock-free hash table; GPU lock-based implementation; OpenMP implementation; data structures; graphics processors; insert workloads; parallel architectures; search workloads; Algorithm design and analysis; Data structures; Educational institutions; Graphics processing unit; Instruction sets; Throughput; GPGPU; Lock-free Hash Table; Many-core; Massively Parallel;
Conference_Titel :
Application Accelerators in High Performance Computing (SAAHPC), 2012 Symposium on
Conference_Location :
Chicago IL
Print_ISBN :
978-1-4673-2882-1
DOI :
10.1109/SAAHPC.2012.25
