使用CUDA计算所有可能的单词组合吗? [英] Use CUDA to compute all possible combinations of words?

问题描述

我想找到可以由11个单词的给定图块集形成的所有可能单词的组合.有可能在CUDA上做到这一点吗?如果是，那怎么办.谢谢！

I want to find combination of all possible words that could be formed from a given tile set of 11 words. Is it possible to do that on CUDA? If yes than how. Thanks!

推荐答案

是的，实际上，您可以在CUDA中进行置换. Wong Shao Voon实现了使用CUDA的置换算法和OpenCL .

Yes, you can do permutations in CUDA, in fact, sr. Wong Shao Voon has an implementation of a Permutations algorithm with CUDA and OpenCL.

他没有按照您的意愿使用String，但这不是主要问题，您只需要制作一种方法即可在算法完成后将他使用的(字母)符号转换为您的(单词)符号.想象一下，他将所有排列保存在2D字符数组中，您对所有矩阵进行了遍历，而不是打印实际的char，而是打印了所需的单词(例如if(matrix[i][j] == 'A') printf("Anaconda");).

He did not use String as you want, but this is not a major problem you just have to make a method that converts the symbols that he used (letters) to yours (words) after the algorithm is finished. Imagining that he saved all the permutations in a 2D array of characters, you perambulate all the matrix and instead of printing the actual char you print the word that you want (e.g. if(matrix[i][j] == 'A') printf("Anaconda");).

基准

我已经针对CPU应用程序对CUDA进行了基准测试.基准测试中使用的CPU和GPU分别是Intel i7 870(8核)，2.93Ghz和NVidia Geforce460.CPU应用程序充分利用了8核CPU应用程序使用阶乘分解在不同CPU内核之间划分第n个排列，并且在每个工作线程中，使用STL next_permutation从第n个排列中查找每个连续的排列，计算11个元素的排列的结果为找到的11个元素的排列总数为39,916,800 .需要存储结果的数组大小为39,916,800 x 11 = 439,084,800.这是我的1GB内存的最大排列数GPU可以存储."

"I have benchmarked the CUDA against the CPU application. The CPU and GPU used in the benchmark, are Intel i7 870 (8 cores), 2.93Ghz and NVidia Geforce 460 respectively. The CPU application make full use of the 8 cores to find permutations. The CPU application is using factorial decomposition to split the nth permutations among different CPU cores and in each worker threads, STL next_permutation is used to find every consecutive permutation from the first nth permutation. The results of computing permutations of 11 elements is listed below. The total number of permutations of 11 elements found is 39,916,800. The size of the array need to store the results is 39,916,800 x 11 = 439,084,800. This is the maximum number of permutations which my 1GB memory GPU can store."

折叠|复制代码 CPU:550ms

Collapse | Copy Code CPU : 550ms

具有纯阶乘分解的版本1(平均时间) CUDA:550ms OpenCL:581ms

Version 1 with pure factorial decomposition (Average timing) CUDA : 550ms OpenCL : 581ms

版本2，每个阶乘分解具有1个next_permutation(平均时序) CUDA:317ms OpenCL:373ms

Version 2 with 1 next_permutation per factorial decomposition (Average timing) CUDA : 317ms OpenCL : 373ms

版本3，每个因子分解具有9个next_permutation(平均时序) CUDA:681ms OpenCL:456ms

Version 3 with 9 next_permutation per factorial decomposition (Average timing) CUDA : 681ms OpenCL : 456ms

这篇关于使用CUDA计算所有可能的单词组合吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！