4

我有一个关于并行程序中的运行时测量的问题（我使用了 C++，但我认为这个问题更笼统）。

一些简短的解释：3个线程并行运行（pthread），以不同的方式解决相同的问题。每个线程可以将信息传递给另一个线程（例如，一个线程获得但另一个线程尚未获得的部分解决方案）以加速其他线程，这取决于他自己的状态/他自己计算中的可用信息。一旦第一个线程准备好，整个过程就会停止。现在我想要一个独特的时间测量来评估从开始到问题解决的运行时间。（最后，我想确定通过并行计算使用协同效应是否比单线程计算更快）。

在我看来，问题在于（由于操作系统暂停/取消暂停单个线程），在进程中传递信息的点在每个进程的状态中都不是确定性的。这意味着，在线程 1 上经过 xxx 单位的 cpu 时间后获得了某个信息，但无法控制线程 2 是在其计算所花费的 yyy 或 zzz 单位的 cpu 时间之后收到此信息。假设这个信息无论如何都会完成线程 2 的计算，线程 2 的运行时间是 yyy 或 zzz，这取决于操作系统的操作。

我可以做些什么来获得运行时比较的确定性行为？我可以命令操作系统“不受干扰”地运行每个线程（在多核机器上）吗？有什么我可以在实现（c++）的基础上做的吗？

或者是否有其他概念用于评估此类实现的运行时间（时间增益）？

最好的问候马丁

4

2 回答 2

1

任何时候有人在同一个句子中使用术语“确定性”和“多核”，它都会敲响警钟:-)

程序中的不确定性有两大来源：1）操作系统，它通过操作系统抖动和调度决策给线程计时增加了噪音；2) 算法，因为程序遵循不同的路径，具体取决于（部分解决方案的）通信发生的顺序。

作为一名程序员，您对操作系统噪音无能为力。即使对于在专用（静止）节点上运行的程序，标准操作系统也会增加很多噪音。用于计算节点的专用操作系统在一定程度上降低了这种噪声，例如Blue Gene 系统的操作系统噪声显着降低，因此时序变化也更小。

关于算法，您可以通过添加同步将确定性引入您的程序。如果两个线程同步，例如交换部分解决方案，那么同步之前和之后的计算顺序是确定性的。您当前的代码是异步的，因为一个线程“发送”部分解决方案但不等待它被“接收”。您可以通过将计算分成多个步骤并在每个步骤之后在线程之间同步来将其转换为确定性代码。例如，对于每个线程：

  1. 计算一步
  2. 记录部分解决方案（如果有）
  3. 屏障 - 等待所有其他线程
  4. 从其他线程读取部分解决方案
  5. 重复 1-4

当然，我们不希望这段代码也能执行得这么好，因为现在每个线程都必须等待所有其他线程完成它们的计算，然后才能继续下一步。

最好的方法可能是接受不确定性，并使用统计方法来比较您的时间安排。针对给定的线程数多次运行程序，并记录时间的范围、平均值和标准偏差。知道给定线程数的所有运行的最大计算时间可能就足够了，或者您可能需要统计测试（例如学生t测试）来回答更复杂的问题，例如“从4 到 8 个线程减少了运行时间？'。正如 DanielKO 所说，时间的波动是用户实际体验到的，因此测量这些波动并进行统计量化是有意义的，而不是旨在完全消除它们。

于 2014-02-24T17:29:33.677 回答
0

这样的测量有什么用？

假设您可以通过一些人为的方法，以线程不受干扰地运行的方式设置 OS 调度程序（即使是间接事件，例如使用缓存、MMU 等的其他进程），这对于并行的实际使用来说是现实的程序？

现代操作系统很少让应用程序控制一般中断处理、内存管理、线程调度等。除非你直接与金属对话，否则你的确定性测量不仅不切实际，而且你的程序的用户永远不会体验到它们（除非它们与您进行测量时一样接近金属。）

所以我的问题是，为什么你需要如此严格的条件来衡量你的程序？在一般情况下，只需接受波动，因为这是用户最有可能看到的。如果某个算法/实现的加速如此微不足道，以至于无法与背景噪声区分开来，那么这对我来说比知道实际的加速分数更有用。

于 2012-07-26T15:27:52.820 回答