Keiichi Oono's Weblog

2008年 3月 28日 金曜日

コンパイラによる自動並列化の捕捉。縮約 (reduction) を自動で行わせる

前回の自動並列化の説明で、理解不足の点がありました。「姫野ベンチ」で自動並列化を試みた際に gosa という変数の演算部分が並列化できなかったため効果が現れませんでした。という説明をしましたが gosa という変数の演算のj自動並列化を可能にするオプションがありました。このエントリでは、前回はどうして並列化できなかったのか、という点と並列化を可能にするオプションについて説明します。

姫野ベンチのソースコードはダウンロードして展開すれば読むことができますが、直接読める形で公開されていません。コードの一部を紹介することに問題はないのかもしれませんが、このエントリでは姫野ベンチのソースコードは直接使わずに、同等のコードに置き換えて説明します。

どうして並列化できなかったのか

前回のエントリでは「変数がループ内に完全に閉じていないため」と簡単に説明しただけですが、具体的には以下のような状況です

for (i=1; i < 1000; i++) {
    sum += a[i]*b[i]; /* S1 */
}

変数 sum は、1 つ前のループ実行時の sum に配列の値から求めた積を加算しているため、単純な方法で並列化することはできません。例えば 2 のスレッドで実行したとしても、最後にはそれぞれのスレッドで求めた sum を一つの値に合算しないと、求める値を得ることはできません。

縮約 (reduction)

この、スレッド毎に一時的な変数で部分和を求めておいて最終的な結果は合算して求める。という処理を行うために、OpenMP では縮約 (reduction) と呼ばれる指定を変数に対して行うことができるようになっています。指定された変数のことを縮約変数と呼びます。ただし丸め誤差の影響から、縮約して複数スレッドで実行した演算結果は、単一スレッドでの演算結果と個なる場合があります。

OpenMP で、ある変数を縮約変数として扱うか否かは明示的に指定する必要があります。

/* OpenMP: for ループで sum を縮約変数として指定 */
#pragma omp parallel for reduction (+:sum)

変数を縮約変数として自動並列化する -xreduction オプション

コンパイラによる自動並列化を行う際にも、コンパイラに縮約を行うように指示をすることができます。縮約可能であると判断された場合には変数は縮約変数として扱われ、並列化されます。OpenMP による並列化を行う場合と同じく、明示的に指示しない限り縮約のための解析と縮約変数の指定は行われません。縮約を行うように指示する場合には -xreduction オプションを追加します。指定されるとコンパイラは、解析の結果可能であれば変数を縮約変数として扱います。

姫野ベンチのソースで試してみる

コンパイル時に gosa の演算が縮約され、198 行目のループが並列化されたことを示すメッセージが出力されました:

cc -c  -fast -m64 -DMIDDLE -xvector=simd -xdepend -xautopar -xreduction -xloopinfo himenoBMTxps.c
"himenoBMTxps.c", 152 行目: 並列化されます
"himenoBMTxps.c", 153 行目: 並列化されません、利得なし
"himenoBMTxps.c", 154 行目: 並列化されません、利得なし
"himenoBMTxps.c", 170 行目: 並列化されます、逐次版が生成されました
"himenoBMTxps.c", 171 行目: 並列化されません、利得なし
"himenoBMTxps.c", 172 行目: 並列化されません、利得なし
"himenoBMTxps.c", 195 行目: 並列化されません、安全でない依存性 (wrk2 p)
"himenoBMTxps.c", 198 行目: 並列化されます、縮約、逐次版が生成されました
"himenoBMTxps.c", 199 行目: 並列化されません、利得なし
"himenoBMTxps.c", 200 行目: 並列化されません、利得なし
"himenoBMTxps.c", 223 行目: 並列化されます、逐次版が生成されました
"himenoBMTxps.c", 224 行目: 並列化されません、利得なし
"himenoBMTxps.c", 225 行目: 並列化されません、利得なし
cc -o bmt himenoBMTxps.o  -fast -m64 -DMIDDLE -xvector=simd -xdepend -xautopar -xreduction -xloopinfo

実行結果は以下のようになりました。前回と同じく自動並列化した実行ファイルは OMP_NUM_TREADS=2 という環境変数を指定した上で実行しています:

CPU	2 次キャッシュ	メモリ
AMD Opteron 250 (2.4GHz) x2	1 MB	3326 MB

結果 (5 回計測した中央値)

コンパイルオプション	結果 (MFLOPS)
-DMIDDLE -fast -m64 -xvector=simd -xdepend	812.315620
-DMIDDLE -fast -m64 -xvector=simd -xdepend -xautopar -xreduction -xloopinfo	1069.074965

自動並列化を行う場合に、「安全でない依存性」と報告された変数が縮約によって並列化される可能性がある場合には -xautopar に加えて -xreduction を指定することで、-xautopar だけでは並列化できなかった部分も並列化することができるようになります。

 
Posted by keiichio ( 3月 28日 2008年, 02:22:46 午後 JST ) Permalink 投稿されたコメント [0]

MySQL と Sun の初めてのセミナーが 4 月 9 日(水) に開催されます

MySQL と Sun の初めてのセミナーが 4 月 9 日(水) に開催されます。

春のMySQL祭り 2008 - Jumping to the Sun !

開催日時：2008 年4月9日(水) 13:30 から
開催場所：ウエスティンホテル東京
参加費用：無料（事前登録制）
主催：MySQL 株式会社、サン・マイクロシステムズ株式会社

会場へアクセス可能でご興味のあるかたは見てみてください。

 
Posted by keiichio ( 3月 28日 2008年, 02:15:17 午後 JST ) Permalink 投稿されたコメント [0]

2008年 3月 25日 火曜日

Sun Studio 12, コンパイラによるプログラムの自動並列化

Sun Studio 12 には自動並列化機能があり、コンパイラがループを解析して並列化を行います。並列化しても安全かどうかを、入れ子になったループも含む全ループにわたって解析し、安全と判断された場合には OpenMP を使って並列化を行います。ループ以外は解析も変更もされません。-xautopar コンパイルオプションを付けてコンパイルすることにより自動並列化が行われます。C/C++/Fortran に対応しています:

  $ cc -xautopar foo.c

すでに OpenMP を使った並列化が実装されていたり、マルチスレッド化が行われたプログラムに対して使用することはできません。並列化が行われていないプログラムを変更することなくコンパイラによって自動的に並列化するのが、このオプションの目的です。

処理全体を把握するわけではなく、あくまでもループの解析のみに基づいて局所的に行われる並列化ですので、限定的な効果にとどまりますが、コードにまったく変更を加えることなくマルチコア/マルチソケット環境の恩恵を得ることができる可能性があるため、手元にあるプログラムの再コンパイルと実行が比較的容易な場合には、試してみる価値のあるオプションだと思います。

実際にどのループが並列化されたのか、という情報は -xloopinfo というオプションを追加することで標準エラー出力上で確認できます。

実行する際には OMP_NUM_THREADS 環境変数によって並列処理領域で使用するスレッド数を指定しておく必要があります。指定しない場合には OMP_NUM_THREADS=1 となります。

例によって「姫野ベンチ」で試してみました。処理時間のもっとも長い部分が並列化されなかったので、目に見える効果は現れませんでした。参考までにコンパイル時に -xloopinfo によって出力された内容を貼り付けておきます:

  $ make
cc -c -fast -g -m64 -DMIDDLE -xvector=simd -xdepend -xautopar -xloopinfo himenoBMTxps.c
"himenoBMTxps.c", 152 行目: 並列化されます
"himenoBMTxps.c", 153 行目: 並列化されません、利得なし
"himenoBMTxps.c", 154 行目: 並列化されません、利得なし
"himenoBMTxps.c", 170 行目: 並列化されます、逐次版が生成されました
"himenoBMTxps.c", 171 行目: 並列化されません、利得なし
"himenoBMTxps.c", 172 行目: 並列化されません、利得なし
"himenoBMTxps.c", 195 行目: 並列化されません、安全でない依存性 (wrk2 p)
"himenoBMTxps.c", 198 行目: 並列化されません、安全でない依存性 (gosa)
"himenoBMTxps.c", 199 行目: 並列化されません、安全でない依存性 (gosa)
"himenoBMTxps.c", 200 行目: 並列化されません、安全でない依存性 (gosa)
"himenoBMTxps.c", 223 行目: 並列化されます、逐次版が生成されました
"himenoBMTxps.c", 224 行目: 並列化されません、利得なし
"himenoBMTxps.c", 225 行目: 並列化されません、利得なし
cc -o bmt himenoBMTxps.o -fast -g -m64 -DMIDDLE -xvector=simd -xdepend -xautopar -xloopinfo

「安全でない依存性」と記されている部分は、変数がループ内に完全に閉じていないため (例えば一つ前のループ実行時の結果を参照している等)、並列化されなかったことを示しています。変数 gosa のために並列化されなかった198 行目から 200 行目にかけてのループが最も処理時間を要する部分なので、ここが並列化されなかった結果、全体のパフォーマンス向上には結びつきませんでした。

「並列化されます、逐次版が生成されました」という部分は、並列処理を行うものと逐次処理を行うものの両方が生成されたことを示しています。ループ内での処理が少ない場合には逐次版が実行されると説明されていますが、詳細はちょっとわかりませんでしたので引き続き調べたいと思います。上記のコンパイル結果を実行した限りでは、並列化された部分は常に並列処理が実行されていました。

試しに gosa を計算しないようにして、-xautopar の有無によるパフォーマンスの変化を見てみました。演算を一つ省いてしまっていますから姫野ベンチのこれまでの実行結果と比較できる値ではありませんが、並列化の効果を知る上での参考値にはなると思います:

-xautopar を付けてコンパイルした実行ファイルは環境変数 OMP_NUM_THREADS=2 を設定した上で実行しています:

CPU	2 次キャッシュ	メモリ
AMD Opteron 250 (2.4GHz) x2	1 MB	3326 MB

結果 (5 回計測した中央値)

コンパイルオプション	結果 (MFLOPS)
-DMIDDLE -fast -m64 -xvector=simd -xdepend -xrestrict	801.706509
-DMIDDLE -fast -m64 -xvector=simd -xdepend -xrestrict -xautopar -xloopinfo	1343.303243

約 60% と、予想外に大きく向上しました。が、元々このプログラムはループ演算の性能評価に特化したものなので、ループの並列化が全体のパフォーマンスに大きく影響を及ぼすことは当たり前だとも言えます。一般的にこのくらい向上するわけでは決してないと思います。

プログラム全体にわたって効率よく最適化するには、OpenMP による並列化やマルチスレッド化を自ら行うのが良いのですが、手元のプログラムにまったく変更を加えることなく、マルチコア/マルチソケット環境の恩恵を得るには良い選択肢だと思います。

また、今回の gosa の演算をやめてしまうような変更は全然ダメですが、手元のプログラムでループ間の変数の依存を比較的簡単に調整できそうな場合は、ちょっとした変更でパフォーマンスの向上が見込めるかもしれません。

参考:

• The OMPlab on Sun Systems (PDF)
  2007 年 6 月に北京で開催された International Workshop on OpenMP 2007 (IWOMP 2007) で使われた Sun の Ruud van der Pas のプレゼンテーション資料。自動並列化のみならず Sun の OpenMP 実装などについても説明されています

 
Posted by keiichio ( 3月 25日 2008年, 02:47:21 午後 JST ) Permalink 投稿されたコメント [0]

2008年 3月 19日 水曜日

NetBeans 6.1 Beta, DTD ファイルから DOM ツリースキャナを自動生成させる

前のエントリで紹介した NetBeans 6.1 で復活予定の DTD から DOM ツリースキャナを生成する機能について具体的に見ていきたいと思います。あわせて紹介した SAX ドキュメントハンドラの自動生成については Beta ではうまく動かないので、バグ が修正されてから確認するつもりです。この機能は NetBeans 5.5.1 または NetBeans 6.1 Beta で試すことができます。

使用方法は単純で以下の手順を実行するだけです。

1. 処理したい XML の DTD を準備
2. DTD が無い場合には、NetBeans 上で XML ファイルをダブルクリックして「DTD を生成」を実行することもできます
3. DTD をマウスの右ボタンでクリックして「DOM ツリースキャナを生成」を選択して、クラス名を指定して「了解」をクリックします

例えば、上記の手順で生成されたクラスを使用する主クラスを作れば DOM を使用したパーサーとして使うことができます。

サンプルファイルと実際のコード

サンプルとして次のような XML を定義する、ちょっとしたマシン管理カードのようなもののための DTD を例に使います:

XML の例 (simpletest.xml)

<?xml version="1.0"?>
<!DOCTYPE machine SYSTEM simpletest.dtd">

<machine cpu="UltraSPARC T2" memory="2GB">
  <drive type="HDD" size="300G">
  <dryve type="DVD">
  <peripheral>DAT DDS3</peripheral>
</machine>

上の XML のための DTD (simpletest.dtd)

<xml version="1.0"?>
<!ELEMENT machine (drive*, peripheral*)>
  <!ATTLIST machine cpu CDATA #REQUIRED>
  <!ATTLIST machine memory CDATA #REQUIRED>

<!ELEMENT drive EMPTY>
  <!ATTLIST drive type (HDD | CD | DVD | none) #REQUIRED>
  <!ATTLIST drive size CDATA #IMPLIED>

<!ELELMENT peripheral (#PCDATA)>

上記の simpletest.dtd を右クリックして DOM スキャナを生成させると、デフォルトでは SimpletestScanner.java が生成され、SimpletestScanner クラスには以下のメソッドが実装されます

メソッド名	用途
SimpletestScanner(org.w3c.dom.Document document)	コンストラクタ
public void visitDocument()	パースして処理する時に呼び出すべきメソッド
void visitElement_drive(org.w3c.dom.Element element)	visitDocument() から呼び出される drive 要素用のメソッド
void visitElement_machine(org.w3c.dom.Element element)	visitDocument() から呼び出される machine 要素用のメソッド
void visitElement_peripheral(org.w3c.dom.Element element)	visitDocument() から呼び出される peripheral 要素用のメソッド

例えば、XML をパースして drive 要素の type 属性の値をプログラムから書き換える必要がある場合には、visitEelement_drive() メソッドに手を加えれば実現します。この例では visitElemnt_drive() は以下のようになっていたので、「ここに処理を追加」と私が追記した部分に必要な処理を書けば OK です。

void visitElement_drive(org.w3c.dom.Element element) {
    // 
// element.getValue();
    org.w3c.dom.NamedNodeMap attrs = element.getAttributes();
    for (int i = 0; i < attrs.getLength(); i++) {
        org.w3c.dom.Attr attr = (org.w3c.dom.Attr) attrs.item(i);
        if (attr.getName().equals("type")) {
            // ここに処理を追加
        }
        if (attr.getName().equals("size")) {
        }
    }
    org.w3c.dom.NodeList nodes = element.getChildNodes();
    for (int i = 0; i < nodes.getLength(); i++) {
...

完成した SimpletestScanner.java を使用するための主クラスは様々な書き方があると思います。一つの例として私が使ったきわめて単純なものを貼り付けておきます。コメントもエラー処理も何もない酷いソースですが、最低限の処理の例と言うことで ...

XML ファイルへのパスを引数として与えると、内容を標準出力に書き出します。StreamResult(System.out)) の部分を StreamResult(new FileOutputStream("/tmp/foo.xml")) などと書き換えるとファイルに出力するようになります。

package xmlsample;

import java.io.File;
import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.transform.Transformer;
import javax.xml.transform.TransformerFactory;
import javax.xml.transform.dom.DOMSource;
import javax.xml.transform.stream.StreamResult;
import org.w3c.dom.Document;

public class RunSimpletestScanner {

    public static void main(String args[]){
        try{
            // 一つめの引数から Document オブジェクトを取得
            DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
            DocumentBuilder builder = dbf.newDocumentBuilder();
            Document doc = builder.parse(new File(args[0]));
  
            // DOM ツリースキャナのインスタンスを取得して visitDocumnent() を呼び出して処理を行う          
            SimpletestScanner scanner = new SimpletestScanner(doc);
            scanner.visitDocument();
            
            // Transformer を準備して、DOM ツリーを標準出力に書き出す
            TransformerFactory tff = TransformerFactory.newInstance();
            Transformer tf = tff.newTransformer();
            tf.transform(new DOMSource(doc), new StreamResult(System.out));
        }catch (Exception ex){
            ex.printStackTrace();
        }
    }
}

 
Posted by keiichio ( 3月 19日 2008年, 02:29:16 午後 JST ) Permalink 投稿されたコメント [0]

2008年 3月 18日 火曜日

NetBeans 6.1 Beta, DTD ファイルから DOM ツリースキャナと SAX ドキュメントハンドラを自動生成

NetBeans 5.5.1 まではプロジェクト内の DTD ファイルを右クリックすると表示されるメニューの中に以下の 2 つが含まれていましたが、6.0/6.0.1 で無くなってしまいました。

• DOM ツリースキャナを生成
• SAX ドキュメントハンドラウィザード

これが 6.1 で復活することになりました。メニュー項目名の通り、これらは以下の機能を提供します:

DOM ツリースキャナを生成

DTD から、DOM ツリー内をスキャンするクラスが自動生成されます。生成されたクラスに少し手を加えると、XML の特定のノードの値を変更して出力するプログラムを作ることができます。

SAX ドキュメントハンドラウィザード

こちらも DTD ファイルを読み込んで、ContentHandler インターフェースを実装したドキュメントハンドラを生成します。DTD で定められた要素が見つかった時に、その内容を標準エラー出力に書き出すデバッグ用メソッドが自動生成されます。

これら 2 の機能は、XML を読み込んで動作するプログラムを作るときに便利だったので、ユーザーからの復活の要望が多く、6.1 で復活することになりました。機能を消したのもじつは、熟慮の結果というわけではなかったみたいです:
http://www.netbeans.org/issues/show_bug.cgi?id=90174

私自身、復活する前に使いたい時があって、その時は 5.5.1 でソースを生成させて 6.0.1 で編集しました。

ただ、SAX ドキュメントハンドラウィザードは 6.1 Beta で動かなかったので、さっきバグ登録をしました:
http://www.netbeans.org/issues/show_bug.cgi?id=130372

Beta でバグがあるとはいえ、便利だと思っていた機能が復活したのは嬉しかったです。

 
Posted by keiichio ( 3月 18日 2008年, 07:38:40 午後 JST ) Permalink 投稿されたコメント [0]

2008年 3月 17日 月曜日

Sun Studio 12, cc, -xprofile による実行時プロファイルデータを用いた最適化

以前の SIMD 命令の使用についてのエントリに続いて、姫野ベンチの実行結果から成績の良かった下記のコンパイルオプションの中の、-xprofile=use:bmt について見ていきたいと思います。

  -DMIDDLE -fast -m64 -xvector=simd -xprofile=use:bmt

-xprofile

このオプションは collect、use というパラメータを指定して使用します。collect、use 以外に tcov というパラメータもありますが、tcov については別の機会に説明したいと思います。

-xprofile=collect
-xprofile=use

他のコンパイルオプションによる最適化がソースコードの解析に基づくのとは異なり、このオプションは実行時のプロファイルデータに基づいた最適化を行うためのものです。一旦実行させて最適化のためのプロファイルデータを蓄えておいて、そのプロファイルデータを使って再コンパイルすることで、実際の実行時に時間のかかかった処理を特定しその部分の再構築などを行います。ですので -xprofile オプションを使用するコンパイルは必ず以下の流れになります:

1. -xprofile=collect を付けてコンパイル
2. 実行。必要に応じてプログラムへの入力値を変えて複数回実行
   (複数回の実行結果はマージされます)
3. -xprofile=use を付けて再コンパイル

 1  $ cc -xtarget=native -xprofile=collect:foo foo.c -o foo
 2  $ ./foo 123
 3  $ ./foo 456
 4  $ rm foo
 5  $ cc -xtarget=native -xprofile=use:foo foo.c -o foo