代码之家 › 专栏 › 技术社区 › Steve

计算公式结果的最佳方法?

rpn formula parallel-processing

0

Steve · 技术社区 · 17 年前

我目前有一个应用程序,可以包含100个用户定义的公式。目前,我使用反向波兰符号来执行计算(将值和变量推到堆栈上,然后将它们从堆栈中弹出并计算)。开始并行化这个过程的最佳方式是什么?我应该看看函数式语言吗?

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

2 回复 | 直到 17 年前

1

Antti Huima 17 年前

让我们假设你的公式(方程式)不是循环的,否则你不能“仅仅”计算它们。如果你有像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

1

C8H10N4O2 8 年前

在不了解更多信息的情况下,我建议尽可能采用SIMD风格的方法。也就是说,创建线程来计算单个数据集的所有公式。尝试将公式的计算划分为并行计算不会带来太多的速度提升,因为将计算划分为适合线程的离散单元所需的逻辑很难编写,也很难获得正确的结果,开销会抵消任何速度增益。它还将很快受到回报递减的影响。

现在,如果您有一组应用于多组数据的公式,那么并行化将变得更容易,并且可以更好地扩展。每个线程对一组数据执行所有计算。为每个CPU核心创建一个线程,并设置其与每个核心的关联。每个线程实例化公式求值代码的一个实例。创建一个加载单个数据集并将其传递给空闲线程的监控器。如果没有空闲线程,请等待第一个线程完成其数据处理。处理完所有数据集且所有线程都完成后,退出。使用这种方法,拥有比CPU上的内核更多的线程没有任何好处,因为线程切换速度慢,并且会对总体速度产生负面影响。

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