タスクの適度な大きさは?

理想的なタスクのサイズはプログラムの詳細に大きく依存します。留意すべきいくつかの一般論があります。

タスク・オーバーヘッド

一般に、有益なワークを実行してシステムの多くのプロセッサー・コアをビジーに保つことができれば、プログラムはシステムを効率良く利用していると言えます。これは、コアをビジーに保ち、有益なワークを実行するという 2 つの要素により達成されます。

新しいタスクの起動には時間がかかります。タスクが非常に小さい場合、プログラムは並列処理タスクの生成に多くの時間を費やし、コアはビジーに保たれますが有益なワークを行わない可能性があります。

負荷バランス

一方大きなタスクは並列性を損ねます。並列プログラムは、最も長いタスクよりも早くなることはありません。経験則として、並列サイト内のタスク数を利用可能なコア数の数倍以上にして、コアが空いたときに実行するワークが常にあるようにします。

正しいレベルを選択

多くの場合、異なるループの入れ子レベルや関数呼び出しの階層でタスクを生成できます。そのため、タスクサイズを容易に選択できます。例えば、次の C/C++ コードについて考えてみます。

 for (i = 0; i != N; ++i) {
    for (j = 0; j != N; ++j) {
        x[i, j] = y[i, j] * z[j, i];
    }
 }

内部ループは有用なタスクとしては小さすぎます。スータビリティー・レポートでタスクの平均インスタンス時間を表示できます。内部ループ全体のほうが適切である可能性があります。

ANNOTATE_SITE_BEGIN(sitename);
for (i = 0; i < N; ++i) {
    ANNOTATE_ITERATION_TASK(task_process_array);
    for (j = 0; j < N; ++j) {
        x[i, j] = y[i, j] * z[j, i];
    }
}
ANNOTATE_SITE_END();

ブロック化

並列処理を導入するのに適していると思われるループの本体が、タスクとしては小さすぎる場合、いくつかの反復をグループ化することを検討してください。インテル® oneAPI スレッディング・ビルディング・ブロック (oneTBB) と OpenMP* を使用してループ本体の並列構造を指定すると、適切なサイズのタスクを生成するため自動的に複数のループ反復がグループ化されます。したがって、単純なループでは、ループ本体が適切なタスクサイズであるかではなく、ループ実行時間の合計を適切なサイズのチャンクに分割できるかどうかが問題です。

例えば、ループレベルが 1 つしかなく、ループ本体が小さすぎる場合について考えます。

 for (i = 0; i < 100000; ++i) {
    a[i] = b[i] * c[i];
}

このループを選択すると、次のように記述した場合と同様に実行されるかもしれません。

ANNOTATE_SITE_BEGIN(sitename);
for (i = 0; i < 100000; i += 1000) {
    ANNOTATE_ITERATION_TASK(task_calculate_a);
    for (j = i; j < i + 1000; ++j) {
        a[j] = b[j] * c[j];
    }
}
ANNOTATE_SITE_END();

インタラクションを回避するサイズを使用

ループ反復やそのほかの潜在的なタスク本体があるレベルでは独立性があっても、そのほかのレベルでは多くのインタラクションが存在することがあります。この場合、プログラムのゲインよりもプログラミングの容易さとプログラムの分かりやすさを優先したほうが良いかもしれません。

Sudoku 問題生成の外部ループは、generate() 間巣を繰り返し呼び出して問題を生成します。問題生成関数には、さまざまなレベルで並列処理を導入できる可能性がありますが、generate() のそれぞれの呼び出しは完全に独立しており、generate() の呼び出しにかかる時間は 1 秒未満です。この外部ループは簡単に並列化できます。1 つの問題の生成に 0.2 秒ではなく 0.8 秒かかっても大した問題ではありませんが、多くの問題を生成する場合のスピードアップは完璧であるべきです。

サーベイレポートを使用

タスクを選択することは科学的というよりも芸術的であるかもしれません。呼び出しツリーのルート (根本) 近くでは大きなタスクを生成されますが、共有変数の競合も多くなる可能性があります。一方、ツリーの終端 (葉) のタスクは小さくなりオーバーヘッドの問題を引き起こす可能性がありますが、競合は少なくなります。いくつかの経験則があります。改善を計画するプログラム領域の大部分お時間を費やす関数 F を調査することから始めます。アムダールの法則を思い出してください。

大部分の時間が F のコードブロックで費やされ、それらがループを実行する場合、コードブロックはデータ並列タスクの最初の候補となります。
F が単に関数 G の呼び出しラッパーである場合、G を調査します。
F のほとんどの時間が関数 G の呼び出し (複数回) に費やされており、関数 G が大きすぎるため適切なタスクにならない場合、関数 G の飛び出しを並列サイトで囲み、実際のタスクを G の内部、または G から呼び出される別の関数で明確にします。
F に費やされる時間が多数の独立したアクティビティーに分散されている場合、タスク並列処理パターンを F に適用すべきか、複数の並列サイトパターンを使用してそれぞれのアクティビティーの並列処理を明確にするか検討する必要があります。

再帰 (Recursion)

再帰的なアルゴリズムには特殊な課題があります。この問題は、一度の呼び出しでは少量のワークしか行わないものの、再帰的に何度も呼び出される関数で多くの時間が費やされた場合に発生します。実際のワークはデータ並列処理かもしれませんが、関数本体は有用なタスクには小さすぎ、ブロック化 (上記の「ブロック化」を参照) を再帰アルゴリズムに適用するのが困難です。

一般的な解決策は、再帰的な並列処理を制御するしきい値を使用することです。例えば、再帰ソートでは、特定のしきい値を超えた場合にのみ部分問題を並列に解くようにします。