GPU 的哈希表实现

Question

我正在寻找一种哈希表实现，可以用于CUDA编程。是否有任何好的选择，比如 Python 字典？我将使用字符串作为我的键。

- Programmer

---

我前几天在GPU上测试了md5哈希算法的实现。你可以使用它来计算数据的哈希值，然后将它们存储在映射中。 - karlphillip

@karlphilip：GPU上是否有地图实现？ - Programmer

什么？你想在GPU上存储数据？不，不行...只能用它来处理！映射本身（将哈希与原始数据连接的那个）应该存储在RAM中。因此，如果您正在使用C++编程，可以使用类似于 std :: map <std :: string，SomePointerToTheData> 的东西，其中std :: string是由GPU计算出的哈希，而pointerToTheOriginalData就是...确切的数据指针。 - karlphillip

@karlphillip 有时候处理过程需要使用哈希映射，例如我目前正在GPU上开发LZ77。除了矩阵乘法和光线投射之外，GPU还可以执行更多的操作。 - Radim Vansa

Answer 1

Alcantara et al展示了一种在GPU上构建哈希表的数据并行算法。我相信该实现作为CUDPP的一部分已经提供。

话虽如此，您可能需要重新考虑您最初选择使用哈希表的原因。在按键排序后，批量执行大量查询应该可以在大规模并行设置中获得更好的性能。您试图解决什么问题？

- Jared Hoberock

---

“批量执行大量查询”是什么意思？我正在尝试将倒排索引存储在哈希表中，其中键将是字符串，值将是整数列表。给定一个查询项，我将在哈希表中查找并检索该列表。 - Programmer

你有使用cudpp哈希表的小代码片段吗？这将非常有帮助。 - Programmer

此外，为什么不建议使用cudpp呢？ - Programmer

有类似于 OpenCL 的东西吗？ - ethanjyx

“通过按键排序数据，然后批量执行多个查询应该在大规模并行设置中产生更好的性能”，你是什么意思？例如，我需要访问很多线程的几百个键。当然，我可以对它们进行排序，但这并不能给我O(1)的访问，因为这些数据不经常更新。即使我有一个包含1k条目的表，只有四分之一实际上被填充，这样的表也比尝试通过列表进行二进制搜索更具性能优势（8个内存访问 vs 1*c）。 - Krupip

顺便提一句，warpcore 是一个框架，用于在 CUDA 加速器上创建高吞吐量的、专为哈希数据结构设计的算法。在现代 CUDA 加速器上以光速进行哈希操作。你可以在这里找到它：https://github.com/sleeepyjack/warpcore - Mojtaba Valizadeh

Answer 2

当我编写一个用于创建字符串简单哈希表的OpenCL内核时，我使用了Java的String.hashCode()中的哈希算法，然后将其模数运算到表中行的数量，以获取行索引。

哈希函数

uint getWordHash(__global char* str, uint len) {
  uint hash = 0, multiplier = 1;
  for(int i = len - 1; i >= 0; i--) {
    hash += str[i] * multiplier;
    int shifted = multiplier << 5;
    multiplier = shifted - multiplier;
  }
  return hash;
}

Indexing

uint hash = getWordHash(word, len);
uint row = hash % nRows;

当然，我手动处理冲突，并且在我预先知道字符串数量时，这种方法效果很好。

- Steve Blackwell