研究の成果

研究上の成果

本研究で開発された本並列仮説推論システムの構成を図--1に示 す。システムはn+1台のUNIXマシンから構成され、1台(マスター)が分散処理 モジュール、残りのn台(スレーブ)が推論実行モジュールを実行する。シス テムは、入力として知識ベース及び観測を受け取ると、進行(progress)フェイ ズと確認(confirmation)フェイズの2段階の状態を経て解を求める。

分散処理モジュール (マスター側)

進行フェイズ

ユーザから与えられた知識ベース及び観測をスレーブへ放送する。その後、全 スレーブからマシンの負荷状況、ゴール節集合を収集し、負荷に応じた数の節 を各スレーブに分配する。この収集・分配をシステムが確認フェイズへ移行す るまで 繰り返す。

確認フェイズ

あるスレーブから送られて来た解候補(複数の場合はコスト最小のもの)を全ス レーブへ放送し、再びスレーブから返された解候補のなかでコスト最小のもの を解として出力する。

推論実行モジュール (スレーブ側)

進行フェイズ

マスターから分配されたゴール節集合を一定時間最良優先SLD反駁で探索し、 生成されたサブゴール節の集合とプロセッサの負荷情報をマスターに返す。探 索中に解候補が見つかった場合には直ちに解候補がマスターに送られシステム のフェイ ズは確認フェーズに移る。この探索・送信をシステムが確認フェイ ズへ移行するまで繰り返す。

確認フェーズ

マスターから送られてきた解候補よりもコストの小さなものがないか最良優先 SLD反駁によって探索し、見つけた場合はそれをマスターへ返す。

外部発表論文リスト

• Kato S., Kamakura C., Seki H. and Itoh H., PARCAR: A Parallel Cost-based Abductive Reasoning System, Proc. of the 9th Intl. Conf. on Industrial & Engineering Applications of Artificial Intelligence & Expert Systems", pp. 57--62, (1996).
• 加藤 昇平、世木 博久、伊藤 英則, コストに基づく仮説推論の並列化, 並列処理シンポジウム JSPP'96, pp. 169--176, (1996).
• Kato S., Seki H. and Itoh H., Parallel Cost-based Abductive Reasoning for Distributed Memory Systems, PRICAI'96, LNAI-1114, pp. 300--311 (1996).

ソフトウェアとしての成果

並列仮説推論システム

本研究で開発された並列仮説推論システムは並行論理型言語KL1の処理系KLIC およびプロセス間通信ライブラリPVMを用いて設計・製作されており、UNIX計 算機ネットワーク上で動作する。

システムにおける並列推論処理のプログラムはKL1を用いてコーディングされ る。また、KLICを用いてKL1版プログラムをCのソースへコンパイルすることに より、プロセス間通信ライブラリPVM (Parallel Virtual Machine)による一般 WS上での並列実行が可能になり、並列仮説推論システムが実現される。

実験結果

本研究で開発したシステムの動作・性能の評価実験を行った。例題としては、 論理回路の故障診断問題を用いた。回路はn-ビット全加算器を対象にした。 回路を構成する素子は「正常」「開放」「短絡」の3つの状態をとるものとし、 これを仮説として表現した。また、各仮説のコストは、各素子が上記の状態と なる確率Ｐを考え、-logＰで与えた。

nをパラメータとしてn-ビット全加算器回路の規模を変化させて実験を行 なった。実験結果を図--2に示す。同図左が問題規模1≦n≦20の実行時間、右が問題規模n=20におけるスレーブ1〜20台のシステムの速度向上比をそれぞれ示している。

  　
図 --2: 実験結果

問題規模が大きくなるにつれてプロセッサ台数を増やした場合でもほぼ線形の 台数効果が得られているのが分かる。

 
   成果ソフトウェア   
   ソフトウェア名:  並列仮説推論システム PARCAR/KP  
   動作環境:  ネットワーク接続されたUNIXワークステーション   
   使用言語:  KL1, C   
   プログラムサイズ:  約 600 Kbyte   
   ドキュメント:   ユーザーマニュアル