如何在多任务环境中测量多线程处理时间？

Question

由于我在(抢占式)多任务,多核环境中运行多线程程序的性能评估测试,因此可以定期更换该进程.我想计算延迟,即只计算进程处于活动状态的持续时间.这将允许我推断性能在非多任务环境中的表现,即,只有一个程序运行(大多数时间),或者在不同的工作负载上.

通常测量两种时间:

• 挂钟时间(即从流程开始以来的时间),但这包括交换流程的时间.
• 处理器时间(即所有线程使用的CPU时间总和),但这对计算进程的延迟没有用.

我相信我需要的是单个线程的完成时间,这可能与任何线程使用的最大CPU时间不同,这是由于线程之间的任务依赖性结构.例如,在具有2个线程的进程中,线程1在运行时的前三分之二(CPU时间t)中负载很重,而线程2在该进程的后三分之二中加载(同样,对于CPU时间t).在这种情况下:

• 挂钟时间将返回3t/2 +上下文切换时间+其他进程在其间使用的时间,
• 所有线程的最大CPU时间将返回接近t的值,并且
• 总CPU时间接近2t.
• 我希望收到的测量结果是完工时间,即3t/2.

此外,多线程本身带来了不确定性.这个问题可能需要多次运行测试并总结结果.

此外,延迟还取决于操作系统如何调度线程; 如果进程的某些线程等待CPU而其他线程运行,则事情会变得更复杂.但是让我们忘记这一点.

有没有一种有效的方法来计算/估计这个完工时间？要提供代码示例,请使用任何编程语言,但最好使用Linux上的C或C++.

PS:我理解这个makepan的定义与调度问题的定义不同.调度问题中使用的定义类似于挂钟时间.

Answer 1

问题的重新表述

我编写了一个多线程应用程序，在我的 K 核机器上执行需要 X 秒。

如何估计程序在单核计算机上运行需要多长时间？

经验上

显而易见的解决方案是购买一台具有单核的计算机，运行您的应用程序，并根据需要使用挂钟时间和/或 CPU 时间。

...哦，等等，你的计算机已经有一个核心（它还有其他一些核心，但我们不需要使用它们）。

如何做到这一点取决于操作系统，但我从 Google 找到的第一个结果解释了 Windows XP 和 Vista 的几种方法。

http://masolution.blogspot.com/2008/01/how-to-use-only-one-core-of-multi-core.html

之后您可以：

• 将应用程序的进程分配给单个核心的亲和力。（您也可以在代码中执行此操作）。
• 启动您的操作系统时只需要了解其中一个核心。（然后再切换回来）

独立并行性

通过分析来估计这一点需要了解您的程序、并行方法等。

举一个简单的例子，假设我编写了一个多线程程序，计算 pi 的十亿分之一位和 e 的十亿分之一位。

我的代码如下所示：

public static int main()
{
    Task t1 = new Task( calculatePiDigit );
    Task t2 = new Task( calculateEDigit );
    t1.Start();
    t2.Start();
    Task.waitall( t1, t2 );
}

发生之前图如下所示：

显然这些是独立的。

在这种情况下

• 时间calculatePiDigit() 本身。
• 时间由calculateEDigit() 本身完成。
• 将时间加在一起。

二级管道

当任务不是独立的时，您将无法将各个时间加在一起。

在下一个示例中，我创建一个多线程应用程序来：拍摄 10 个图像，将它们转换为灰度，然后运行线条检测算法。由于某些外部原因，不允许对每张图像进行乱序处理。因此，我创建了一个管道模式。

我的代码看起来像这样：

ConcurrentQueue<Image> originalImages = new ConcurrentQueue<Image>();
ConcurrentQueue<Image> grayscaledImages = new ConcurrentQueue<Image>();
ConcurrentQueue<Image> completedImages = new ConcurrentQueue<Image>();

public static int main()
{
     PipeLineStage p1 = new PipeLineStage(originalImages, grayScale, grayscaledImages);
     PipeLineStage p2 = new PipeLineStage(grayscaledImages, lineDetect, completedImages);

     p1.Start();
     p2.Start();

     originalImages.add( image1 );
     originalImages.add( image2 );
     //... 
     originalImages.add( image10 );

     originalImages.add( CancellationToken );

     Task.WaitAll( p1, p2 );
}

以数据为中心的发生之前图：

如果该程序一开始就被设计为顺序程序，则出于缓存原因，一次获取每个图像并将其移至完成，然后再移至下一个图像会更有效。

无论如何，我们知道 GrayScale() 将被调用 10 次，LineDetection() 将被调用 10 次，因此我们可以单独为每个时间计时，然后将它们乘以 10。

但是推送/弹出/轮询并发队列的成本又如何呢？

假设图像很大，那么时间可以忽略不计。

如果有数百万个小镜像，每个阶段都有很多消费者，那么你可能会发现，当程序顺序运行时，等待锁、互斥锁等的开销非常小（假设在关键部分很小，例如在并发队列内）。

上下文切换的成本？

看看这个问题：

如何估计线程上下文切换开销？

基本上，您将在多核环境和单核环境中进行上下文切换。

执行上下文切换的开销非常小，但每秒也会发生很多次。

危险在于缓存在上下文切换之间被完全破坏。

例如，理想情况下：

• 由于执行灰度处理，image1 被加载到缓存中
• LineDetection 在 image1 上运行得更快，因为它位于缓存中

然而，这可能会发生：

• 由于执行灰度处理，image1 被加载到缓存中
• image2 作为灰度处理的结果被加载到缓存中
• 现在管道阶段 2 在 image1 上运行 LineDetection，但 image1 不再位于缓存中。

结论

没有什么比在运行环境相同的情况下计时更好的了。

接下来最好的方法是尽可能模拟该环境。

无论如何，了解程序的设计应该能让您了解在新环境中会发生什么。