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 |
Abstract
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:
http://referaat.cs.utwente.nl/conference/20/paper/7420/design-of-a-scalable-hash-table-on-a-gpu.pdf
References
- Alfons Laarman, Jaco van de Pol, Michael Weber: Parallel Recursive State Compression for Free. SPIN 2011: 38-56 (Digital version available here)
- Khronos OpenCLWorking Group. The OpenCL Specification, version 1.2, 2001, URL (Digital version available here)
- J. Tompson, K. Schlachter. An Introduction to the OpenCL Programming Model. (Digital version available here)