1

我正在优化时间复杂度为 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);
  }
}

我希望这能让我的问题更清楚。

4

1 回答 1

1
  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 上生成可能的字符串数组吗？

关于递归：

  • 因为您将在 GPU 中激活许多线程，所以可能有多个结果/匹配。返回第一个匹配项或所有匹配项可能是个问题。
  • 如果递归是必须的，您可以通过每次将部分进度存储在全局内存中来多次调用内核。
  • 正如@harrism 所指出的，您可以将递归部分转换为更简单的流程，并让并行处理每种情况。
于 2012-10-08T12:37:02.013 回答