次の方法で共有

スレッド プール

  • [アーティクル]

スレッド プールによるスケーラブルなマルチスレッド プログラミング

Ron Fosner

プログラミングは日ごとに難しさを増していますが、スループットができる限り高くなるようにアプリケーションをチューニングするよう求められる場合は、特に難しくなります。その要因の 1 つが、コンピューターの進化過程におけるここ数年の変化です。コンピューターの処理能力を高めるため、これまではシングル プロセッサの速度を究極まで引き上げようとしていましたが、ここ数年は処理能力が複数のコアに分散されるようになっています。これは良い傾向です。比較的コストをかけずに潜在能力を大きく引き上げることができ、多くの場合、電力消費量も、冷却ニーズも大幅に低下します。

ですが、マルチコア システムの普及には否定的側面もあります。複数のプロセッサを使用するには、並列処理について深く掘り下げる必要があります。つまり、プログラマがこの潜在能力を活用するには、多くの手間がかかります (ときには、多くの学習が必要になります)。プロジェクトにコンパイラ ヒントをいくつか設定し、コンパイラにマルチスレッド コードを生成させることもできますが、マルチコア コンピューターの能力を最大限に活用するには、大きなジョブのプログラミング方法をいくつか変えなければなりません。

作業を複数のコアに分散する方法は数多くあります。最も簡単かつ堅牢な方法の 1 つが、タスクベースのプログラミングです。タスクを使うことによって、使用可能な CPU コア全体またはその一部にアプリケーションの作業を分散することができます。プログラミング方法について少し考えてみると、データどうしの依存関係や時間同期による制限事項を最小限に抑えたり、時には完全に取り除いたりできることがあります。マルチコアの能力を最大限に活かすには、プログラミングに関する問題の対処方法についての先入観をいくつか見直し、タスクベースのプログラミングの観点から再検討することが必要です。

タスクベースのプログラミングのしくみを示すために、シングル スレッドのアプリケーションをタスクベースに変換し、コンピューター上で使用可能な CPU をすべて利用するようスケールアップしてみました。今回は、このときに行ったことを、失敗も含めて、順を追ってすべて説明します。この説明の中で、マルチスレッド プログラミングの概念をいくつか紹介し、OpenMP とスレッド プールを使ってコードを複数のスレッドに分けて実行するための簡単な方法を示します。また、Visual Studio 2010 を使用して、こうした手法によってどの程度パフォーマンスが向上するかを測定する方法も見ていきます。今後のコラムでは、今回のコラムを基盤として、タスクを使ったさらに高度なマルチスレッド実行を紹介する予定です。

スレッドからタスクへ

プログラムを CPU コアの数に合わせてスケール変換するうえでの大きな課題は、いくつかのジョブをそれぞれ独自のスレッドに分けて実行させるだけでは済まないことです。これは多くの開発者が行っていることですが、実際にはアプリケーションが設計の対象にしたコア数にしか適切にスケール変換されません。対象となるコアが多くなっても少なくなっても、適切にスケール変換されません。また、そのようなアプローチがいずれ陳腐化してしまうことも完全に見過ごされています。

アプリケーションをコア数の変化に合わせて適切にスケール変換させるには、大きなジョブを、より小さく、スレッドに適したサブジョブに分割します。このサブジョブをタスクと呼びます。モノリシックなシングルスレッドのプログラムや、専用スレッドをいくつか使用しているプログラムを、タスクベースのジョブ システムに変換するうえで最も大きな課題は、実は、ジョブを複数のタスクに分割することなのです。

大きなシングルスレッドのジョブをマルチスレッド タスクに変換する際に留意しておくいくつかのガイドラインを、次に示します。

  • 大きなジョブは、1 ～ n 個のタスクに自由に分割することができます。
  • タスクは、どんな順番でも実行できるようにします。
  • タスクは、それぞれが独立している必要があります。
  • タスクには、関連するコンテキスト データが必要です。

これらをどれも簡単に実現できれば、アプリケーションをあらゆる数のコアで実行させることは困難ではありません。残念ながら、必ずしもすべての問題が、これらのガイドラインを満たしたタスクにきちんと分割できるわけではありません。

これらのガイドラインが重要なのは、このガイドラインに従えば、相互に依存関係を持たせることなく、スレッドで各タスクを独立して実行することができるためです。理想的には、タスクはどんな順番でも実行できるべきなので、依存関係を取り除いたり減らしたりすることが、タスク ベースのシステムの起動と実行における最優先事項です。

実際に使用されているプログラムのほとんどは、さまざまな段階の処理を経て実行されており、その各段階は、次の段階が開始される前に完了していることを求められています。こうした同期ポイントは避けられない場合がほとんどですが、タスク ベースのシステムの目標は、すぐに利用できる CPU の能力は何でも利用することです。大きなジョブを小さなジョブにうまく分割できれば、多くの場合、最初のタスクがいくつか実行されている間に、完了したタスクの結果を使って次の段階の処理を同時に開始することが可能になります。

OpenMP による簡単なマルチスレッド処理

アプリケーション全体をタスクを使用するように変換する前に、あらゆるものをタスクにするという苦労を伴わずに、マルチスレッドのメリットを利用できる方法があることをお知らせしておきましょう。マルチスレッド処理をアプリケーションに組み込む方法は非常にたくさんあり、その多くはほとんど作業を必要としませんが、それらの方法を使用すると、マルチスレッド処理をコードに追加することで得られるメリットを享受できます。

OpenMP は、プログラムに並列処理を追加する最も簡単な方法の 1 つで、2005 年から Visual Studio C++ コンパイラでサポートされています。OpenMP を有効にするには、どこに、どんな種類の並列処理を加えるかを示すプラグマをコードに追加します。たとえば次のように、簡単な Hello World プログラムに並列処理を追加することができます。

#include <omp.h> // You need this or it won't work
#include <stdio.h>
int main (int argc, char *argv[]) {
  #pragma omp parallel
  printf("Hello World from thread %d on processor %d\n",
    ::GetCurrentThreadfID(), 
    ::GetCurrentProcessorNumber());
  return 0;
}

OpenMP プラグマは、プラグマの次に来るコード ブロック (この場合は、単なる printf) を並列化し、すべてのハードウェア スレッド間で同時にそのコード ブロックを実行します。スレッドの数は、コンピューターで使用できるハードウェア スレッドの数によって異なります。出力は、各ハードウェア スレッドで実行される printf ステートメントです。

OpenMP プログラムが並列化を行う (また、OpenMP プラグマを暗黙のうちに無視しない) ようにするには、プログラムに対して OpenMP を有効にする必要があります。これにはまず、/openmp コンパイラ オプションを含めます (Visual Studio 2010 で、[構成プロパティ]、[C/C++]、[言語]、[OpenMP のサポート] を順にクリックします)。次に、omp.h ヘッダー ファイルをインクルードします。

アプリケーションが関数やデータをループ処理するのにほとんどの時間を費やしているときにマルチプロセッサによるサポートを追加するような場合に、OpenMP の真価が発揮されます。たとえば、実行するのにしばらく時間がかかる for ループがある場合、OpenMP を使用すると簡単にそのループを並列化することができます。次の例では、自動的に配列計算を分割し、それを現在使用可能な数のコアに分散します。

#pragma omp parallel for
for (int i = 0; i < 50000; i++)
  array[i] = i * i;

OpenMP には、スレッドローカル データ、同期ポイント、クリティカル セクションなどを作成しながら、分散された作業が次のコード ブロックの実行前に完了する必要があるかどうかを、作成されたスレッドの数に対して制御できる構造もあります。

おわかりのように、OpenMP は、既存のコード ベースに並列処理を簡単に導入できる便利な方法です。ただし、OpenMP の簡潔さは魅力的である一方で、アプリケーションが実行していることをさらに制御する必要がある場合 (プログラムの実行内容に対して動的に適合させる場合や、スレッドが特定のコアにとどまるようにする必要がある場合など) もあります。OpenMP は、マルチスレッド プログラミングの一部の側面をプログラムに簡単に統合できるように設計されていますが、複数のコアを最適に利用するための高度な機能が一部不足しています。そこで、タスクとスレッド プールの出番です。

スレッド プールの使用

スレッドは、OS による数多くのブックキーピングを必要とするため、気まぐれにスレッドを作成して削除することはお勧めできません。スレッドの作成と削除にはかなりのコストが伴うため、あまり頻繁に行うと、マルチスレッドによって得られるメリットが簡単に失われてしまいます。

代わりに、必要に応じてリサイクルされる既存のスレッド一式を、すべてのスレッド アクティビティに使用することをお勧めします。この設計はスレッド プールと呼ばれ、Windows には 1 つのスレッド プールが用意されています。このスレッド プールを使用すると、スレッドの作成、削除、管理がすべてスレッド プールによって処理されるため、それらの作業を行う手間が省けます。OpenMP はスレッド プールを使用して、複数のスレッドに作業を分散します。Windows Vista と Windows 7 には、開発者が直接使用できる、最適化されたバージョンのスレッド プールが用意されています。

独自のスレッド プールを作成することも十分可能ですが (なんらかの、スケジュールに関する特殊な要件がある際に必要になることがあります)、OS か Microsoft .NET Framework によって提供されるものを利用する方がずっと簡単です。

ここで、いくつかの用語をはっきりさせておく必要があります。スレッドについて語られる大半の場合、スレッドとは 1 つの CPU コアを使用する実行フローを指します。これは、ソフトウェア スレッドです。CPU では、実行フロー (実際の命令実行) はハードウェア スレッドで行われます。ハードウェア スレッドの数は、アプリケーションが実行されるハードウェアによって制限されます。以前、CPU はシングル スレッドでしたが、今では、最低でもデュアル コア プロセッサを搭載したシステムを見かけることが普通になりました。4 コアの CPU は、4 つのハードウェア スレッド (ハイパースレッド CPU の場合は 8 つ) を実行する能力があります。ハイエンドのデスクトップ システムには 16 個のハードウェア スレッドがあり、一部のサーバー構成には、100 個を超えるスレッドを備えるものもあります。

ハードウェア スレッドが実際に命令を実行するのに対して、ソフトウェア スレッドは、ハードウェア スレッドでジョブを実際に実行するのに必要なコンテキスト全体 (レジスタの値、ハンドル、セキュリティ属性など) を指します。重要なのは、ソフトウェア スレッドはハードウェア スレッドよりも多く存在させることができる点です。そのため、ソフトウェア スレッドがスレッド プールの基盤になります。スレッド プールでは、ソフトウェア スレッドと共にタスクをキューに入れ、そのタスクとソフトウェア スレッドを実際のハードウェア スレッドで実行するようにスケジュールを設定できます。

独自のスレッドを作成する代わりにスレッド プールを使用する利点は、OS がタスクのスケジュールを管理してくれることです。ジョブは、OS がすべてのハードウェア スレッドをビジー状態に保てるように、タスクをスレッド プールに送り続けます。これを示したものが図 1 です。ボックスの中身はすべてスレッド プールの構成要素ですが、プログラマはこれらを意識する必要はありません。アプリケーションが決めるのは、タスクをスレッド キューに配置し、最終的にはハードウェア スレッドで実行するようスケジュールが設定されるスレッド プールにタスクを送るかどうかです。

image: A Thread Pool

図 1 スレッド プール

難しいのはここからです。コアのビジー状態を維持し、CPU 使用率を最大限に高めるようにジョブを構造化する最適な方法は何でしょう。これは、アプリケーションで何を行う必要があるかによって異なります。

私は、よくテレビ ゲーム会社で仕事をしますが、ここで取り組むアプリケーションは最も難しい種類に属します。やるべきことが多く、いくつかの作業は特定の順番で行う必要があり、また、遅延にも敏感です。たいていの場合、プログラムは特定のフレーム レートで更新を行う必要があるため、フレーム レートが遅れ始めると、ゲームのエクスペリエンスに悪影響が出ます。このため、ハードウェアを最大限に活用したいと強く感じます。

一方で、アプリケーションがまとまった大きな作業を行うときは、やるべきことが少しわかりやすくなりますが、それでも 1 つのジョブを複数のコアに分散するのが難しいことには変わりありません。

マルチスレッドの並べ替え

まずは、アプリケーションでよく見受けられるモノリシックなジョブを簡単に紹介してから、そのジョブをよりマルチスレッドに適した形式に変換する方法について見ていきます。ここでは当然、並べ替えを考えています。というのも、並べ替えは特に優れた例で、大きな障害があるためです。その障害とは、何かを並べ替えるときにこの並べ替えを複数のコアに分散し、1 つのコアで行われる並べ替えを、別のコアで行われる並べ替えから分離するにはどうするか、という点です。

よく見受けられる単純なアプローチは、ミューテックス、セマフォ、クリティカル セクションなどを使用して、複数のコアから同じデータにアクセスできないようにロックする方法です。このアプローチでも機能はしますが、共有データへのアクセスが適切にスケジュールされていないことへの解決策としてこのアプローチが使用されると、たとえうまくいったとしても、他のスレッドの実行をブロックすることによって、複数のコアに分散したことから得られるメリットが失われます。最悪の場合、見つけ出すのがきわめて難しい、微妙な競合状態に陥ることになります。

さいわい、適切な並べ替えアルゴリズムを選択すれば、複数のスレッドから共有データにほとんどアクセスしないように、アプリケーションを設計できます。

適切なのは、各コアに、並べ替える配列のサブセクションを渡すアプローチです。このような分割統治方式は、同じデータ セットへの操作を複数のコアに分散する簡単な方法です。分割統治方式で機能するマージ ソートやクイック ソートなどのアルゴリズムは、マルチコア システムを活用する方法で実装するのが簡単です。

ランダムな整数の文字列でどのようにマージ ソートが機能するか見てみましょう (図 2 参照)。まず、配列における中間点を選択して、2 つのサブリストに分割します。この分割操作を、リストの要素の長さが 0 か 1 になるまで続けます。

image: Sorting a String of Random Integers

図 2 ランダムな整数の文字列の並べ替え

ほとんどの実装において、小さなリストで効率がよくなるように設計されたアルゴリズムではリストの最大サイズに制限がありますが、限界まで分割を続ければ機能します。重要なのは、リストを 2 つのサブリストに分割すると、分割されたリストどうしが独立することです。これを、図 2 の赤い点線で示しています。リストを 2 つのサブリストに分割すると各サブリストが独立するため、CPU に各サブリストを渡せば、CPU は何もロックすることなくそのリストを自由に操作できるようになります。

並べ替えの効率をできるだけ高めるには、各サブリストを受け取ってその場で並べ替えるアルゴリズムを選択します。このことは、データを不必要にコピーしないだけでなく、CPU の L2 キャッシュのデータを有効にしておくために重要です。より効率の良い並列コードを書こうとすると、最終的には、データを L2 キャッシュ内外に入れ替える方法が重要であることがわかります (現在のほとんどのプロセッサでは、一般に L2 キャッシュは約 256 KB です)。

並列化を利用できる並べ替えアルゴリズムはたくさんあります。クイック ソート、選択ソート、マージ ソート、基数ソートはどれも、データを細分化し、細分化したデータで独立して操作するアルゴリズムです。それでは、並べ替え処理を直列に行うルーチンの実装について見てみましょう。その後、このルーチンを並列バージョンに変換します。

理論上は、配列を再帰的に細分化し続けると、最終的には 1 つの要素になります。この時点ではもう並べ替えることはないので、アルゴリズムは、並べ替えられた複数のサブリストをマージするという次の段階に移行します。個々の要素は、大きな、並べ替え済みのリストにマージされます。その後、これらの並べ替え済みのサブリストは、元の配列が並べ替え順になっている状態になるまで、さらに大きな並べ替え済みリストにマージされます。先ほど申し上げたように、リストのサイズが特定のしきい値に達したら、小さなリストを並べ替えるように最適化されたアルゴリズムに切り替える方が通常は速く実行できます。

並べ替えのアルゴリズムを記述する方法は数多くありますが、ここでは C# でクイック ソート ルーチンを記述することを選択しました (図 3 参照)。このプログラムは、同一のランダムな整数のシーケンスを大きな配列に格納し、クイック ソート ルーチンを使用してそれらを並べ替え、これにどのくらい時間がかかったかをレポートします。

図 3クイック ソート

using System;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ParallelSort {
  class Program {
    // For small arrays, use Insertion Sort
    private static void InsertionSort(
      int[] list, int left, int right) {

      for (int i = left; i < right; i++) {
        int temp = list[i];
        int j = i;

        while ((j > 0) && (list[j - 1] > temp)) {
          list[j] = list[j - 1];
          j = j - 1;
        }
        list[j] = temp;
      }
    }

    private static int Partition(
      int[] array, int i, int j) {

      int pivot = array[i];

      while (i < j) {
        while (array[j] >= pivot && i < j) {
          j--;
        }

        if (i < j) {
          array[i++] = array[j];
        }

        while (array[i] <= pivot && i < j) {
          i++;
        }

        if (i < j) {
          array[j--] = array[i];
        }
      }

      array[i] = pivot;
      return i;
    }

    static void QuickSort(
      int[] array, int left, int right) {


      // Single or 0 elements are already sorted
      if (left >= right)
        return;

      // For small arrays, use a faster serial routine
      if ( right-left <= 32) {
        InsertionSort(array, left, right);
        return;
      }

      // Select a pivot, then quicksort each sub-array
      int pivot = Partition(array, left, right);

      QuickSort(array, left, pivot - 1);
      QuickSort(array, pivot + 1, right);
    }

    static void Main(string[] args) {

      const int ArraySize = 50000000;

      for (int iters = 0; iters < 1; iters++) {
        int[] array;
        Stopwatch stopwatch;

        array = new int[ArraySize];
        Random random1 = new Random(5);

        for (int i = 0; i < array.Length; ++i) {
          array[i] = random1.Next();
        }

        stopwatch = Stopwatch.StartNew();
        QuickSort(array, 0, array.Length - 1);
        stopwatch.Stop();

        // Verify it is sorted
        for (int i = 1; i < array.Length; ++i) 
          if (array[i - 1] > array[i - 1]) 
            throw new ApplicationException("Sort Failed");

        Console.WriteLine("Serialt: {0} ms",  
           stopwatch.ElapsedMilliseconds);
      }
    }
  }
}

QuicSort 関数を見ると、しきい値に達するまで配列を再帰的に 2 つに分割し、その時点で、さらなる細分化は行わずにリストを並べ替えていることがわかります。これを並列バージョンに変更する場合は、次の 2 行を変更するだけです。

QuickSort( array, lo, pivot - 1);
QuickSort( array, pivot + 1, hi);

並列化したバージョンは、次のとおりです。

Parallel.Invoke(
  delegate { QuickSort(array, left, pivot - 1); },
  delegate { QuickSort(array, pivot + 1, right); }
);

Parallel.Invoke インターフェイスは、.NET Task Parallel Library の Systems.Threading.Tasks 名前空間の一部です。これにより、関数を非同期に実行するよう指定できます。この場合は、各並べ替え関数を、個々のスレッドで実行するよう指定しています。

新しく生成するスレッドを 1 つだけにし、別のサブリストの並べ替えに現在の実行スレッドを使用する方が効率的でしたが、対称性を保ちたかったことと、直列処理のプログラムを並列プログラムに変換するのがどれだけ簡単かを示すために、このようにしました。

コアの利用率

今度は、この並列化によって、パフォーマンスが本当に向上したかどうかを調べてみましょう。

Visual Studio 2010 には、プログラムのどこに時間がかかっているのか、そしてプログラムがマルチスレッドのアプリケーションとしてどのように動作しているのかを把握できるツールがいくつか用意されています。Stephen Toub と Daniel Moth による、MSDN Magazine 2009 年 9 月号の記事「Visual Studio 2010 におけるタスクベースの並列アプリケーションのデバッグ」(msdn.microsoft.com/magazine/ee410778) では、マルチスレッド アプリケーションのパフォーマンスを測る、そのような Visual Studio 2010 のツールを使用することについての概要がわかりやすく示されています。また、Channel 9 では、Daniel Moth が概要をわかりやすくビデオで解説しています (channel9.msdn.com/posts/DanielMoth/Parallel-Tasks--new-Visual-Studio-2010-debugger-window/、英語)。

並列プログラミングを行う際は、パフォーマンスが本当に向上していることと、ハードウェア全体を活用していることを確認するために、測定を行う必要があります。並列化がサンプル アプリケーションでどのように使用されているかを詳しく知るために、これらのツールを使用して、並べ替え処理を行う実行中のルーチンを測定しましょう。Visual Studio 2010 のパフォーマンス ウィザードを起動して、並べ替えを行うアプリケーションの実行中に、同時実行に関する測定を行いました。

まず、使用可能な CPU サイクルをアプリケーションがどのように利用しているかを示す、コアの利用率に注目します。テスト プログラムは、直列にソートを実行し、2 秒間のスリープ状態を経て、並列バージョンのソートを実行します。図 4 は、4 コアのコンピューターにおけるコアの利用率のグラフです。緑色は今回のアプリケーション、黄色は OS と他のプログラム、灰色はアイドル状態です。1 コア レベルの平らな線は、直列バージョンの実行中にはシングル コアでの処理を完全に飽和状態にしていることと、並列バージョンの実行中には 4 コアのうち約 2.25 コアを利用していることを示しています。それほど驚くことではありませんが、並列ソートの実行時間は、直列ソートに必要な時間の約 45% です。2 行のコードを変更しただけにしては、なかなかすばらしい結果です。

image: Core Utilization

図 4 コアの利用率

では、CPU 使用率から、図 5 のスレッド ビューに移りましょう。ここでは、使用可能なスレッドをアプリケーションがどのように利用しているかが示されています。実行時間の大半がシングル スレッドで行われていることに注目してください。多くのスレッドが作成されるようになるのは、タスクを生成し始めてからです。ここでは、サーモン色の部分が、他のスレッドによってブロックされているスレッドです。

image: Thread Work

図 5 スレッドの利用状況

実際、スレッド ビューからは、実行速度は劇的に速くなったにもかかわらず、スレッドをあまり効率的に行っていなかったことがわかります。タスクの完了をメイン スレッドが待機していることが理由で他のスレッドを待機し、スレッドがブロックされていることはまったく問題ありません。ですが、本当に注目するのは、CPU コアと同数のタスク上の密集した緑色の部分です。したがって、CPU 使用率のグラフで CPU コアの利用率が高くなったことが示されていても、タスクがスレッド プール全体にどのように分散されていたか詳しく見てみると、最適化できる余地はまだあることがわかります。

実際、ここで行ったような簡単な作業でも、なんらかのマルチスレッドの作業を行った後は、コードのパフォーマンスを常に測定すべきです。小さなジョブでは、オーバーヘッドがスレッド パフォーマンスを上回るため、マルチスレッド化することは望まないでしょう。大きなジョブでは、スレッド プールをオーバーサブスクライブしないように、使用可能な CPU コアと同数までジョブを分割することになります。

次のステップ

コード以外でパフォーマンスをさらに向上する方法はたくさんありますが、この最初のコラムではそれを目標としませんでした。ですが、コードを少し変更して、スレッドに適したものにするだけで、CPU 使用率を 80% にする方法をおわかりいただけたと思います。今度は、このコードをさらに最適化するのではなく、ジョブの設計に少し変化を加えることで、システムの CPU からパフォーマンスを最大限に引き出すことに注目する予定です。

ここで紹介した方法での並べ替えは、特にマルチスレッドに適しています。ジョブをどの程度分割するかを計算し、サブジョブをそれぞれスレッドに渡すことができます。ただし、パフォーマンスは向上したものの、いくつかのパフォーマンスは重視しなかったことも事実です。

ですが、実際のアプリケーションでは、一意のタスク一式を提供する多くのジョブがある場合や、特定のタスクがどのくらい長く実行されるかわからないという不確実さの中でタスクのスケジュールを設定する必要がある場合もあります。これは、特に難しい問題です。次回の記事では、スレッドに全体的なアプローチを取るアーキテクチャに注目し、複数の、おそらく異なったジョブを分散できるようにします。そして、タスクとスレッド プールの使用を通して、最初からマルチコア対応になるようにアプリケーションを設計する方法をご紹介する予定です。

Ron Fosner は、過去 20 年間にわたり高パフォーマンスのアプリケーションとゲームを Windows で最適化し、そのこつを掴んできたところです。彼は Intel でグラフィックと最適化の専門家として活躍しており、あらゆる CPU コアが完全に実行されているのを見ると幸せな気持ちになります。連絡先は Ron@directx.com (英語のみ) です。

この記事のレビューに協力してくれた技術スタッフの Stephen Toub に心より感謝いたします。