１.　学会の概要

本学会は，情報処理学会の計算機アーキテクチャ研究会とハイパフォーマンスコンピューティング研究会が合同で開催する研究会であり，毎年３月に北海道で行われる。今回は，アーキテクチャ，アルゴリズム，グリッド，性能評価などの分野から全35件の発表があった。

２.　興味深かった講演

今回聴講した講演のうち，興味深かったもの（主にグリッド応用，性能予測，数値／非数値アルゴリズム関係）に関するメモを以下にまとめる。なお，研究会のプログラムは http://www.ipsj.or.jp/09sig/kaikoku/2003/ARC149HPC97.html で見ることができる。

(1) Ninf-G version2の実装および性能評価
　　武宮博，田中良夫（産総研），中田秀基（産総研／東工大）

Ninf-G version2は，グリッド環境においてGrid RPCを用い，数百〜千CPUを用いたタスク並列処理を効率的に実行することを目標としたミドルウェアである。このような大規模並列処理においては，(i) ネットワークやバックエンドサーバ（実際にプログラムを遠隔実行する計算機）の不安定性への対処，(ii) 遠隔実行プログラムの起動コストやデータ転送オーバーヘッドの削減によるスケーラビリティの確保，の２つが重要な課題となる。

Ninf-G version2では，(i)に対し，関数ハンドル（遠隔実行プログラムの抽象化）作成のタイムアウト機能やハートビート機能（遠隔実行プログラムからクライアントに対して一定間隔でハートビートを送る機能）を付加することで対処した。また，(ii)に対しては，複数の関数ハンドルを同時作成する機能の追加とリモートオブジェクトの実装を新たに行った。リモートオブジェクトを使うと，パラメータサーベイなど複数回のプログラム実行で共通の入力データを用いる場合，その部分の通信は１回で済み，データ通信が大幅に削減できる。

気象シミュレーションプログラムを使ったパラメータサーベイを例題として性能評価を行ったところ，Ninf-G version2を使ったシステムではそれぞれ数十秒程度の処理を300ノード程度で並列実行する場合において，効率的な処理が可能であることがわかった。

(2) MPIプログラム実行時間予測ツールMPIETEの評価
　　堀井洋，岩渕寿寛，山名早人（早大）

グリッドのように複数の並列計算機システムが混在する環境において計算機資源を有効活用するには，プログラムの実行前に各システム上での実行時間を予測し，最適なシステムを選択する必要がある。実行時間の予測方法として，従来から命令レベルのシミュレーション，プログラムの静的解析などが提案されていたが，それぞれ予測に要する時間，予測精度の面で難点があった。

本システムでは，並列プログラムを計算ブロック，通信ブロック，通信待ちブロックの３種類の部分に分割し，計算ブロックの実行時間はターゲットマシン（1CPU）上で実測し，通信部分の時間はデータ量から計算することにより，高速かつ高精度な実行時間の予測を目指す。計算ブロックの実行時間を測定するためのプログラムは元のプログラムから自動生成し，DOループの回数を削減することで，実際のプログラム実行より少ない時間で測定することを可能とする。ただし，ループの回数を最低２回とし，測定には２回目以降の値を使うことにより，キャッシュヒット率を実際のプログラム実行に近い値とするなどの工夫をしている。

本システムをNAS Parallel Benchmarkを例題として評価したところ，EP，CG，LUのいずれにおいても，計算部分の時間は128CPUまで12%以下の誤差で予測できた。しかし，通信時間には大きな誤差が見られた。なお，予測に要する時間はいずれのケースでも実際の実行にかかる時間の1/10以下であった。

通信時間の誤差の原因として，モデル化されていないネットワーク上での衝突の影響などが考えられる。今後の課題としては，ネットワークシミュレータを用い，この部分の予測を高精度化することなどが挙げられる。

(3) 不均一クラスタ上での実行時間予測モデルとその改良
　　岸本芳典，市川周一（豊橋科技大）

PCを寄せ集めて作ったクラスタでは，各プロセッサの計算性能やメモリが不均一となる場合が多い。一方，並列化された応用プログラムでは，計算性能が均一であることを前提していることが多い。このような場合，応用プログラムを修正せずに不均一クラスタの性能を引き出すには，高速なプロセッサに複数のプロセスを担当させることが考えられる。その際，各プロセッサに何個のプロセスを担当させるかを決めるため，性能予測モデルとその結果に基づく組み合わせ最適化が必要となる。

本研究では，High Performance Linpackベンチマークに対し，性能予測モデルを作成した。まず，クラスタ内の性能が同じプロセッサ群を一まとめにし，これに対して問題サイズN，全プロセス数P，１プロセッサ上でのプロセス数Miを入力とする実行時間モデルを作る。そして，この結果を元にクラスタ全体での実行時間を予測する。各モデルの作成には，パラメータを変えて実行時間の測定を数十回行うことが必要であり，数時間が必要となる。そこで，この時間を節約するため，あるいはこのような長時間の占有ができない場合のため，性能が異なる他のプロセッサ群で作成したモデルを借用し，補正係数をかけることによってモデルを作成する方法も提案した。

Athlon（1.33GHz）1台とPentium II（400MHz）4台からなる不均一クラスタに対して本手法に基づくモデルを作成し，N，P，Miを様々に変えて実行時間を予測したところ，N≧3200のときには誤差は12.4%以下となった。また，予測によるP，Miの最適値は実測によるP，Miの最適値と極めて良く合っていることが確認できた。さらに，Pentium III（866MHz）2台を加えた3種類のマシンからなるクラスタについても実行時間を予測したところ，誤差はやや大きくなるが，N≧4800のとき17%程度の誤差で予測ができることを確認した。

(4) Multi-master divisible load modelにおける漸近最適スケジューリング
　　須田礼仁（東大）

数値ライブラリを使って並列計算環境でのアプリケーションプログラムの性能を向上させようとする場合，数値ライブラリ実行のために計算資源を追加したり，数値ライブラリ実行に適した形にデータを再分散する必要が生じる場合がある。このとき，システムの実行性能を最適化するには，再分散した結果の計算時間だけではなく，再分散に要する通信時間も合わせて最適化を行う必要がある。

そこで本研究では，マスター・ワーカー型の並列処理のデータ分散問題のためのモデルであるDivisible Load Theoryを拡張し，任意のプロセッサがタスクを輸出／輸入できるモデルを考える。処理すべきタスクとしては，一様で相互に依存関係がなく，どのプロセッサでも処理できるものを考える。また，タスクは任意に切り分けることができ，タスクの処理及び転送には，タスク量に比例する時間がかかると仮定する。一方，計算機システムとしては，計算機性能が不均一で通信性能が一定であり，全プロセッサがクロスバーで接続されたシステムを考える。

これらの条件の下で，計算時間 + 再分散に要する通信時間を小さくするスケジューリングアルゴリズムを提案した。本アルゴリズムは，通信と演算のオーバーラップがない場合，問題サイズを大きくしていった極限で最適解を与えることが示される。さらに，オーバーラップを許す場合でも，オーバーラップにより通信性能が変化しないなどの条件を加えることで，本アルゴリズムにより漸近最適解が得られることが示される。

感想： グリッド上の計算では，計算量の大きな数値ライブラリの部分をアプリケーションプログラムと異なる計算機で実行することが普通になると予想され，その場合，本研究のようなスケジューリング技術が重要となる。本研究では，タスクが均質，タスク間に依存関係がないなどの制約を課しており，そのままでは行列計算ライブラリに適用することはできないが，今後，モデルが拡張されるか，あるいはうまい工夫により適用が可能となることを期待したい。

(5) Bayesian Optimization Algorithmの並列化に関する実験的検証
　　村尾直哉，棟朝雅晴，赤間清（北大）

通常の遺伝的アルゴリズムでは解きにくい最適化問題を解く進化的計算法として，Bayesian Optimization Algorithm（BOA）が提案されている。本手法では，個体集団において適応度の高い個体群を抽出し，それらについて，個体を構成する文字の依存関係に関する条件付き確率（遺伝子のある位置の文字が決まったとき，別の位置にどの文字が来るかについての確率）をベイジアンネットワークとして構成して，それに基づいて次世代の個体群を生成する。ここで，ネットワークのノードは遺伝子の位置であり，ノード間の（向きのついた）枝が依存関係を表す。ノード間に枝を付加するかどうかは，それによりネットワークの品質が向上する（Bayesian Dirichlet Metricという指標を用いる）かどうかにより決める。

このネットワーク構築を並列化するには，各ノードをプロセッサに割り当て，各ノードを出発点とする枝を付加するかどうかの判断を並列に行うことが考えられる。しかし，この方式では，ネットワークに巡回路ができる可能性があり，条件付き確率を表現するネットワークの要件を満たさない。そこで，ノードにランダムに番号を割り振り，枝は番号の小さいノードから大きいノードに向かってのみ付加できることにする。これにより，巡回路はないことが保証される。なお，このランダムな番号付けは，世代ごとに新たに行う。

この手法に基づいて並列化を行った結果，ネットワーク構築の部分については８台のプロセッサを用いた場合で８倍近い高速化が得られ，かつ，最適解を得るための平均世代数は，逐次アルゴリズムの場合と同程度であることがわかった（それ以外の部分の並列化に関する説明と実験結果もあったが，省略）。

感想： 本並列化手法では，(1) ノードにランダムに割り振った番号により，枝の方向を予め固定していること，(2) ２本（以上）の枝を付加する場合，付加するかどうかの判定を逐次的にではなく独立に行っていること，の２つの要因により逐次アルゴリズムと異なるネットワークが得られる可能性があるが，それがネットワークの品質を劣化させることになっていないのは大変興味深い。須田先生がコメントされていたように，これは従来アルゴリズムのような逐次的な枝の付加が必ずしも最適ではないことを示唆していると考えられる。

(6) グリッド技術を用いた進化系統樹推定の並列化
　　山本洋（東工大），中田秀基（産総研／東工大），下平英寿（東工大），松岡聡（東工大／国情研）

生物進化の系統樹を推定する方法として，DNA配列に基づく系統樹の尤度を計算し，尤度最大となる系統樹を選ぶ方法が提案されている。しかし，n種の生物の系統樹を推定する場合，可能な系統樹の数はO(n! * 2**n)と大きく，各系統樹の尤度の計算にも大きな時間がかかる。

そこで，本研究では３つの側面から高速化を行った。まず，(1) 系統樹を根元の方から見ていったときの分岐であるスプリットを定義し，スプリットの列が系統樹を一意的に定めることを利用して，まずスプリットの尤度を厳密に計算し，それを用いて各系統樹の尤度を近似的に求める。スプリットの個数はO(2**n)であることが示されるため，これにより時間のかかる（厳密な）尤度計算の回数がO(n! * 2**n)からO(2**n)へ大きく減少する。 (2) 以上の改良法ではスプリットの尤度を用いた系統樹の尤度計算は相変わらずO(n! * 2**n)回行う必要があるが，この部分の計算量を分枝限定法あるいは焼きなまし法を用いて削減する。(3) 分枝限定法のマスター・ワーカー型並列化，あるいは焼きなまし法のレプリカ交換法による並列化で，さらに高速化を図る。

生物種nが５種から９種の問題に対して系統樹推定を行ったところ，(1) 近似計算による尤度は厳密な尤度と非常によく合う，(2) 分枝限定法あるいは焼きなまし法の適用により，近似的な尤度計算の回数を95%程度削減できる，(3) 分枝限定法の並列化では９種の場合で16プロセッサで12.8倍程度の高速化が得られた。また，レプリカ交換法では，４プロセッサ（温度が４段階）では４倍程度の高速化が得られたが，それ以上温度を増やしても並列化の効果はほとんど見られなかった。

感想： 大変興味深い発表だったが，必要な予備知識が多く，発表と論文だけでは内容がよく理解できなかったのが残念だった。高速化手法(1)を提案している原論文に当たってみたい。

(7) Jojoによる遺伝的プログラミングの並列化
　　徳田拓（東工大），田中康司（JST／東工大），中田秀基（産総研／東工大），松岡聡（東工大／国情研）

遺伝子が他の遺伝子からの影響を受け，その発現量が増加あるいは減少することを遺伝子の相互作用と呼ぶ。n種類の遺伝子があるとき，この相互作用はn変数のn元連立常微分方程式で表される。実験データを再現するように，この常微分方程式の形を求めることを考える。

そのため，n個の常微分方程式の右辺を計算グラフ（木構造）で表し，n個の計算グラフをまとめたものを遺伝子として遺伝的プログラミングにより最適化を行う。新しい個体の生成としては，突然変異（ランダムに生成した木を，個体の部分木と入れ替える）と交叉（２つの個体に対し，それぞれランダムに選んだ部分木どうしを入れ替える）の２つを用いる。また，適合度としては，得られた連立常微分方程式を４次のルンゲ・クッタ法で解いた解と実験データとの最小二乗誤差を用いる。

本手法をGrid上でマスター・ワーカー型の並列化を行い，n=2の問題に適用したところ，400個体を使って数千世代で，元の入力データを生成した連立常微分方程式に，計算グラフの形，係数とも非常に近い式が得られた。n=3の問題に対しては，５万世代計算しても最適解の式の形は正解とかなり異なっていたが，出力データは入力データにかなり近いものが得られた。今後は実際の遺伝子相互作用解析に適用するため，n=5〜10の場合への適用を目指す。

(8) OmniRPCによるグリッド環境での大規模固有値問題の並列解法
　　桜井鉄也，早川賢太郎，佐藤三久，高橋大介（筑波大）

一般固有値問題Ax=λBxにおいて，ある領域内にある固有値と対応する固有ベクトルとを効率的に求める方法として，桜井のアルゴリズムがある。この方法では，計算の主要部分が複数の複素数ωに対してωB-Aを係数とする連立一次方程式を解く処理となるため，各連立一次方程式をそれぞれ別のプロセッサに割り当てることで，極めて大粒度の並列化が可能となる。

本アルゴリズムをGrid上で遠隔手続き呼び出しによる並列化を可能とするミドルウェアであるOmni RPCを用い，８台のPCを用いて並列化した。9274元の行列で４個の固有値を求める場合で，６〜７倍の高速化が得られた。