JPH0287232A - プロダクション・システムの並列実行方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はプロダクション・システムに係り、詳しくは５
条件の照合したルールを複数のプロセッサで実行するこ
とにより高速化をはかったプロダクション・システムの
並列実行方式に関する。

〔従来の技術〕

人工知能（ＡＩ）システムの実現方式としてプロダクシ
ョン・システムがある。プロダクション・システムは知
識を記述した知識ベースと推論を行う推論エンジンから
構成される。

知識ベースは、事実に関する知識であるファクトと、規
則に関する知識であるルールからなる。

各々のファクトはワーキングメモリ要素（ＷＭＥ）とし
て記述され、ワーキングメモリ（ＷＭ）に記憶される。

ＷＭＥは通常、クラス名、＠性１：属性値、・・・、属
性ｎ：属性値と記述される。また、各々のルールは条件
を記述した条件部（ＬＨ３部）と実行手続きを記述した
動作部（ＲＨ５部）から成る。ルールのＬＨＳ部は一つ
以上の条件要素からなり１条件要素には、一つ以上の条
件式が記述される。ＲＨ８部は一つ以上の実行要素から
なり、実行要素にはＷＭＥの更新・表示及び入力などの
動作が記述される。ルールのＬＨ８部の全ての条件要素
の全ての条件式を満足するＷＭＥ群が存在するとき、Ｌ
Ｈ３部はそのＷＭＥ群によって満足されたという。

推論エンジンは、照合フェーズ→競合解消フェーズ−ル
ール実行フェーズの繰り返しによって推論を行う、この
一連の動作は認知サイクルと呼ばれる。照合フェーズで
は全てのＷＭＥに対して、全てのルールのＬＨ３部の条
件要素に記述された条件式を満足するか否かの照合を行
い、ＬＨ５部を満足するＷＭＥ群とそれにより満足され
たルールの組の集合を生成する。この組をインスタンシ
ェーションと呼び、インスタンシェーションから成る集
合を競合集合と呼ぶ。競合解消フェーズでは、競合集合
から実行すべきインスタンシェーションを一つだけ選出
する。ルール実行部は競合解消フェーズで選出されたイ
ンスタンシェーション中のＷＭＥ群に対して選出された
ルールのＲＨ５部を作用させる。

従来、プロダクション・システムを高速化させるための
実行方式として、競合集合の中から複数のインスタンシ
ェーションを選び、ある逐次実行結果と一致するように
ルールを並列実行する方法が提案されている（＠子情報
通信学会論文誌Ｄｖｏ１．Ｊ　７１−Ｄ　Ｎ（１３ｐｐ
、５６７−５７６　１９８８．３石田：プロダクション
・システムの並列実行可能性の解析）。以下、この方式
について簡単に説明する。

２ル一ル間に次に示す関係がある場合、これらのルール
を並列実行した結果はいかなる逐次実行結果とも一致し
ない。

■　ルール１で削除するＷＭＥをルール２で条件要素と
している場合 ■　ルール２で生成するＷＭＥをルール２でｎｏｔ条件
要素（そのＷＭＥがなければ成立する）としている場合 ■　ルール１で生成し、ルール２で削除する共通のＷＭ
Ｅがある場合 これらの関係はルール干渉と呼ばれており、競合集合か
ら複数のインスタンシェーションを選択する時は、いか
なる２ルールの間にもルール干渉がおきないように選択
しなければならない。よって、ルール実行を並列に行う
ときは、ルール干渉を検出するフェーズが必要となり、
これを干渉検出フェーズと呼ぶとすると、プロダクショ
ン・システムの認知サイクルは、照合フェーズ→干渉検
出フェーズ→実行フェーズという形になる。

次に干渉検出を用いた並列実行を順次例を用いて説明す
る。こＮでは全てのプロセッサからアクセスできる共通
ＷＭを用いる。まず初期のＷＭ（ＷＭ　Ｏ）に記憶して
いるＷＭＥが（ａｔ　ｂ、ｃ）であり１次のルールがあ
るとする。

ルール１　：　Ｉ　Ｆ　　ａ　、　ＴＨＥ　Ｎ　ｄｅｌ
ｅｔｅ　ｂルール２　：　Ｉ　Ｆ　　ｂ、　ＴＨＥＮ　
ｄｅｌｅｔｅ　ａルール３　：　Ｉ　Ｆ　　ｃ、　ＴＨ
ＥＮ　ｃｒｅａｔｅ　ｄ第３図は逐次実行を行った例で
ある。（ａ）の逐次実行１では、まずルール１を実行し
、ルール２の条件要素であるｂを削除するので、ルール
２は実行できない。従って次に実行するルールはルール
３となり、逐次実行結果は（ａ、ｂ）となる。

また、（ｂ）の逐次実行２ではルール２を先に実行し、
ルール１の条件要素であるａを削除するので、ルール１
は実行することができず１次の認知サイクルではルール
３を実行し、結果は（ｂ、ｄ）となる。

第４図には、干渉検出を行わず、無条件にルールを並列
実行した例を示す。こＳではＷＭＯと照合した全てのイ
ンスタンシェーション、即ちルール１、ルール２、ルー
ル３を同時に実行し、ルール１とルール２の実行によっ
てａとｂが削除され。

ルール３の実行によってｄを生成し、実行結果は（ｄ）
となる。このように無条件に並列実行を行うと、第３図
におけるいずれの逐次実行結果とも一致しない結果にな
る。

第５図には、干渉検出の結果、選択したルールを並列実
行した例を示す。ＷＭＯと照合するルール１，２．３は
ルール１とルール２が干渉検出をおこす条件の■を満た
す。従って、こ＼ではルール１とルール２のうちどちら
かは選択候補から除き、干渉検出後のルール集合は（１
）：　　（ルール１、ルール３）か、（２）：　　（ル
ール２．ルール３）となる。これらのルール集合にたい
して優先度はなく、どちらのルール集合を選択してもか
まわない、第５図ではルール集合（１）を選択し、並列
実行した場合を示す。ルール１とルール３の実行により
、ＷＭＯのＷＭＥ　：　ｂ、ｃが同時に変更され、実行
結果は（ａ、ｃ）となり、第３図（ａ）の逐次実行１の
結果と一致する。

〔発明が解決しようとする課題〕

以上説明してきたように、プロダクション・システムに
おいて、並列実行を行う時は、干渉検出を必ず行わなれ
ばならないが、この干渉検出における計算量が大きいと
いう問題がある。今、総ルール数がｎであり、１ルール
につき１インスタンシエーシヨンが照合しているとする
と（以下においても同様）、干渉検出フェーズでは、２
ル一ル間についてルール干渉を検出するため、該干渉検
出フェーズにおける計算量は、ｎＣ，＝ｎ　（ｎ−１）
／２．すなわちｎ２オーダの計算量が必要になる。

プロダクション・システムのルール数としては。

数１００ル一ル以上あることも珍しくないため、干渉検
出フェーズによるオーバヘッドにより、かえって逐次実
行方式より遅くなることもありうる。

そこで、干渉検出を高速に行う方法の一つとして、干渉
検出を行うルールを限定する方法が考えられる。まず、
ルールコンパイル時に、ルールの条件部と実行部を調べ
ることによって、干渉をおこす可能性のあるルール（干
渉ルール）を調べておく、干渉検出フェーズにおいては
、該干渉ルールについてだけ照合しているＷＭＥが同一
であるか調べる。この方法によれば、干渉ルールが１ル
ールあたり平均ｍルールである場合、干渉検出フェーズ
での計算量は、ｎ−ｍ／２となる。こ＼で１／２として
いるのは、２ルールのうち、どちらか一方で検出を行え
ばよいからである。したがって、ｎ＞ｍならば効果的で
あるが、実際にはｍはｎに比例して大きいことが多く、
結局はｎ２のオーダとなってしまい。計算量は削減され
ない。

このように、従来の干渉検出を用いた並列実行方式では
、干渉検出フェーズにおける計算量が、ルール数が多く
なるほど増えるため、結果的には逐次実行よりも遅くな
るという問題があった。

本発明の目的は、各プロセッサの照合結果について部分
的に干渉検出を行って、インスタンシェーションを絞り
込み、干渉検出フェーズの実行時間を削減することによ
って、高速なプロダクション・システムの並列実行方式
を提供することにある。

〔課題を解決するための手段〕

上記目的を達成するため１本発明は、各プロセッサにお
いて照合フェーズを終了した後、干渉検出フェーズを行
う前に、該プロセッサの照合結果について干渉検出を行
い（以下１部分干渉検出と呼ぶ）、該部分干渉検出フェ
ーズの終了後、該部分干渉検出では調べられなかった他
プロセッサの部分干渉検出結果との干渉検出を行い、該
干渉検出フェーズで選択されたインスタンシェーション
を実行することを特徴とするものである。

〔作　用〕

並列実行方式は、ルール実行フェーズだけでなく、照合
フェーズでも複数のプロセッサを用いて並列化する方式
が通常とられる。したがって、照合フェーズの結果は各
プロセッサ毎に得られる。

本発明では、各プロセッサにおいてルール照合を実行し
た後、該プロセッサの照合結果について部分的に干渉検
出を行ってインスタンシェーションを絞り込む。

本発明方式における干渉検出にかへる計算量を求めてみ
る。こぎでは、２台のプロセッサを用いるとすると、プ
ロセッサあたりの照合ルール数は平均□であるので１部
分干渉検出にかぎる計算量は　　　となる。次に干渉検
出フェーズでは、ｐ １プロセッサあたりの計算量は、部分干渉検出にｐ 　ｘ すると、（ｐ−１）プロセッサにアクセスし、そとなる
。よって全プロセッサでは ２（ｐｘ）” 以上示したように、本発明方式における干渉検に削減さ
れる。この式から、プロセッサ数ｐ及び部分干渉検出に
おけるルールの絞り込み度Ｘが高ければ高いほど、本発
明方式は効果を発揮することがわかる。実際、照合フェ
ーズの並列方式の一つとして、干渉をおこすルール群を
同一のプロセッサに割り当て＼照合を行うようにする方
法も考えられるので、この照合方法を用いて１部分干渉
検出において、１桁のルール数に絞り込めることができ
れば１水力式がより有効になることがわかる。

次に本発明方式の変形として、干渉検出フェーズにおい
て、あるルールを優先して選択することが考えられる。

実際、ルール干渉をおこすルールは、どちらを選択して
もかまわない、こぎでは。

一番はじめに部分干渉検出が終了したプロセッサの選択
したインスタンシェーションすべてを、実行フェーズに
おいて実行することにする。すなわち、このプロセッサ
は干渉検出フェーズを行うことなく、すぐに実行フェー
ズに移る。実行されたルールは、全てのプロセッサから
アクセス可能なメモリ上に記憶しておく。次に部分干渉
検出が終了したプロセッサは１部分干渉検出結果から、
既に実行されたルールと干渉をおこさないインスタンシ
ェーションを選択して実行する。

この方式の先の方式との違いは、干渉検出において、他
のプロセッサの部分干渉検出結果を必要としないことで
ある。先の方式では、他のプロセッサの部分干渉検出結
果が必要なため１部分干渉検出が早く終了しても、全て
のプロセッサが部分干渉検出を終了するまで干渉検出は
行えない。また、干渉検出を始めた後も、全プロセッサ
が同時に他のプロセッサにアクセスするので、プロセッ
サ間を結ぶ通信線が他のプロセッサの通信に使われてい
るような通信の競合がおこりやすい、一方、この方式で
は、他のプロセッサの実行状態にか＼わらず、各プロセ
ッサは共通メモリ内のインスタンシェーションを参照す
ることによって干渉検出フェーズを行うことができる。

また、干渉検出フェーズに移るタイミングが各プロセッ
サで異なるので、通信の競合もおこりにくい。このよう
に、干渉ルールのうち優先的に一部のルールを選択すれ
ば、干渉検出フェーズで同期をとる必要がなく。

高速に認知サイクルを実行できる。

〔実施例〕

以下、本発明の一実施例について図面により説明する。

第１図は本発明方式の一実施例を説明するためのブロッ
ク図である。第１図において、プロダクション・システ
ム実行装置１はワーキングメモリ（ＷＭ）管理部２．干
渉検出部３、及び数台のプロセッサ４から構成される。

各プロセッサ４は、ルール照合部５、部分干渉検出部６
．ルール実行部７から構成される。

各プロセッサ４のルール照合部５では、ＷＭ管理部２を
参照しながらルール照合を行うゆこＮでＷＭ管理部２は
、全てのプロセッサ４からアクセス可能な共通メモリ（
ＷＭ）を管理している。照合したルールとＷＭＥの組は
、インスタンシェーション８としてルール照合部５から
部分干渉検出部６へ送られる。部分干渉検出部６では、
同じプロセッサで照合が行われているルールについて干
渉検出を行う。

部分干渉検出を終了したプロセッサ４は、共通バス９を
介し、選択したインスタンシェーションを干渉検出部３
へ送る。干渉検出部３は、全てのプロセッサ４からイン
スタンシェーションを受信した時に、ルールの干渉検出
を行う。すなわち、あるプロセッサの部分干渉検出部６
で検出できなかった。他のプロセッサにおいて照合され
ているルールについて、干渉検出を行う。干渉検出部３
は全てのプロセッサからアクセス可能であればよく、各
プロセッサ４と干渉検出部３間の通信方法は、共通バス
９の他に通信線を用いてもよい。

干渉検出の終了後は、選択したインスタンシェーション
を各プロセッサ４のルール実行部７へ知らせる。ルール
実行部７ではルールを実行し、ＷＭ管理部２へ新しく追
加、または削除するＷＭＥ情報１０を送る。ＷＭ管理部
２では該ＷＭＥに関して、ＷＭを書き換える。

以上の認知サイクルを、全てのプロセッサ４において照
合するルールがなくなるまで繰り返す。

第２図は干渉検出部３を各プロセッサ４内に設け、一部
のルールを優先して選択する実施例のブロック図を示す
。プロダクション・システム実行装置１の構成は、基本
的には第１図と同様であるが、干渉検出部３を各プロセ
ッサ内に持つかわりに、ルールバッファ記憶部１１を各
プロセッサ４に共通に設ける。

各プロセッサ４では、部分干渉検出が終了すると、ルー
ルバッファ記憶部１１にアクセスする。

こ＼で、ルールバッファ記憶部１１は、全てのプロセッ
サからアクセス可能で、各プロセッサ４とルールバッフ
ァ記憶部１１間の通信方法は、共通バス９を用いてもよ
いし、通信線を用いてもよい。

ルールバッファ記憶部１１に何も書き込まれていない場
合は、当該プロセッサ４が部分干渉検出部６で選択した
インスタンシェーションをすべてルールバッファ記憶部
１１に送り、干渉検出部３の実行はスキップして、ルー
ル実行部７においてこれらのルールを実行する。ルール
バッファ記憶部１１に何らかのインスタンシェーション
が書き込まれている場合は、当該プロセッサ４の干渉検
出部３において、これらのインスタンシェーションと干
渉をおこさないインスタンシェーションを選択する。さ
らに、選択したインスタンシェーションをルールバッフ
ァ記憶部１１に書き込み、ルール実行部７においてこれ
らのルールを実行する。

〔発明の効果〕

以上述べたように１本発明によれば、従来のプロダクシ
ョン・システムの並列実行方式と比較して、部分干渉検
出を行うことによって干渉検出にか＼る計算量を削減し
、プロダクション・システムを高速に実行できるという
利点がある。

【図面の簡単な説明】

第１図及び第２図は本発明の一実施例を説明するための
ブロック図、第３図、第４図及び第５図は、従来のプロ
ダクション・システムの実行方式を説明するため図であ
る６ １・・・プロダクション・システム実行装置、２・・・
ＷＭ管理部、　３・・・干渉検出部。 ４・・・プロセッサ、　５・・・ルール照合部、６・・
・部分干渉検出部、　７・・・ルール実行部、９・・・
共通バス、　　１１・・・ルールバッファ記憶部。 並Ｊ１］賞り予１ （α９ 悉二疋寅イ弯” Ｃ））） 逐ン、廻犬イテ ？

Claims (2)

【特許請求の範囲】
1. （１）複数のプロセッサによって認知サイクルを実行す
   るプロダクシヨン・システムにおいて、各プロセッサに
   おいてルール照合を実行したのち、該プロセッサの照合
   結果について干渉検出を行う部分干渉検出フェーズと、
   全てのプロセッサにおいて部分干渉検出を終了したのち
   、該部分干渉検出結果と他プロセッサの該部分干渉検出
   結果との干渉検出を行う干渉検出フェーズを設け、該干
   渉検出フェーズで選択されたインスタンシェーシヨンを
   実行することを特徴とするプロダクション・システムの
   並列実行方式。
2. （２）上記干渉検出フェーズにおいて、一番はじめに部
   分干渉検出フェーズが終了したプロセッサは選択された
   インスタンシェーションをすべて実行し、続いて部分干
   渉検出フェーズが終了したプロセッサは、該部分干渉検
   出結果の中から、既に実行に移されたインスタンシェー
   ションと干渉をおこさないインスタンシェーシヨンを選
   択して実行することを特徴とする請求項（１）記載のプ
   ロダクシヨン・システムの並列実行方式。