cuda - 使用 CUDA 计算所有可能的单词组合？

Question

我想找到可以由给定的 11 个单词组成的所有可能单词的组合。有可能在CUDA上做到这一点吗？如果是，那么如何。谢谢！

Answer 1

是的，你可以在 CUDA 中进行排列，事实上，sr。Wong Shao Voon使用 CUDA 和 OpenCL实现了Permutations 算法。

他没有按照你的意愿使用字符串，但这不是一个主要问题，你只需要在算法完成后将他使用的符号（字母）转换为你的（单词）的方法。想象他将所有排列保存在一个二维字符数组中，您遍历所有矩阵，而不是打印实际的字符，而是打印您想要的单词（例如if(matrix[i][j] == 'A') printf("Anaconda");）。

基准

“我已经针对 CPU 应用程序对 CUDA 进行了基准测试。基准测试中使用的 CPU 和 GPU 分别是 Intel i7 870（8 核）、2.93Ghz 和 NVidia Geforce 460。CPU 应用程序充分利用 8 核来寻找排列. CPU 应用程序使用阶乘分解将第 n 个排列拆分到不同的 CPU 内核中，在每个工作线程中，使用 STL next_permutation 从第一个第 n 个排列中找到每个连续排列。下面列出了 11 个元素的排列计算结果。找到的 11 个元素的排列总数为 39,916,800。需要存储结果的数组大小为 39,916,800 x 11 = 439,084,800。这是我的 1GB 内存 GPU 可以存储的最大排列数。”

折叠 | 语言：cpu：550ms

版本 1 纯因子分解（平均时间） CUDA：550ms OpenCL：581ms

版本 2，每个阶乘分解有 1 个 next_permutation（平均时间） CUDA：317 毫秒 OpenCL：373 毫秒

版本 3，每个阶乘分解有 9 个 next_permutation（平均时间） CUDA：681 毫秒 OpenCL：456 毫秒

Answer 2

看看https://github.com/kkilictepe/CudaCombination 它是带有 numba 的 python 实现，但有帮助。