如何并行实现树遍历算法的策略？

Question

我已经实现了一种迭代算法，其中每次迭代涉及一个先序树遍历（有时称为向下累积）和一个后序树遍历（向上累积）。每次访问每个节点都涉及计算和存储信息以供下一次访问使用（无论是在随后的后序遍历还是在随后的迭代中）。

在先序遍历期间，只要它和根之间的所有节点都已处理，就可以独立地处理每个节点。处理后，每个节点需要将一个元组（具体而言是两个浮点数）传递给其每个子节点。在后序遍历中，只要其所有子树（如果有）已经被处理，就可以独立地处理每个节点。处理后，每个节点需要将一个单一的浮点数传递给其父节点。

树的结构在算法期间是静态且不变的。但是，在向下遍历过程中，如果传递的两个浮点数都变为零，则此节点下面的整个子树无需进行处理，并且此节点的向上遍历可以开始。（必须保留子树，因为在此节点上的后续迭代中，传递的浮点数可能会变为非零值，并且遍历将恢复）。

每个节点的计算强度在整个树中是相同的。每个节点上的计算都很简单：只需要对一个与节点子数相等的数字列表执行几个求和和乘除运算。

被处理的树是不平衡的：一个典型节点会有2个叶子加上0-6个额外的子节点。因此，将树分成一组相对平衡的子树并不明显（至少对我来说）。此外，这些树旨在消耗所有可用的RAM：我可以处理的更大的树越多，就越好。

我的串行实现在我的小测试树上达到每秒约1000次迭代；对于“真正”的树，我预计它可能会减慢一个数量级（或更多？）。鉴于该算法需要至少1亿次迭代（可能高达10亿）才能达到可接受的结果，我希望并行化算法以利用多个核心。我没有任何并行编程经验。

考虑到我的算法性质，推荐什么样的并行化模式？

- travis

---

第一步是分析您的算法，确定哪些部分是独立的。这可能需要您以比现在更低的级别考虑您的算法。 - Nate W.

树的节点之间是否存在共享数据，还是它们在逻辑上是可分离的？我可以提供一些不错的建议，但更多的细节会让它变得更容易。 - Phil Miller

另外，随着计算的进行，树的结构是否会发生变化，还是保持不变？每个节点所需的工作量是否相同，还是以可预测的方式变化？ - Phil Miller

在开始并行化工作之前，我建议您对顺序代码进行剖析，并查看是否存在任何突出的热点没有明显的瓶颈。在添加必要的并行执行垃圾之前进行这项工作要容易得多。 - Phil Miller

答案现在已发布。在尝试并行化之前，我仍然建议将其移植到具有优化实现的顺序语言中。付出的努力与回报的比例要好得多。 - Phil Miller

Answer 1

尝试重写你的算法，使其由纯函数组成。这意味着每个代码片段本质上都是一个（小型）静态函数，不依赖于全局变量或静态变量，并且所有数据都被视为不可变的——更改只会对副本进行——所有函数仅通过返回（新的）数据来操作状态（在“操作”一词的宽泛意义下）。

如果每个函数都是引用透明的——它仅依赖于其输入（没有隐藏状态）来计算其输出，并且每次具有相同输入的函数调用总是产生相同的输出——那么您就处于一个很好的位置来并行化算法：由于您的代码从不改变全局变量（或文件、服务器等），函数执行的工作可以安全地重复执行（重新计算函数的结果）或完全忽略（因为未来的代码不依赖于此函数的副作用，因此完全跳过调用不会破坏任何东西）。然后，当您运行一组函数时（例如在某些MapReduce、hadoop等实现上），函数链将基于一个函数的输出和另一个函数的输入，以及您尝试通过纯函数计算的内容完全与您尝试计算它的顺序分离（这是由类似MapReduce框架的调度程序实现回答的问题）。

一个学习这种思维方式的好地方是使用编程语言Haskell（或者F#或Ocaml之类）来编写你的算法，这些语言具有出色的并行/多核编程支持。Haskell强制要求你的代码是纯函数式的，因此如果你的算法可行，它很可能很容易被并行化。

- Jared Updike

---

这里有一些有趣的想法。Haskell看起来很有吸引力。如果我花时间学习它来移植算法，那么我是否还需要学习MapReduce/hadoop，或者它们是不相关的方法？ - travis

在Haskell中重新编码与在MapReduce/Hadoop环境中重新编码是不同的。选择取决于您尝试处理的树的规模。 - Phil Miller

Haskell 学起来有点令人费解（但是这是好事）。O'Reilly 最近出版了一本最佳书籍，可以免费在线获取：http://book.realworldhaskell.org/read/。第 24 章详细介绍了并行编程的方法，使用 MapReduce 提供了具体示例：http://book.realworldhaskell.org/read/concurrent-and-multicore-programming.html。 - Jared Updike

Answer 2

通常的方法是使用某种深度优先的任务分割方式。首先，您会有一些等待空闲队列的工作人员，以及一个从根开始遍历的工作人员。执行任务的工作人员按照深度优先的顺序进行遍历，每当到达具有多个子节点需要处理的节点时，它就会检查空闲工作人员队列，如果该队列不为空，则会将子树（子节点）分配给另一个工作人员进行处理。在处理完子树后，出现了一些复杂的合并处理，但总体而言，这种方法可以很好地应用于各种树形结构（平衡或不平衡）。

- Chris Dodd

---

通常的方法要求每个寻求并行加速的程序员直接使用目录中最难使用的两个结构之一——线程和共享数据结构。这还需要在程序员想要将并行性扩展到单个共享内存机器以外时跨越过多的障碍。 - Phil Miller

Answer 3

这个回答描述了我在日常工作中使用的并行语言和运行时系统Charm++如何实现。请注意，在该框架内用于顺序代码的语言是C或C ++，因此您需要花费一些精力来移植计算代码。 Charm++确实具有与Python代码进行交互的机制，但我对这些方面不太熟悉。可能您可以将驱动程序和接口代码保留在Python中，只将重型计算代码放入C ++中。无论如何，在顺序代码的移植工作上，您都很可能会获得更好的性能。

设计：

创建一个并行对象数组（在我们的环境中称为chares），并为每个对象分配一个起始于某个子树根部并向下延伸一部分的内部树节点工作列表。任何连接到这些节点的叶子也将属于该chare。

每个并行对象都需要两个异步远程可调用方法，称为“entry methods”，即passDown(float a, float b)和passUp(int nodeID, float f)，它们将成为这些对象之间通信的点。 passDown将调用用于执行前序计算的任何节点方法，并且具有超出对象子代的节点将在这些后代对象上调用passDown。

一旦所有向下的工作完成，对象将在其叶子上计算向上的工作并等待其后代。对passUp的调用将尽可能地计算到接收对象树的顶部，直到它遇到一个尚未从其所有子项接收数据的父项。当整个树的根节点完成向上的工作时，它将在持有父节点的对象上调用passUp。当整个树的根节点完成工作时，您就知道迭代已经完成。 运行结果： 一旦实现了这个功能，运行时系统会为你处理并行执行。它将在处理器之间分配对象，甚至跨越不同的计算节点（因此显著提高了你的树大小上限，因为可用内存可以扩展得更高）。处理器和节点之间的通信看起来就像进程内通信-异步方法调用。运行时可以负载平衡对象，使每个迭代尽可能让所有处理器保持繁忙状态。

调优：

如果您选择这种方式并开始调优并行性能，还可以设置消息的优先级，以保持关键路径长度短。我建议按以下顺序完成工作的优先级：

1. 非零的下行工作 - 更靠近根部的先进行 2. 上行工作 - 更靠近叶子的先进行

Charm++使用称为Projections的性能分析工具进一步了解程序的执行情况。

- Phil Miller