cuda适合阵列过滤
我正在优化一个时间复杂度为O（N ^ 7）的程序。 我有一个字符串数组，表示为32位整数，其中每个位对应于输入字符串中的特定字符。 这项工作是查找输入字符串的所有组合，其中每个字符只出现一次，并显示所有字符。 天真的解决方案需要7层递归，每层迭代整个列表。 这很快就变得非常缓慢。
所以我想知道我是否可以使用cuda来加速这个过程，通过向GPU提供一系列可能的字符串，以及一个不应该匹配的位掩码，并获得一个过滤列表，以便加速递归步骤了一下。
所以问题是：这种滤波适合并行处理吗？
下面介绍我现在在C中做什么。
void recursive_search (unsigned int used, unsigned int *list, int listlen,
int start,unsigned int * stack, int reclevel) {
int index, newindex;
newindex = 0;
for (index=0; index< listlen; index++) {
if (!list[index] & used) {
newlist[newindex++] = list[index];
}
}
if ((newindex == 1 && (used | newlist[0])) == 0xffffffff) {
/* Hooray! We have a match */
stack[reclevel] = newlist[0];
report_match(stack);
return;
}
for (index = 0;index < newindex; index++) {
recursive_search (used | newlist[index], newlist, newindex,
index, stack, reclevel + 1);
}
}
我希望这能让我的问题更清楚。
以下代码段可能会转换为copy_if语句。
for (index=0; index< listlen; index++) {
if (!list[index] & used) {
newlist[newindex++] = list[index];
}
}
声明就像
thrust::copy_if(list.begin(), list.end(), newlist.begin(), predicate());
所以你会很容易地实现你的新列表。
你可以在GPU上生成可能的字符串数组？
关于递归：