design-patterns - 并行实现树遍历算法的策略？

Question

我实现了一个迭代算法，其中每次迭代都涉及先序树遍历(有时称为向下累积)，然后是后序树遍历(向上累积)。每次访问每个节点都涉及计算和存储信息以用于下一次访问(在后续的后序遍历或后续迭代中)。

在前序遍历过程中，每个节点都可以独立处理，只要它与根之间的所有节点都已经被处理过。处理后，每个节点需要向其每个子节点传递一个元组(具体来说，两个 float )。在后序遍历中，每个节点都可以独立处理，只要它的所有子树(如果有的话)都已经被处理过。处理后，每个节点需要向其父节点传递一个 float 。

树的结构在算法过程中是静态的和不变的。但是，在向下遍历的过程中，如果传递的两个float都变为0，则该节点下的整颗子树都不需要处理，可以开始对该节点的向上遍历。 (必须保留子树，因为在后续迭代中传递的 float 可能在此节点变为非零，并且遍历将恢复)。

树中每个节点的计算强度是相同的。每个节点的计算都很简单:只需对长度等于该节点的子节点数的数字列表进行一些加法和乘法/除法运算。

正在处理的树是不平衡的:一个典型的节点将有 2 个叶子加上 0-6 个额外的子节点。因此，简单地将树划分为一组相对平衡的子树并不明显(对我而言)。此外，树的设计目的是消耗所有可用的 RAM:我可以处理的树越大越好。

我的串行实现仅在我的小测试树上就达到了每秒 1000 次迭代；对于“真正的”树，我预计它可能会减慢一个数量级(或更多？)。鉴于该算法需要至少 1 亿次迭代(可能高达 10 亿次)才能达到可接受的结果，我想对该算法进行并行化以利用多核。我对并行编程的经验为零。

鉴于我的算法的性质，推荐的并行化模式是什么？

Answer 1

尝试重写你的算法，使其由 pure functions 组成.这意味着每一段代码本质上都是一个(小的)静态函数，不依赖于全局变量或静态变量，并且所有数据都被视为不可变的---更改仅对副本进行---并且所有函数仅操作通过返回(新)数据来状态(广义上的“操纵”一词)。

如果每个函数都是referentially transparent ---它只依赖于它的输入(而不是隐藏状态)来计算它的输出，并且每个具有相同输入的函数调用总是产生相同的输出---那么你就可以很好地并行化算法:因为你的代码永远不会改变全局变量(或文件、服务器等)函数所做的工作可以安全地重复(重新计算函数的结果)或完全忽略( future 的代码不依赖于这个函数的副作用，所以完全跳过调用是赢的'破坏任何东西)。然后，当您运行您的函数套件时(例如，在 MapReduce、hadoop 等的某些实现上)，函数链将仅基于一个函数的输出和另一个函数的输入，导致神奇的依赖级联函数，以及您尝试计算的内容(通过纯函数)将与您尝试计算它的 ORDER 完全分开(一个问题由 MapReduce 等框架的调度程序的实现来回答)。

学习这种思维模式的一个好地方是用编程语言编写算法 Haskell (或 F# 或 Ocaml 的东西)它对并行/多核编程有很好的支持，开箱即用。 Haskell 强制您的代码是纯净的，因此如果您的算法有效，它可能很容易并行化。