0

我目前有一个可以包含 100 个用户定义公式的应用程序。目前，我使用反向波兰符号来执行计算（将值和变量推入堆栈，然后将它们从堆栈中弹出并进行评估）。开始并行化此过程的最佳方法是什么？我应该看功能语言吗？

计算是在数字数组上执行的，例如，简单的 A+B 实际上可能意味着 100 次加法。我目前正在使用 Delphi，但这不是未来的要求。我将使用最适合这项工作的工具。公式也可能相互依赖，例如，我们可能有一个公式 C=A+B 和第二个公式 D=C+A。

4

2 回答 2

1

在不了解更多信息的情况下，我建议尽可能采用 SIMD 风格的方法。也就是说，创建线程来计算单个数据集的所有公式。尝试划分公式的计算以并行化它们不会产生太大的速度改进，因为能够将计算拆分为适合线程的离散单元所需的逻辑将难以编写且更难正确，开销将取消出任何速度增益。它也将很快遭受收益递减的影响。

现在，如果您有一组适用于多组数据的公式，那么并行化会变得更容易并且可以更好地扩展。每个线程对一组数据进行所有计算。每个 CPU 核心创建一个线程，并设置其与每个核心的亲和性。每个线程实例化公式评估代码的一个实例。创建一个加载单个数据集并将其传递给空闲线程的主管。如果没有线程空闲，则等待第一个线程完成其数据处理。当所有数据集都处理完毕并且所有线程都完成后，然后退出。使用这种方法，线程数多于 CPU 上的内核数并没有任何优势，因为线程切换速度很慢，并且会对整体速度产生负面影响。

如果您只有一个数据集，那么这不是一项简单的任务。这将需要解析评估树的分支而不依赖于其他分支，并将这些分支耕种为在每个核心上运行的单独线程并等待结果。然后，您会遇到同步数据和确保数据一致性的问题。

于 2009-02-11T09:54:36.640 回答
1

假设您的公式（方程式）不是循环的，否则您不能“​​仅仅”评估它们。如果您有像 A = B + C 这样的矢量化方程，其中 A、B 和 C 是数组，让我们在概念上将它们拆分为组件上的方程，这样如果数组大小为 5，则该等式被拆分为

a1 = b1 + c1
a2 = b2 + c2
...
a5 = b5 + c5

现在假设这一点，您有大量关于简单量（无论是整数、有理数还是其他）的方程。

如果您有两个方程 E 和 F，假设 F 的右侧提到 E 的左侧，则 F 依赖于 E，例如

E: a = b + c
F: q = 2*a + y

现在要了解如何计算这个，你总是可以使用随机迭代来解决这个问题（这只是解释中的一个中间步骤），遵循这个算法：

1 while (there is at least one equation which has not been computed yet)
2   select one such pending equation E so that:
3     for every equation D such that E depends_on D:
4       D has been already computed
5   calculate the left-hand side of E

无论您如何在线上进行选择，此过程都会以正确的答案结束 // 2。现在很酷的是，它也很容易并行化。您可以在任意数量的线程中运行它！您需要的是一个并发安全队列，它包含那些先决条件（那些方程所依赖的）已被计算但尚未自行计算的方程。每个线程一次（线程安全地）从这个队列中弹出一个方程，计算答案，然后检查现在是否有新的方程，以便计算出它们的所有先决条件，然后添加这些方程（线程安全）到工作队列。完毕。

于 2009-02-13T16:50:13.160 回答