algorithm - 不平衡树上基于 GPU 的包容性扫描

Question

我有以下问题:我需要根据 GPU 上的树结构计算值的包含扫描(例如 prefix sums )。这些扫描要么来自根节点(自上而下)，要么来自叶节点(自下而上)。简单链的情况是easily handled , 但树结构使得并行化很难有效地实现。

例如，在自上而下的包容性扫描之后，(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 个分支，因此这将在一个 block 内运行并且工作将在线程之间拆分.不同的 block 将简单地处理不同的节点值。就占用率而言，这显然不是最佳选择，但这是对稍后将要解决的问题的限制。现在，我将依靠 Instruction-level parallelism .
• 图的结构不能改变(它描述了一个实际的系统)，因此它不能被平衡(或者只能通过改变树的根，例如使用 (6) 作为新的根)。尽管如此，一棵典型的树不应太不平衡。
• 我目前将 CUDA 用于 GPGPU，因此我愿意接受任何可以解决此问题的支持 CUDA 的模板库。
• 节点数据已经在全局内存中，结果将被其他 CUDA 内核使用，因此目标只是实现这一点而不使其成为巨大的瓶颈。
• 没有“循环”，即分支不能向下合并到树上。
• 树的结构是固定的，并在初始化阶段设置。
• 单个二元运算可能非常昂贵(例如多项式矩阵的乘法，即每个元素都是给定阶数的多项式)。

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

Answer 1

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