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

　インテル Parallel Studio 2011に新たに搭載されたツール「インテル Parallel Advisor」は、並列化したいプログラムを関数・命令レベルで分析し、並列化すべき個所を提案する分析ツールだ。本記事ではこのインテル Parallel Advisorを使用し、実際にプログラムの分析や並列化を行う例を紹介する。

並列化を支援する3つの機能を搭載、5つのステップでプログラムを並列化

　プログラムを並列化することで、近年多くのコンピュータに搭載されているマルチコアCPUでパフォーマンス向上が見込める。しかし、プログラムを効率的に並列化するには並列化に関する知識や経験が必要であり、むやみやたらな並列化はパフォーマンスを低下させることにもつながる。

　たとえば、プログラムを並列化する場合、時間ののかかる処理を複数のスレッドに分割して並列実行する、というのが一般的であるが、スレッドの生成のオーバーヘッドが並列化によるパフォーマンス向上を上回る場合、パフォーマンスが悪化してしまう。また、マルチスレッドプログラムでは複数のスレッドが同時に同じ変数にアクセスする可能性があり、適切な排他制御などを行わずに単純に並列化を行った場合、これによる不具合が発生することも多い。

　そのため、プログラムの並列化を行う際にはプログラムを綿密に分析して並列化すべき個所を判断したり、実際に並列化を行ったプログラムを実行して問題点を探す、といったトライ＆エラーの作業が必要であった。Parallel Advisorは、このような面倒な手順を自動で行ってくれるツールである。

　Parallel Advisorの中核となっているのは、「Survey Analysis」と「Suitability Analysis」、「Correctness Analysis」という3つの機能である（表1）。

表1 Parallel Advisorの3つの機能

機能	説明
Survey Analysis	プログラムを実行してパフォーマンスを調査し、時間のかかっている個所を見つけ出す
Suitability Analysis	指定した個所を並列化した場合、どの程度のパフォーマンス向上が見込めるかを分析する
Correctness Analysis	指定した個所を並列化した場合に発生するであろう問題を検出する

　Parallel Advisorでは、次のような5つのステップでこれらを実行するというワークフローが想定されている（図1）。これにしたがって作業を行うことで、効率良くプログラムの並列化が行える。

図1 Parallel Advisorのワークフロー

　Parallel Advisorのそれぞれの機能は簡単に利用できるが、「Annotate Source」や「Add Parallel Framework」のステップではユーザーが並列化すべき個所に手動でコードを埋め込む必要があるため、若干の知識やノウハウが必要だ。そこで以下ではParallel Advisorに付属するサンプルを使用してワークフローやParallel Advisorの機能や使い方を紹介していく。

Parallel Advisorのドキュメント

　Parallel Advisorのドキュメントは、Visual Studioヘルプの「Intel(R) Parallel Studio 2011」?「Intel(R) Parallel Advisor 2011」内にまとめられている（図2）。また、ツールバーの「Open the Intel Parallel Advisor 2011 Getting Started Tutorial」ボタンをクリックすると、WebブラウザでParallel Advisorの概要およびチュートリアルが記述された文章が開かれる。ただし、こちらには必要最小限の情報しか書かれていないので、詳しい情報を調べるには前述のヘルプをチェックする必要がある。

図2 Parallel Advisorのドキュメント

今回使用するサンプルコード

　Parallel Advisorをインストールすると、「C:\Program Files\Intel\Parallel Studio 2011\Advisor\samples\en」以下にサンプルコードがインストールされる（表2）。それぞれのサンプルコードはZIP形式で圧縮されており、コードのほかVisual Studioのソリューションファイルや簡単なドキュメントも付属している。

表2 Parallel Advisorに付属するサンプルコード

サンプルコード	説明
heart.zip	筋肉や神経、心臓の動きをシミュレートする
newton.zip	多数のボールの挙動を物理的にシミュレートする
primes.zip	素数を計算して求める
sudoku.zip	数独の問題と答えを生成する
tachyon_Advisor.zip	レイトレーシングを用いて画像をレンダリングする

　今回はこのうち、数独の問題と答えを生成するプログラム「sudoku」をサンプルとして使用し、Parallel Advisorの機能や使い方を紹介する。

Parallel Advisorを使用するための準備

　Parallel Advisorではプログラムを実際に実行して各種分析を行うため、対象とするプログラムはあらかじめコンパイルされている必要がある。

　サンプルコードを含む「sudoku.zip」を適当なフォルダに展開し、含まれる「sudoku.sln」をダブルクリックするとVisual Studioが起動し、ソリューションが開かれる。ソリューション内には「sudoku」および「sudoku_annotated_final」、「sudoku_annotated_tasks」、「sudoku_cilk」、「sudoku_tbb」というプロジェクトが表示されるはずだ。このうち、「sudoku」プロジェクトに含まれるソースコードが並列されていないオリジナルのコードとなる（表3）。

表3 sudokuソリューションに含まれるプロジェクト

プロジェクト	説明
sudoku	並列化されていないオリジナルコード
sudoku_annotated_final	Parallel Advisorで使用する解析用コードをすべて追加したコード
sudoku_annotated_tasks	Parallel Advisorで使用する解析用コードを追加したコード
sudoku_cilk	Cilk Plusによる並列化が加えられたコード
sudoku_tbb	インテルスレッディング・ビルド・ブロック（TBB）による並列化が加えられたコード

プログラムのビルド設定

　Parallel Advisorでプログラムを解析する際に、Survey AnalysisおよびSuitability Analysisでは各種最適化を有効にしたReleaseビルドを、Correctness Analysisではコンパイラの最適化オプションを無効にしたデバッグビルドを利用することが推奨されている。また、Correctness Analysisの実行時はプログラムの実行速度が大きく低下するため、入力データのサイズについても少なくすることが推奨されている（表4）。

表4 テストに使用する際のビルドおよびデバッグ設定

分析ツール	ビルド設定	実行時の入力データサイズ
Survey Analysis	Release	フル
Suitability Analysis	Release	フル
Correctness Analysis	Debug	できるだけ少なくする

　今回使用するsudokuプロジェクトでは、デフォルトのコンパイラとしてVisual C++を使用する設定となっている。そのため、先にツールバーの「Use Intel C++」ボタンをクリックしてParallel Stdioに含まれるインテルコンパイラーを使用するように切り替えたうえで、DebugおよびRelease設定でリビルドし、それぞれ実際にコンパイルが成功するか、また生成されたプログラムが問題なく動作するかを確認しておこう。

　また、Parallel Advisorはリリースビルド・デバッグビルドの両方でデバッグ情報ファイルを使用する。これを生成するよう、「Debug Information Format」で「Program Database（/Zi）」もしくは「Program Database for Edit Continue（/ZI）」を選択しておく（図3）。

図3 「Debug Information Format」として「Program Database（/Zi）」もしくは「Program Database for Edit & Continue（/ZI）」を選択しておく

プログラムのパフォーマンスを調査する

　プログラムを並列化するにあたり、まず最初に必要なのがプログラムのパフォーマンス分析だ。前述のとおり並列化にはオーバーヘッドが発生するため、むやみやたらに処理を並列化するのではなく、処理に時間がかかっている個所（「ホットスポット」と呼ばれる）のみをピンポイントで並列化することが求められる。この作業を支援するツールが、Survey Analysis機能だ。

　Survey Analysisを実行するには、ツールバーの「Open Advisor Workflow」ボタンをクリックすると表示される「Advisor Workflow」ウィンドウの「1.Survey Target」内にある「Start」ボタンをクリックする（図4）。このときビルド設定が「Debug」になっているとその旨を確認する画面が表示されるので、その際は「Cancel」をクリックし、ビルド設定を「Release」にしてから再度実行しよう。

図4 「Advisor Workflow」の「1. Survery Target」内にある「Start」ボタンをクリックするとSurvey Analysisが実行される

　Survey Analysisを実行すると分析対象となるプログラムが実行され、パフォーマンスの計測が行われたのち結果が「Survey Report」として表示される（図5）。

図5 Survey Analysisの実行が完了すると「Suervey Report」が表示される

Survey Reportでプログラムのパフォーマンスをチェックする

　Survey Reportでは、画面左側（「Function Call Sites and Loops」）にプログラム内のブロック（「サイト」と呼ばれる）やループが、右側にはそれぞれの実行時間や対応するソースコードの個所が表示される。このなかで「Total Time %」が大きいサイトやループが並列化の候補となる個所となる。

　また、Survey Reportに表示されている関数やループをダブルクリックすると、対応するソースコードが表示される（図6）。関数の場合「Total Time」でその関数の総実行時間が、ループの場合「Loop Time」でループの総実行時間が表示される。

図6 関数やループをダブルクリックすると対応するソースコードが表示される

　今回のプログラムの場合、main.cxxファイル129行目からのループ内で呼び出されている「generate」関数が大きく時間を消費していることが分かる（図7）。

図7 「Total Time」から「ホットスポット」となる個所を検出できる

指定した個所が並列化に適しているかを調査する

　Survey Analysisでは実行に時間のかかっている個所を調査できるが、その部分を並列化したからといって必ずしもパフォーマンスが向上するとは限らない。プログラムによってはオーバーヘッドなどにより、並列化すると逆にパフォーマンスが低下する場合もあるからだ。

　Parallel AdvisorのSuitability Analysisでは、実際にプログラムを並列化することなしに、指定した個所が並列化に向いているかどうか、また並列化によってどの程度のパフォーマンス向上が見込めるかを診断できる。作業としては、Survery Analysisで発見したホットスポットに対し、Suitability Analysisで並列化の効果を診断する、という流れとなる。

ソースコードにAnnotationを付加する

　Suitability Analysisでは、コード中に「Annotation」と呼ばれる追跡用マクロを挿入することで調査対象となる個所を指定する。AnnotationはParallel Advisorに付属する「advisor-annotate.h」で定義されているマクロで、Suitability AnalysisやCorrectness Analysisはこのマクロで指定された個所を対象に分析を実行する。

　Annotationは「ANNOTATE_＜Anotation名＞_BEGIN(＜パラメータ＞)」と「ANNOTATE_＜Anotation名＞_END(＜パラメータ＞)」のペアになっており、この2つを対象とする関数呼び出しやループの前後に挿入していく。

Annotationに使用するコード

　Parallel Advisorでは目的やコードに合わせてさまざまなAnnotationが用意されているが、そのなかでもよく使用すると思われる基本的なものは表5の3つだ。

表5 よく使われると思われるAnnotation

Annotation	説明
ANNOTATE_SITE_BEGIN(sitename);	分析対象サイト（ブロック）の開始
ANNOTATE_SITE_END(sitename);	分析対象サイト（ブロック）の終了
ANNOTATE_TASK_BEGIN(taskname);	分析対象タスクの開始
ANNOTATE_TASK_END(taskname);	分析対象タスクの終了
ANNOTATE_LOCK_ACQUIRE(address);	ロックの開始。addressにはロック対象となる変数のアドレスを指定する
ANNOTATE_LOCK_RELEASE(address);	ロックの終了。addressにはロック対象となる変数のアドレスを指定する

　Parallel Advisorではサイト（もしくはループ）内で実行される処理を「タスク」と呼ぶ。基本的にはSurvey Analysisで検出された、処理に時間がかかっているサイトの前後に「ANNOTATE_SITE_BEGIN」および「ANNOTATE_SITE_END」を、サイト内で実行している処理それぞれの前後に「ANNOTATE_TASK_BEGIN」および「ANNOTATE_TASK_END」を挿入する、という形となる。

　また、並列実行した際に複数のスレッドから同時に実行されると問題となる個所の前後には「ANNOTATE_LOCK_ACQUIRE」および「ANNOTATE_LOCK_RELEASE」を挿入する。なお、「sitename」および「taskname」はそのAnnotationを区別するための名称で、半角英数字およびアンダースコア（_）が使用できる。

#include "advisor-annotate.h"

Annotationをコードに挿入する

　今回、多くの処理時間を消費している個所は前述のとおり「main.cxx」内129行目からのループとなり、このなかで実行されている「generate」関数がタスクに相当する。そこで次のようにforループの前後に「ANNOTATE_SITE_BEGIN」および「ANNOTATE_SITE_END」を、generate関数の前後に「ANNOTATE_TASK_BEGIN」および「ANNOTATE_TASK_END」を挿入し、調査対象とする。

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;
}

　なお、Visual Studioのコードエディタを利用している場合、対象を選択した状態でコンテキストメニューの「Intel Parallel Advisor 2011」?「Annotate Site」などでコードを挿入することが可能だ（図8）。

図8 Visual StudioのコードエディタではコンテキストメニューからAnnotationを挿入できる

　また、同時にAnnotationを定義している「advisor-annotate.h」をincludeするよう設定しておく。今回は共通して呼び出されている「solver.h」内に「#include "advisor-annotate.h"」を追加した。このファイルは「$(ADVISOR_2011_DIR)\include」というディレクトリに格納されているので、インクルードファイルの探索パスにこのディレクトリを追加しておく。最後にプロジェクトをリビルドすれば作業は完了だ。

Suitability Analysisを実行する

　Suitability Analysisは、Advisor Workflowウィンドウ内の「3. Check Suitability」から実行できる。「Start」ボタンをクリックするとプログラムが開始され、実行終了後にデータ集計が行われて結果が「Suitability Report」として表示される（図9）。

図9 Suitability Analysisの実行結果は「Suitability Report」画面に表示される

　「Suitability Report」画面では、Annotationで指定した個所を並列化することでどの程度パフォーマンスが向上するかを確認できる。パフォーマンス向上倍率はCPU数や使用する並列化技術ごとに推定でき、たとえば「インテルスレッディング・ビルディング・ブロック（TBB）を用いて並列化を実装し8コアのマシンで実行するとパフォーマンスが7.63倍向上する」など、具体的な数字で効果を確認できる。

　また、画面下には指定したサイトごとに、CPU数に応じたパフォーマンス向上度がグラフで表示される。今回問題となっている個所では、16コア程度まではほぼCPU数に比例してパフォーマンスが向上することが分かる。また、グラフ横には問題とする個所を並列化することによるオーバーヘッドの大小も表示される。

　なお、今回の例ではソースコードの変更を行わずとも並列化の効果がある、という診断結果が得られているが、プログラムによってはそのままでは並列化を行ってもパフォーマンスが得られない、という場合がある。このような場合、Selected Site画面右側に表示される「変更を加えるとどれだけパフォーマンスが変化するか」という情報を確認するととよい。

　ここでは行う変更（Type of Change）として5つの項目が用意されており（表6）、それぞれにチェックを入れることでその効果がグラフにも反映される。

表6 提案されている変更（Type of Change）

Type of Change	説明
Reduce Site Overhead	サイトを実行する際のオーバーヘッドを少なくする
Reduce Task Overhead	タスクを実行する際のオーバーヘッドを少なくする
Reduce Lock Overhead	ロックを実行する際のオーバーヘッドを少なくする
Reduce Lock Contention	ロック内で実行される処理を少なくする
Enable Task Chunking	サイト内で実行する処理を分割する

並列化によって発生する問題を検出する「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

プログラムの並列化に必要な作業を大幅に効率化できるParallel Advisor

　さて、以上ではParallel Advisorの機能をサンプルを用いて説明してきたが、このようにParallel Advisorでは5つのステップを順に行うことで、簡単に効率よくプログラムを並列化できる。今回使用したサンプルは非常にシンプルなプログラムであるため、特に困難なく作業が進んだが、実際のプログラムの場合も基本的な作業は同一である。しかし、大規模なプログラムの場合、今回の例のように簡単には並列化が行えない場合がある。

　たとえば次の図12は、とあるプログラムに対しSuitability Analysisを実行した結果のSuitability Reportだ。「Target CPU Number」が増えてもパフォーマンス向上率は1以下となっているのが分かる。

図12 そのまま並列化してもパフォーマンス向上が難しいプログラムの解析例

　このプログラムの場合、そのまま並列化を行ってもパフォーマンスは向上しない、ということが分かるのだが、Parallel Advisorではこのようなプログラムに対し、どのように修正を加えれば並列化の効果が見込めるのか、という情報も提示してくれる。注目して欲しいのが「Changes I will make to this site to improve performance」の部分だ。

　ここで「Reduce Task Overhead」が「+0.77x」というのは、タスク実行時のオーバーヘッドを小さくすれば0.77倍パフォーマンスが向上する可能性がある、ということを示している。また、「Enable Task Chunking」が「+0.95x」というのは、タスクを適切に分割することで0.95倍パフォーマンスが向上する可能性がある、ということになる。実際、コードにそのような修正を加えたところ、図13のように並列化により最大4倍までパフォーマンス向上が期待できる、という結果が得られた。

図13 コードを修正し、再度Suitabilit Analysisを実行した結果

　このように、Parallel Advisorは複雑なプログラムに対しても十分に効果を発揮する並列化支援ツールである。使い方も容易であり、並列化の経験が浅い開発者からベテラン開発者まで、多くの開発者に有用なツールと言えるだろう。

HPC/並列プログラミングポータル

新着トピックス

新着記事

インテルソフトウェア最新情報