1-6 スレッドの代替としてのタスクの使用

概要

タスクはスレッドよりも軽量であり、より迅速なスタートアップとシャットダウン、より優れたロード・バランシング、利用可能なリソースの効率的な利用、より高いレベルの抽象化を実現します。タスクベースのプログラミングを含むプログラミング・モデルとして、インテル® スレッディング・ビルディング・ブロック (インテル® TBB) と OpenMP* があります。この記事は、タスクベースのプログラミングの概要と、スレッドとタスクのどちらを使用するかを決定する上で重要なガイドラインを説明します。

この記事は、「マルチスレッド・アプリケーションの開発のためのインテル・ガイド」の一部で、インテル® プラットフォーム向けにマルチスレッド・アプリケーションを効率的に開発するための手法について説明します。

はじめに

Win32 スレッドや Pthread などのネイティブスレッドを直接使用したプログラミングがマルチスレッド・プログラミングの手法として選択されることは少なくなっています。これらのモデルで作成されるスレッドは、オペレーティング・システムがハードウェアの物理スレッドに論理スレッドをマップします。作成する論理スレッドの数が少なすぎると、システムでアンダーサブスクリプションが発生し、利用可能なハードウェア・リソースの一部が浪費されます。逆に、作成する論理スレッドの数が多すぎると、システムでオーバーサブスクリプションが発生し、ハードウェア・リソースにタイムスライス・アクセスすることによる大きなオーバーヘッドがオペレーティング・システムにかかります。ネイティブスレッドを直接使用する場合、開発者はアプリケーションで利用可能な並列性とハードウェアで利用可能なリソースを一致させる必要があります。

この困難なバランス調整を行う一般的な方法は、アプリケーションの生存期間にわたって使用されるスレッドのプールを作成することです。一般に、1 つの物理スレッドについて 1 つの論理スレッドを作成します。次に、スレッドプールのスレッドの計算を動的にスケジュールします。スレッドプールの使用により、ハードウェア・リソースと並列性の一致に役立つだけでなく、スレッド作成と破棄の繰り返しによるオーバーヘッドが回避されます。

インテル® スレッディング・ビルディング・ブロック (インテル® TBB) や OpenMP のような並列プログラミング・モデルでは、開発者がスレッドプールを明示的に管理する必要はありません。これらのモデルでは、開発者がタスクを使用してアプリケーションで論理的な並列性を表現し、ランタイム・ライブラリーがこれらのタスクをワーカースレッドの内部プールにスケジュールします。タスクを使用すると、開発者は並列性の管理について心配することなく、アプリケーションの論理的な並列化に集中できます。また、タスクはスレッドよりも非常に軽いため、より細かい粒度で並列化を表現できます。

タスクを使用する簡単な例を以下に示します。関数 fibTBB は、TBB task_group を使用して nth のフィボナッチ数列を計算します。n >= 10 の各呼び出しで、1 つのタスクグループが作成されて 2 つのタスクが実行されます。この例では、各タスクについて記述するラムダ式 (C++0x 標準の機能) を関数 run に渡します。これらの呼び出しにより、タスクがスポーンされ、実行するスレッドプールのスレッドで利用できるようになります。タスクグループのすべてのタスクの実行が完了するまで、関数 wait の呼び出しはブロックされます。

int fibTBB(int n) {
  if( n<10 ) {
    return fibSerial(n);
  } else {
    int x, y;
    tbb::task_group g;
    g.run([&]{x=Fib(n-1);}); // spawn a task
    g.run([&]{y=Fib(n-2);}); // spawn another task
    g.wait();                // wait for both tasks to complete
    return x+y;
  }
}

ルーチン fibSerial はシリアル可変であると推定されます。タスクを使用するとスレッドより細かい粒度の並列化が可能になりますが、サブルーチン呼び出しよりオーバーヘッドが非常に大きいことに変わりはありません。このため、一般に、小さな部分問題を連続的に解くために利用されます。

タスクをサポートしている別のライブラリーは OpenMP です。インテル® TBB とは異なり、これらのモデルはどちらもコンパイラー・サポートを利用するため、インターフェイスは単純ですが移植性に欠けます。例えば、上記の TBB タスクを使用しているフィボナッチ数列の例は、下記の OpenMP タスクを使用している例では fibOpenMP として実装されています。OpenMP はコンパイラー・サポートを利用するので、より単純なプラグマを使用してタスクを示すことができます。ただし、これらのプラグマは OpenMP をサポートしていないコンパイラーでは利用できません。

int fibOpenMP( int n ) {
  int i, j;
  if( n < 10 ) {
  return fibSerial(n);
  } else {
    // spawn a task
  #pragma omp task shared( i ), untied
    i = fib( n - 1 ); 
    // spawn another task
  #pragma omp task shared( j ), untied
    j = fib( n - 2 );
    // wait for both tasks to complete
  #pragma omp taskwait
  return i + j;
  }
}

インテル® TBB および OpenMP は、ワークスチールによってタスク・スケジューリングを管理します。ワークスチールでは、スレッドプールの各スレッドはデック (両端キュー) で構成されるローカルのタスクプールを維持します。スレッドはタスクプールをスタックのように使用し、スポーンした新しいタスクをスタックの上にプッシュします。スレッドがタスクの実行を完了すると、ローカルスタックの上からタスクをポップします。スタックの上のタスクは最も新しいタスクなので、データキャッシュでホットなデータにアクセスします。ただし、ローカルのタスクプールにタスクがない場合は、別のスレッド (犠牲スレッド) から作業をスチールします。スチールの際、スレッドは犠牲スレッドのデックをキューのように使用して、犠牲スレッドのデックから最も古いタスクをスチールします。再帰アルゴリズムでは、これらの古いタスクはタスクツリーで高い (大きなチャンクの) ノードであり、犠牲スレッドのデータキャッシュではホットでない作業になります。このため、ワークスチールはキャッシュの局所性を維持しながら負荷のバランスを保つための効果的なメカニズムです。

タスク・ライブラリーを使用すると、スレッドプールとワークスチール・スケジューラーによる複数スレッドへの作業の割り当ては開発者からは透過です。このため、開発者が並列化の管理について心配することなくアプリケーションの論理的な並列化に集中できる、ハイレベルな抽象化が提供されます。ワークスチールによるロード・バランシング、およびタスクの作成と破棄コストの低さにより、タスクベースの並列化はほとんどのアプリケーションで有効なソリューションとなっています。

利用ガイド

タスクの使用はパフォーマンスの向上を目的としたスレッド化アプローチとしては最も優れた方法ですが、タスクの使用が適切でない場合もあります。インテル® TBB と OpenMP で使用されるタスク・スケジューラーはノンプリエンプティブです。タスク・スケジューラーは、非ブロックタスクで構成されるハイパフォーマンスなアルゴリズム用ですが、タスクがまれにブロックする場合でも動作します。ただし、タスクが頻繁にブロックする場合、タスクがブロックされている間、そのタスクに割り当てられているスレッドは別のタスクで作業を行うことができないため、パフォーマンス・ロスが発生します。ブロックは、長い間 I/O や mutex を待つ際に発生します。スレッドが長い間 mutex を保持する場合、どんなに多くのスレッドがあったとしてもコードのパフォーマンスは向上しません。ブロックタスクがある場合は、タスクではなくスレッドを使用すると良いでしょう。

タスクを使用したほうが良い場合でも、最初からタスクパターンを実装する必要がないこともあります。インテル® TBB ライブラリーには、タスク・インターフェイスだけでなく、parallel_invokeparallel_forparallel_reducepipeline.のような最も一般的なタスクパターンを実装するハイレベルのアルゴリズムも用意されています。OpenMP には並列ループが用意されています。これらのパターンはチューニングされテストされているため、利用可能な場合は常にこれらのハイレベルなアルゴリズムを使用すると良いでしょう。

以下の例は、単純なシリアルループと tbb::parallel_for algorithm を使用して並列化したループを示しています。

// serial loop
for (int i = 0; i < 10000; ++i)
  a[i] = f(i) + g(i);
// parallel loop
tbb::parallel_for( 0, 10000, [&](int i) { a[i] = f(i) + g(i); } );

上記の例で、TBB parallel_for は、範囲 [0,10000) のすべての要素について、ループ本体 a[i] = f(i) + g(i) に適用するタスクを作成します。ラムダ式の & は、変数 a を参照でキャプチャーする必要があることを示します。parallel_for を使用すると、TBB ランタイム・ライブラリーは、負荷のバランスをとりながらオーバーヘッドが最小になるように、適切な反復数を選択してタスクをグループ化します。