JPS6069748A - 情報処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は記憶領域に格納されているプログラム情報を取
出し、取出されたプログラム情報に基づいて情報処理を
行う情報処理装置に関し、特に述語論理型言語の代表で
あるＰ　ｒｏｌｏｇのごとき非決定性処理に好適な情報
処理装置に関する。

〔従来技術〕

ストアトプログラム方式の情報処理装置は、第１図に示
すごとくプログラム情報は通常のランダムアクセスメモ
リ装置（ＲＡＭ）１３内のプログラム情報格納領域１３
ａに格納しており、プログラムカウンタ（ＰＣ’＞１２
の値によって、この値に対する番地に格納されているプ
ログラム情報を取出し、取出されたプログラム情報に基
づいて情報処理装置（ＣＰＵ）１１とＲＡＭ１３のワー
ク領域１３ｂを用いて情報処理を行う構成となっている
。ワーク領域１３ｂは処理を進めていく上で必要な記憶
領域である。

一般的な汎用計算機の構成は第１図と同じであるが、こ
のような構成を持つ情報処理装置の場合、例えばＦ　ｏ
ｒｔｒａｎのような逐次処理を前提とし決定性処理を基
本とする情報処理（次に何を実行するかがプログラムの
段階で決定されている）は、効率的に行われる。これは
、現在の汎用ａ１算機の鵬栄を見ても明らかである。し
かし、このような情報処理装置においては、プログラム
情報および情報処理の性格によっては、制御が複雑とな
り、処理速度の高速化が図れないという問題がある。こ
こでは、その−例として述語論理型言語の代表であるｐ
　ｒｏｌｏｇを取り上げ説明する。

第２図はＰ　ｒｏｌｏｇのプログ、ラム（積木の例）と
事物関係のｌ界を示す図である。Ｐ　ｒｏｌｏｇは第２
図に示すように節で記述され、その節は述語と呼ばれる
構成要素よりなり立っている。述語は、述語名（引数１
．引数２．・・）（第２図では例えばｏ　ｎ　（Ａ、　
Ｂ）　’）という表現形式で表される。

Ｐ　ｒｏｌｏｇのプログラムは宣言節と規則節によりデ
ータベース（事物関係の世界）を創り上げる。このデー
タベースに対して間合せ節が与えられると、自動的にデ
ータベースの中の規則節により述語を置き換えて宣言節
に導くことにより答えを得る。

Ｐ　ｒｏｌｏｇの実行は、まずユニフィケーションと呼
ばＪしる述語同士の照合から開始される。ユニフィケー
ションでは、まず間合せ節が与えられると間合せ節の先
頭の述語名と同じ述語名をヘッド部に持つ節をプログラ
ム内から取出さなければ成らなイ（以下、ユニフィケー
ションにおける間合せ述語名の検索と書く）。それ以降
のＰ　ｒｏｌｏｇの処理は、ユニフィケーションにおけ
る間合せ述語名の検索の処理の確定後起動される。この
ため、Ｐｒｏｌｏｇの処理装置の高速化を図る場合、ユ
ニフィケーションにおける間合せ述語名の検索は速度的
要因となる。しかし、従来のＰ　ｒｏｌｏｇの処理装置
は汎用計算機上にソフトウェアで実現されているため、
基本的には上で述べたように、プログラム情報を通常の
ランダムアクセスメモリ装置内に格納しておき、プログ
ラムカウンタ（ｐｃ）の値によって、該値に対応する番
地に格納されているプログラム情報を取出し、取出さ１
した該プログラム情報に基づいて情報処理を行う第１図
に示すごとき構成であるため、以下に示すような問題が
あった。

ユニフィケーションにおける間合せ述語名の検索の処理
を実現するためには、ＰＣの値によって、該値に対応す
る番地に格納されているプログラム情報（Ｐ　ｒｏｌｏ
ｇプログラムのひとつの節に対応すると考えて良い）を
１つ取り出してはそのヘッド部の述語名が間合せ述語名
と一致するかどうかを判定し、一致すればそれを取出し
、一致しなりればＰＣの値をひとつ増し、次の番地のブ
Ｕグ゛ラム情報を取出し同様な処理を行うというシーケ
ンスを、一致するものが出てくるまで繰り返さなければ
ならないにの処理はただ必要な対象としたいプログラム
情報を取出す（第２図の例では、ａｂｏｖｅ　（Ａ、＊
ｘ）の間合せに刻してプログラムの（３）、あるいは（
４）を取出す）だけの処理であるが、その間、ＣＰＵと
ＲＡＭ間では無駄な情報の授受を行Ｕ）、かつ一致判定
に終始しなければならず、制御は複３１１Ｌとなり、Ｃ
ＰＵの負荷が大きく処理の高速化が図れない。また、検
索対象（間合せ述語名をヘッド部に持つ節）は検索空間
（プログラム全体：データベース）に対して非′帛に小
さい場合が普通であるが、このような状況はプログラム
が膨大になればなるほど顕著となり、ユニフィケーショ
ン番；おける間合せ述語名の検索の処理に多大な時間力
１浪費される。

第２図の例であれば、（１）、　（２）、　（３）、　
（’Ｉ）の４個の節からなるデータベース（検索空間）
の中力蔦ら、ユニフィケーションにお番ノる問合せ述語
名：ａｂｏｖｅをまずひとつ探しだすまでに、ＣＰＵと
ＲＡＭ間では３回の情報の授受と一致判定を行わなけれ
ばならない。すなわち（１）を取出してはぞのヘッド部
が間合ぜ述語名と一致するかどうかを調べ、一致しない
から、（２）を取出してはそのヘッド部が間合せ述語名
と一致するかどうかを調べ、一致しないから、（３）を
取出してはそのヘッド部が間合せ述語名と一致するかど
うかを調へ、−１，＆するからやっと、　Ｐ　ｒｏｌｏ
ｇの実行においてユニフィケーションにおける間合せ述
語名の検索以降の処理に実行を進めることができるわけ
である。したがって、プログラムが膨大となり、例えば
１０００個の節からなるデータベースの中からただ１饅
の述語名を探し出すような場合であれば、最悪ケースと
してＣＰＵとＲＡＭ間ではｉｏｏ。

回の情報の授受と一致判定を行わな（づればならず、ま
たそのうちの９９９回は無駄な処理となる。

このように、従来のＰ　ｒｏｌｏｇ処理装置では、ユニ
フィケーションにおける間合せ述語名の検索の処理にお
いて、ＣＰＵは不必要な処理に専有され、処理装置全体
として処理の高速化が図ＪＬない。

以上、従来のＰｒｏｌｏｇの処理装置を取り上げ、従来
のこの種の情報処理装置の欠点をあげてきたが、これは
、すなわちＰ　ｒｏｌｏｇのような次に１可を実行する
かが処理の実行段階で動的に決定される非決定性処理を
基本とする情報処理を第１図に示すごとき情報処理装置
で実行しようとしているところに無理があるわけである
。しかし、従来、Ｐｒｏｌｏｇをはじめとするような非
決定性処理を基本とする情報処理を専用に効率良く実行
するような情報処理’Ｊ／４匝はなかった。

〔発明の目的〕

本発明の目的は非決定性処理を基本とする情報処理に高
速に９ｊう情報処理装置を提供することにある。

〔発明の概要〕

本発明は、プログラム情報を連想メモリ装置に格納し、
この連想メモリ装置から連想アクセスによりプログラム
情報を取出して情報処理を行うことを特徴とする。

〔発明の実施例〕

以下本発明の実施例を図面を参照して詳細に説明する。

第３図は本発明の第一の実施例を示す。即ち、第３図は
、記憶領域に格納されているプログラム情報を取出し、
該取出されたプログラム情報に基づいて情報処理を行う
情報処理装置において、プログラム情報を連想メモリ装
置に格納し、この連想メモリ装置から連想アクセスによ
り必要なブロクラム情報を取出し、取出されたプログラ
ム情（・μに基づいた情報処理を行う構成とした情報処
理装置である。図中、２１は連想メモリ装置であり。

２２は連想メモリ本体ＣＡ　Ｍ　（ＣｏｎシｃｎＬ、　
Ａｄｃｌｒｅｓｓａｂｌｅ　Ｍｅｍｏｒｙ）　２２であ
る。２３はＣＡＭ２２の動作を制御するための制御系で
あり、２４は制御系２３とＣＡＭ２２との情報の授受を
行う通信線である。２５は第１図と同様で中央処理装置
ｃＰＵである。また２６はＣＰＵ２５と連想メモリ装置
２１との情報の授受を行う通信線である。■くΔＭ２７
は通信線２８を介してＣＰ　Ｕ　２５と接続さ九、ワー
ク領域として使用される。プログラム情報を連想メモリ
装置２１のＣＡＭ２２に格納しておき、ＣＰＵ２５が実
行にともなう必要に応じて連想メモリ装置２１から連想
アクセスにより必要なブロクラム情報を取出すには、Ｃ
ＰＵ２５から必要なプログラム情報の一部を制御系２３
を介してＣＡＭ２２に与えると、ＣＡＭ２２の連想アク
セスによって、プログラム情報全体の中から必要な部分
のプログラム情報を；ｎ択して取出し、制御系２３を介
してＣＰ　Ｕ　２５に送ることができる。

なお、本実施例では、連想メモリ装置２１が制御系２３
を有し、制御系２３を介してＣＰＵ２５と情報の授受を
行う構成としているが、こＪＬは制御系２３がなく、Ｃ
Ｐ　Ｕ　２５とＣＡＭ２２との間で直接情報の授受を行
う構成でもよい。

この連想メモリ装置の連想アクセスにより、プロゲラｔ
１カウンタＰ　Ｃの値によって、この値に対応する番地
に格納されているプログラム情報を一つ一つ取出しては
、いま必要としているブロクラム情報かどうかを判定す
るというシーケンスが削除することができ、その分処理
装置どしてＣＰＵの負荷が軽減されるとともに制御が簡
単化され、また連想メモリ装置自身の連想アクセスその
ものの高速性と相乗され、より一層処理の高速化が図れ
る。

特に、連想メモリ装置２１に、述語論理型言語（例えば
、　Ｐ　ｒｏｌｏｇ）に基づくプログラム３語によって
作、成されたプログラム情報を格納した＠今。

ユニフィケーションにおける間合せ述語名の検索が連想
メモリ装置２１により自立的に実行さＪしるため、ＣＰ
Ｕ２５の負荷が軽減されるとともに制御が簡単化され、
また連想メモリ装置２１自升の連想アクセスそのものの
高速性と相乗され、全体としてより一層処理の高速化が
図れる。このことは、全体のプログラムの規模の大小に
よらず成り立つことである。例えば、第２図の（１）、
　（２）。

（３）、　（４）の４個の節から成るプログラムを連想
メモリ装置２１内に格納し、各節のヘッド部（（１）な
らＯｎ、（２）ならｏｎ、　（３）ならａｂｏｖｅ、　
（４）ならａｂｏｖｅ）に対して間合せ述語ａｂｏｖｅ
を連想アクセスのインデックスとしてＣＡＭ２２を連想
アクセスすることにより、１回のＣＡＭ２２の動作で（
３）。

（４）を選択することができる。　その間、ＣＰＵ２５
とＣＡＭ２２をつむ連想メモリ装置２】との情報の授受
は必要でない。ＣＰ　ｔＪ　２５は問合せ述語ａｂｏｖ
ｅを連想メモリ装置２１に与え、連想メモリ装置２１の
結果（（３）、　（４）のプロゲラＡ））を受け取るだ
けで、ユニフィケーションにおける間合せ述語名の検索
の処理以降のＰｒｏｉｏにの処理な起動することができ
る。したがって、一致判定は不用となる。

このように、述語論理型言語（例えばＰ　ｒｏｌｏｇ）
に基づベプログラム言語によっ°Ｃ作成されたプログラ
ム１ｎ報を連想メモリ装置に格納しておくことにより、
ユニフィケーションにお４Ｊる問合せ述語名の検索が連
想メモリ装置により自立的に実行されるため、ＣＰＵの
負荷が軽減さＪＬ、るとともに制御が簡単化さばし、ま
たＣＡＭ自身の連想アクセスそのものの高速性と相乗さ
れ、全体としてより一層処理の高速化が図れることは明
らかである。

ここで、ＣＰＵ２５とＲＡＭ２７のワーク領域との通信
線２８を用いた情報の授受は、第１図の従来のこの種の
情報処理装置のＣＰＵどＲＡ　Ｍのワーク領域との情報
の授受と同様であり、特に本発明において規定するもの
ではない。

第４図は本発明の他の実施例を示し、第３図の連想メモ
リ族＠２１の構成を連想メモリ装置３１として変更した
ものである。図中、３２は述語論理型言語の述語名に対
応する第１の情報をこの第１の情報間の接続状況を示す
情報とともに１ａ納する連想メモリであり、３３は連想
メモリ本体ＣＡＭであり、３４は第１の情報から述語論
理型言語の述語名に付随した引数に対応する第２の情報
への第１ポインタ情報である。３５はＣＡＭ３３の動作
を制御するための制御系であり、３６は制御系３５とＣ
ＡＭ３３との情報の授受を行う通信線であり、３７は第
１のポインタ情報の坤信線である。３８は述語論理型言
語の述語名にイリ随した引数に対応する第２の情報を格
納する第１のランダムアクセスメモリ装置ＲＡＭである
。３９は連想メモリ３２とＲＡＭ３８の動作を制御する
制御系であり、′４０は制御系３９と連想メモリ３２と
の通信線、４１は制御系３９と連想メモリ３２との第１
のポインタ情報３４との通（ａ綿である。また、４２は
制御系３９とＲＡＭ３８との通信線である。

第４図のように構成すると、プログラム情報の取出しに
際して、制御系３９から通信線４０を介し−Ｃ連想メモ
リ３２に間合ぜ述語名を与えることにより、検索の対象
となる述語名は連想メモリ３２の連想アクセスレ；より
、ＣＡＭ３３内から通信線３６を介して制御系３５へ、
制御系３５から通（ｇ綿４０により制御系３９し；取り
出すことができる。それと同時に９通イ目線３７から制
御系３５を槍して４１により、ＣＡＭ３３から取り出し
た述語名に付随した第１ポインタ情報３４を制御系３９
に取り出すことができ、その第１のポインタ情報に対応
した番地を通信線４２を介してＲＡＭ３８に与えること
により、検索の対象とならない引数はＲＡＭ３８内から
の制御系３９に取り出すことができる。これにより、プ
ログラム情報の取出しの処理速度を低下させることなく
゛、高価な連想メモリ装置の資源を節約することができ
、経済的である。

第５図は第４図の実施例に基づいて第２図に示したＰｒ
ｏｌｏｇのプログラムの格納した場合の概念図である。

第１の情報間の接続状況を示す情報として、その述語が
ヘッド部かボディ部かを示ずＩ−ＩＢタグ、およびその
述語の後に続くボディ部の述語があるかないかを示すＢ
Ｃタグを用いている。

図中３３ａはＨＢタグ、３３ｂは述語名、３３ｃはＢＣ
タグ、３４は第１ポインタ情報を示し、ＲＡＭ３Ｂには
引数が格納さＪｔている。ユニフィケーションにおける
間合せ述語名の検索は、ＨＢタグのＨ（ヘッド）と間合
せ述語名を用いて連想メモリ３２内を連想アクセスする
ことにより容易に実現できる。また、ボディ部の述語名
はＢＣＣタフより連想メモリ３２により、それらの引数
は第１ポインタ情報によりＲＡＭ３Ｂ内より取出すこと
ができる。なお、この格納例は一例にすぎず、ＨＢタグ
、ＢＣタグを用いず１つの節の述語名の情報をＣＡＭ３
３の１ワードに格納する方法や。

引数にも引数が次に続くかどうかのタグ（ＡＣタグ）を
イ１与してＲＡ　Ｍの１ワードに引数を１個とＡＣタグ
を格納する方法も容易に考えられる。

第６図は本発明のさらに他の実施例であり、第４図の連
想メモリ３２の部分の構成を連想メモリ５１と変更した
ものである。図中、５２は述語論理型言語のヘッド部の
述語名に対応する第３の１青報を格納する連想メモリで
あり、５３は連想メモリ本体ＣΔＭ５３であり、５４は
第３の情報力）ら述語論理型言語のボディ部の述語名に
対応する第４の情報への第２のポインタ情報である。５
５１まＣＡ　Ｍ　ｂ　３の動作を制御するだめの制御系
であり、５６は制御系５５とＣΔＭ５３の情報の授受を
ｆ７う通（ａ線であり、５７は第２のポインタ情報５４
の通（ｉｊ線である。５８は述語論理型言語の７ＪＣデ
イ６１の述語名に対応する第４の情報を格納するランタ
ムアクセスメモリ装［１；！へＭ　５８である。５９は
連想メモリ５２とＲＡ　Ｍ　５８の動作を制御する制御
系であり、６０は制御系５９と連想メモ１）５２との通
（Ｂ線、６１は制御系５９と連想メモリ５２との第２の
ポインタ情報５４の通信線である。

また、６２は制御系５９とＲＡＭ５Ｂとの通信線である
。なお、３４は第１のポインタ情報である。

第６図のように構成すると、プログラムｔ＃　ｆｌのう
ち述語名の取出しに際して、制９１１系５９から通信線
６０を介して連想メモリ５２に間ａせ述語名を与えるこ
とにより、検索の対象となるヘッド部の述語名は連想メ
モリ５２の連想アクセスによりＣＡＭ５３内から通信線
５６を介して制御ｆ＋５５に、制御系５５から通（ａ線
６０により制御系５９に取り出すことができ、それと同
時に通（ａ梓５７から制御系５５を介して通信ＩｆＡ６
１により、ＣハＭ　５３から取り出したヘッド部の述語
名にｆ］ｌ’４　した第２のポインタ情報５４を制御系
５９に取り出すことができ、その第２のポインタ情ｔｕ
　５４に対応した番地を通信線６２を介し−Ｃ１ｌΔＮ
１５８にあたえることにより、検索の対象とならないボ
ディ部の述語名は■えＡ　Ｍ　５８内から取り出すこと
により、プログラム情報のうち述語名の取出しの処理速
度を低下させることなく、高価な連想メモリ装置の資源
を節約することができ、経済的である。

第７図は第６図の実施例に基づいて第２図に示したＰ　
ｒｏｌｏｇのプログラムの述語名を格納した場合の概念
図である。図中５３ａはヘッド部述語名、５４は第２の
ボ、インタ情報、５８ａはボディ部述語名、５８ｂはぞ
の述語の後に続くボデ７ｒ部の述語があるかないかを示
すＢＣタグである。また、３４は第１のポインタ情報で
ある。ユニフィケーション１月Ｊる問合せ述ｎｌｊ名の
検索は、間合せ述語名を用い−ＣＣＡ　Ｍ　５３内を連
想アクセスすることにより容易に実現できる。また、ボ
ディ部の述語名は第２のポインタ１青報およびＢ　Ｃタ
グによりＲＡＭ　５８内より取り出すことができる。な
お、この１Ｂ拍例は一例にすぎず、ＢＣタグを用いず、
ボデ１部の述語名の情報をＲＡＭ５８１ワードに格Ａ１
１する方法なども容易に考えられる。

ここでは第４図の実施例、第６図の実施例とも、連想メ
モリ装置が内部に連想メモリ本体とその連想メモリ本体
を制御するだめの制ｆＯ′ＩＩ系を有しておリ、連想メ
モリ装置と上位制御系との情報の授受は内部の制御系を
介して行う構成としているが、これは内部の制御系がな
く、上位の制御系と連想メモリ本体との間で直接に情報
の授受を行う１１５成でもよい。

一方１本発明で中心的に用いている′４想メモリ装置で
あるが、近年、低価格で高速人容旦な連想メモリ装置が
構成できるようになってきＣおり（例えば特願昭５８　
９４５２５号）、情報処理の核どなる処理への適用が、
性能的にも、経１斉的にも可能となってきている。この
ような状況の中で本発明の意義は大さい。

〔発明の効果〕

以上、説明したように、本発明は記憶順ｊ或に＋８納さ
れているプログラム情報を取出し、該取出されたプログ
ラム情報に基づいて情報処理を行う情報処理装置におい
て、プログラム情報を連想メモリ装置から連想アクセス
により必要なプロゲラ１１情報を取出さ４したプログラ
ム情報に基づいたＩｆＪ報処理を行う新規な情報処理装
置を実現するので、以下のＪ：うな利点が生じる。

（１）情報の実行にともない必要に応じて、記憶領域に
＋８納されているプログラム情報から必要なプログラム
情報を取出す処理が、連想メモリ装置により自立的に行
われるため、処理装置全体としてＣＰＵの負荷が軽減さ
れるとともに制御が簡単化され、また連想メモリ装置自
身の連想アクセスそのものの高速性と和平され、王り一
層の処理の高速化が図れる。

（１１）　ユニフィケーションにおける間合せ述語名の
険１；が連想メモリ装置により自立的に実行されるため
、ＣＩ）　ＩＪは負荷が軽減されるとともに制御が簡単
ｆしされ、また連想メモリ装置白ηの連想アクセスその
ものの高速性と相乗され、より一層の処理の高速化が図
れる。このことは、全体のプログラムの規模の大小に１
、らず成り立つことである。

（ｉｉｉ　）　ｌ記連想メモリ装置にＲＡ　Ｍを含み、
プログラム情報のうち、直接検索の対象となるものと検
索の対象とはならないものが関連しているものとに分離
し、直接検索の対象となるものを連想メモリ内に、検索
の対象とはならないが関連しているものを連想メモリ内
の情報からのポインタ情報によりＲＡ　Ｍ内に１ｈ拍す
ることにより、必要なプロゲラ１１情報の取出しの処理
速度を低下させることなく、高価な連想メモリ装置の資
源を節約することができ経済的である。

なお、（ｉｉ）以降は述語論理型言語（たとえばｐｒｏ
ｌｏｇ）を対象とした場合の効果である。

【図面の簡単な説明】

第１図は従来の一般的な情報処理袋Ｕｌを示すブロック
図、第２図はＰ　ｒｏＬｏｇのプログラムと事物関係の
世界の例を示す図、第３図、第４図および第６図はそれ
ぞれ本発明の一実施例を示すブロック図、第５図および
第７図はそ４しぞれ第４図、第６図の実施例に基づいて
第２図のＰｒｏ］ｏＢのプログラムを（８納した場合を
示す、［急回である。 ２１・・・連想メモリ装置、２２・・連想メモリ本俸Ｃ
ＡＭ、２５・・中央処理装置。 ＣＡＭ３３　ＲＡＭ３８

Claims (3)

【特許請求の範囲】
1. （１）記憶領域に格納されているプログラム情報を取出
   し、取出された該プログラム情報に基づいて情報処理を
   行う情報処理装置において、上記プログラム情報を連想
   メモリ装置に格納し、該連想メモリ装置から連想アクセ
   スにより必要なプログラム情報を取出して情報処理を行
   うことを特徴とする情報処理装置。
2. （２）上記連想メモリ装置に上記プログラム情報として
   、述語論理型言語に基づくプログラム言語に゛よって作
   成されたプログラム情報を格納することを特徴とする特
   許請求の範囲第１項記載の情？１１処理装置。
3. （３）上記連想メモリ装置は連想メモリとランダムアク
   セスメモリ装置とを含み、述語論理型言語の述語名に対
   応する第１の情報を該第１の情報間の接続状況を示す情
   報と共に上記連想メモリに格納し、述語論理型言語の述
   語名に付随した引数に対応する第２の情報を上記第、１
   の情報に付与したポインタが示す位置の上記ランダムア
   クセスメモリ装置に格納し、実行に伴なって、上記第１
   の情報は連想アクセスにより上記連想メモリから、上記
   第２の情報は上記第１の情報に伺与されているポインタ
   により上記ランダムアクセスメモリ装置から取出し、上
   記第１および第２の情報に基づいて情報処理を行うこと
   を特徴とする特許請求の範囲第２項記載の情報処理装置
   。