ノート
訪問者数　923　　　　　　最終更新　2013-01-18 (金) 16:31:10

2013/12/29　OpenMP メモ2 〜 forループでない並列 †

↑

OpenMPでのforループ自動並列の条件 †

OpenMPの最も簡単で便利な使い方は、forループの自動並列化だろう。一定の条件を満たすforループは、ほとんど何も考えなくても並列化される。

forループが並列化される条件は、きちんと確認してリストする必要があるが、マニュアルによると

ループ構文の文法は、以下の通りです。
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
#pragma omp for [clause[[, ] clause] ...]  new-line
          for-loops
- - - - - - - - - - - - - - - - - - - - - - - - - - - -

ここで、指示節（clause）は、以下のいずれかです。
  private（list）
  firstprivate（list）
  lastprivate（list）
  reduction（operator： list）
  schedule（kind[, chunk_size]）
  collapse（n）
  ordered
  nowait

for 指示文は、関連付けられたすべての for-loops の構造に対する制限があります。具体的には、関
連付けられたすべての for-loops は、以下の標準形でなければなりません。

- - - - - - - - - - - - - - - - - - - - - - - - - - - -
for  (init-expr; test-expr; incr-expr)  structured-block
- - - - - - - - - - - - - - - - - - - - - - - - - - - -

init-expr     以下のいずれかです。
    var = lb
    integer-type var = lb
    random-access-iterator-type var = lb
    pointer-type var = lb
test-expr     以下のいずれかです。
    var relational-op b
    b relational-op var
incr-expr    以下のいずれかです。
    ++var
    var++
    --var
    var--
    var += incr
    var -= incr
    var = var + incr
    var = incr + var
    var = var - incr
var    以下のいずれかです。
    ・符号付き、または符号なしの整数型の変数
    ・C++の場合、ランダムアクセスイテレータ型の変数
    ・C の場合、ポインタ型の変数
      この変数が、何らかの形で共有されていない場合は、ループ構文内では暗黙的
      にプライベート化されます。
      この変数は、for-loop の実行中に incr-expr 以外で変更してはいけません。
      この変数がループ構文で lastprivate と指定されない限り、ループ後の値は、
      不定となります。
relational-op     以下のいずれかです。
    <
    <=
    >
    >=
lb と b     以下のいずれかです。
    var の型と一致した型のループ不変式
incr     ループ不変の整数式


この標準形では、最も外側のループの実行前に、すべての関連付けられたループの繰り返し数を計算
することができます。この計算は、それぞれのループに対して整数型で行われます。この型は、次の
ように var の型から決まります。
・ もし、var が整数型の場合、型は var の型です。
・ C++において、var がランダムアクセスイテレータ型の場合、型は、var の型の変数に適用される
    std::distance が使用する型になります。
・ C において、var がポインタ型の場合、型は ptrdiff_t となります。

繰り返し数の計算に必要な中間結果が、上で決まる型で表現できない場合、振舞いは丌定となります。

lb、b、または incr の式の評価中に暗黙的に同期をとることはありません。lb、b、または incr の式の
順序や回数、副作用が起こるかどうかは規定されていません。

これらの条件のポイントは、並列化したいループに入る前に（ループの外側で）、繰り返し実行の形（何が何回）が決まっていることである。具体的には、forループの回数がインデックス（指標、変数iなど）からループに入る前に計算できることになるだろう。

もう１つ、ループ終了条件で等号「==」が許されていないことがある。

↑

リンクトリストデータの並列処理 †

一般にリンクトリスト（以下「リスト」と呼ぶ）のような動的なデータ構造は、要素の追加・削除が動的に行われるので、forループの自動並列化の仕組には載せにくい。ループの本体処理で要素の追加・削除がある場合は、そもそも始端・終端・増分を指定するfor文によるループ制御すら難しい。

しかし、並列化対象部分での動的な要素追加・削除を行わないリストであれば、原理的には安心して並列化が可能である。（コンパイル時には並列構造は決められないが、実行中でもループに入る前に決めることはできる）。　ちなみに、なぜこのような場合でのリンクトリスト構造を使っている理由は、並列か対象部分ではなくそれ以外の部分において動的な要素追加・削除が必要になるからである。　つまり、並列化対象部分ではデータ要素は固定されており、追加・削除されることは無いような（特定の）場合である。　幸い、今目前にあるプログラムは、この条件を満たしている。　具体的には、時刻ステップを追ったシミュレーションプログラムであり、ある時刻でのシステム状況から要素の追加・削除の条件を計算し、それに基づいて追加・削除の処理を行う。そこでは、システム状況から追加・削除のための条件の計算を行う部分の計算量が多く、一時刻ステップの計算の大半を占めるため、並列化による時間短縮の効果が予測されるのだが、該当部分の中では要素の追加・削除は行わない。また更には、該当部分ではシステム状況値の変更は行っておらず、単に追加・削除の判定に必要な条件の計算のみを行っている。　従って、該当部分の並列化は安心して考えられる。システム状況値のロックすら必要がない。

（昨年度の卒業研究では、上記のことを理解した上で、システム状況値をリンクトリストから配列にコピーして、その上でforループの自動並列化を適用した。）

リンクトリスト構造を生かした上で、並列化を実現する方法として、いくつかのアプローチが考えられる。

  1. forループの自動並列化を使えるように、リンクトリストを追うforループの制御に必要な情報を加える
  2. forループの並列化ではなく、スレッドを所定の個数（たとえばCPUコア数）生成し、リンクトリストを追うループをスレッド数に応じて分割して、それぞれのスレッドにフィードして処理させる。

例題として、次のプログラムを出発点とする。

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int d;                         /* 整数nを保持 */
  struct node *next;     /* 次のノードへのポインタ */
} node_t;
node_t *first = NULL;

void Append(int n);
void Print();

void Append(int n) {  /* リストの後尾にノード追加 */
  node_t *p;
  node_t *s;
  s = (node_t *)malloc(sizeof(node_t));
  s->d = n;
  if (first==NULL) {
    first = s;
  } else {
    for (p=first; p->next!=NULL; p=p->next);
    p->next = s;
  }
}

void Print() {     /* リスト全体を印刷 */
  node_t *p;

  for (p=first; p!=NULL; p=p->next) {
    printf("%d\n", p->d);
  }

}

main () {
  int i;
  for (i=0; i<20; i++) {   /* 20個追加したリストを作る */
    Append(i);
  }
  Print();
}

前述のようにforループの回数はループ開始前に決まっているので、あらかじめ数えておいてforループのインデックスを整数でカウントするようにする。　関数Printを次のように修正する。また、簡単のためリストの長さは20ではなくて8にしておく。

void Print() {
  node_t *p; 
  int i, max;   /* openMPでループ回数を数えられるように、あらかじめリストの個数を数える */
  max = 0;
  for (p=first; p!=NULL; p=p->next) {
    max++;
  }
  printf("max %d\n", max);

  p = first;                            /* ループ先頭でpをfirstにセット（今までforの内だった）  */
#pragma omp parallel for     /* 「parallel for」＝for分の自動並列化機能を使う */
  for (i=0; i<max; i++) {           /*  この場合、リストの長さの分だけスレッド生成するはず  */
    printf("%d\n", p->d);
    p=p->next;                     /*  ループ実行本体の最後で、pを１つ進める（今までforの内だった）  */
  }
}

これはうまく行かなかった。問題は変数pの扱いにある。pはprivateとすればp=p->nextが効かなくなるし、globalとすればいつ設定された値であるのかによって変わってしまう（各スレッドがpを更新するからその更新とprintfでの読み取りとのタイミングによって変わる）。　つまり、こんな手抜きではうまくいかない。

なお、同じロジックを、for文の書き方（初期化、ステップインクリメント）を凝ることでも実現できるのだが、

  for (i=0, p=first; i<max; i++, p=p->next) {

こちらはopenMPとしては構文エラーになる。

そこで、代案として、リンクトリストをたどることによって各スレッドの処理対象を決めるのではなくて、処理対象は並列処理に入る前に決めてしまい、並列化部分では既に用意された処理対象を受け取って並列に処理する、という方法を考えることができる。

この時、各スレッドで処理する対象（＝処理するリストの先頭）だけでなく、リストの終りも、うまく教えてやるのがよかろう。２つの方法が考えられるが（(1)リストの最終要素へのポインタを教えてやる、(2)リストの要素の個数を教えてやる）、どちらでもほとんど変わらないと思う。ここでは、リストの個数を教えてやることにする。　（2013-01-18に加筆）

void Print() {
  node_t *p;
  int i, max;
  int percore, plusone, j;
  node_t *a[8];                 /* スレッド毎に処理させる先頭ノードへのポインタ  */
  int len[8];                   /* スレッドごとに処理させるノードの個数 （2013-01-18追加) */
  node_t *q;
  int myID;                       /* スレッド番号 ０〜７ */

  max = 0;
  for (p=first; p!=NULL; p=p->next) {     /* リスト長（ノードの個数）を数える  */
    max++;
  }
  if (max < 8) {        /* リスト長がスレッド数より小さい時の処理が面倒なのでさぼります  */
    printf("max %d < 8\n", max);
    exit(1);
  } else {
    percore = max/8;   /* コア数＝スレッド数8で決め打ちにしておきます。スレッド当りの処理ノード数  */
    plusone = max - (percore*8);   /* 割切れないので、1ノードずつ余分にやらせるスレッドの数  */
    printf("max %d, percore %d, plusone %d\n", max, percore, plusone);
  }

 p = first;
 for (i=0; i<plusone; i++) {      /* 割切れないために１ノード余分にやらせるスレッドについて  */
   a[i] = p;                                /*    先頭ノードへのポインタを配列aに記憶  */
   len[i] = percore+1;                      /*    このスレッドで処理するノードの個数   (=percore+1) (2013-01-18加筆) */
   printf("i %d, p->d %d\n", i, a[i]->d);
   for (j=0; j<percore+1; j++) p=p->next;   /*    このスレッドが処理すべき個数分だけリンク上を進める */
 }
 for (i=plusone; i<8; i++) {      /* 残りのスレッドについて  */
   a[i] = p;                                /*    先頭ノードへのポインタを配列aに記憶  */
   len[i] = percore;                      /*    このスレッドで処理するノードの個数   (=percore) (2013-01-18加筆)  */
   printf("i %d, p->d %d\n", i, a[i]->d);
   for (j=0; j<percore; j++) p=p->next;   /*    このスレッドが処理すべき個数分だけリンク上を進める */
  }

  omp_set_num_threads(8);      /* 実際のスレッド数を8に設定　（なぜこれが要るかよく分からないが） */
  #pragma omp parallel private(q, myID, i)    /* 「parallel for」ではなくて「parallel」で終り。つまりforの自動並列化でなく、以下のブロックをmax_thread数分だけ並列に作る。  */
                                                                 /*  処理内容の割当はたとえばスレッドIDを用いて自分でプログラムする。   */
                                                                /* なお、private変数の指定を忘れないこと  */
  {                   /* このブロック開始は必要。さぼるとpragma omp parallelが１行分しか効かない  */
    myID = omp_get_thread_num();        /* 自分のスレッド番号０〜７を受け取る  */
    i = 0;                              /* iはこのスレッドで処理する個数を数えるカウンタ (2013-01-18加筆）*/
    for (q=a[myID]; /*q!=NULL*/ i<len[myID] ; q=q->next) {   /* 配列a上で自スレッドに割り当てられた開始ノードから  */
                                                             /*   forループ終了条件をカウンタiに変更した　(2013-01-18変更) */
      printf("%d  %d\n", myID, q->d);              /*     リストの最後（nextがNULL）まですべて印刷  */
      i++;                               /* iをカウントアップ　(2013-01-18加筆) */
    }                                                               /*     自スレッド分の最後の検出は面倒なのでさぼっている  */
  }
}

これの実行結果は、

max 20, percore 2, plusone 4

各スレッドの処理リストの先頭は

スレッド0, p->d 0
スレッド1, p->d 3
スレッド2, p->d 6
スレッド3, p->d 9
スレッド4, p->d 12
スレッド5, p->d 14
スレッド6, p->d 16
スレッド7, p->d 18

それぞれのスレッドの処理（＝リストの印刷）は (以下2013-01-18変更)

5  14
5  15
3  9
3  10
3  11
4  12
4  13
1  3
1  4
1  5
0  0
0  1
0  2
6  16
6  17
7  18
7  19
2  6
2  7
2  8

となった。このやり方を踏襲すればよさそうである。

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-01-18 (金) 16:31:10 (2152d)