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

Question

由于我正在(抢占式)多任务、多核环境中运行我的多线程程序的性能评估测试，因此该进程可以定期换出。我想计算延迟，即只有进程处于事件状态时的持续时间。这将使我能够推断在非多任务环境中的性能如何，即只有一个程序在运行(大部分时间)，或在不同的工作负载上。

通常测量两种时间:

挂钟时间(即自进程开始以来的时间)，但这包括进程被换出的时间。

处理器时间(即所有线程使用的 CPU 时间的总和)，但这对于计算进程的延迟没有用。

我相信我需要的是单个线程的时间跨度，由于线程之间的任务依赖结构，这可能与任何线程使用的最大 CPU 时间不同。例如，在一个有 2 个线程的进程中，线程 1 在运行时的前三分之二(对于 CPU 时间 t)加载很重，而线程 2 在进程运行时的后三分之二加载(再次，对于 CPU 时间 t)。在这种情况下:

挂钟时间将返回 3t/2 + 上下文切换时间 + 其他进程使用的时间，

所有线程的最大 CPU 时间将返回一个接近 t 的值，并且

总CPU时间接近2t。

我希望得到的测量输出是完工时间，即 3t/2。

此外，多线程本身会带来不确定性。这个问题可能可以通过多次运行测试并总结结果来解决。

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

有没有一种有效的方法来计算/近似这个完工时间？为了提供代码示例，请使用任何编程语言，但最好在 linux 上使用 C 或 C++。

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

Answer 1

问题的重新表述

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

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

经验上

显而易见的解决方案是获得一台只有一个内核的计算机，然后运行您的应用程序，并根据需要使用挂钟时间和/或 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 );
}

发生之前的图看起来像:



显然这些都是独立的。

在这种情况下

时间计算PiDigit() 本身。

时间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。

但是推送/弹出/轮询 ConcurrentQueues 的成本呢？

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

如果有数百万个小镜像，每个阶段都有很多消费者，那么你可能会发现，当程序顺序运行时，等待锁、互斥等的开销非常小(假设执行的工作量在临界区很小，例如在并发队列中)。

上下文切换的成本？

看看这个问题:

How to estimate the thread context switching overhead?

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

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

危险在于缓存在上下文切换之间完全中断。

例如，理想情况下:

由于执行 GrayScale

，image1 被加载到缓存中

LineDetection 在 image1 上运行得更快，因为它在缓存中

但是，这可能会发生:

由于执行 GrayScale

，image1 被加载到缓存中

由于执行 GrayScale

，image2 被加载到缓存中

现在管道阶段 2 在 image1 上运行 LineDetection，但 image1 不再在缓存中。

结论

在它将运行的同一环境中，没有什么比计时更好的了。

下一个最好的方法是尽可能地模拟该环境。

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