65.9K
CodeProject 正在变化。 阅读更多。
Home

PetriDish：C# 中的多线程以提高性能

Nicholas Butler
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.95/5 (44投票s)

2008 年 5 月 28 日

CPOL

13分钟阅读

viewsIcon

132982

downloadIcon

1326

深入探讨高级并发编程。

key

screenshot

目录

引言

"PetriDish" 是一个用于提高性能的并发编程示例。它是一个模拟，包含三类生物，它们都在生长、繁殖和相互捕食。它完全基于个人杜撰的生态理论，没有任何科学依据。然而，它确实是一个有用的实验。

首先，我将快速描述模型，然后深入探讨多线程。

1 模型

从图例可以看出，三类生物是：植物、食草动物和食肉动物。核心方程代表了这些类群之间的平衡。如果您运行该应用程序，您会看到绿色区域是植物的生长。这些区域变成蓝色，表示食草动物的繁盛。然后，红色区域出现，表示食草动物被不断增长的食肉动物种群捕食。黄色区域是植物、食草动物很少的、不稳定的平衡状态。食肉动物会消失，植物会重新生长，然后循环开始。

每个像素或单元格都有三个 byte 值，分别代表这三类生物的数量。帧是迭代生成的。也就是说，每一帧仅取决于其前一帧以及一些随机的不稳定性。

1.1 核心方程

核心方程相当简单。对于每个像素，它们取值：gn、bn 和 rn，分别代表当前帧的植物、食草动物和食肉动物的数量。结果：gn+1、bn+1 和 rn+1 是下一帧的数量。

 gn+1 = gn * 1.1 - bn * 0.1 - rn * 0.01 - Randomg
 bn+1 = bn * 1.1 + gn * 0.1 - rn * 0.09 - Randomb
 rn+1 = rn * 1.1 + bn * 0.1 + gn * 0.00 - Randomr

每个方程中的第一项将现有数量增加 10%。这代表了繁殖。

每个方程中的最后一项代表死亡。这是一个随机值，用于在模型中引入不稳定性。对于植物，该值在 -42 和 42 之间。对于食草动物和食肉动物，该值在 0 和 42 之间。

对于植物，中间两项代表被食草动物（10%）和食肉动物（1%）捕食。

对于食草动物，两项代表吃植物（10%）和被食肉动物吃（9%）。

食肉动物吃食草动物（10%），但不受植物数量的影响。

关于这些方程，最后要说的是，它们只是松散地基于现实世界。我的动机是生成令人愉悦的图案，所以我对它们进行了调整，直到我对结果满意为止。不要基于它们来撰写你的生态学博士论文！

1.2 现有种群

方程使用的现有数量取决于周围像素的数量。在下载文件中，使用了 5x5 的网格。细胞的影响由其与中心单元格的距离加权，尽管您可以关闭此功能，而仅使用网格上的平均值。移除此计算不会对生成的图像产生过度影响，并且可以将性能提高约三分之一。

视口被一个草地环绕，其中没有食肉动物或食草动物，但有 75% 的植物数量。嗯，边缘情况就是这样处理的。

1.3 绿洲

视口中有 25 个小绿洲，以 5x5 的网格放置。每个绿洲内的植物数量永远不会低于 42。

1.4 不稳定性

模型被证明过于稳定和可预测，因此引入了一些随机不稳定性。这是通过将视口的某些部分延迟随机量（5% 到 15% 之间）来实现的。

视口被分成 100x100 像素的方块。其中四分之三的方块被随机选择延迟。延迟是通过随机值低于阈值时就不计算下一迭代来实现的。

1.5 总结

生成的图像表现出足够的不稳定性以保持趣味性，同时保留一定的连贯性。最初有大约 1000 帧的时期，相当可预测，但随后，每次运行都会进入一个令人愉悦的随机周期。

2 多线程

最初，线程控制是使用 Microsoft 的 Parallel Extensions Library 实现的。这使事情变得更容易，但不幸的是，性能非常糟糕。我必须指出，我使用的是 2007 年 12 月发布的第一个 CTP 版本，因此该库尚未优化。但是，我认为真正的问题是工作单元的大小。程序每像素每核心的处理时间仅为 10-6 秒左右，或大约 1000 个时钟周期。这是一个非常小的工作单元，它被库的开销所吞没。所以最后，我手动处理了线程，结果好得多。

本文是关于多线程以提高性能的，所以我们需要一些度量。我使用的基本度量是使用单个线程计算一个像素所需的时间。这消除了多线程引入的所有开销，因此它提供了我的机器执行计算所需的最小时间。不使用加权，每像素每核心的数字是 310 纳秒。使用加权，数字是 460 ns / 像素 / 核心。我将在本文的其余部分使用这两个选项，以说明不同的观点。

2.1 用户界面

UI 非常简单。当生成一帧时，它会更新其度量并使自身失效。它重写了 OnPaint 方法，使用 Graphics 对象直接在屏幕上绘图。

UI 通过调用 Engine.Painted() 让 Engine 知道一帧已被绘制。即使 Engine 已经计算出下一帧，它也不会继续，直到上一帧已被绘制。实际上，这很少引起等待，因为 UI 比 Engine 快得多。

2.2 引擎

引擎代码都在一个名为 Engine 的 static 类中。

  partial static class Engine
  {
    public static event EventHandler Update;
    public static Bitmap Bitmap { get { ... } }
    public static void Painted() { ... }
  }

UI 主要通过这三个成员与该类交互：Update 事件、Bitmap 属性和 Painted 方法。当 Bitmap 中的帧准备好时，Engine 会触发 Update 事件。作为响应，UI 会使自身失效。当屏幕在 OnPaint 覆盖中更新后，UI 会调用 Painted 来让 Engine 知道它可以继续。

2.3 缓冲区

使用两个 Int32 数组作为缓冲区，并在每一帧之间切换。因此，对于一帧，BufferA 是源，BufferB 被更新。对于下一帧，缓冲区会被切换。这可以节省将一帧的结果复制到下一帧的源缓冲区。

这种架构还有另一个优点：没有共享的易变状态。这对于性能非常重要。尽管所有线程都从同一个输入缓冲区读取，但每个线程只负责写入其输出缓冲区的自己的部分。这一点很重要，因为它意味着在计算下一帧时，线程之间不需要任何同步。

然后将输出缓冲区复制到 Bitmap 并触发 Update 事件。此代码受 lock 保护，该锁也用于 UI 以防止并发访问 Bitmap。由于 UI 在写入 Bitmap 后更新，因此此锁的争用很少。它主要是为了正确性。

我将这项工作放在一个单独的线程中，因为它不是并行的，并且妨碍了并发计算。

2.4 串行定律

我不记得是谁发明了这个定律，但它自 60 年代以来就存在了。每个程序都有一个串行部分和一个并行部分。该定律规定，程序的执行时间受限于串行执行所花费的时间。换句话说，即使你有无限的并行度，你的程序仍然会受到串行部分执行所需时间的限制。

这是我们将使用的图例

key

考虑一台具有八个核心的机器。在 10 个时间单位内，它能够执行 80 个单位的工作。但如果其中 3 个工作单元必须顺序执行，我们将损失 3 x 7 = 21 个单位的工作，这大约是可用功率的 25%。

bad

我现在将推导一个描述这个定律的方程。考虑下面的简单示例。有 16 个工作单元和 4 个核心。4 个工作单元是串行的，所以串行：总工作的比率为 4 / 16 = 25%。时钟时间为 7 个时间单位，因此容量为 7 x 4 = 28。所以，实际工作与容量的比率为 16 / 28 = 4 / 7。将此比率乘以核心数，我们得到 16 / 7 = 2.286。这是实际使用的核心数。

example

所以，给定

N = number of cores
S = ratio sequential : total
C = ratio concurrent : total = ( 1 - S )
W = total work

实际工作由 N x W 给出。顺序完成的工作量为 S x W，并行完成的工作量为 C x W。因此，容量为 N x S x W + C x W。我们想要实际工作与容量的比率，所以消去 W，得到这个方程

bad

这里有一个关于此方程的表格和图，针对 1 到多个核心。

table

graph

正如您所看到的，在一台双核机器上，它的影响不是那么大。最坏情况下你只能损失一个核心，即 50%。然而，在一台 16 核的机器上，仅仅 10% 的工作顺序执行就会让你损失超过 50% 的容量，即 9 个核心。可用的核心越多，任何串行组件的影响就越严重。

我的观点是，任何大量的串行执行都会浪费你试图好好利用的容量。随着核心数量的增加，这种影响只会变得更糟。

2.5 缓冲区线程

这段代码的并行部分是输出缓冲区的计算。它在尽可能多的核心上运行相同的代码。串行部分是将输出缓冲区复制到位图。这两个操作实际上可以同时运行，因为它们都从一个缓冲区读取。读取的缓冲区在写入输出缓冲区时是不可变的。

所以，我分出了一个线程来处理位图。它要做的工作不多，占用的容量也不大，但它将极大地消除主循环的串行部分。事实上，它几乎总是在下一帧准备好之前完成工作。

real

正如您所看到的，每帧的时钟时间减少了 25%，这意味着在花费很少的精力的情况下，帧率提高了 25%。

2.6 同步

现在的问题是，缓冲区线程何时开始复制下一帧？答案是主线程通过 AutoResetEvent 告诉它。是时候写代码了。

// Events

  partial class Engine
  {
    static AutoResetEvent _ToggleEvent = new AutoResetEvent( true );
    static AutoResetEvent _UIEvent = new AutoResetEvent( true );
    static AutoResetEvent _BufferEvent = new AutoResetEvent( false );
  }
  
// The master thread

  static void Master()
  {
    for ( ; ; )
    {
      Work();

      _UIEvent.WaitOne();

      _ToggleEvent.WaitOne();

      _BufferToggle = !_BufferToggle;

      _BufferEvent.Set();
    }
  }
  
// The buffer thread

  static void BufferMaster()
  {
    for ( ; ; )
    {
      try
      {
        _BufferEvent.WaitOne();

        UpdateUI();
      }
      finally
      {
        _ToggleEvent.Set();
      }
    }
  }

当线程启动时，缓冲区线程立即等待 _BufferEvent。主线程继续计算第一帧。完成后，它会等待 _UIEvent 和 _ToggleEvent，因为它们是在已发出信号的状态下创建的。然后它会切换缓冲区，并发出 _BufferEvent 的信号以释放缓冲区线程。然后两个线程都继续。主线程开始计算下一帧，而缓冲区线程将最后一帧复制到屏幕。

通常，缓冲区线程和 UI 会在主线程完成下一帧之前完成它们的工作。如果发生这种情况，主线程不必等待即可再次切换缓冲区。但是，如果 UI 由于某种原因尚未更新，主线程将不会继续，直到这项工作完成。这确保了每一帧都在 UI 中显示，从而消除了闪烁。

这种架构是正确的，同时最大程度地减少了主线程的等待。同步确实需要少量时间，即使事件已经发出信号。但是，每帧只有三个事件被使用。每帧大约需要 30 毫秒，对于现代处理器来说，这已经是相当长的时间了。您想要避免的是在紧密循环中进行同步，因为在那里会注意到开销。

2.7 工作线程

下面的 Work 方法由我们刚才看到的主线程每帧调用一次。

// Work thread ( naive )

  unsafe static void Work()
  {
    _ThreadCounter = ThreadCount;
    _ThreadSemaphore.Release( ThreadCount );
    _ThreadEvent.WaitOne();
  }

ManualWork 方法由所有工作线程使用，用于计算下一帧。

// Worker thread ( naive )

  unsafe static void ManualWork( object o )
  {
    int thread = ( int ) o;
    TLS tls = _ThreadLocalState.Current;

    for ( ; ; )
    {
      _ThreadSemaphore.WaitOne();

      try
      {
        fixed ( Int32* read = &ReadBuffer[ 0 ] )
        fixed ( Int32* write = &WriteBuffer[ 0 ] )
        {
          int start = _ThreadStarts[ thread ];
          int end = _ThreadEnds[ thread ];

          for ( int i = start ; i < end ; i += 1 )
            Next( i, tls, read, write );
        }
      }
      finally
      {
        if ( Interlocked.Decrement( ref _ThreadCounter ) == 0 )
          _ThreadEvent.Set();
      }
    }
  }

此方法使用 unsafe 指针来优化内存访问，但我将避免详细介绍我为提高性能所做的优化。如果您正在进行多线程以提高性能，您通常需要优化您的代码。这两项任务通常是齐头并进的。但是，由于这是一篇关于并发的文章，我不会再多说优化。

工作线程使用 Semaphore 释放。这是一个允许控制多个对象的同步原语。在这种情况下，它控制所有工作线程，每个核心有一个线程。

每个线程完成分配的工作，然后递减一个共享计数器。当此计数器达到零时，所有线程都已完成，并且 Work 方法发出信号，允许它返回主线程。

2.8 负载均衡

上面方法中的工作在所有线程之间均匀分配。因此，每个线程负责计算相同数量的像素。虽然这很简单，但对于真正的程序来说还不够好。不能保证每个线程都能获得相同的处理器时间（由内核调度程序分配）。实际上，在物理多核机器上，这实际上非常不可能。在此实现中，所有线程都必须等待最慢的线程完成。

我测试了最快和最慢的线程，结果令人惊讶。最快的线程每个像素大约需要 450 ns，最慢的线程大约需要 620 ns。这几乎有 40% 的差异！只有使用物理多核机器才能发现像这样的真实结果。

解决方案是实现一个负载均衡枚举器。

顺便说一句，TLS 类来自我的另一篇文章：Thread Local Storage。基本上，它提供了线程本地存储，但也可以从其他线程访问。这使得它们能够跟踪整体进度等。

// Work thread ( balanced )

  unsafe static void Work()
  {
    _BalancingMaster.Reset();
    _ThreadCounter = ThreadCount;
    _ThreadSemaphore.Release( ThreadCount );
    _ThreadEvent.WaitOne();
  }
  
// Worker thread ( balanced )

  unsafe static void ManualWork( object o )
  {
    TLS tls = _ThreadLocalState.Current;

    for ( ; ; )
    {
      _ThreadSemaphore.WaitOne();

      tls.Enum.Reset();
      
      try
      {
        fixed ( Int32* read = &ReadBuffer[ 0 ] )
        fixed ( Int32* write = &WriteBuffer[ 0 ] )
        {
          foreach ( int i in tls.Enum )
            Next( i, tls, read, write );
        }
      }
      finally
      {
        if ( Interlocked.Decrement( ref _ThreadCounter ) == 0 )
          _ThreadEvent.Set();
      }
    }
  }

平衡主控器是一个线程安全对象，它向枚举器分配工作块。每个线程有一个枚举器，因此它们不需要同步。每个枚举器获取一个工作块，然后逐个将这些值提供给 ManualWork 方法。完成一个块后，枚举器从平衡主控器获取另一个。这是实现：

// BalancingMaster

  class BalancingMaster
  {
    public static readonly int MAX = X * Y;

    volatile int _Current = 0;
    object _Key = new object();

    public void Reset()
    {
      _Current = 0;
    }

    public int Next
    {
      get
      {
        lock ( _Key )
        {
          if ( _Current >= MAX ) return -1;

          int current = _Current;
          _Current += BalancingChunk;
          return current;
        }
      }
    }
  }

// BalancingEnumerator

  partial class BalancingEnumerator : IEnumerator<int>
  {
    BalancingMaster _Master;
    
    int _Base = 0;
    int _Index = BalancingChunk;
    bool _Finished = false;
    
    public void Reset()
    {
      _Base = 0;
      _Index = BalancingChunk;
      _Finished = false;
    }    
    
    public int Current
    {
      get { return _Base + _Index; }
    }

    public bool MoveNext()
    {
      if ( _Finished ) return false;

      _Index++;

      if ( _Base + _Index < BalancingMaster.MAX )
      {
        if ( _Index < BalancingChunk ) return true;

        _Index = 0;
        _Base = _Master.Next;
        if ( _Base >= 0 ) return true;
      }

      _Finished = true;
      return false;
    }
  }

如您所见，BalancingMaster 在其 Next 方法中使用 lock。但是，当块大小为 1000 时，与八个线程相比，该锁的争用几乎可以忽略不计。利用机器的全部容量的优势远远超过了开销。

使用这种负载均衡后，平均速度为每像素每核心 520 ns，这大约是预期的值：介于 450 和 620 之间。然而，帧率提高了约 30%，因为每帧使用的机器容量更多。处理器使用率从约 70% 上升到约 90%，这是可以接受的。

结论

好了，差不多就这些了。我在探索这个程序的过程中学到了很多东西。我学到的最重要的一点是，多核机器与双核机器的行为截然不同。我建议买一个来玩玩；这是一个新领域！

希望您喜欢阅读本文，非常感谢。

历史

  • 2008 年 5 月 28 日 - v1.0

    • 初始发布。

© . All rights reserved.