并行效率

计算科学 并行计算 表现 效率
2021-12-13 00:27:45

我想使用计算次数而不是时间计算来计算并行算法的效率。

在我研究的材料中,我有一个如下公式: 其中

η(n,p)=ω(n)ω(n)+h(n,p)=11+h(n,p)/ω(n),

  • η(n,p) - 在具有 p 个 CPU 的机器上实现 n 大小任务的并行程序的效率
  • ω(n) - n 大小任务的计算次数
  • h(n,p) - n 大小并行任务的 I/O 操作数

我有一个应用程序在两种模式下实现了 200 万次相同的操作:

  • 4 个线程,4 个 CPU。(所有线程之间的操作划分)
  • 具有 4 个 CPU 的串行计算。

这个公式看起来很简单,但我不知道如何应用它。我想问一下在现实世界的例子中提到的公式的解释。

1个回答

这个公式似乎假设一个由计数的一个 I/O 操作一样长因此,要应用它,您必须能够计算代码中的操作并将它们缩放到相同的时间尺度。将分子和分母除以的进一步详细说明可能有效地扩展了这一点,但您仍然必须能够计算操作。根据您的 CPU/协处理器,计数操作可能更容易或更难。ω(n)h(n,p)ω

您还需要能够为自己定义 I/O 操作所指的操作类型。即,这是否意味着写入磁盘或它是否包括对 RAM、网络等的操作。我假设这个公式是通过替换转化为阿姆达尔定律并用t(n,p)=tcompute(n,p)+tI/O(n,p)+tcompute(n,p)=ω(n,p)/ω˙(n,p)+等等。我还认为这是解释的一部分,试图解释出现在阿姆达尔定律中的部分时间来自哪里。为了使用这样的公式,您必须对您的计算机和代码有很多了解。您必须能够计算代码中许多不同类型的操作,并且您必须知道您的计算机实际执行这些操作的速率。

我认为这比仅测量每个的执行时间要困难得多,而且不值得探讨。np