计算公式结果的最佳方法是什么？

Question

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

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

Answer 1

让我们假设你的公式（方程）不是循环的，否则你不能“仅仅”评估它们。如果已矢量方程式如A = B + C，其中A，B和C是数组，让我们概念性他们分成方程上的组件，因此，如果该数组的大小是5，这个等式被分成

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

现在假设这一点，你有一个关于简单量（无论是整数，理性还是别的）的大量方程组。

如果你有两个方程E和F，比方说那个F depends_on 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.现在很酷的是th在它也容易并行化。你可以在任意数量的线程中运行它！你所需要的是一个并发安全队列，它保存那些已经计算出其先决条件（那些方程依赖于）的方程，但它们还没有被计算出来。每个线程一次从这个队列中弹出一个方程（线程安全），计算答案，然后检查是否有新的方程，以便它们的所有先决条件已经计算出来，然后将这些方程（线程安全）到工作队列。完成。

Answer 2

不知道更多，如果可能的话，我会建议采取SIMD风格的方法。也就是说，创建线程来计算单个数据集的所有公式。试图将公式的计算划分为并行化并不会产生太多的速度改进，因为要求能够将计算分割成适合线程化的离散单元的逻辑将难以编写并且难以正确地进行，开销将取消取得任何速度收益。它也会因收益递减而迅速受损。

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

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