author: Thomas Neele
title: Implementation of a compression algorithm in a GPU
keywords: gpu programming, parallel algorithms, compression algorithm
topics: Algorithms and Data Structures
committee: Afshin Amighi ,
Marieke Huisman ,
Saeed Darabi
end: January 2014


We investigate the scalability of an existing lockless hash table when it is implemented on a GPU. This lockless hash table is an essential part of a model checker, a tool that can be used to prove the correctness of software that performs critical tasks. We show that our implementation of the hash table on a GPU is scalable and that a GPU can lookup twice as much per second as a CPU when running the same OpenCL implementation. We also propose a design for integrating our implementation with a model checker. We argue that this design will lead to better performance of the model checker.

For the paper see:



  1. Alfons Laarman, Jaco van de Pol, Michael Weber: Parallel Recursive State Compression for Free. SPIN 2011: 38-56 (Digital version available here)
  2. Khronos OpenCLWorking Group. The OpenCL Specification, version 1.2, 2001, URL (Digital version available here)
  3. J. Tompson, K. Schlachter. An Introduction to the OpenCL Programming Model. (Digital version available here)

Additional Resources

  1. The paper