JPH065507B2

JPH065507B2 - 推論計算機

Info

Publication number: JPH065507B2
Application number: JP61185043A
Authority: JP
Inventors: 正弘菅谷; 衛杉江; 貢米山; 正明岩嵜; 利明森
Original assignee: Agency of Industrial Science and Technology
Current assignee: National Institute of Advanced Industrial Science and Technology AIST
Priority date: 1986-08-08
Filing date: 1986-08-08
Publication date: 1994-01-19
Anticipated expiration: 2009-01-19
Also published as: JPS6341933A

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は推論計算機に係り、特にユニフィケーション処
理の実行速度を高速化するために好適な、タグを用いた
推論計算機に関する。

〔従来技術〕

従来のユニフィケーション処理では、情報処理学会第３
０回全国大会講演論文集（１９８５年）「並列推論マシ
ンＰＩＭ−Ｒにおけるプロセス内部表現」（６Ｃ−７，
Ｐ．１９７）に示すごとく、ゴール側とクローズ側の引
数を表わすデータにタグ部を設け、そのタグにより引数
の種類を識別し次の処理を決定していた。しかしタグ部
をデータ内から取り出す処理は、プログラムで記述され
ており、データをマスクし、ビットをシフトさせること
により行なわれていた。

〔発明が解決しようとする問題点〕この方式では、タグ部をデータから取り出す処理だけで
も多大のステップ数即ち時間を要し、しかもコール側
と、クローズ側の引数に対して、それぞれ同じ処理が必
要である。その為に１度のユニフィケーション処理を行
なう毎に、同じ処理を２度も繰り返さなければ、ゴール
側とクローズ側の引数同士の組み合わせを知ることはで
きなかった。

従って、タグによる引数の識別や引数同士の組み合わせ
による次の処理ルーチンの決定とそこへの分岐などとい
った一連の処理を考え合わせると、ユニフィケーション
の前処理に当たる「引数の組み合わせに従った処理の分
岐」は、実行過程が複雑で時間も掛かった。以上の様
に、上記文献に示される様な従来のユニフィケーション
処理では、以上で述べた一例の処理、しいてはユニフィ
ケーション全体の処理の高速化の点に問題があった。

本発明の目的は、処理手順（ステップ数）が少なく、従
って、処理時間が短く、より高速で効率の良い、タグを
用いたデータ処理装置を提供することにある。

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

プロログ（Ｐｒｏｌｏｇ）実行における主要な処理がユ
ニフィケーション（統一化）処理である。その処理は、
対応する述語内のゴール側とクローズ側の引数同士の比
較と書き込みである。この処理は、処理される引数の種
類によって異なる。またこの引数の種類は、一般にデー
タ内のタグ部に示されている。従って、引数同士の比
較、書き込み処理は、データ内のタグ部を取り出し、タ
グの内容により対応するルーチンへ制御を移して行なわ
れる。

以上の処理の中で、タグ部を取り出して対応するルーチ
ンを識別し、制御を移す部分に注目した。従来この処理
はプログラムにより記述され、データをマスクしてタグ
部を取り出し、タグの内容によりその引数の種類に対応
したルーチンへ制御を移していた。この処理は、処理手
順（実行ステップ数）が多い上に、ゴールの引数とタグ
の引数の２回に分けて同様な処理を行なっていた。つま
り、ユニフィケーションされるゴールとクローズの引数
が、対応する処理ルーチンに渡されるまでに、手順の多
い処理が２度も必要であった。

この処理をゴール側クローズ側両者同時に１度で済ませ
ることができれば、ユニフィケーション処理の高速化に
通ずる。その為には、１）データからのタグ部の取り出し。

２）タグによる分岐先ルーチンのアドレスの決定。

３）そのアドレスに従った処理の分岐。

といった一連の処理を、ゴール側クローズ側両者同時
に、しかも１命令で実行できる装置が必要である。そこ
で、上記の様な機能を持ったハードウエア装置を設ける
ことにより、先に述べた高速化の目的を実現しようとす
るのが本発明である。

〔発明の実施例〕以下、本発明の一実施例を図面により詳細に説明する。

まず第２図は、本発明による「タグを用いたデータ処理
装置」の一実施例における処理のフロー・チャートであ
る。ここには、オペランドのタグ部を取り出すところか
ら、プログラムが分岐するところまでを表わしてある。

第３図は、第２図のフロー・チャートで表わされる一実
施例の概略構成を示す図である。１はオペレーション・
コードとオペランド（実際はアドレス）３つが納められ
た命令語のレジスタ、２はプログラムやデータが納めら
れた主記憶ユニット、３は主記憶ユニット２にアクセス
しデータなどを取り出す（フェッチする）アドレス・フ
ェッチ回路、４は命令語レジスタ内のオペレーション・
コードによりデータの流れやタイミングなどを制御する
命令制御回路、５はオペランドのタグ部に演算を加えて
分岐先アドレスを作り出す演算器であり、第１図に示す
ごとく５個のデータ・レジスタと、１個ずつのビット・
シフタと加算器から成る。

主記憶ユニット２から、命令が、アドレス・フェッチ回
路３を介して命令語レジスタ１へ送られる。この中のオ
ペランドのアドレス・コードに従って、アドレス・フェ
ッチ回路３が主記憶ユニット２からオペランドをフェッ
チし、またアドレス・フェッチ回路３を介してオペラン
ドをアドレス演算器５へ送る。命令語レジスタ１内のオ
ペレーション・コードからは、命令制御回路４へ信号が
送られ、そこからアドレス・フェッチ回路３とアドレス
演算器５へ制御信号が送られる。

以上の様な概略構成で、分岐先アドレスが求まり、プロ
グラムの制御がそこへ移る。

第１図は、上記第３図の詳細構成を表わす図である。こ
の図の構成で、第２図のフローに従って処理が進んでい
く。以下図に従って説明していく。

まず主記憶（ＭＳ）２以上のプログラムの中から、命令
（ＩＮＳＴ）２１が取り出され、命令語レジスタ（Ｉ
Ｒ）１へアドレス・フェッチ回路（ＡＦＣ）３を介して
送られる。その命令のオペレーション・コード（ＯＣ）
１１から、命令制御回路（ＩＣＣ）４へ制御信号２００
が送られ、それに基づいて第２図に示されるような処理
の制御が開始される。ＩＲ１の第１オペランド・アドレ
ス（第１ＯＰＡ）１２と第２オペランド・アドレス（第
２ＯＰＡ）１３から、ＡＦＣ３を介して第１オペランド
（第１ＯＰ）２２と第２オペランド（第２ＯＰ）２３が
フェッチされ、ＡＦＣ３を介してそれぞれデータ・レジ
スタ（ＤＲ１）５１データ・レジスタ（ＤＲ２）５２へ
送られる。この時点でＤＲ１５１にはゴール側引数の
データが、ＤＲ２５２にはクローズ側引数のデータが
格納されている。ＤＲ１５１のタグ部（Ｔ）５１１
と、ＤＲ２５２のタグ部（Ｔ）５２１とから、それぞ
れ上位３ビットを取り出し、データ線１０７と１０８を
通して、データ・レジスタ３（ＤＲ３）５３へ送られ
る。このレジスタ内のデータ形式を第６図に示すが、６
ビット・データ内の上位３ビット（Ｂ１）５３１がゴー
ル側、下位３ビット（Ｂ２）５３２がクローズ側のタグ
のビット群で形成される。

ここを出た６ビット・データは、データ線１０９を通り
２ビットのビット・シフタ（ＢＳ）５４へ送られる。こ
のＢＳ５４において、６ビット・データは左へ２ビット
だけシフトされ、右端の２ビットに０が代入され８ビッ
ト・データに変えられる。

この８ビット・データは、データ線１１０を通り、アド
レス加算器（ＡＤＤＥＲ）５６へ入力される。ＡＤＤＥ
Ｒ５６のもう一方の入力は、ＩＲ１の第３ＯＰＡ１４か
らＡＦＣ３を介してフェッチされ、データ・レジスタ
（ＤＲ４）５５からデータ線１１１で入力される第３Ｏ
Ｐ２４であり、これは第７図で示されるルーチン・アド
レス・テーブル（ＲＡＴ）２５のオリジン（ＲＡＴＯ）
２６を示しているアドレスである。（ＡＤＤＥＲ５６の
２つの入力は足し合わされて、データ・レジスタ５７と
ＡＦＣ３を介してＭＳ２内に格納されている上記ＲＡＴ
２５のエントリ２７を指し示すアドレスとなる。つまり
ＢＳ５４の出力の８ビット・データがＲＡＴＯ２６から
のエントリ２７のディスプレイスメント２８を表わして
いることになる。このエントリ２７の中には、分岐先ア
ドレス（ＢＤＡ：ブランチ・ディストネーション・アド
レス）２７′が格納されている。

これで、ゴール側とクローズ側の引数のデータ内のタグ
により、分岐先アドレスが求められたので、ＩＲ１内の
ＯＣ１１に従って、ＩＣＣ４の制御によりプログラムは
ＢＤＡ２７′で示されるルーチンへ分岐される。尚、Ｂ
ＤＡ２７′は引数同士の組み合わせに対応した処理ルー
チンが格納されているＭＳ２上のアドレスである。

以上の様に、第１図の構成において第２図のフローに従
って、一命令だけで引数により分岐が行なわれる。

以下に第１図中の個々の命令やデータやテーブルを図面
により説明する。

まず、第４図はＩＲ１内の命令語の形式を表わす。左か
ら、専用命令のオペレーションコード１１，ゴール側引
数のデータの格納されているアドレスを表わす第１オペ
ランド・アドレス１２，クローズ側引数のデータの格納
されているアドレスを表わす第２オペランド・アドレス
１３，ルーチン・アドレス・テーブル（分岐先アドレス
が格納された、主記憶上にある表）のオリジン（開始ア
ドレス）を表わす第３オペランド・アドレスである。１
１からは、命令制御回路４へ制御信号２００が、１２，
１３，１４からは、アドレス・フェッチ回路３へ、デー
タ信号（それぞれ１０２１，１０２２，１０２３）が出
ている。

第５図は、第１，第２オペランド・アドレス１２，１３
により示され、アドレス・フェッチ回路３により取り出
される。第１，第２オペランドのデータ形式を表わす。
これは、第３図のデータ・レジスタ５１，５２の中身で
もある。データの形式は、ゴール側もクローズ側も共通
で、タグ部を含んだデータ全体の長さは４バイト（３２
ビット）、その内上位１バイト（８ビット）がタグ部５
１１に当たり、残りの下位３バイトがデータ部５１２で
ある。本実施例では、分岐の為の引数の種類の識別に
は、８ビットあるタグの内の上位３ビットのみを用いて
いる。データ・レジスタ１，５１内に格納されたデータ
の場合では、上位３ビットがデータ信号１０７として取
り出され、データ・レジスタ５３の上位３ビット５３１
の入力となる。尚、この取り出される（引数の種類の識
別に利用される）タグのビット数（副）は、３ビットに
限ることはなく、場合に応じて８ビット以下ならば幾つ
でも良い。

第６図は、データ・レジスタ５３内の６ビット・データ
の内部形式を表わす。ビット０からビット２までの上位
３ビット５３１は、第１オペランドであるゴール側の引
数が格納されたデータ・レジスタ５１から、タグの上位
３ビットがデータ信号１０７として入力され作られる。
同様にビット３からビット５までの下位３ビット５３２
は、第２オペランドであるクローズ側の引数が格納され
たデータ・レジスタ５２から、タグの上位３ビットがデ
ータ信号１０８として入力され作られる。この様にして
作られた６ビットのデータは、データ信号１０９として
ビット・シフタ５４へ送られる。

第７図は、分岐先ルーチンのアドレスが格納されている
ルーチン・アドレス・テーブル２５を表わす。先に記し
た様にこのテーブルは主記憶上の連続した領域に取ら
れ、そのオリジン２６は第３オペランドにより示され
る。第１と第２オペランドのタグによって作られた８ビ
ット・データは、オリジンからのディスプレイメント２
８を表わし、第３オペランドと足し合わされるとその結
果はテーブル内のエントリ２７を示すアドレスとなる。
このエントリ内に、引数の組合せに対応した分岐先ルー
チンのアドレス（ブランチ・ディスティネーション・ア
ドレス２７′）が格納されており、このアドレスへプロ
グラムは分岐する。エントリ２７は、３ビットと３ビッ
トの組合せの数である６４個存在し、その中身は同一ア
ドレスが存在しても良く、引数同士の組み合わせに対応
する処理のアドレスを配置する。またこのエントリ２７
の幅は４バイト（３２ビット）で、３２ビット・アドレ
シング・モードでアドレスを格納されていても、上位８
ビットを何等かの制御ビットに用いた２４ビット・アド
レシング・モードで格納されていても良い。テーブル２
５のエントリ２７は、アドレス加算器５６を出で、デー
タ・レジスタ５とアドレス・フェッチ回路３を介した、
データ信号１０６によって指し示される。

上述の実施例では、引例のタグの上位ビットを取り出
し、それを並べて、その後シフトさせることによってア
ドレスを形成していた。しかし、本発明におけるタグに
よるアドレスの形成部分には、他の方法も存在し、それ
に対応した装置が考えられる。以下に第２の実施例とし
て、前記の実施例とは異なった装置を図面により説明す
る。

まず、タグによりアドレスを形成する部分は、装置の概
略構成を示した第３図によると、アドレス演算器５の中
の一部であり、他の部分の構成は最初の実施例と変わら
ない。装置の詳細構成を第８図に示す。図中で破線に囲
まれた部分が、前の実施例と異なる所で、他の部分は第
１図と同じである。

信号の流れを説明すると、まずデータ・レジスタ５１と
データ・レジスタ５２のタグ部が、それぞれ信号線１０
７と１０８を通してＰＬＡ（プログラマブル・ロジック
・アレイ）５８に入力される。ＰＬＡ５８は、ＩＣＣ４
から制御信号２０６によって制御される。ＰＬＡ５８に
おいて、入力のタグの組み合わせに対応した出力が選ば
れる。その出力が、タグにより形成されたアドレスであ
り、前の実施例においては、第１図のビット・シフタ５
４の出力に当たる。先に述べた様に、このアドレスは分
岐先アドレス・テーブル２５のオリジン２６からのディ
スプレイスメント２８になっている。

後の処理は、第１図と同様で、ＰＬＡ５８を出た出力ア
ドレスは、データ線１１３を通じてデータ・レジスタ５
９へ送られる。ＩＣＣ４から制御信号２０７によって制
御されるデータ・レジスタ５９は、アドレス信号をデー
タ線１１４を通じて、アドレス加算器５６の１方の入力
として送り込む。

その後は、構成も信号の流れも第３図と同様で、前の実
施例と変わらない。尚この実施例において、データ・レ
ジスタ１と２から取り出されるタグのビット数は、前回
の様に３ビットに限らず、８ビット以下なら自由に選べ
る。またＰＬＡ５８の出力アドレスも、前回の様に８ビ
ットに限らず、何ビットでも良い。

〔発明の効果〕

本発明によれば、従来プログラムにより記述され、数ス
テップを要する上に、ゴール側とクローズ側の引数で２
度に分け同じ処理を繰り返している、データ内からのタ
グ部の読み出し処理が、分岐処理までをも含めてゴール
側，クローズ側同時に、１ステップで実行できる様にな
る。この処理は、述語の引数ひとつひとつ、リストに対
しては要素のひとつひとつに対して行なわれる為に、対
応１述語同士のユニフィケーション１回の間に数回行な
われる。従って、Prolog実行中に行なわれるこの処理の
回数は非常に多い。その為に、この処理が、Prolog実行
処理全体に占める割合も大きい。このことから、本発明
による「タグによるデータの判定，処理の分岐」の処理
の高速化は、Prologの実行速度向上に対して、非常に大
きな効果をもたらす。

【図面の簡単な説明】

第１図は第１実施例の詳細な構成を表わす図、第２図は
第１実施例における処理のフロー・チャート、第３図は
実施例の概略の構成を表わす図、第４図は命令語の形式
を表わす図、第５図は第１と第２オペランドのデータの
形式を表わす図、第６図はデータ・レジスタ（第１図内
の５３）内の６ビット・データの内部形式を表わす図、
第７図は分岐先アドレス表（ルーチン・アドレス・テー
ブル）を表わす図、第８図は第２実施例の詳細な構成を
表わす図である。５…アドレス演算器、５３…データ・レジスタ、５４…
ビット・シフタ、５６…アドレス加算器、５８…ＰＬ
Ａ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者森利明東京都国分寺市東恋ヶ窪１丁目280番地株式会社日立製作所中央研究所内審査官佐藤秀一

Claims

【特許請求の範囲】

【請求項１】引数を含むデータ内に引数の種類を表わす
タグ部を設け、ゴールである引数とクローズである引数
同志をユニフィケーション処理する推論計算機におい
て、１つの命令によって前記ゴールである引数と前記ク
ローズである引数とを読み出して、分岐先アドレスが格
納されたテーブルの先頭アドレスからのディスプレイス
メントの上位側ビット群を前記ゴールである引数のタグ
部から形成し、同時に、前記ディスプレイスメントの下
位側のビット群を前記クローズである引数のタグ部から
形成する手段、分岐先アドレスが格納されたテーブルの
先頭アドレスと前記形成されたディスプレイスメントと
を足し合わせて得られるアドレスに対応するルーチンに
制御を移す手段を有することを特徴とする推論計算機。