14

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

通常测量两种时间：

  • 挂钟时间（即自进程启动以来的时间），但这包括进程被换出的时间。
  • 处理器时间（即所有线程使用的 CPU 时间的总和），但这对于计算进程的延迟没有用。

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

  • 挂钟时间将返回 3t/2 + 上下文切换时间 + 其他进程使用的时间，
  • 所有线程的最大 CPU 时间将返回接近 t 的值，并且
  • 总CPU时间接近2t。
  • 我希望作为测量输出收到的是制造跨度，即 3t/2。

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

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

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

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

4

1 回答 1

4

问题的重新表述

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

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

凭经验

显而易见的解决方案是获得一台具有单核的计算机，并运行您的应用程序，并根据需要使用 Wall-Clock 时间和/或 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() 本身。
  • 把时间加在一起。

2级管道

当任务不独立时，您将无法将各个时间相加。

在下一个示例中，我创建了一个多线程应用程序：拍摄 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 不再在缓存中。

结论

在将要运行的相同环境中，没有什么比时间更好的了。

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

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

于 2013-09-14T21:32:30.893 回答