tree - 树状依赖图的 OpenCL 执行策略

Question

我正在尝试使用 OpenCL 来处理最好建模为倒置树结构的数据（根在底部，就像物理树一样），其中树中的每个节点都依赖于来自其上方子叶节点的处理数据. 不同分支上的节点可以并行执行，但同一分支（祖先）上的节点必须串行执行。处理是在规则的时间片上完成的，用于实时数据流。我的问题是关于如何使用 OpenCL、命令队列、工作组和工作项来最好地构建它。

数据实际上是几棵大小不一的树（子树），最后全部处理成最终结果，再复制回主机。每个节点“输出”一个固定大小的浮点数据缓冲区（可能来自子节点或全局缓冲区）。对于所有节点（例如 64 个元素），这些缓冲区的大小是全局相同的。

我首先想到将其结构化为每个工作项都是缓冲区中的单个数据值。然而，每个节点进程都由许多条件计算阶段组成，其中许多阶段因节点而异，并且一些过滤阶段可能需要来自其他索引的值。这似乎排除了完全数据并行模型。

因此，我认为每个子树都可以分配给一个工作组，其中各个节点是工作项。就缓冲区而言，这似乎是有道理的，因为每个子树中的节点将经常在彼此之间共享结果数据缓冲区（本地数据）。这样做的问题是每个子树可以有不同数量的节点（工作项），我认为 OpenCL 需要每个组有相同的工作项，如果不使用这些工作项是浪费的。依赖关系图也各不相同，这可能排除了将屏障用作有用的同步机制的可能性。可以使用事件列表和命令队列中的等待来处理依赖关系，但出于性能原因，我试图避免这种情况。所以这似乎也不是正确的解决方案。

我现在想到的最终解决方案是让每个子树成为每个组的单个工作项。我认为这更像是一种并行任务方法，但仍然可以利用循环中的 SIMD 操作和多个计算核心。

这个最终解决方案似乎是建模的最佳方法吗？或者有人对如何改进并行执行有更好的想法吗？

标签： treeopencl