研究の成果

研究上の成果

本年度は、Parade におけるルール条件照合の並列化と耐故障並列ソフトウェ アに関して、大きな研究成果が得られた。以下、それぞれの概要を紹介する。 なお、ページ数の関係もありここでは割愛するが、KLIC を用いた関係データ ベース並列結合演算の動的偏り制御に関しても研究を進めている。

ルール条件照合の並列化

ルールベースシステムにとってもアクティブデータベースにとっても、ルール の条件照合は非常に多数のパターンマッチを必要とし重い処理である。ルール 条件照合の高速化手段として、ルールベースシステムにおいては Rete ネット ワークや TREAT ネットワークといった弁別ネットワークを利用することが一 般的であり、アクティブデータベースでも同様のアプローチを取っている研究 が多数ある。弁別ネットワークは、ルールをコンパイルすることにより新たに 条件照合を行なう対象を絞り込むもので非常に有効であるが、それでも十分と は言えない。

そこで我々は、弁別ネットワーク処理を効率良く並列化する方法を提案した。 これは、弁別ネットワークの中の２入力ノードをハッシュ関数によって並列プ ロセッサに分解し独立にパターンマッチを行なう方法を改良したものである。 具体的には、ハッシュ関数による偏り制御と終端処理を効率化するために、プ ロセッサをクラスター化すると同時に、クラスター内の通信量を大幅に減らす ソフトウェアキャッシュを導入した[1]。nCUBE2 を用いた実験 の結果、単純にハッシュ関数を適用していた従来の手法に比べて、ベンチマー クによっては最大 7.5 倍の性能向上を得ることができることを示した。例と して、最短経路問題を解いた場合のキャッシュ導入の効果を図--1 に示す。

    
図 --1: クラスタ化(CPPS)とソフトウェアキャッシュ(CPPS＋MX)の効果

図 --2: 耐故障並列ソフトウェアのオーバヘッド

また、アクティブデータベースにおいて、弁別ネットワークは問合せ木で表す ことができ、その問合せ木を最適化することにより、高速化を図ることができ る。ここで、我々は、並列環境を有効利用し、アクティブデータベースでは同 じ問合せ木が何度も用いられることとデータベースの状態変化が緩やかである ことを前提に、問合せ木の最適化を実際の問合せ木の実行と並列して行なう方 法を提案し、その効果を実験によって示した[2]。並列化により最適 化処理の時間を隠蔽できる効果が大きい。

耐故障並列ソフトウェア

一般の並列システムにおいては、要素数が増えれば増える程、要素単体の信頼 性と比較してシステムの信頼性は低下する。データベースシステムはその利用 前提から高い耐故障性が要求され、並列化によって信頼性が大きく低下するこ とは許されない。それだけでなく、一般に並列システムの信頼性を確保するこ とはデータベースに限らず重要である。しかし、ハードウェアによる耐故障機 能の実現はコスト的に高くつく。耐故障ソフトウェアによって信頼性を確保す るアプローチが考えられるが、一般のプログラマに耐故障機能まで含めて並列 プログラムを記述させるのは、生産性の面で問題が生じる。そこで、我々は、 オリジナルの並列プログラムを耐故障並列ソフトウェアに変換することを前提 に、耐故障並列ソフトウェアの構成の方法を提案した[3]。

並列システムにおいては、非決定的な動作が含まれること、故障の影響範囲を 絞り込むのが難しいこと、全プロセッサ対し安定記憶を想定するのが高価なこ と、などからプロセッサをプライマリグループとバックアップグループに分け、 その間でログを転送する手法を採用した。耐故障並列ソフトウェアでは、耐故 障化によるオーバヘッドを低く抑えることが重要となる。実行モデルによる見 積もりと、並列マシン上での実験により、プログラムの非決定的な部分が少な く、並列システムの通信性能が十分用意されている場合には、オーバヘッドが 少なくて済むことを示した(図--2)[4]。