5

我对编程和 Cuda 真的很陌生。基本上我有一个 C 函数，它读取数据列表，然后根据哈希图检查每个项目（我在 C 中为此使用uthash）。它运行良好，但我想在 Cuda 中运行这个过程（一旦它获得哈希键的值，然后它会进行大量处理），但我不确定创建一个只读哈希函数的最佳方法可能在库达。

背景

基本上，我正在尝试尽快评估非常大量的投资组合。我不断得到数以百万计的投资组合，它们以两个列表的形式出现。一个有股票名称，另一个有重量。然后我使用股票名称查找哈希表以获取其他数据（价值、百分比变化等），然后根据权重进行处理。在纯 C 语言的 CPU 上大约需要 8 分钟，所以我对在 GPU 上尝试它很感兴趣。

我已经阅读并完成了其中的示例，cuda by example所以我相信我知道除了散列函数之外的大部分内容（附录中有一个，但它似乎专注于添加它，而我只希望它作为参考，因为它'永远不会改变。我可能在边缘处很粗糙，cuda for example所以在这种情况下，我可能缺少一些对我有帮助的东西，比如为此使用文本或某种特殊形式的记忆）。如果每个块都有自己对哈希图的访问权限，或者每个线程或者对于整个 GPU 来说足够好，我将如何构造它以获得最佳结果？

编辑

很抱歉澄清一下，我只使用 C。最坏的情况是我愿意使用另一种语言，但理想情况下，我想要一些东西，我可以在 GPU 上放置一次，然后让所有未来的线程读取它，因为要处理我的数据我需要分几批做）。

4

3 回答 3

9

这是关于在 GPU 上使用哈希映射的潜在性能问题的一些想法，以支持我关于将哈希映射保留在 CPU 上的评论。

NVIDIA GPU 以 32 个线程为一组运行线程，称为 warp。为了获得良好的性能，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，所有的值都整齐地排列在一起，使整个 warp 能够加载值非常快。b当然，对于 's也是如此。

于 2012-06-09T18:42:39.167 回答
2

在cuda-thrust-extensions库中有一个 CUDA Thrust 的 hash_map 扩展。我还没有尝试过。

于 2012-06-08T18:48:57.817 回答
0

因为你的hash map太大了，我觉得可以换成数据库，mysql或者其他产品都可以，估计比自己设计hash map快。并且我同意 Roger 的观点，它不适合移动到 GPU 上，它会消耗太大的设备内存（可能无法容纳它），并且内核函数访问设备上的全局内存非常慢。

此外，您的程序的哪一部分需要 8 分钟，在哈希图中查找或处理权重？如果是后者，可能是GPU可以加速。

最好的祝福！

于 2012-06-10T04:09:23.277 回答