5

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

在前序遍历过程中，每个节点都可以独立处理，只要它与根之间的所有节点都已经被处理过。处理后，每个节点需要将一个元组（特别是两个浮点数）传递给它的每个子节点。在后序遍历中，每个节点都可以独立处理，只要它的所有子树（如果有的话）都已经被处理过。处理后，每个节点需要将一个浮点数传递给它的父节点。

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

每个节点的计算强度在树上是相同的。每个节点的计算是微不足道的：只需对长度等于节点上的子节点数的数字列表进行一些求和和乘/除。

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

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

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

4

3 回答 3

4

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

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

学习这种思维模式的好地方是用编程语言Haskell（或 F# 或 Ocaml）编写算法，它对并行/多核编程有很好的支持，开箱即用。Haskell 强制你的代码是纯的，所以如果你的算法有效，它可能很容易并行化。

于 2010-02-09T01:16:53.323 回答
3

通常的方法是使用某种深度优先的工作分割。您从多个等待空闲队列的工作人员开始，一个工作人员在根处开始遍历。有工作的工作人员首先遍历深度，并且每当它位于一个节点上还有多个子节点要完成时，它会检查空闲的工作队列，如果该队列不为空，则将子树（子树）移植给另一个工作人员。当工作人员完成子树时，处理连接有一些复杂性，但通常这对于各种树结构（平衡或不平衡）都可以很好地工作

于 2010-02-09T00:50:54.343 回答
2

这个答案描述了我将如何使用我日常工作的并行语言和运行时系统Charm++来做到这一点。请注意，此框架中用于顺序代码的语言是 C 或 C++，因此您必须在移植计算代码方面付出一些努力。Charm++ 确实有一些与 Python 代码互操作的机制，尽管我对这些方面不太熟悉。您可以将驱动程序和接口代码保留在 Python 中，而将繁重的计算代码放在 C++ 中。无论如何，对顺序代码的移植工作可能会为您带来良好的下一次性能提升。

设计：

创建一个并行对象数组（在我们的环境中称为chares），并为每个对象分配一个内部树节点的工作列表，该工作列表从某个子树根开始并部分向下延伸。任何附着在这些节点上的叶子也属于那个字符。

每个并行对象都需要两个异步远程可调用方法，称为入口方法passDown(float a, float b)和，passUp(int nodeID, float f)这将是它们之间的通信点。passDown将调用用于进行预排序计算的任何节点方法，并且具有对象外子级的节点将调用passDown这些后代对象。

一旦完成所有向下的工作，该对象将计算其叶子上的向上工作并等待其后代。的调用passUp将尽可能地计算到接收对象的树中，直到它遇到尚未从其所有子代接收数据的父代。当对象的根节点完成向上的工作时，它会调用passUp持有父节点的对象。当整个树的根完成时，您就知道迭代已经完成。

运行时结果：

一旦实现这一点，运行时系统就会为您处理并行执行。它将在处理器之间分配对象，甚至跨单独的计算节点（因此大大提高了树的大小上限，因为您的可用内存可以扩展得更高）。跨处理器和节点的通信看起来就像进程内通信——异步方法调用。运行时可以对对象进行负载平衡，以使所有处理器在每次迭代中尽可能多地保持忙碌。

调音：

如果您采用这种方式并达到调整并行性能的目的，您还可以设置消息的优先级以保持关键路径长度较短。在我的脑海中，我建议的优先级将按此顺序进行

  1. 非零的向下工作
    • 离根越近越快
  2. 向上工作
    • 越靠近叶子越快

Charm++ 与称为 Projections 的性能分析工具一起工作，以进一步了解您的程序的执行情况。

于 2010-02-09T17:34:40.827 回答