Technical Report MSC-2017-33

Title: A GPU-Friendly Skiplist Algorithm
Authors: Nurit Moscovici
Supervisors: Erez Petrank
PDFCurrently accessibly only within the Technion network
Abstract: We propose a design for a fine-grained lock-based skiplist optimized for execution on Graphics Processing Units (GPUs). GPUs have become increasingly popular in recent years as a platform for accelerating general purpose computations (GPGPU). GPUs are often used to accelerate streaming parallel computations, and it has been shown that highly data-intensive applications can achieve an order of magnitude speedup when run on a GPU. However, it remains a significant challenge to efficiently offload concurrent computations with more complicated data-irregular access and fine-grained synchronization. Natural building blocks for such computations would be concurrent data structures, such as skiplists, which are widely used in general purpose computations. Many efficient implementations of concurrent data structures have been designed and are widely used in parallel applications for the CPU. However, many of these algorithms do not fit with the specialized architectural requirements of the GPU, and may not scale well or even perform correctly. Our design utilizes array-based nodes which are accessed and updated by warp-cooperative functions, thus taking advantage of the fact that GPUs are most efficient when memory accesses are coalesced and execution divergence is minimized. The proposed design has been implemented, and measurements demonstrate improved performance of up to 11.6x over skiplist designs for the GPU existing today.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2017
To the main CS technical reports page

Computer science department, Technion