c++ - 测量相互依赖线程的并行计算时间

Question

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

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

在我看来，问题在于(由于操作系统暂停/取消暂停单线程)，在进程中传递信息的时间点在每个进程的状态下都不确定。也就是说，线程1在xxx个cpu时间后获取到某条信息，但无法控制线程2在其计算中花费了yyy或zzz个cpu时间后是否接收到该信息。假设此信息在任何情况下都会完成线程 2 的计算，线程 2 的运行时间是 yyy 或 zzz，具体取决于操作系统的操作。

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

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

最好的问候马丁

Answer 1

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

程序中存在两大不确定性来源:1) 操作系统，它通过操作系统抖动和调度决策为线程计时增加噪音； 2) 算法，因为程序根据(部分解决方案的)通信发生的顺序遵循不同的路径。

作为一名程序员，您对操作系统噪音无能为力。即使对于在专用(静态)节点上运行的程序，标准操作系统也会增加很多噪音。用于计算节点的专用操作系统在某种程度上减少了这种噪音，例如 Blue Gene systems exhibit significantly less OS noise and therefore less variation in timings .

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

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

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

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