组织基于任务的科学计算

Question

我有一个计算代数任务，我需要编码。问题被分解成明确的个体任务，自然形成一棵树--任务在本质上是组合的，所以有一个主要任务需要少量的子计算才能得到结果。那些子计算有子计算等等。每个计算只取决于树中它下面的计算(假设根节点是顶部的)。不需要在分支之间进行数据共享。在较低级别上，子任务的数量可能非常大。

我以前以函数的方式对此进行了编码，根据需要调用函数，并将所有内容存储在RAM中。这是一种糟糕的方法，但我当时更关心这个理论。

出于各种原因，我计划用C++重写代码。我有几个要求：

• Checkpointing:计算需要很长的时间，所以我需要能够在任何时候停止并将later.
• Separate的单个任务恢复为对象：--它帮助我很好地处理我在计算中的位置，并且提供了一种通过serialization.
• Multi-threading:进行检查点的干净方法--任务显然是令人尴尬的并行的，因此利用它是很好的。我可能想为此使用Boost线程。

我想就如何实际实施这一制度提出建议。我想过的方法是：

1. 将任务实现为一个简单的堆栈。当您遇到需要完成子计算的任务时，它会检查它是否拥有所需的所有子计算。如果没有，则创建子任务并将它们抛到堆栈上。
2. 将任务存储为一棵树，并执行类似于深度优先访问模式的操作。这将在开始时创建所有任务，然后计算将遍历树。

这些似乎不太正确，因为低级别的问题需要大量的子任务。我想，我可以在这个层次上以迭代器的方式来接近它。

我觉得我想得太多了，而且已经有了一种简单的，成熟的方法来做这样的事情。有一个吗？

技术细节如有关系：

任务树具有5 levels.

• Branching因子的树对于所有级别来说都是很小的(例如，2到5之间)，除了最低的级别(按照几个million.

• Each的顺序)，单个任务只需要存储几十个字节的结果。我不介意尽可能多地使用磁盘，只要它不停止performance.

• For调试，我就必须能够回忆/重新计算任何单个任务。

• 所有的计算都是离散的数学:带整数、多项式和组的计算。根本没有浮点。

Answer 1

有一个主要的任务，需要少量的子计算才能得到结果。那些子计算有子计算等等。每个计算只取决于树中它下面的计算(假设根节点是顶部的)。不需要在分支之间进行数据共享。在较低级别上，子任务的数量可能非常大.诸如此类的恢复、多线程等。

如果我错了，请纠正我，但在我看来，你完全是在描述一个地图缩减算法。

只需阅读维基百科对地图的评论-减少：

"Map“步骤:主节点接受输入，将其划分为较小的子问题，并将其分发给工作节点。工作节点可能会再次这样做，从而导致多层树结构。工作者节点处理这个较小的问题，并将答案传回其主节点。

“减少”步骤:主节点然后获取所有子问题的答案，并以某种方式组合它们以获得输出--它最初试图解决的问题的答案。

使用现有的mapreduce框架可以节省大量时间。

我只是谷歌“地图减少C++”，我开始得到结果，特别是在boost http://www.craighenderson.co.uk/mapreduce/中

Answer 2

--这些看起来不太正确，因为低级别需要大量的子任务。我想，我可以在这个层次上以迭代器的方式来接近它。

你肯定不想要数以百万计的CPU绑定线程。您最多需要N个CPU绑定线程，其中N是CPU数量和计算机上每个CPU的核数的乘积。超过N一点，你就会放慢一些速度。比N多了很多，你就把事情拖慢了很多。机器将花费几乎所有的时间来交换上下文内外的线程，花费很少的时间来执行线程本身。超过N的整数，你很可能会崩溃你的机器(或碰到一些限制的线程)。如果您想同时输出大量并行任务(以及大量并行任务)，您需要使用多台机器或使用您的显卡。