cuda - 有没有在 cuda 上使用只读 HashMap 的好方法？

Question

我对编程和 Cuda 真的很陌生。基本上我有一个 C 函数，它读取数据列表，然后根据哈希图检查每个项目(我在 C 中使用 uthash 来实现)。它运行良好，但我想在 Cuda 中运行这个过程(一旦它获得哈希键的值，然后它会进行大量处理)，但我不确定创建只读哈希函数的最佳方法可能在 Cuda 中。
背景
基本上，我试图尽快对非常大的一批投资组合进行估值。我不断收到几百万个以两个列表形式出现的投资组合。一个有股票名称，另一个有权重。然后我使用股票名称查找哈希表以获取其他数据(值、百分比变化等)，然后根据权重对其进行处理。在普通 C 语言的 CPU 上大约需要 8 分钟，所以我很感兴趣在 GPU 上尝试它。
我已经阅读并完成了 cuda by example 中的示例所以我相信我知道除了哈希函数之外的大部分内容(附录中有一个，但它似乎专注于添加它，而我真的只想要它作为引用，因为它永远不会改变。我可能会很粗糙在 cuda for example 的边缘附近，所以在这种情况下，我可能缺少一些对我有帮助的东西，例如为此使用文本或某种特殊形式的内存)。如果每个块都有自己的哈希映射访问权限，或者每个线程是否应该对整个 GPU 足够好，我将如何构建以获得最佳结果？
编辑
抱歉只是澄清一下，我只使用 C。最坏的情况我愿意使用另一种语言，但理想情况下，我想要一些我可以在 GPU 上原生放置一次的东西，并让所有 future 的线程读取它以进行处理我的数据我需要分几批进行)。

Answer 1

这是对在 GPU 上使用散列图的潜在性能问题的一些想法，以支持我关于将散列图保留在 CPU 上的评论。

NVIDIA GPU 以 32 个线程为一组运行线程，称为扭曲。为了获得良好的性能，warp 中的每个线程都必须做本质上相同的事情。也就是说，它们必须运行相同的指令，并且必须从彼此靠近的内存位置读取。

我认为散列图可能会违反这两个规则，可能会大大降低 GPU 的速度，以至于将散列图保留在 GPU 上是没有用的。

考虑在 warp 中运行 32 个线程时会发生什么:

首先，每个线程必须创建股票名称的哈希值。如果这些名称的长度不同，这将涉及不同长度的散列循环中不同轮数，并且经线中的所有线程必须等待最长名称的散列完成。根据散列算法的不同，代码在散列算法中可以采用的路径可能不同。每当 warp 中的不同线程需要采用不同的路径时，相同的代码必须运行多次(每个代码路径一次)。这称为经线发散。

当 warp 中的所有线程都获得了一个哈希值时，每个线程都必须从慢速全局内存(由哈希值指定)中的不同位置读取。当扭曲中的 32 个线程中的每一个都以紧密、连贯的模式读取时，GPU 会以最佳方式运行。但是现在，每个线程都从内存中的一个基本上随机的位置读取。这可能会导致 GPU 必须序列化所有线程，从而可能将性能降低到潜力的 1/32。

线程读取的内存位置是哈希桶。每个可能包含不同数量的哈希，再次导致扭曲中的线程必须做不同的事情。然后他们可能不得不再次分支，每个分支到一个随机位置，以获得映射的实际结构。

如果您将股票名称和数据结构保存在 CPU 上的哈希映射中，则可以使用 CPU 将信息数组放在一起，这些信息以 GPU 擅长处理的确切模式存储。根据 CPU 的繁忙程度，您可以在 GPU 处理先前提交的工作时执行此操作。

这也让您有机会将 CPU 上的结构阵列 (AoS) 更改为 GPU 的阵列结构 (SoA)。如果你不熟悉这个概念，基本上，你转换:

my_struct {
  int a;
  int b;
};
my_struct my_array_of_structs[1000];

到:

struct my_struct {
  int a[1000];
  int b[1000];
} my_struct_of_arrays;

这把所有的 a在内存中彼此相邻，以便当warp 中的32 个线程到达读取 a 的指令时，所有值都整齐地排列在一起，从而使整个扭曲能够非常快速地加载值。 b也是如此的，当然。