並列化すべき個所を自動診断する新ツール「インテル Parallel Advisor」を使ってみよう 4ページ

並列化によって発生する問題を検出する「Correctness」 Analysis

　インテルスレッディング・ビルディング・ブロック（TBB）やインテル Cilk Plusといった並列化技術を用いてプログラムを並列化する際、注意しなければならないのがメモリやスレッドの管理だ。並列プログラムでは複数のスレッドが同一のメモリ空間を参照するため、たとえば同時に複数のスレッドが同じ変数に異なる値を書き込んだり、書き込みと読み出しが同時に発生する、といった問題が発生することがある。これらは「メモリアクセスの競合」などと呼ばれ、致命的な問題を引き起こすことが多いため必ず対処を行う必要がある。このような問題を事前に検出する機能がCorrectness Analysisだ。

Correctness Analysisを使う

　Correctness AnalysisはAdvisor Workflowウィンドウの「4. Check Correctness」から呼び出せる。「Start」ボタンをクリックすると対象とするプログラムが実行され、データが集計されて結果が「Correctness Report」画面に表示される。なお、Correctnessを実行する際はコンパイラによる最適化を無効にしたデバッグ設定でビルドしたプログラムを使用することが推奨されている。また、このときプログラムの実行パフォーマンスは大きく低下するため、繰り返し数が少なくなるよう入力データや設定を変更しておくと良い。

　実行が完了すると、「Correctness Report」画面にレポートが表示され、問題が検出された個所や、確認しておくべき個所がリスト表示される。また、リストされている項目を選択すると、対応するソースコードが画面下部に表示される（図10）。

図10 メモリアクセスの競合を表示する「Correctness Report」画面

　また、リストされている項目をダブルクリックするとその部分のソースコードとともにCall Stackやそれぞれの関係といったより詳細な情報が「Correctness Source」画面で表示される（図11）。

図11 ソースコードとともに問題のより詳細な情報が表示される「Correctness Source」画面

　さて、今回の例の場合、ソースコード中の「random.cxx」内の「initialized」変数で競合が発生していることが分かる。具体的には、random.cxx内25行目で変数に対し書き込み操作を、23行目で読み出し操作を行っており、これらが複数のスレッド間で同時に行われる可能性があるという問題だ。

　この場合、読み込みと書き込みが同時に発生しないように排他制御を行えば良い。複数スレッド間で排他制御を行うにはmutexやクリティカルセクションといった機能を使用することが多いが、この段階ではこれらを使用して実際に実装を行う必要はなく、Annotationを追加するだけでよい。具体的には、排他制御を開始すべき個所に「ANNOTATE_LOCK_ACQUIRE」を、終了するべき個所に「ANNOTATE_LOCK_RELEASE」を挿入する。

Random::
Random()
{
    ANNOTATE_LOCK_ACQUIRE(0);　　←ロックを取得
    if (!initialized) {
        std::srand((unsigned int)time(0));
        initialized = true;
    }
    ANNOTATE_LOCK_RELEASE(0);　　←ロックを解放
}

　Annotationを追加したらプログラムを再コンパイルし、再度Correctness Analysisを実行して問題が解決されているかを確認しておく。今回の例の場合、この修正のみで問題は解決できた。

Annotationを並列化コードに置き換える

　以上のステップにより、プログラム中で並列化を行うべき個所と、その部分を並列化した際に問題が発生する個所が特定できた。あとは、これらの個所をTBBやCilk Plusといった並列化技術を用いて並列化し、また適切に排他制御を行うようにコードを修正すればよい。

　この作業については完全にユーザーの手にゆだねられているが、Cilk Plusを用いる場合、ヘルプの「Intel(R) Parallel Advisor 2011」?「Adding Parallelism to Your Program」?「Adding Intel Cilk Plus Code to Synchronize Shared Resources and Create Tasks」以下にヒントとなる情報がまとめられている。詳細はこちらを確認してほしいが、たとえば今回のサンプル（リスト1）のように「ANNOTATE_SITE_BEGIN」の直後にforループがある場合、このforループを「cilk_for」に置き換えればよい（リスト2）。

リスト1 ANNOTATE_SITE_BEGIN直後にforループが来るコード

int main()
{
    Grid::initialize();
    ANNOTATE_SITE_BEGIN(main_loop);
    for (int i = 0; i != 100; ++i) {
        ANNOTATE_TASK_BEGIN(main_generate);
        generate(Solver::METHOD_BOX_LINE);
        ANNOTATE_TASK_END(main_generate);
        }
    ANNOTATE_SITE_END(main_loop);
    return 0;
}

リスト2 リスト1のコードをcilk_forを用いて並列化する例

int main()
{
    Grid::initialize();
    // ANNOTATE_SITE_BEGIN(main_loop);
    cilk_for (int i = 0; i != 100; ++i) {
        // ANNOTATE_TASK_BEGIN(main_generate);
        generate(Solver::METHOD_BOX_LINE);
        // ANNOTATE_TASK_END(main_generate);
    }
    // ANNOTATE_SITE_END(main_loop);
    return 0;
}

　また、リスト3のようなロックが必要とされる個所については、Windowsのクリティカルセクションを用いた排他制御に置き換えれば良い。

リスト3 ロックが必要な個所の例

Random::
Random()
{
    ANNOTATE_LOCK_ACQUIRE(0);
    if (!initialized) {
        std::srand((unsigned int)time(0));
        initialized = true;
    }
    ANNOTATE_LOCK_RELEASE(0);
}

　たとえばリスト3のコードは、リスト4のように実装できる。

リスト4 リスト3をクリティカルセクションを用いて実装する例

Random::
Random()
{
    // ANNOTATE_LOCK_ACQUIRE(0);
    // 事前に「section」変数は適切に初期化しておく必要があるので注意
    EnterCriticalSection(section);　　←クリティカルセクション開始
    if (!initialized) {
        std::srand((unsigned int)time(0));
        initialized = true;
    }
    LeaveCriticalSection(section);　　←クリティカルセクション開始
    // ANNOTATE_LOCK_RELEASE(0);
}

　なお、以上の手順で並列化を行ったプログラムの実行速度を「timeit」というWindows Server 2003 Resource Kit Toolsに付属するツールで測定し比較したところ、実行時間がほぼ半分になるという結果が得られた（リスト5）。速度に使用したPCはCPUとして2コアのCore 2 Duo E6550（2.33GHz）を搭載したものだ。Suitability Analysisでの診断結果どおり、ほぼ2倍近いパフォーマンス向上が確認できる。

リスト5 実行速度の測定

> timeit sudoku_org.exe > nul　　←オリジナル版の実行速度を測定
　：
　：
Version Number:   Windows NT 6.1 (Build 7600)
Exit Time:        9:32 pm, Friday, October 1 2010
Elapsed Time:     0:00:01.200　　←プログラムの実行時間
Process Time:     0:00:01.045
System Calls:     123235
Context Switches: 159034
Page Faults:      1076
Bytes Read:       11284
Bytes Written:    70036
Bytes Other:      2580
　：
　：
> timeit sudoku.exe > null　　←並列化版の実行速度を測定
　：
　：
Version Number:   Windows NT 6.1 (Build 7600)
Exit Time:        9:32 pm, Friday, October 1 2010
Elapsed Time:     0:00:00.683　　←プログラムの実行時間
Process Time:     0:00:01.138
System Calls:     180170
Context Switches: 126604
Page Faults:      1844
Bytes Read:       324843
Bytes Written:    43004
Bytes Other:      7034

前のページへ 1 2 3 4 5 次のページへ