tra*_*vis 5 algorithm parallel-processing tree design-patterns tree-traversal
我已经实现了迭代算法,其中每次迭代都涉及预订树遍历(有时称为向下累积),然后是后序树遍历(向上累积).对每个节点的每次访问涉及计算和存储要用于下次访问的信息(在随后的后序遍历或后续迭代中).
在预订序遍历期间,只要已经处理了它与根之间的所有节点,就可以独立地处理每个节点.处理完成后,每个节点都需要将元组(特别是两个浮点数)传递给每个子节点.在后序遍历中,只要已经处理了所有节点的子树(如果有的话),就可以独立处理每个节点.处理完成后,每个节点都需要将一个浮点数传递给它的父节点.
在算法期间,树的结构是静态的并且不变.但是,在向下遍历的过程中,如果传递的两个浮点数都变为零,则不需要处理该节点下的整个子树,并且可以开始该节点的向上遍历.(必须保留子树,因为后续迭代中传递的浮点数可能在此节点处变为非零并且将继续遍历).
每个节点的计算强度在整个树中是相同的.每个节点的计算是微不足道的:只需要几个总和并乘以/除以数字列表,其长度等于节点处的子节点数.
正在处理的树是不平衡的:典型节点将有2个叶子加上0-6个额外的子节点.因此,简单地将树划分为一组相对平衡的子树是不明显的(对我而言).此外,树设计为消耗所有可用的RAM:我可以处理的树越大越好.
我的串行实现仅在我的小测试树上达到每秒1000次迭代的顺序; 对于"真正的"树,我预计它可能会减慢一个数量级(或更多？).鉴于该算法需要至少1亿次迭代(可能高达10亿次)才能达到可接受的结果,我想并行化算法以利用多个核心.我对并行编程没有经验.
鉴于算法的性质,推荐的并行化模式是什么？
尝试将您的算法重写为由纯函数组成。这意味着每段代码本质上都是一个（小）静态函数，不依赖于全局变量或静态变量，并且所有数据都被视为不可变的——仅对副本进行更改——并且所有函数仅进行操作通过返回（新）数据来状态（在“操纵”一词的宽松意义上）。
如果每个函数都是引用透明的——它只依赖于它的输入（而不是隐藏状态）来计算它的输出，并且具有相同输入的每个函数调用总是产生相同的输出——那么你就处于有利的位置并行化算法：由于您的代码永远不会改变全局变量（或文件、服务器等），因此可以安全地重复函数所做的工作（重新计算函数的结果）或完全忽略（未来的代码不会依赖于该函数的副作用，因此完全跳过呼叫不会破坏任何东西）。然后，当您运行您的函数套件时（例如在MapReduce、hadoop等的某些实现上），函数链将仅基于一个函数的输出和另一个函数的输入而导致神奇的依赖级联，以及什么您尝试计算（通过纯函数）将与您尝试计算它的顺序完全分开（通过为 MapReduce 等框架实现调度程序来回答这个问题）。
学习这种思维模式的一个好地方是用编程语言Haskell（或 F# 或 Ocaml）编写算法，它对并行/多核编程有很好的支持，开箱即用。Haskell 强制你的代码是纯粹的，所以如果你的算法有效，它可能很容易并行化。