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

Question

我有以下问题:我需要根据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内核使用,因此目标只是实现这一目标而不会成为一个巨大的瓶颈.
• 没有"循环",即分支不能合并树.
• 树的结构是固定的并且在初始化阶段设置.
• 单个二进制运算可能非常昂贵(例如,多项式矩阵的乘法,即每个元素是给定顺序的多项式).

在这种情况下,什么是"最佳"数据结构(对于树结构)和最佳算法(对于包容性扫描/前缀总和)来解决这个问题？

Answer 1

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