ループ分割

概要

OpenMPで想定しているマルチスレッド化方式である。

これは、配列等を処理するためのループを、複数のスレッドで同時に処理することで、処理時間を短縮しようとするものである。一般に、行列演算や画像処理等で使用される事が多い。

OpenMPは、単純なルールに則りループを分割し、マルチスレッド化するだけである。そのため、所定のルールに沿ったコーディングになっている部分であれば、OpenMPによる高速化が可能である。だが、その「所定のルール」という制約が厳しく、こういっては何だが、業務系のアプリケーションでは、あまり利用できるパターンは無いのではないかと思われる。

理論

配列全体を処理するループを、複数スレッド（すなわち複数個CPU）で処理することで、処理時間の短縮を図る。

例えば、要素数20個の配列を処理するループが存在した場合、それを4つのスレッドで5個づつ分担して処理するようにすれば、処理時間が4分の1になるものと考えられる。（無論CPUが4つ無かった場合には、処理時間の短縮は望まれない）

図で書けば下記のようになる。

ループ分割は、スレッドに対して処理させるデータを割り当てる方法の違いにより、下記3つの種類に分類することができる。

ブロック分割

サイクリック分割

ブロック・サイクリック分割

上記の用語は俺の独創ではない。MPIで使用されていたものだ。

ブロック分割とは、上記の絵のように、各スレッドに対してある一部分の領域を担当させる方式である。

サイクリック分割とは、各スレッドに対して要素を一つずつ順番に、すなわちサイクリックに割り当てる方式である。図で表せば下記のようになる。

ブロック・サイクリック分割とは、ブロック分割とサイクリック分割の間を取った方式で、各スレッドに対して数個ずつ順番に有り当てる方式である。図で表せば下記のようになる。

一概にどの方式が一番いいと言うことはできない。処理の特性やスレッド数とデータ件数との比率を考え、その都度最適な方式を選択する必要がある。

実装

まずはOpenMPを用いない方式で、ブロック分割に基づき実装してみる。
#include "Thread.h"
#include <stdio.h>

class CFoo : public CThread
{
public:
  // 初期化
  void Initialize( int ThID, int ThCnt, int *pv, int len )
  {
    ThreadID = ThID;
    ThreadCount = ThCnt;
    pVec = pv;
    VecLength = len;
  };

  // スレッドのエントリポイント
  void run()
  {
    int i;

    // ブロック長を計算
    int BlockSize = VecLength / ThreadCount;

    // 処理対象範囲の下限を求める
    int R1 = BlockSize * ThreadID;

    // 処理対象範囲の上限を求める
    int R2 = R1 + BlockSize;

    // あまりは最後のスレッドにやらせておく
    if ( ThreadCount - 1 == ThreadID )
      R2 = VecLength;

    // 割り当てられたブロックを処理する
    for ( i = R1; i < R2; i++ )
      pVec[i] = ThreadID;
  };

protected:
  int ThreadID;    // スレッド番号（0から振り出す）
  int ThreadCount; // 総スレッド数
  int *pVec;       // 演算対象の配列
  int VecLength;   // 配列長
};

int main()
{
  int Vec[128] = { 0 };
  CFoo t0, t1, t2, t3;
  int i;

  // 128個のデータを4つのスレッドで処理する
  t0.Initialize( 0, 4, Vec, 128 );
  t1.Initialize( 1, 4, Vec, 128 );
  t2.Initialize( 2, 4, Vec, 128 );
  t3.Initialize( 3, 4, Vec, 128 );

  t0.start();
  t1.start();
  t2.start();
  t3.start();

  // 処理が終わるのを待ち合わせる
  Sleep( 1000 );

  // 処理結果を表示する
  for ( i = 0; i < 128; i++ )
    printf( "Vec[%d] = %d\n", i, Vec[i] );

  return 0;
}
上記は128個の要素を4つのスレッドで処理している。処理内容としては、自分が処理した配列要素に自分のスレッド番号を設定するようにしている。

最後に処理結果を画面に表示しているが、この直前で作業用スレッドの処理が終了するのをSleepで待ち合わせている。本来であれば、全スレッドの終了を待ち合わせるための仕掛けを作り込む必要があるのだが、ここでは簡略化のためにSleepで代用させてもらった。

同じ要領で、サイクリック分割について下記に示す。
  // スレッドのエントリポイント
  void run()
  {
    int i;

    // 割り当てられたブロックを処理する
    for ( i = ThreadID; i < VecLength; i += ThreadCount )
      pVec[i] = ThreadID;
  };
違いがあるのはCFoo::runだけなので、その部分だけ示した。

同様に、ブロック・サイクリック分割の場合も示す。
  // スレッドのエントリポイント
  void run()
  {
    int i, j;
    int BlockSize = 3;

    for ( i = BlockSize * ThreadID;
          i < VecLength;
          i += ( BlockSize * ThreadCount ) ) {
      for ( j = 0; j &ly; BlockSize; j++ ) {
        pVec[ i + j ] = ThreadID;
      }
    }
  };
次に、OpenMPを用いた場合の例を示す。
#include <stdio.h>
#include <openmp.h>

int main()
{
  int i;
  int Vec[128] = { 0 };

  #pragma omp parallel for
  for ( i = 0; i < 128; i++ ) {
        Vec[i] = omp_get_thread_num();
  }

  for ( i = 0; i < 128; i++ )
    printf( "Vec[%d] = %d\n", i, Vec[i] );

  return 0;
}
あっけないほど簡単である。

シングルスレッドでの動作を想定したプログラムの、マルチスレッド化したいループの前に、 #pragma omp parallel forを追記しただけである。

だが、これでもOpenMP対応のコンパイラで処理すると、上記pragmaを追記したループは、マルチスレッドで高速に処理されるようになる。

なおOpenMPを用いた場合、生成されるスレッドの数や、分割方法（ブロック分割やサイクリック分割など）を制御することはできない。必ずしも不可能というわけではないが、基本的には処理系や環境に合わせた最適な設定が自動的に使用される。

利用

このパターンの利用目的や利用できる状況などは、結構限られている。

まず利用目的だが、これは純粋に処理時間の短縮にある。複数の入出力に同時並行的に応答しなければならないとか、マルチスレッドで考えた方が明瞭簡潔だから、といった理由でこのパターンが使用されることはないと言っていい。

利用できる状況にも制約がある。配列の各要素に対する処理を並列で処理するのだから、各要素間に依存性のある処理をこの方法で並列化することはできないのだ。

例えば、次のような例を考えてみる。
for ( i = 0; i < 9; i++ ) {
  v[ i + 1 ] += v[i];
}
この処理では、配列の先頭から末尾に向かって要素を順番に加算している。このような処理を上述の方法で「並列化」してしまったら、処理内容が大幅に異なったものとなってしまう。

よって、各要素間に依存関係がある場合には、簡単には並列化できないと言うことができる。

<< 「マルチスレッド開発の傾向と対策」に戻る