• Showing Page History #49524

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

[[PageNavi(NavigationList)]]


==== 要素数が分からないデータ群に対する反復処理の並列実装(whileループの並列化) ====
 先で解説したparallel_forを使用した並列処理は、あらかじめ処理するデータの個数が決まっている場合にのみ利用できる。一方、次に紹介するparallel_whileは入力ストリームに対する処理など、処理したいデータの個数が事前に分からない場合でも利用できる並列アルゴリズムだ。

 たとえば次の'''リスト4'''は、ファイルから1行ずつテキストを読み出し、正規表現で指定した特定のキーワードを含む行の行番号とその内容を出力するというプログラムだ。この場合、データの個数(ここでは行数)を調べるにはストリームを最後まで読まなければならず、データが非常に多い場合は現実的ではない。parallel_whileはこのような処理を並列化するのに有用である。

====== リスト4 ストリーム入力に対する処理の実装例 ======

{{{
#includeiostream
#includefstream
#includestring
#inclue "boost/regex.hpp"

bool SearchText(ifstream is, string keyword) {
    boost::regex rex;
    boost::match_resultsconst char* results;
    string buf;
    int lineNumber = 1;

    rex = keyword;
    while( is getline(is, buf) ) {
        if( boost::regex_search(buf.c_str(), results, rex) ) {
            cout lineNumber ": " buf endl;
        }
        lineNumber++;
    }
    cout "read " lineNumber - 1 " lines." endl;
    return true;
}
}}}

 '''リスト4'''を、parallel_whileを使用してTBBで並列実装したものが次の'''リスト5'''だ。

====== リスト5 リスト4の処理をTBBで並列実装した例 ======

{{{
#includeiostream
#includefstream
#includestring

class LinedString {
public:
    string contents;
    int lineNumber;
};

class LinedStream {
    istream is;
    int num;

public:
    bool pop_if_present( LinedString lstr ) {
        if( getline(is, lstr.contents) ) {
            num = num++;
            lstr.lineNumber = num;
        } else {
            return false;
        }
        return true;
    }

    LinedStream(istream inputStream) :
        is(inputStream),
        num(1)
    {}
};

class Searcher {
    string keyword;
public:
    void operator()( LinedString lstr ) const;
    Searcher(string key): keyword(key) {}
    typedef LinedString argument_type;
};

void Searcher::operator()( LinedString lstr ) const {
    boost::regex rex;
    boost::match_resultsconst char* results;

    rex = keyword;
    if( boost::regex_search(lstr.contents.c_str(), results, rex) ) {
        cout lstr.lineNumber ": " lstr.contents endl;
    }
}

bool ParallelSearchText(istream is, string keyword) {
    tbb::parallel_whileSearcher w;
    LinedStream stream(is);
    Searcher body(keyword);
    w.run( stream, body );
    return true;
}
}}}

 parallel_forなどと同様、parallel_whileでも関数オブジェクトとして実行すべき処理を渡すが、parallel_forと異なるのはparallel_whileは関数ではなくテンプレートクラスになっている点だ。テンプレート引数としては実行すべき処理を実装したクラスを取る。このparallel_while型のオブジェクトを生成し、引数に入力ストリームと関数オブジェクトを与えて「run」メンバー関数を実行することで、並列処理が行われる。

 '''リスト5'''では、並列実行すべき処理を実装したクラスとして「Searcher」クラスを、入力ストリームとして「LinedStream」クラスを用意している。

{{{
bool ParallelSearchText(istream is, string keyword) {
    tbb::parallel_whileSearcher w;
    LinedStream stream(is);
    Searcher body(keyword);
    w.run( stream, body );
    return true;
}
}}}

 parallel_whileに与える入力ストリームは、ストリームからデータを取り出す「pop_if_present」というメンバー関数を備えている必要がある。pop_if_present関数は引数に「argument_type」(後述)で指定した型のオブジェクト(の参照)を取り、次に処理すべきデータをこのオブジェクトに格納してtrueを返す。また、もし次に処理すべきデータがない場合はfalseを返せば良い。

 なお、'''リスト5'''の例では「行番号」と「その行に含まれる文字列」という2つのデータを格納するクラス「LinedString」を用意し、これをargument_typeとして使用している。

{{{
class LinedString {
public:
    string contents;
    int lineNumber;
};

class LinedStream {
    istream is;
    int num;

public:
    bool pop_if_present( LinedString lstr ) {
        if( getline(is, lstr.contents) ) {
            num = num++;
            lstr.lineNumber = num;
        } else {
            return false;
        }
        return true;
    }

    LinedStream(istream inputStream) :
        is(inputStream),
        num(1)
    {}
};
}}}

 並列実行すべき処理を実装するクラスには、operator()に加えてその引数の型を「argument_type」として定義しておく必要がある。

 '''リスト5'''の場合、入力ストリームからデータをLinedString型で取り出すので、argument_typeをLinedStreamとして定義している。また、operator()内では取り出したLinedStreamオブジェクトに対する処理を記述している。

{{{
class Searcher {
    string keyword;
public:
    void operator()( LinedString lstr ) const;
    Searcher(string key): keyword(key) {}
    typedef LinedString argument_type; // operator()の引数として利用する型を「argument_type」として定義しておく
};

void Searcher::operator()( LinedString lstr ) const {
    boost::regex rex;
    boost::match_resultsconst char* results;

    rex = keyword;
    if( boost::regex_search(lstr.contents.c_str(), results, rex) ) {
        cout lstr.lineNumber ": " lstr.contents endl;
    }
}
}}}

 なお、parallel_whileを使用した並列化の場合、ループ内で実行する処理の内容によってはあまりパフォーマンス向上が見られない場合がある。たとえば今回の例は1行分のテキストに対する正規表現検索という比較的軽めの処理であるため、次の'''表2'''のように並列化の効果は若干にとどまっている。

{{{ html
<h6>表2 10万行のテキスト(Webサーバーのアクセスログファイル)に対し、「MSIE [78]\..; Windows NT 5.1;」という正規表現にマッチする行を検索するのにかかった時間</h6>
<table class="wikitable" border="1">

<tr><th>関数</th><th>処理時間</th></tr>
<tr><td>SearchText(非並列版)</td><td>1389ミリ秒</td></tr>
<tr><td>ParallelSearchText(並列版)</td><td>1294ミリ秒</td></tr>

</table>
}}}
'''[//sourceforge.jp/magazine/09/08/21/1128207 オープンソース化された並列化テンプレートクラスライブラリ「Intel Threading Building Blocks」入門]'''[http://sourceforge.jp/magazine/09/08/21/1128207 Page 1: Intel Threading Building Blocksが持つ機能][http://sourceforge.jp/magazine/09/08/21/1128207/2 Page 2: TBBのメリット、TBBを用いた並列アプリケーションの設計と実装][http://sourceforge.jp/magazine/09/08/21/1128207/3 Page 3: 要素数が分かっているデータ群に対する反復処理の並列実装(forループの並列化)]'''[http://sourceforge.jp/magazine/09/08/21/1128207/4 Page 4: 要素数が分からないデータ群に対する反復処理の並列実装(whileループの並列化)]'''[http://sourceforge.jp/magazine/09/08/21/1128207/5 Page 5: パイプライン処理の並列化][http://sourceforge.jp/magazine/09/08/21/1128207/6 Page 6: パイプライン処理の並列化・ソースコード詳細解説][http://sourceforge.jp/magazine/09/08/21/1128207/7 Page 7: 高い抽象度でアルゴリズムを実装できるTBB

]

[[PageNavi(NavigationList)]]