Next: Up: Previous:

概要

研究の背景

「独創的情報技術育成事業」は, 大学, 研究機関, 民間企業等における情報 技術分野での先進的かつ独創的な研究開発の技術シーズを育成し, 研究開発成 果を広く普及することによって, 情報処理技術の振興を図ることを目的とする ものである. 近年においては高並列マシンのハードウェア開発も進み, 研究の 場を離れて現実の問題において, 並列計算による計算能力の向上が期待されて いる. その中でも特にMIMD型並列計算機は, 並列計算機アーキテクチャの中で も柔軟性が高く, 不規則な問題にも適用範囲が広いと認識されている. しかし ながら, プロセッサ間の通信コストの高さと負荷バランス制御の難しさから, MIMD型アーキテクチャのソフトウェア開発は遅れがちであった. そこで, ソフ トウェア開発の有力な方法論の一つとして, 並列オブジェクト指向言語が注目 されてきている. 従来, 並列オブジェクト指向言語は実行効率に問題があった が, 近年, 並列計算機上での高効率実装方式が開発され, 実用的処理システム の実現が次の段階の課題となってきた.

研究の目的

このような状況を踏まえ, 並列オブジェクト指向言語の高効率な実用的処理シ ステムの実現を目的として3年間に亙り本研究開発を実施した. 本研究開発は 次の二つを柱とした. 第1に, これまでに確立した並列オブジェクト指向言語 の高効率並列実装方式の研究に基づき, プログラム開発支援環境を含む並列オ ブジェクト指向言語 ABCL/f の言語仕様を設計し, その本格的な高効率処理系 を汎用並列計算機上に実現すること, 第2に, 言語の記述性, 処理システムの 機能実証のため, 対象問題をいくつか設定し, それらの並列解法を研究開発し, 開発した処理システム上に応用実証プログラムとして実現することである.

言語設計・処理系の設計開発

オブジェクト指向言語 ABCL/f の設計において念頭においたのは, 分散メモリ型並列コンピュータ向けのプログラム作成において, 適切なレベルの抽象化をユーザに対して提供することである. 具体的には, データの配置や計算処理を可視化するか否かを, 言語の記述力と性能への犠牲のトレードオフの点で注意深く検討して決断した. 分散メモリ型並列コンピュータにおいて, データ配置, 粒度選択, 負荷分散は劇的に性能に影響を与えるが, それらをコンパイラや実行時システムおいて静的・動的に(準)最適化することは 少なくとも現在の技術では不可能である. したがって, ABCL/f 言語においては, これらはプログラム毎にユーザ自身がコントロールできるような 言語プリミティブを提供するようにした. 具体的には, 並列処理単位を明示する future, データ同期を行なう touch, および データ・計算配置を指定する on, である. また, 実行時の動的判断による性能低下を避けるため, 静的データ型を採用した. 特に, データ同期前のデータ型は同期後のデータ型(通常の数値など)と異なっており, 同期前のデータに対して直接的な演算が『間違って』行なわれることがない.

また, 並列オブジェクト指向プログラムで問題となる 同一オブジェクトへの同時アクセスに対して, 安全かつ低オーバヘッドで解決する方法を設計した.

処理システムの設計・実装では, 逐次性能において手続き型言語に匹敵する水準を目指し, 並列プリミティブの処理コストを小さく抑えることを目指した. 結果として, ABCL/f ソースプログラムを C++ 言語に変換するコンパイラ, および C++ の関数呼び出しを少ないオーバーヘッドで非同期に行なうための 実行時システムからなる処理系を構築した. これらにおいては上記目標に沿った様々な工夫を行ない (例えば, C++ コンパイラによる最適化が行ないやすいような プログラム構造への変換方式), これらの目標をほぼ達成したと考える.

分散メモリ型並列計算機上の記号処理言語処理系で問題となる ごみ集めについては, 従来, 独立ごみ集めが優れているとされていたが, 実験的な裏付けがなかったため, 複数方式を実装して実験したところ, 独立ごみ集めの性能上の問題点が明らかになり, また全体ごみ集めのオーバヘッドが許容範囲にあることが分かった. さらに進んで, 独立ごみ集めモードと同期ごみ集めモードを適応的に切り換える方式を実現し, その優秀な性能を確認した.

ABCL/f 言語は個々のオブジェクトが排他制御の単位となっており, また非同期に生成されるデータは同期プリミティブを通さないとアクセスでき ないため, 単純なレーシングや同期バグは生じないようになっている. しかしながら, より複雑なバグやアルゴリズムのバグの追求のために, デバッグ環境としてシンボリックデバッガを提供した. これはマルチスレッディングに対応した環境を提供しつつ, ABCL/f の持つ移植性を重視して設計した.

応用実証プログラムの研究開発

応用実証プログラムの研究開発は本プロジェクトの2本目の柱である. これは, 応用分野側からの並列処理の研究に ABCL/f 言語・処理システムを用いて, それを評価・実証すること, および ABCL/f 処理システムを広く一般に公開する際の ABCL/f 言語での具体的な問題記述の参考例とすること, を目的として行なった. 具体的な応用問題として, 流体シミュレーション, マルチエージェントシステム, 遺伝的アルゴリズム, RNA 2 次構造予測, CKY 構文解析をを取り上げ, 具体的な幾つかの問題の ABCL/f 言語による記述と性能測定を行なった.

流体シミュレーションは科学技術計算の連続系の問題として取り上げた. 差分法でのメッシュをオブジェクトで表現するのは自然だが, オブジェクト間の頻繁な通信が性能ボトルネックとなったため, 複数個のセルをまとめて一つのオブジェクトとすることで, 計算量当たりの通信コストを下げ, 高い並列速度向上を得た.

マルチエージェントシステムでは, 共通言語の獲得問題と分散診断問題を取り上げ, 自律エージェントを並列オブジェクトとして表現するモデルを考案し, 実装した.

遺伝的アルゴリズムでは, 多目的最適化問題の遺伝的アルゴリズム (GA) による解法の並列化に取り組み, 個体間の競合を局所的に限定することによって, 並列度を向上させると同時に, 集団の多様性を永続的に維持できる長所を持つ 並列遺伝的アルゴリズムを開発し, 高い並列速度向上を確認した.

RNA 2次構造の予測では, 最安定な解に近いエネルギーを持つ解を全て求める探索アルゴリズムを作成し, 高い台数効果を実現した.

CKY構文解析アルゴリズムの ABCL/f による並列化では, 制御/データの依存関係を考察し, 高い並列度を抽出できたため, 従来の類似の試みと比較してかなり良い結果を得ることができた.

応用プログラムの設計開発を通して, ABCL/f の柔軟な並列言語としての能力, 低レベル処理の隠蔽によるプログラマ負担が軽減などを 確認することができた. 一方, 高い並列性能を達成するためのデータ配置や疎粒度化が必要だった箇所もあり, これらはプログラマ側の負担だったと言える. しかしながら, 現状のハードウェア, プロセッサ, 通信レイヤソフトの特質に起因する オブジェクト間通信や並列プリミティブの処理コストを 積極的に意識し, 必要な疎粒度化等をプログラマが行なえる, というのが正に ABCL/f 言語の設計思想であった.

応用実証プログラム開発者からの バグ報告や言語機能への要望をフィードバックは, ABCL/f 処理システムが実際に「使える」システムに近付くのためにも 役立った.

まとめ

MIMD 方式の分散メモリ型並列コンピュータ向けの 並列オブジェクト指向言語を設計し, 高効率な並列処理システムを開発した. 現状, 分散メモリ型並列コンピュータ上のプログラミングは, Express, PVM, MPI 等のメッセージパッシング・ライブラリを用いて C や Fortran 等の逐次手続き型言語で記述するか, あるいは HPF や並列論理型言語のような「生まれつき」の並列言語で 記述するか, の大きく二種類の選択肢がある. 前者の場合, メッセージ送受信のオーバヘッドが大きく (特に, 小さなメッセージ処理の相対的オーバヘッドが大きい), また後者の場合, 言語機能が高く設定されているために, 現状のコンパイラ技術では実行時の動的判断の箇所が多くなっている. すなわち, 記述力の向上と引き換えに, 逐次・並列性能が犠牲となってしまっている. 並列計算機の利用の目的が大幅な性能向上にあるとすれば, これは(現状では)致命的に近い問題であろう. 本研究で我々の開発した ABCL/f 言語および処理システムは, 逐次性能を保ちつつ, 並列プリミティブの処理コストを抑えることに成功した. 今後, 中長期的に高並列計算機の重要度が増大して行くことに疑いがない. 高並列計算機の性能を高度に引き出す鍵は, 応用問題解法における高い並列度の抽出と, 細粒度並列処理を高効率にサポートする言語・実行時システムにある. 今回の研究開発は, この理想実現に向けた細やかなしかし意義のある貢献であったと信じる.



Mitsubishi Research Institute,Inc.
Mon Feb 24 17:00:51 JST 1997