• Showing Page History #49795
  • Showing Page History #49501

Show page source of オープンソース化された並列化テンプレートクラスライブラリ「Intel_Threading_Building_Blocks」入門_p3 #49795

[[PageNavi(NavigationList)]]



==== 要素数が分かっているデータ群に対する反復処理の並列実装(forループの並列化) ====


 並列処理が有効な典型的な例として、配列や各種コンテナに格納されたデータに対し、始点と終点を指定して次々と反復処理を行う、というパターンがある。'''リスト2'''はその典型的なパターンで、要素数がそれぞれdimである配列aと配列bに対し、おのおのの要素を足し合わせる処理をするものだ。


====== リスト2 典型的な反復処理の例:配列どうしの加算 ======

{{{
void VectorAdd( double* a, double* b, int dim ) {
    for( int i = 0; i  dim; i++ ) {
        a[i] = a[i] + b[i];
    }
}
}}}


 このような反復処理を実装したアルゴリズムが、TBBの「parallel_for」テンプレート関数だ。parallel_forテンプレート関数は、次の'''図3'''のような処理を行う。
[[Thumb(b5e78af860f22a0f0fedf2e395350ce9.png, caption=図5 parallel_forテンプレート関数の動作)]]



 parallel_forテンプレート関数の引数は、反復処理の範囲を表すオブジェクト(「Range」クラスの派生オブジェクト)と、反復して行う処理を定義した関数オブジェクトの2つだ。parallel_forテンプレート関数は、与えられたRangeオブジェクトを適切に分割し、分割したオブジェクトを引数として関数オブジェクトを実行する、という処理を行う。TBBにはRangeクラスの派生クラスとして、閉区間(ループの開始点と終了点)を表す「blocked_range」や、2次元の範囲を表す「blocked_range2d」といった汎用的なオブジェクトがあらかじめ用意されているので、これらから適切なものを選択して使用すればよい。もちろん、独自のRange派生クラスを定義して使用することも可能だ。


 たとえば、'''リスト2'''の処理をparallel_forテンプレート関数を用いて実装すると、次の'''リスト3'''のようになる。


====== リスト3 リスト2の処理をTBBで実装した例 ======

{{{
#include "tbb/parallel_for.h"
#include "tbb/blocked_range.h"

class VectorAdder {
    public:
        double* vec1;
        double* vec2;

        VectorAdder( double* a, double* b ) :
        vec1(a),
        vec2(b)
        {}

    void operator() ( const tbb::blocked_rangeint r ) const {
        for( int i = r.begin(); i != r.end(); i++ ) {
            vec1[i] = vec1[i] + vec2[i];
        }
    }
};

void ParallelVectorAdd( double* a, double* b, int dim ) {
    tbb::blocked_rangeint range = tbb::blocked_rangeint(0, dim, 100);
    VectorAdder body = VectorAdder(a, b);
    tbb::parallel_for( range, body );
}
}}}

==== パイプライン処理の並列化・ソースコード詳細解説 ====


 それでは、このコードについて詳しく解説していこう。まず、parallel_forテンプレート関数は「parallel_for.h」で定義されており、利用の際はこのヘッダーファイルをincludeしておく必要がある。また、後述する「blocked_range」クラスも利用しているので、こちらが宣言された「blocked_range.h」も同様にincludeする。
{{{
#include "tbb/parallel_for.h"
#include "tbb/blocked_range.h"
}}}


 次に、実行したい処理を行う関数オブジェクトを用意する。ここでは配列同士の加算処理を行う「!VectorAdder」クラスを作成している。処理に必要な変数等はクラスのメンバー関数として用意しておき、オブジェクトのコンストラクタで初期化を行う。
{{{
class VectorAdder {
    public:
        double* vec1;
        double* vec2;

        VectorAdder( double* a, double* b ) :
        vec1(a),
        vec2(b)
        {}
}}}


 parallel_forテンプレート関数で並列処理を実装する際に、キモとなるのがoperator()関数である。operator()関数はデータに対する処理を実装する関数で、引数には処理すべきデータ範囲を表すRange派生クラス型のオブジェクトを取る。ここではint型の閉区間を示すblocked_rangeintクラスを用いている。Rangeオブジェクトに対し、begin()関数を呼ぶことで反復処理すべき最初のデータを、end()関数を呼ぶことで最後のデータを取得できるので、この範囲でループを実行すればよい。
{{{
    void operator() ( const tbb::blocked_rangeint r ) const {
        for( int i = r.begin(); i != r.end(); i++ ) {
            vec1[i] = vec1[i] + vec2[i];
        }
    }
};
}}}


 以上のように関数オブジェクトを定義したら、あとはRangeオブジェクトと関数オブジェクトを作成し、それを引数にparallel_forテンプレート関数を呼び出せばよい。
{{{
void ParallelVectorAdd( double* a, double* b, int dim ) {
    tbb::blocked_rangeint range = tbb::blocked_rangeint(0, dim, 100);
    VectorAdder body = VectorAdder(a, b);
    tbb::parallel_for( range, body );
}
}}}


 まず、Rangeオブジェクトを作成する。関数オブジェクトの引数にはblocked_rangeint型のオブジェクトが渡されるので、ここでも同じ型のオブジェクトを作成する。なお、blocked_rangeのコンストラクタの引数は次のようになっている。
{{{
template typename Value class blocked_range {
  :
  :
    blocked_range( Value begin, Value end, size_type grainsize=1 );
  :
  :
}}}


 ここで「Value」はテンプレートで指定した型、「begin」は反復を開始する値、「end」は反復を終了する値である。また、「grainsize」はループを分割する際の粒度を指定する。通常は100~1000程度を指定すると良いようだ。


 '''リスト3'''の例では、0から次元数(この例では変数「dim」に相当)-1までの整数に対して反復処理を行うため、引数にはそれぞれ「0」および「dim」を指定してblocked_rangeオブジェクトを作成し、!VectorAdder型のオブジェクトとともにparallel_for関数に与えることで並列処理を実行している。


 なお、上記で紹介した!VectorAdd関数および!ParallelVectorAdd関数を用いて、要素数が52428800(50×1024×1024)の配列の加算を行ったところ、その処理時間は次の'''表1'''のようになった。並列化を行うことで、大幅な高速化が行えていることが分かる。
{{{ html
<h6>表1 VectorAddおよびその並列版であるParallelVectorAddの実行パフォーマンス</h6>
<table class="wikitable" border="1">

<tr><th>関数</th><th>処理時間</th></tr>
<tr><td>VectorAdd(非並列版)</td><td>78ミリ秒</td></tr>
<tr><td>ParallelVectorAdd(並列版)</td><td>125ミリ秒</td></tr>

</table>
}}}


 また、TBBにはループの並列化を行うアルゴリズムとしてparallel_forテンプレート関数のほか、並列プレフィックス演算を行うparallel_scanや、リダクション演算を行うparallel_reduceといったテンプレート関数も用意されている。これらについても、基本的にparallel_forテンプレート関数と同じような方法で利用が可能だ。


[[PageNavi(NavigationList)]]