ワークキューイング・コード生成

ここでは、中間言語スカラー最適化機構 (Intermediate Language Scalar Optimizer) を使用して、コンパイラーがマルチスレッド・コードを生成する方法について説明します。

次の while ループがコンパイラーに渡されると仮定します。すべての例では、解説の便宜上、行番号が記載されています。

1 void test1(LIST p)

2  {

3    #pragma intel omp parallel taskq shared(p)

4    {

5      while (p != NULL)

6      {

7        #pragma intel omp task captureprivate(p)

8        {

9          do_work1(p);

10       }

11       p = p->next;

12     }

13  }

parallel taskq プラグマは、囲まれた task プラグマに指定された作業単位をエンキューする while ループの環境を指定します。ループの制御構造とエンキューは、シングルスレッドで実行され、チーム内の他のスレッドは taskq キューからの作業をデキューし、実行します。captureprivate 構文は、各タスクがエンキューされる (シーケンシャル・セマンティクスが保存される) 時点で、リンクポインター p のプライベート・コピーが確実に取り込まれるようにします。

最初に、コンパイラーは次のようなワークキューイング・コードの中間表現 (IL0) を生成します。ここでは、while ループは、if 文および goto 文に置き換えられ、各ワークキューイング・プラグマは、構造の範囲を定義する IL0 の begin/end 宣言子に変換されます。

1 void test1(p)

2 {

3   DIR_PARALLEL_TASKQ SHARED(p)

4   if (p != 0)

5   {

6   L1:

7     DIR_TASK CAPTUREPRIVATE(p)

8       do_work1(p)

9     DIR_END_TASK

10    p = p->next

11    if (p != 0)

12    {

13      goto L1

14    }

15   }

16   DIR_END_PARALLEL_TASKQ

17   return

18 }

次に、OpenMP のバックエンドは private 変数と shared 変数を処理する新しいデータ構造体を作成します。各 taskq 構造に対して 2 つの struct 型が定義されます。1 つ目の shared_t は、sharedfirstprivatelastprivate、および reduction 変数へのポインターを保持します。

2 つ目の structthunk_t は、privatefirstprivatelastprivatecaptureprivate、または reduction として taskq にリストされている変数のプライベート・コピーに加え、shared_t へのポインターを保持します。コンパイル時に、各 struct へのポインターが作成されます。ポインターが指す実際のオブジェクトは、ワークキューイング・ライブラリー・ルーチンを起動することにより、ランタイム時にインスタンス化されます。

この例で生成されるシンボルテーブルのエントリーは次のとおりです。

typedef struct shared_t {

...                     // fields for internal use

  p_ptr;                // pointer to shared variables p

};

auto struct shared_t *shareds;

typedef struct thunk_t {

...                      // fields for internal use

  struct shared_t *shr;  // := shareds

  p;                     // captureprivate p

};

auto struct thunk_t *taskq_thunk;

この例では、自動ポインター sharedstaskq_thunk は、taskq のスレッドエントリー外に割り当てられます。private 変数に加え、thunk_ttaskq のコードとデータに関する十分な情報を保持するため、キューがいっぱいで実行が停止された場合でも、後で再開することができます。

OpenMP のバックエンドは、IL0 宣言子をマルチスレッド IL0 コードに変換します。このマルチスレッド IL0 コードは、インテルの OpenMP ランタイム・ライブラリー・ルーチンを明示的に呼び出し、作業のエンキュー/デキューとスレッドの管理および同期化を行います。コード変換の結果、3 つのスレッドエントリー (T エントリー) がオリジナル関数 test1() に挿入されます。test1_par_taskq() (6 行目〜 16 行目) は、複合 parallel taskq プラグマの parallel 部分のセマンティクスに対応します。test1_taskq() (18 行目〜 50 行目) は、複合プラグマの taskq 部分に対応し、test1_taskq() 内で入れ子された test1_task() (36 行目〜 40 行目) は、囲まれた task 構造に対応します。

1 void test1(p)

2 {

3   __kmpc_fork_call(test1_par_taskq, &p)

4   goto L3

5

6   T-entry test1_par_taskq(p_ptr)

7   {

...

16   }

17

18   T-entry test1_taskq(taskq_thunk)

19   {

...

36     T-entry test1_task(task_thunk)

37     {

...

40     }

...

50   }

51 L3:

52   return

53 }

T エントリーは、いくつかの小さな相違点はありますが、通常の関数エントリーに類似しています。

3 行目で起動されるインテルの OpenMP ライブラリー・ルーチン __kmpc_fork_call() は、ランタイム時にスレッドチームを形成します。すべてのスレッドが test1_par_taskq() を実行しますが、test1_taskq() を実行するスレッドは 1 つのみです。test1_taskq() は、while ループの骨格ともいうべきもので、その主な目的は各反復時に test1_task() で指定された作業をエンキューすることです。他のすべてのスレッドは、作業をデキューし実行する作業スレッドとなります。

これらの T エントリーについて、test1_par_taskq() から検証します。

6 T-entry test1_par_taskq(p_ptr)

7 {

8   taskq_thunk = __kmpc_taskq(test1_taskq, 4, 4, &shareds)

9   shareds->p_ptr = p_ptr

10   if (taskq_thunk != 0)

11   {

12     test1_taskq(taskq_thunk)

13   }

14   __kmpc_end_taskq(taskq_thunk)

15   T-return

16 }

パラメーター p_ptr (6 行目) は、共通変数 p へのポインターです。8 行目ですべてのスレッドはライブラリー・ルーチン __kmpc_taskq() を呼び出し、(shareds の) shared_t をインスタンス化します。すべてのスレッドは、(taskq_thunk の) thunk_t もインスタンス化しようと試みますが、1 つのスレッドのみ成功し、そのスレッドが T エントリー test1_taskq() (12 行目) に進みます。他のスレッドは 10 行目で失敗し、14 行目で __kmpc_end_taskq() を呼び出し、作業スレッドになります。T エントリー test1_taskq() を次に示します。

18 T-entry test1_taskq(taskq_thunk)

19 {

20   if (taskq_thunk->status == 1)

21   {

22      goto L2

23   }

24   if (*(taskq_thunk->shr->p_ptr) != 0)

25   {

26 L1:

27      task_thunk = __kmpc_task_buffer(taskq_thunk, test1_task)

28      task_thunk->p = *(taskq_thunk->shr->p_ptr)

29      if (__kmpc_task(task_thunk)!= 0)

30      {

31       __kmpc_taskq_task(taskq_thunk, 1)

32       T-return

33      }

...

41 L2:

42      *(taskq_thunk->shr->p_ptr) =

                (*(taskq_thunk->shr->p_ptr))->next

43       if (*(taskq_thunk->shr->p_ptr) != 0)

44       {

45         goto L1

46       }

47   }

48   __kmpc_end_taskq_task(taskq_thunk)

49   T-return

50 }

test1_taskq() の主な目的は、ループの制御構造を実行する過程で各タスクをエンキューすることです。ループのテストは 24 行目〜 43 行目にあたり、42 行目でポインターが更新されます。共有 p へのアクセスは、*(taskq_thunk->shr->p_ptr) をもって実現されます。

反復の作業をエンキューする前に、ライブラリー・ルーチン __kmpc_task_buffer() (27 行目) が呼び出され、task_thunk を作成し、taskq_thunk に基づき初期化します。T エントリー test1_task() のアドレスは、作業をデキューして実行する作業スレッドのために task_thunk にも格納されます。captureprivate セマンティクスを満たすために、28 行目でタスクの task_thunk に格納されている p のプライベート・コピーに共有変数 p の値をコピーします。

実際のタスクのエンキューは、29 行目でライブラリー・ルーチン __kmpc_task() によって行われます。戻り値ゼロは、キューがいっぱいではなく、次のタスクをエンキューできることを示します。戻り値が非ゼロの場合、キューはいっぱいとなり、taskq の実行が停止され (スレッドは作業スレッドとなり)、潜在的に異なるスレッドによって後で再開されることを示します。

31 行目のライブラリー・ルーチン __kmpc_taskq_task() は、この目的のために taskq_thunk をエンキューします。後でこれをデキューする作業スレッドが、41 行目の L2taskq の実行を再開します。これを実現するために、ジャンプテーブルの値 (例では、整数 1) が引数として __kmpc_taskq_task() に渡されます。

この値は taskq_thunk に格納され、この呼び出しサイトを一意に識別しなければなりません。これは、同じ taskq に複数のタスクが囲まれている場合があるためです。また、ゼロは taskq の最初の実行用に予約されているため、この値は非ゼロでなければなりません。

この値に基づき、ジャンプテーブル (20 行目〜 23 行目) は、現在の test1_taskq() の実行が最初か、停止された実行の継続かを判断し、正しい場所に実行を移します。

作業スレッドが task_thunk をデキューした後、test1_task() のアドレスを抽出して、そこに格納されているタスクを実行します。この T エントリーは次のとおりです。

36 T-entry test1_task(task_thunk)

37 {

38   do_work1(task_thunk->p)

39   T-return

40 }