JPH0554136B2

JPH0554136B2 -

Info

Publication number: JPH0554136B2
Application number: JP58030722A
Authority: JP
Inventors: Setsuo Tsuruta; Makoto Nomi; Shoji Myamoto; Koichi Ihara; Masaharu Yabushita
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1983-02-28
Filing date: 1983-02-28
Publication date: 1993-08-11
Also published as: JPS59157760A

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は、計算機にデータとして記憶された専
門知識（経験則）や事実をもとに推論を行う知識
ベースシステムにおいて、大量のリストデータを
高速に処理するに好適な並列推論方式に関する。

〔発明の背景〕

従来の知識ベースシステムの並列推論方式は、
各プロセツサが共通にアクセスできるメモリ（共
有メモリ）を使用し、これに便利な方式である
が、共有メモリのアクセスの競合処理のためのソ
フトウエア、ハードウエアのオーバヘツドが高
く、10台以上の計算機の複合システムでは、アク
セスネツクのため性能改善が期待できなかつた。
従来の並列推論方式としては、例えば、R.D.
FENNELL、V.R.LESSER ： Parallelism
in Artificial Intelligence Problom Solving：
Ａ Case Study of Hearsay ， IE³.
Trans. Comput.、 Feb.1977が知られている。

〔発明の目的〕

本発明の目的は、数10台のマイクロコンピユー
タを用いて、LISPによつて記述された知識ベー
スシステムにおける推論を並列処理することによ
つて、超高速にするための推論方法を提供するこ
とにある。

〔発明の概要〕

このような目的を達成するために本発明では、
各プロセツサのメモリを拡張し、共有メモリを排
し、事実データを拡張した各プロセツサのメモリ
に記憶させ、新事実だけを全推論プロセツサに一
斉送信をするようにしたことに特徴がある。

〔発明の実施例〕

以下、本発明の一実施例を、第１〜５図により
説明する。

第１図と第２図は、本発明の方式を実現する装
置の実施例のシステム構成を示す。第１図は全体
の概略構成図、第２図はシステムの詳細構成図で
ある。

１および２は、それぞれインタプリタコンピユ
ータおよび推論コンピユータと呼ばれるマイクロ
コンピユータで、例えば、第１図のような６角形
の格子状バス４によつて、お互いに、あるいは、
インタプリタコンピユータ１と、推論データ入出
力装置と呼ばれるコンソールやデイスク、あるい
はプロセス入出力装置等の入出力装置３とが結合
されている。バスの結合形態は、４角形など他の
形態でも良い。

なお、マイクロコンピユータ１，２としては
HMCS68000等が使用できる。

第２図で示されるようにインタプリタコンピユ
ータ１は、インタプリタプロセツサ１１とそのロ
ーカルメモリ１２から構成され、推論コンピユー
タ２は、推論プロセツサ２１とそのローカルメモ
リ２２から構成される。

第３図は、本実施例のシステムにおける、各プ
ロセツサ１１または２１の間、および、インタプ
リタプロセツサ１１と推論データ入出力装置３と
の間のメツセージの流れの一例を示す。

インタプリタプロセツサ１１は、推論データ入
出力装置３を通して、推論データ５１を入力し、
推論結果メツセージ５５を出力する。

並列推論処理を行うため、インタプリタプロセ
ツサ１１は全ての推論プロセツサ２１に対して、
推論要求メツセージ５２、および、必要に応じて
推論データメツセージ５３を、ブロードキヤスト
方式で送信する。

推論プロセツサ２１は、推論結果を、推論応答
メツセージ５４として返す。

第４図は、推論要求メツセージ５２のフオーマ
ツトの一例である。

要求メツセージフラグ５２１は、推論要求メツ
セージ５２であることを示すフラグである。要求
メツセージ通番５２２は、推論要求メツセージ５
２に対して付けられた通し番号である。

推論データ種別５２３は、推論データ５２５の
内容を示す。たとえば、推論データ５２５が既知
事実（へのポインタ）６２か、経験則（へのポイ
ンタ）６４かを示す。推論データ長５２４は、推
論データの長さ、つまり、本メツセージで送信さ
れる既知事実６２や経験則６４のデータ数を示
す。

第５図は、推論データメツセージ５３のフオー
マツトの一例である。

データメツセージフラグ５３１は、推論データ
メツセージ５３であることを示すフラグである。
推論データメツセージ５３は、推論に必要な推論
データ５２５の量が多い場合、一定量に達した推
論データを、その都度、送信することにより、推
論要求において、推論要求メツセージ５２の機能
の補うものである。対応要求メツセージ通番５３
２は、このような関係にある（つまり、推論デー
タメツセージ５３が、一定量に達した推論データ
５３６を前もつて送ることにより、その機能を補
おうとする。）推論要求メツセージ５２の通し番
号５２２である。

データメツセージ通番５３３は、推論データメ
ツセージ５３に対して付けられた通し番号であ
る。これは、対応要求メツセージ通番５３２が更
新される度に、０にリセツトされる。

推論データ種別５３４、推論データ長５３５、
推論データ５３６は、第４図で既に説明した、推
論要求メツセージ５２に対するものと全く同じで
ある。

第６図は、推論応答メツセージ５４のフオーマ
ツトの一例である。

応答メツセージフラグ５４１は、推論応答メツ
セージ５４であることを示すフラグである。応答
要求メツセージ通番５４２は、推論応答メツセー
ジ５４が、どの推論要求に対応するかを、その推
論要求に対応する推論要求メツセージ５２の通番
５２２によつて示すものである。応答プロセツサ
番号５４３は、本応答メツセージの送信元である
推論プロセツサ２１のID（番号）を示す。応答メ
ツセージ通番５４４は、推論応答メツセージ５４
に対して付けられた通し番号であり、推論要求に
対して、および各推論プロセツサ２１に対して独
立につけられる。

応答データ種別５４５は、応答データ５４７の
内容（新事実、終了情報など）を示す。応答デー
タ長５４６は、応答データ５４７の長さ、たとえ
ば、新事実の個数などを示す。

第７図は、インタプリタプロセツサ１１のロー
カルメモリ１２のマツプの一例である。

リスト領域７５は、事実群や経験則群などのリ
スト、つまり、既知事実や経験則などのデータの
記憶場所へのポインタとその構造（リスト構造）
を示すポインタ群を含むエリアである。フルワー
ド領域７８は、リストによつてポイントされるデ
ータ本体（例えば、既知事実データ、経験則デー
タ）を記憶するエリアである。

新事実キユー７６は、各推論プロセツサ２１か
ら推論応答メツセージにより送信されてきた新事
実を到着順に保存するためのキユーである。

推論結果記録位置表７７は、推論要求メツセー
ジ５２に対する最初の新事実の新事実キユー７６
内での相対位置（順位）を求めるための表であ
る。

第８図は、推論プロセツサ２１のローカルメモ
リ２２のマツプの一例である。

事実群リスト（領域）６１、経験則群リスト
（領域）６３は、それぞれ、事実群や経験則群な
どのリスト（つまり、既知事実や経験則などのデ
ータの記憶場所へのポインタと、その構造（リス
ト構造）を示すポインタ群）を記憶する領域であ
る。

第９図は、事実群リスト６１と経験則群リスト
６３の構造の一例を示す。

事実群リスト６１は、既知事実（データへのポ
インタ）６２の一方向連鎖である。

経験則群リスト６３は、経験則（データへのポ
インタ）６４の一方向連鎖である。さらに、各経
験則６４は、条件部６５と結論部６６から成り、
条件部６５は、条件（条件データへのポインタ）
６５１の一方向連鎖から成り、結論部６６は結論
（結論データへのポインタ）６６１の一方向連鎖
から成る。

第１０図は新事実キユー７６の一例の構成図で
ある。

新事実キユー７６（本体）には、新事実（への
ポインタ）７６１が、推論応答メツセージ５４に
より新事実を受信した順にキユーされる。

第１１図は、推論結果記録位置表７７の一例の
構成である。

推論結果記録位置表７７は、推論要求メツセー
ジ番号７７０と、このメツセージによる推論の結
果生成された新事実の相対位置７７１との対の集
まりである。

第１２図および第１３図はそれぞれ、インタプ
リタプロセツサおよび推論プロセツサの処理の流
れの一例を示すものである。

以下に、本発明の実施例の動作の説明を行う。

簡単のため順方向推論について説明する。

順方向推論の処理は、以下のようにして行われ
る。

(1) その条件部を既知事実が満足させる経験則を
見つけるため、経験則ぐをサーチする。

(2) 該当する経験則の結論部を取り出し、既知事
実でないかどうか、つまり新事実が見つかつた
かどうかを、事実群に対して調べる。

(3) 新事実を、新事実群に記憶するとともに、既
知事実として事実群に加え、(1)に戻る。

(4) 新事実が見つからなくなるか、結論部が停止
要求なら処理を終了する。

順方向推論（以下、推論と呼ぶ。）における本
発明の実施例の動作は次のとおりである（第１２
図、第１３図参照）。

(1) 推論データ入出力装置３から、推論データ５
１が入力されると（ステツプ201）、インタプリ
タプロセツサ１１は、このデータから、推論要
求メツセージ５２を作成し（ステツプ202）、各
推論プロセツサ２１全部に、一斉送信する（ス
テツプ203）。まとめて推論を行つて推論効率を
上げるため、推論データメツセージ５３を何回
か送信した後、推論要求メツセージ５２を送る
ことも許される。

(2) 推論プロセツサ２１は、推論データメツセー
ジ５３を受信する（ステツプ301）と、既知事
実（のポインタ）６２を、事実群リスト６１に
記憶する（ステツプ302）。推論要求メツセージ
を受信すると、既知事実（のポインタ）６２
を、事実群リスト６１に記憶した上で、推論を
開始する（ステツプ303）。

(3) 推論プロセツサ２１での推論は、下記の通
り。

(i) 経験則群リスト６３の先頭から順に、経験
則６４を取り出す（ステツプ304）。最後の経
験則６４に達したら(iv)の処理を行う。

(ii) 取り出した経験則６４の条件部６５を第１
条件６５１から順に取り出し、事実かどうか
をチエツクする（ステツプ305）。すなわち、
事実群リスト６１の先頭から順に既知事実
（のポインタ）６２を取り出し、条件（のポ
インタ）６５１と一致するかどうかをチエツ
クする。事実群リスト６１のどの既知事実６
２とも、条件６５１が一致しなければ、(i)の
処理（ステツプ304）に戻り次の経験則６４
を取出す。第１条件６５１に一致する既知事
実６２があれば（つまり第１条件６５１が事
実なら）、条件部６５の全ての条件６５１を
順次チエツクする。

事実でない条件６５１があれば、(i)の処理
（ステツプ304）に戻り次の経験則６４を取出
す。条件部６５の条件が全て事実なら(iii)の処
理を行う。

(iii) 条件部６５の条件６５１が、全て事実であ
ることのチエツクを完了した経験則６４の結
論部６６から全ての結論６６１を取り出し新
事実５４７を見つける（ステツプ306）。

すなわち、結論部６６の先頭順に結論（ポ
インタ）６６１を取り出し、既知事実（のポ
インタ）６２と一致するかどうかを、事実群
リスト６１の全ての既知事実６２に対してチ
エツクし、どの既知事実６２とも一致しなけ
れば、新事実５４７とする。

新事実が見つからなければ、(i)の処理（ス
テツプ304）に戻り、次の経験則６４を取出
す。見つかれば(iv)の処理（ステツプ308）を
行う。

(iv) 見つかつた新事実（のポインタ）５４７と
その個数５４６、および新事実５４７を導出
した経験則（のポインタ）６４を、推論応答
メツセージ５４にセツトして送信する（ステ
ツプ308）。新事実が見つからなかつた場合
は、新事実の個数５４６を０にした推論応答
メツセージ５４を返す（ステツプ307）。

(4) インタプリンタプロセツサ１１は、各推論プ
ロセツサ２１の推論応答メツセージ５４を受信
し（ステツプ204）、新事実があれば、新事実キ
ユー７６に入れる。ただし、各推論要求メツセ
ージ５２に対する最初の新事実７６１の新事実
キユー７６内相対位置は、新事実相対位置７７
１として、推論結果記録位置表７７に記録され
る（ステツプ205）。

送出した推論要求メツセージ５２に対する推
論応答メツセージ５４を、全推論プロセツサ２
１から受信し終えた時（ステツプ206）、この推
論要求に対応する新事実７６１がなければ、(5)
の処理（ステツプ209）を行う。

この新事実があれば、新事実キユー７６と推
論要求対応新事実表７７をもとに、対応する新
事実７６１全部から推論要求メツセージ５２を
組立て（ステツプ207）、全推論プロセツサ２１
に一斉送信する（ステツプ203）。

この新事実７６１の一斉送信方式としては、
効率を上げるため、新事実７６１が、規定数以
上あつまつたら推論データメツセージ５３とし
て、推論プロセツサ２１に一斉送信しておき、
すでに送出した推論要求メツセージ５２に対す
る推論応答メツセージ５４を、全推論プロセツ
サ２１から受信し終えた時、未送信の新事実７
６１だけから推論要求メツセージ５２を組立て
一斉送信することも考えられる。ただし、この
場合は、推論プロセツサ２１は、推論要求メツ
セージ５２処理中に受信した推論データメツセ
ージ５３中の新事実（即ち既知事実５３６）
を、(2)のように事実群リスト６１に組込むこと
をしないで、推論要求処理が終了してから、つ
まり推論応答メツセージ５４を送り返した後
に、上記の既知事実５３６を事実群リスト６１
に加える。

(5) インタプリタプロセツサ１１は、推論終了状
況情報、および、必要に応じて、新事実キユー
７６の内容を編集した推論結果メツセージ５５
を、推論データ入出力装置３に出力する（ステ
ツプ209）。

第１４図は、本発明の方式を実現するシステム
構成の他の実施例を示す図である。

１００１はインタプリタプロセツサ、１００２
は推論プロセツサと呼ばれる処理装置である。こ
れらのプロセツサは、メツセージ伝送バス１０６
１で結合されている。

１００９は、コンソールタイプライタ、デイス
プレー、プロセス入出力装置などの入出力装置
で、以下推論用入出力装置と呼ぶ。インタプリタ
プロセツサ１００１は、推論用入出力装置１００
９とバス１０６２で結合されている。

インタプリタプロセツサ１００１は、メモリ１
００３を持つ。メモリ１００３は、インタプリタ
専用メモリブロツク１０３０と知識リストブロツ
ク１０４１から成る。インタプリタ専用メモリブ
ロツク１０３０は、専用メモリアクセスバス１０
７０により、インタプリタプロセツサ１００１だ
けから読み書きされるメモリブロツクである。

推論プロセツサ１００２は、推論メモリ１００
４を持つ。メモリ１００４は、推論プロセツサ専
用メモリブロツク１０４０と知識リストブロツク
１０４１から成る。

知識リストブロツク１０４１は、読み込みは、
バス１０７１を通して各プロセツサからローカル
に行われるが、書き込みは、共通書込みバス１０
６８を通して、インタプリタプロセツサ１００１
により、全部の推論プロセツサ１００２に対して
一斉に行われる。アービタ１００５は、知識リス
トブロツク１０４１に対する読み込みと書き込み
の競合処理を行う（読み込み時は書き込みが出来
ない。逆も成り立つ。）。デユアルポートメモリ等
で実現する。

各プロセツサの知識リストブロツク１０４１の
内容はすべて同一である。

以下に、第１４図の動作の説明を行う。

コンソールタイプライタ、デイスプレー、ある
いはプロセス入出力装置などの入出力装置（推論
用入出力装置と呼ぶ）１００９から、推論コマン
ドが入力されると、インタプリタプロセツサ１０
０１は、これから推論用データを作成し、バス１
００８（の制御線）により全プロセツサ１００
１，１００２の知識リストブロツク１０４１への
一斉書込み要求を出した後、バス１００８（のデ
ータ線）により全プロセツサ１００１，１００２
の知識リストブロツク１０４１への一斉書込みを
行い、必要な推論用データを全て書込んだ後、バ
ス１００８（の制御線）により推論要求を全推論
プロセツサに出力する。

なお、知識リストブロツク１０４１に、推論要
求を事実として（つまり、データの１つとして）
書き込み、これを推論プロセツサ専用メモリブロ
ツク１０４０に格納した経験則に基づき駆動開始
データとしてもよい。また、共通バス１００８
は、インタプリタプロセツサ１００１、推論プロ
セツサ１００２に対しDMAバスである。したが
つて、インタプリタプロセツサ１００１から各推
論プロセツサ１００２への伝送オーバヘツドが極
めて小さく、性能を著しく向上できる。

全推論プロセツサは、知識リストブロツク１０
４１を参照するだけで、すなわちメモリアクセス
を競合することなく、並列に推論を行い、結果
を、推論応答メツセージにして返す。

インタプリタプロセツサ１００１は、全ての推
論プロセツサからの応答が返るか、一定時間が経
過した後、推論要求メツセージに対して返された
全ての推論応答をチエツクし、推論が終了したと
判断すれば推論結果を、推論結果メツセージとし
て、推論用入出力装置１００９に出力する。推論
が終了していないと判断すれば、推論応答メツセ
ージから、推論メツセージを作成し推論プロセツ
サに対する推論要求を繰返すとともに必要な情報
は推論結果として、保存する。

第１５図および第１６図はそれぞれ第１４図の
インタプリタプロセツサおよび推論プロセツサで
の処理の流れの一例を示すものである。

第１２図および第１３図の処理フローとの相違
点については上述した通りであり、その他の点は
第１２図および第１３図と同じであるので、ここ
では説明を省略する。

〔発明の効果〕

本発明によれば、マイクロコンピユータを複数
台接続して、各プロセツサのローカルメモリにリ
スト形式の知識データを分散し、これらの知識デ
ータを用いた推論処理をメモリやバスを競合しな
いように並列に行う知識ベース用組込み関数を持
つLISPマシンが構成できるので、実用新規の知
識ベースシステム（例えば、経験則の数が500以
上のプロダクシヨンシステム）などの高知能情報
処理が、 (1) 高性能に（従来の数10倍以上） (2) フレキシブルかつ効率良く (3) 安価に（従来のミニコンの価格以下）作成できる効果がある。

【図面の簡単な説明】

第１図は本発明を実現するシステムの一例の構
成の概要図、第２図は本発明を実現するシステム
の一例の構成図、第３図は第１図のシステム内の
バス上のデータの流れを示す図、第４〜６図はそ
れぞれ推論要求メツセージ、推論データメツセー
ジ、推論応答メツセージを一例のフオーマツト、
第７図、第８図はそれぞれインタプリタプロセツ
サ、推論プロセツサのローカルメモリの一例のマ
ツプ、第９図は事実群リストと経験則群リストの
一例の構成図、第１０図は新事実キユーの一例の
構成図、第１１図は、推論結果記録位置表の一例
の構成図、第１２図および第１３図はそれぞれ第
２図のインタプリタプロセツサおよび推論プロセ
ツサの処理の流れの一例を示すフローチヤート、
第１４図は本発明を実現するシステムの他の実施
例の構成図、第１５図および第１６図はそれぞれ
インタプリタプロセツサおよび推論プロセツサの
処理の流れの一例を示すフローチヤートである。１１……インタプリタプロセツサ、２１……推
論プロセツサ、１２……インタプリタプロセツサ
のローカルメモリ、２２……推論プロセツサのロ
ーカルメモリ、５２……推論要求メツセージ、５
３……推論データメツセージ、５４……推論応答
メツセージ、６１……事実群リスト、６２……即
知事実、６３……経験則群リスト、６４……経験
則、６５……条件部、６６……結論部、６５１…
…条件、６６１……結論、７６……新事実キユ
ー、７７……推論結果記録位置表。

Claims

【特許請求の範囲】１バス結合された複数の処理装置と各処理装置
に付属したメモリから成る複合計算機システムに
おいて、特定の処理装置は推論指令を受付け、該
推論指令を他の複数の処理装置で並列に推論処理
する推論要求に変換し、該推論要求を他の複数の
処理装置に一斉に送信し、他の複数の処理装置
は、それぞれ、該処理装置に予め割当てられた経
験則データのすくなくとも一部とこれに関連する
事実データを、該処理装置に付属した専用メモリ
に記憶させておいて、上記推論要求を受信した
時、事実データをチエツクして適用可能な経験則
データを探索する処理と、探索された事実データ
を適用したとき新事実が生成されるかどうかを推
論する処理と、推論の途中で生成される新事実を
上記特定の処理装置及び他の複数の処理装置に送
信する処理と、以後、新事実を受信した他の複数
の処理装置が該新事実データをチエツクして上記
探索する処理と、推論する処理と、送信する処理
とを繰り返し、上記特定の処理装置がどの処理装
置も新事実を送信しなくなつたと判断したときに
該繰り返す処理を終了し、上記特定の処理装置は
得られた新事実を推論の最終結果として出力する
ことを特徴とする並列推論方法。２上記経験則データのすくなくとも一部とこれ
に関連する事実データを、ポインタで結合された
リストの形で専用メモリに記憶する特許請求の範
囲第１項記載の並列推論方法。３上記繰り返す処理は、上記推論の途中で生成
される新事実を受信した特定の処理装置で該新事
実にもとづき推論要求データを編集し、該推論要
求データを他の複数の処理装置に一斉に送信する
ことを繰り返す処理を含む特許請求の範囲第１項
記載の並列推論方法。４上記専用メモリは、該メモリを備えた処理装
置だけが読み書きできるメモリブロツクと、該処
理装置だけが読め、該処理装置とは異なる１つの
特定の処理装置だけが、書き込むことができ上記
知識リストを記憶するメモリブロツクとからなる
特許請求の範囲第１項記載の並列推論方法。５上記新事実を上記特定の処理装置及び他の複
数の処理装置に一斉に送信する特許請求の範囲第
１項記載の並列推論方法。