9

我有以下问题：我需要基于 GPU 上的树结构计算值的包容性扫描（例如前缀和）。这些扫描要么来自根节点（自上而下），要么来自叶节点（自下而上）。简单链的情况很容易处理，但是树结构使得并行化很难有效地实现。

树示例

例如，在自上而下的包容性扫描之后，(12)将保持(0)[op](6)[op](7)[op](8)[op](11)[op](12)，对于自下而上的包容性扫描，(8)将保持(8)[op](9)[op](10)[op](11)[op](12)，其中[op]是给定的二元运算符（矩阵加法、乘法等）。

还需要考虑以下几点：

  • 对于一个典型的场景，不同分支的长度不应该太长（~10），大约有 5 到 10 个分支，所以这将在一个块内运行并且工作将在线程之间拆分。不同的块将简单地处理不同的节点值。这对于占用率显然不是最优的，但这是对稍后将要解决的问题的限制。现在，我将依赖指令级并行性。
  • 图的结构不能改变（它描述了一个实际的系统），因此不能平衡（或者只能通过改变树的根，例如(6)用作新根）。尽管如此，典型的树不应该太不平衡。
  • 我目前将 CUDA 用于 GPGPU，因此我对任何可以解决此问题的支持 CUDA 的模板库持开放态度。
  • 节点数据已经在全局内存中，结果将被其他 CUDA 内核使用，因此目标只是实现这一点，而不使其成为巨大的瓶颈。
  • 没有“循环”，即分支不能沿树合并。
  • 树的结构是固定的，并在初始化阶段设置。
  • 单个二元运算可能非常昂贵（例如多项式矩阵的乘法，即每个元素都是给定阶数的多项式）。

在这种情况下，解决这个问题的“最佳”数据结构（对于树结构）和最佳算法（对于包容性扫描/前缀和）是什么？

4

4 回答 4

3

我认为并行前缀扫描可能不适合您的情况，因为：

并行前缀扫描算法会增加总数[op]，在您的前缀和链接中，16 输入并行前缀扫描需要 26 [op]，而顺序版本只需要 15。并行算法性能更好是基于有足够硬件资源的假设并行运行多个[op]。

您可以[op]在尝试并行前缀扫描之前评估您的成本。

另一方面，由于树的大小很小，我认为您可以简单地将您的树视为 4（叶节点的数量）独立的简单链，并使用并发内核执行来提高这 4 个前缀扫描内核的性能

0-1-2-3
0-4-5
0-6-7-8-9-10
0-6-7-8-11-12
于 2013-10-03T16:28:41.860 回答
3

可能是一个轻率的想法，但想象一下您将 0 值的节点插入到树中，这样您就可以得到一个 2D 矩阵。例如，在您的示例中， 5节点下方将有 3 个零值节点。然后使用一个线程水平移动矩阵的每一层。对于自上而下的前缀和，以这样一种方式偏移线程，即每个较低的线程都延迟了树在该位置可以拥有的最大分支数。所以，你会得到一个带有倾斜边缘的“波浪”在矩阵上运行。更远的上层线程及时计算这些节点，以便它们被运行得更远的线程进一步处理。您需要与树深相同数量的线程。

于 2013-10-03T14:48:41.670 回答
0

我认为在 Kepler GK110 架构中，您可以递归调用内核，他们称之为动态并行。因此，如果您需要计算树的每个节点的值的总和，动态并行会有所帮助。但是，递归的深度可能是一个约束。

于 2013-10-04T19:18:59.913 回答
0

我的第一印象是您可以将树节点组织在一维数组中，类似于 Eric 的建议。然后您可以对该数组进行分段前缀和扫描（http://en.wikipedia.org/wiki/Segmented_scan ）。

以您的树节点为例，1-dim 数组如下所示：

0-1-2-3-0-4-5-0-6-7-8-9-10-0-6-7-8-11-12

然后你会有一个并行的标志数组，指示新列表的开始位置（列表我的意思是从根开始到叶节点结束的序列）：

1-0-0-0-1-0-0-1-0-0-0-0- 0-1-0-0-0- 0- 0

对于自下而上的情况，您可以像这样创建一个单独的段标志数组：

0-0-0-1-0-0-1-0-0-0-0-0- 1-0-0-0-0- 0- 1

并使用相同的算法以相反的顺序遍历它。

至于如何实现分段前缀扫描，我自己还没有实现，但我发现了一些参考资料，这些参考资料可能会提供有关如何做到这一点的信息： http ://www.cs.cmu.edu/afs/cs/ Academic/class/15418-s12/www/lectures/24_algorithms.pdf 和http://www.cs.ucdavis.edu/research/tech-reports/2011/CSE-2011-4.pdf（见第 23 页）

于 2013-10-04T20:57:36.377 回答