１.　学会の概要

本会議はロシア科学アカデミーの Institute of Computational Mathematics and Mathematical Geophysics と Program System Institute（PSI）が主催し，隔年で行われる並列計算に関する国際会議である。今回は第9回目で，モスクワから120kmほどの距離にあるPereslavl-Zalesskyで開かれた。Pereslavl-Zalesskyは古い歴史のある町で，ロシア正教の修道院など，多くの文化遺跡がある。会議は，この町の郊外にあるPSIで行われた。参加者は約100名で，37件の発表があった。発表論文のテーマは並列計算全般で，アルゴリズム，応用，性能評価，ソフトウェアツール，言語，グリッド，セルオートマトン（CA）など幅広いが，特にCAに関する発表が10件以上と多いのが特徴的であった。

２.　興味深かった講演

興味深かった発表と自分の発表について，以下にまとめる。

(1) Intel Technology and Software for Parallel Programming
　　Andrey Semin (Intel Corporation)

Intelの今後2，3年のプロセッサ戦略と，並列計算のための様々なソフトウェアツールが紹介された。プロセッサに関しては，来年中に，Nehalemという新しいプロセッサが出荷予定である。1〜8個のコアを持ち，命令はSIMD機能を強化したSSE4が搭載される。また，L2キャッシュが50%増加し，デュアルコアで6MB、クアッドコアで12MBの容量を持つ。プロセスは45nmで，3GHz以上で動作する予定である。また，様々なアプリケーションに向けたアクセラレータを開発中である。科学技術計算・金融計算向けとしては，TFLOPSレベルの性能を持つmany coreプロセッサを開発している。各コアは改良されたIntel Architectureを持つ。一方，FPGAを利用したアクセラレータも，Altera，Xilinxなどと共同して開発している。これらのアクセラレータは，CPUバス（FSB）に直結して密結合で動作させる方式と，PCI Expressバスを解して結合する方式の両方を検討している。ただし，ほとんどのアプリケーションについては，後者の疎結合方式を取る予定である。また，アクセラレータの利用を容易にするため，ソフトウェア的な抽象レイヤーの導入を行う予定とのことであった。

ソフトウェアツールに関しては，コンパイラ，パフォーマンスアナライザ，Math Kernel Libraryなどが紹介された。

(2) Latencies of Conflicting Writes on Contemporary Multicore Architectures
　　Josef Weidendorfer, Michael Ott, Tobias Klug and Carsten Trinitis (Technical University of Munchen)

著者はMunich Multicore Initiativeの所属。この組織は，マルチコアプロセッサの効率的利用法，プログラミング環境，アプリケーションソフトウェアの移植法などを研究している。今回の発表では，コア間のフォールス・シェアリングによるメモリ書き出し性能の低下について，実際のマルチコアプロセッサでの評価結果が紹介された。フォールス・シェアリングとは，同じキャッシュライン内の異なるアドレスに対して2つのプロセッサが読み書きを行うとき，本来は不要なキャッシュラインの無効化が起こる現象である。本発表では特に，2個のプロセッサが2次キャッシュ（L2）を共有する場合と別々に持つ場合について，フォールス・シェアリングの影響がどう異なるかが報告された。

デュアルコアのIntel Core2 Duo T2600（L2共有），クワッドコアのIntel Xeon 5300（2個のプロセッサでL2共有），デュアルコアのAMD Opteron 275（L2はプロセッサ毎）を用い，フォールス・シェアリングが生じる条件で，メモリへの書き込みのレイテンシを測定した。その結果，Core2 Duoでの評価，およびXeonでL2を共有する2個のプロセッサを用いた評価では，データサイズがL1容量以下の場合，レイテンシは100サイクル以上の高い値を示したが，L1容量を越え，L2容量以下である間は，レイテンシが大きく減少した。ｋろえは，2次キャッシュの共有により，この領域ではフォールス・シェアリングが生じないためと解釈できる。実際，XeonでL2を共有しない2個のプロセッサを使った場合，フォールス・シェアリングによるレイテンシは，データサイズによらず高い値を示した。一方，Opteronでは，データサイズとともにレイテンシが減少する傾向が見られた。これは，同プロセッサがMOESIと呼ばれるキャッシュ・コヒーレンス・プロトコルを使っており，キャッシュラインをプロセッサ間で直接交換していることによると考えられる。

(3) A Novel Algorithm of Matrix Partitioning for Parallel Dense Factorization on heterogeneous Processors
　　Alexey Lastovetsky and Ravi Reddy (University College of Dublin)

ヘテロジニアスクラスター上でLU分解を行う際に，実行時間を最小化するデータ分割を求める新しいアルゴリズムの提案。行列はブロック列分割とし，第Kブロック段での処理が完全に終了してから第K+1ブロック段の処理を開始するという前提（すなわち，HPLのように，第K段の消去演算とオーバーラップして第K+1段のブロックピボットを作成・送信するといったことは行わない）。また，各プロセッサの性能はLU分解の最初から最後まで一定値であるとする。この前提の下で，各ブロック段での実行時間の合計を最小化するブロックの割り当て方式を求める。

この問題に対する従来の解法として，動的計画法を利用し，最終ブロック段から順にブロックの割り当てを決めていくことで最適な割り当てを求める方法が提案されている。一方，本研究では，まず各ブロック段での最適な割り当てブロック数をそれぞれ独立に求める。そして，第Kブロック段と第K+1ブロック段において各プロセッサの（最適な）担当ブロック数を比較し，1個のプロセッサについてのみ，ブロック数に差があるときは，そのプロセッサに第K+1ブロックを割り当てる。一方，ブロック数に差があるプロセッサが2個以上あるときは，例外処理を行う。この手続きによって最初のブロック段から順に割り当てを決めていけば，動的計画法と同様，最適な割り当てが得られることを証明した。

一方，実際の計算機では，キャッシュやTLBなどの影響により，計算が進んで消去領域の大きさが変化すると，実効性能も変化する。動的計画法や提案手法はこの場合にも拡張できるが，一般には最適解を与えない。しかし，性能評価の結果，動的計画法の与える近似解に比べ，提案手法の与える近似解はより優れていることがわかった。数倍程度のプロセッサ間性能差を持つ16台のクラスターで1024〜25360元の問題を解く場合，提案手法による割り当てを用いたLU分解は，動的計画法を用いた場合に比べて最短2/3程度の時間で実行できた。

(4) Accelerating the Singular Value Decomposition of Rectangular Matrices with the CSX600 and the Integrable SVD
　　Yusaku Yamamoto, Takeshi Fukaya (Nagoya University), Takashi Uneyama (Kyoto University), Masami Takata (Nara Women's University),
　　Kinji Kimura (Niigata University), Masashi Iwasaki (Kyoto Prefectural University) and Yoshimasa Nakamura (Kyoto University)

大規模長方行列の特異値分解を，ClearSpeed社の浮動小数点アクセラレータCSX600を使って高速化した。m×n長方行列Aの特異値分解は，(a) AのQR分解，(b) Rの二重対角化，(c) 二重対角行列の特異値分解，(d) 逆変換によるRの特異ベクトルの計算，(e) Qと左特異ベクトルとの乗算，の5つのステップからなる。このうち，(a)，(e)の計算量は共にO(mn²)なので，m≫nの場合はこれら2つが演算量の大部分を占める。そこで，この2つのステップをCSX600を使って高速化した。また，ステップ(c)では，演算量がO(n²)で所要メモリも少ない可積分系に基づく特異値分解アルゴリズムI-SVDを用いた。

ステップ(a)，(e)では，QR分解のアルゴリズムを行列乗算を用いる形に変形し，行列乗算をCSX600向けのライブラリCSXLで計算した。行列乗算を用いてQR分解を行う方法としては，(A) LAPACKなどで用いられるブロック化QR分解，(B) 再帰的QR分解，(C) 両者の組合せ，などが考えられる。このうち，(A)は演算量は少ないが，level-2 BLASで実行される部分が残り，また，使われる行列乗算のサイズは小さい。一方，(B)は演算量は(A)の約1.5倍だが，ほぼすべての演算がlevel-3 BLAS（行列乗算）で実行でき，乗算のサイズも大きい。(C)はその中間である。

この3手法を実装して評価した結果，CSX600では(B)の再帰的QR分解が最高速となった。また，LAPACK（Intel MKL）をホストPC（Xeon 3.2Hz）のみで実行した場合と比べ，最大で4倍の高速化が達成できた。結果の誤差はLAPACKに比べ，やや増大するが，実用上は問題ない範囲と考えられる。

Q1: 「今後の課題」でGRAPE-DRなど他のアクセラレータでの評価が挙げられていたが，GRAPEは重力計算専用のチップと聞いている。行列乗算ができるのか？（Peter Sloot教授）
A1: GRAPE-6までは重力計算専用のチップだったが，GRAPE-DRはより汎用のチップであり，行列乗算でも性能が出るように設計されている。そのため，今回と同じアルゴリズムを使えば，特異値分解も高速に計算できると考える。

Q2: スライドのp. 24で，残差が階段状になっているのはなぜか。
A2: グラフの描き方が誤解を招く形になっていた。グラフでは，最初の4列がn=1000のとき，次の4列がn=2000のときを示しているので，4列目と5列目の間で値にギャップがあるように見える。実際には，m，nにつれて，残差はほぼ滑らかに増大する。

Q3: Xeonのモデル番号は？浮動小数点計算が1サイクルで何回できるタイプか。
A3: 1サイクルで倍精度浮動小数点演算が2回実行できるタイプを使った。

(5) Self-organization in time-warped DES
　　Peter Sloot (University of Amsterdam)

セルオートマトンによる自然現象のシミュレーションについて，基本的な考え方，並列化手法，臨界現象との関係，生物の成長シミュレーションへの適用例などが紹介された。
CAによるシミュレーションでは，対象とする自然現象と同じユニバーサリティクラスに属するプロセスを，簡単な計算モデルにより実現しようとする。セル間の相互作用は単純かつ局所的で，効率的に計算できる。また，自然と同様，非同期的な時間発展を取り入れることができる。実際的なシミュレーションでは，10^12程度のセル，10^5程度の時間ステップが必要となる場合もある。

そのため，並列化が重要である。CAの時間発展には時間駆動型と事象駆動型があるが，ここでは後者を考える。並列化において，保守的なアプローチでは，事象の起こる順序が逐次版の場合と同じであることを保証しようとする。しかし，これでは並列化効率を上げることが難しい。一方，楽観的なアプローチ（Optimistic time warp approach）では，順序を保証せずに時間発展を行う。その結果，因果律を破ってしまう場合があるが，その場合は，問題が起きた時点まで巻き戻してシミュレーションをやり直す。

この手法を使ってイジングモデルのシミュレーションを行った例を示す。このモデルでは温度が重要なパラメータであるが，温度を横軸，巻き戻しの深さを縦軸に取ったグラフを描くと，グラフはある温度でピークを持つ。実は，この温度はイジングモデルの臨界温度であり，この温度以下では系は長距離秩序を持ち，以上では系は短距離秩序を持つ。巻き戻しの深さがピーク値を取るのは，ちょうど系において遠くの要素との相互作用が起こり始め，遠くの要素の状態を無視した時間発展が因果律の破れを引き起こし始める点である。このように，系の臨界状態とCAの時間発展における因果律の破れとがちょうど対応しているのが興味深い。

次に，CAを用いて珊瑚の成長シミュレーションを行った。珊瑚の成長では，拡散の効果が支配的か，流れの効果が支配的かによって，できる形が異なる。これをCAによるシミュレーションで再現した。拡散が支配的な場合，シミュレーションで得られた最終的な形のフラクタル次元は2.27であり，流れが支配的な場合，2程度であった。これは両方とも実際の珊瑚のフラクタル次元とよく一致している。

(6) Coarse-Grained Parallelization of Cellular-Automata Simulation Algorithms
　　Olga Bandman (ICM & MG, Siberian Branch, Russian Academy of Sciences)

非同期型CAに対する粗粒度並列化手法の提案。CAには同期型と非同期型があり，同期型CAではすべてのセルについて一斉に状態の更新を行う。一方，非同期型CAで時間ステップを1つ進めるには，乱数によってセルを1つ選んで更新し，この操作をすべてのセルが1回ずつ更新されるまで繰り返す。同期型CAは領域分割法により簡単に並列化できるが，非同期型セルでは更新演算の依存関係が乱数の値により異なるため，並列化が困難である。

そこで本研究では，非同期型CAを近似する多段の同期型CAを使う手法を提案した。非同期型CAではセルの更新順序が任意の順序（n個のセルがあればn!通り）を取ることが可能であるが，これをある条件を満たす順序に制限することで，順序関係のないセルを生じることができ，これらを並列に更新できる。本手法を極性媒体内の流れの問題に適用した結果，16プロセッサ時に90%以上の高い並列化効率を得ることができた。

３.　メモ

(1) 会議の感想

会場のProgram System Instituteは人里離れた原野の中にあり，交通手段といえば学会側が用意してくれる朝夕の送迎バスしかなかったため，学会の間，参加者は全員朝から夕方までPSIでずっと一緒に過ごした。さらに夕方ホテルに帰ってきても，街中にはレストランが2，3軒しかなく，どこに行っても結局会議のメンバーと再び顔を合わせることになった。お蔭で，全然違う分野の人たちも含め，ずいぶん多くの参加者と話すことができ，親しくなった。小さな町でやる小さな学会の良い点だと思う。主催者側も，盛りだくさんの内容のツアー（修道院，狭軌鉄道博物館，遺跡，バーベキューなど）を用意したり，歓迎会・交流会を開いてくれたりして，参加者どうしの交流の機会を積極的に作ってくれた。

(2) 通貨

日本円を持っていけば現地で両替できるだろうと安易に考えていたら，大失敗だった。ホテルではクレジットカードが使えず，街中の2軒の銀行でも両替はドルとユーロしか受け付けない（実際には言葉も通じなかったので身振り手振りから判断しただけ）。幸い，キャッシュカードでルーブルの現金を引き出せるATMを見つけたが，１日に引き出せる額を低く設定していたので，2日に分けてようやくホテル代と学会参加費を引き出した。大都市以外に行くときは，必要な費用をドルに両替して持っていくべきだと痛感した。

(3) 言葉

英語は全く通じなかった。が，夕食以外の時間はほとんど学会会場にいたし，夕食のときもレストランに行けば誰かしらロシア人参加者がいたので，あまり困らなかった。あと，キリル文字とアルファベットの対応だけはわかるので，それが意外と役立った。たとえば，Бизнес　Цｅнтр ＝ Business Center，Интｅрнｅт ＝ Internet など。

(4) 食事

今まで学会出張で行った国の中では，ブルガリアに次いでおいしかった。特に，ひき肉，ジャガイモ，小麦粉，乳製品を使った料理。ピロシキ，水餃子に似たペリメニ，ひき肉のクレープ包み（ホテルの朝食），大きなミートボールとマッシュポテト，豚肉の上にジャガイモの厚切りとチーズを載せ，オーブンで焼いた料理など，どれも素朴な味で，たっぷりと実質のある料理だった。

４.　写真

学会会場の Program System Institute（左）とそこから見た湖の風景（中，右）

Peter Sloot 教授による招待講演

Pereslavl-Zalessky の町にあるロシア正教の教会と修道院。左の写真は The Cathedral of Transfiguration（1152年-1157年）。中央ロシアで現存する最も古い建築。

左から，St. Nikita's Monasttery，St. Nikolas's Convent，Goritsky Monastery（2枚）。

狭軌鉄道博物館にて

交流会にて