JPS6361334A - デ−タ処理装置 - Google Patents
デ−タ処理装置Info
- Publication number
- JPS6361334A JPS6361334A JP61205412A JP20541286A JPS6361334A JP S6361334 A JPS6361334 A JP S6361334A JP 61205412 A JP61205412 A JP 61205412A JP 20541286 A JP20541286 A JP 20541286A JP S6361334 A JPS6361334 A JP S6361334A
- Authority
- JP
- Japan
- Prior art keywords
- data
- list
- memory
- memory means
- node
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
産業上の利用分野
本発明は主に人工知能分野で使用することを目的とした
データ処理装置に関するものである。
データ処理装置に関するものである。
従来の技術
近年、コンピュータ応用の一つとして人工知能分野が盛
んに研究されている。この分野においては構造を持った
データを処理する必要があり、そのため構造データを取
り扱うことのできる言語であるＬＩＭＰが広く使用され
ている。ＬＩＳＰ言語は汎用のコンピュータで実行する
のは非効率であるため様々な工夫を施した専用マシンが
開発されてきた。
んに研究されている。この分野においては構造を持った
データを処理する必要があり、そのため構造データを取
り扱うことのできる言語であるＬＩＭＰが広く使用され
ている。ＬＩＳＰ言語は汎用のコンピュータで実行する
のは非効率であるため様々な工夫を施した専用マシンが
開発されてきた。
これら専用マシンは主に言語的側面からアプローチを行
って改善を行ったものでその改善の内容の代表的なもの
を以下に示す。
って改善を行ったものでその改善の内容の代表的なもの
を以下に示す。
＋１１ ＣＡＲ，ＣＤＲ等、原始的関数はマイクロプ
ログラムレベルで実行する。
ログラムレベルで実行する。
（２） ジェネリックデータタイプを扱うためＴＡＧ
付きデータ形式とする。
付きデータ形式とする。
（３）スタック処理を高速にするためハードウェアコン
トロールスタックを設ける。
トロールスタックを設ける。
（参考文献（ＬＩＭＰマシン〕情報処理Ｖｏｌ。
２３ 魚８ ｐｐ７５２−７７２）
発明が解決しようとする問題点
しかしながら、前記したような言語の実行系に関する改
善はなされてきたものの、計算機内部における構造体デ
ータの表現としては基本的には要素の順序関係と結合の
方法をポインタで表現したもの（以下リストと呼ぶ）を
使用しているため次のような問題があった。
善はなされてきたものの、計算機内部における構造体デ
ータの表現としては基本的には要素の順序関係と結合の
方法をポインタで表現したもの（以下リストと呼ぶ）を
使用しているため次のような問題があった。
（１１個々の要素へのアクセスがリストのトップからの
リストたくりとなり非効率である。
リストたくりとなり非効率である。
（２） マツチング処理はリストを順次要素に分解し
て行わなければならないため時間がかかる。
て行わなければならないため時間がかかる。
（３） ガーベージコレクションが困難である。
本発明は上記問題点に鑑みてなされたもので、簡単な構
成で効率良くリスト処理を行うことのできるデータ処理
装置を提供するものである。
成で効率良くリスト処理を行うことのできるデータ処理
装置を提供するものである。
問題点を解決するための手段
上記問題点を解決するために本発明のデータ処理装置は
、リストデータのノードの位置をベクトルで表現した表
形式のデータとして記憶する第一のメモリ手段と、連想
メモリで構成され、上記第一のメモリ手段に蓄えられた
上記表形式のデータの一部を記憶する第二のメモリ手段
と、上記第一のメモリ手段と第二のメモリ手段との間で
データを転送する転送手段と、上記第二のメモリ手段に
蓄えられた表形式のデータを操作する演算手段とを備え
、リストデータを表形式データとして高速に処理するよ
うにしたものである。
、リストデータのノードの位置をベクトルで表現した表
形式のデータとして記憶する第一のメモリ手段と、連想
メモリで構成され、上記第一のメモリ手段に蓄えられた
上記表形式のデータの一部を記憶する第二のメモリ手段
と、上記第一のメモリ手段と第二のメモリ手段との間で
データを転送する転送手段と、上記第二のメモリ手段に
蓄えられた表形式のデータを操作する演算手段とを備え
、リストデータを表形式データとして高速に処理するよ
うにしたものである。
作用
本発明は上記した構成によって、リストデータをリスト
の長さ方向に順次番号を付は深さ方向に順次項目を割り
当てた一次元ベクトルでノードの位置を表し、その中で
要素を指しているものを抜きだして要素データと共に表
の形に展開したものに対して処理を行うもので、要素デ
ータへのアクセスやリストの比較がリストたぐりやリス
ト分解を行うことなしに実行できる。
の長さ方向に順次番号を付は深さ方向に順次項目を割り
当てた一次元ベクトルでノードの位置を表し、その中で
要素を指しているものを抜きだして要素データと共に表
の形に展開したものに対して処理を行うもので、要素デ
ータへのアクセスやリストの比較がリストたぐりやリス
ト分解を行うことなしに実行できる。
実施例
以下本発明の一実施例のデータ処理装置について、図面
を参照しながら説明する。第１図は本発明の一実施例に
おけるデータ処理装置の構成を示すものである。
を参照しながら説明する。第１図は本発明の一実施例に
おけるデータ処理装置の構成を示すものである。
第１図において、１１はすべてのりストデータを表形式
で表現して蓄える第１メモリ手段、１２は第１メモリ手
段１１に蓄えられたデータの一部を記憶するために連想
メモリで構成された第２メモリ手段、１３は第１メモリ
手段１１と第２メモリ手段１２の間で表形式データを転
送する転送手段、１４は第２メモリ手段１２に蓄えられ
た表形式データを操作する演算手段である。
で表現して蓄える第１メモリ手段、１２は第１メモリ手
段１１に蓄えられたデータの一部を記憶するために連想
メモリで構成された第２メモリ手段、１３は第１メモリ
手段１１と第２メモリ手段１２の間で表形式データを転
送する転送手段、１４は第２メモリ手段１２に蓄えられ
た表形式データを操作する演算手段である。
以上のように構成されたデータ処理装置について、以下
第１図、第２図、第３図および第４図を用いてその動作
を説明する。
第１図、第２図、第３図および第４図を用いてその動作
を説明する。
第２図は第１メモリ手段１１におけるメモリ領域の構成
、第３図はリストデータの図形表現、第４図は同データ
の第２メモリ手段１２における連想メモリ内表現を示す
ものであって、第２図において２１は全体のメモリ領域
、２２は一つのリストが占めるリストデータ領域、第３
図において３１はリストのノード、３２は値、第４図に
おいて４１は連想メモリのｃｏｎ ｔｅｎ を部、４２
はＶａｌｕｅ部である。連想メモリ内ではリストデータ
のノードの中で要素を指しているもののみを抜き出し、
リストの長さ方向に順次番号を付は深さ方向に順次項目
を割り当てたノードの位置を表す一次元ベクトルをｃｏ
ｎ ｔｅｎ を部、要素データをｖａｌｕｅ部とした表
形式で表される。第３図（δ）、第４図ｆａｔはリスト
データＸ： （Ａ （Ｂ （Ｃ））Ｄ）を、第３図ｉ
ｂｌ 。
、第３図はリストデータの図形表現、第４図は同データ
の第２メモリ手段１２における連想メモリ内表現を示す
ものであって、第２図において２１は全体のメモリ領域
、２２は一つのリストが占めるリストデータ領域、第３
図において３１はリストのノード、３２は値、第４図に
おいて４１は連想メモリのｃｏｎ ｔｅｎ を部、４２
はＶａｌｕｅ部である。連想メモリ内ではリストデータ
のノードの中で要素を指しているもののみを抜き出し、
リストの長さ方向に順次番号を付は深さ方向に順次項目
を割り当てたノードの位置を表す一次元ベクトルをｃｏ
ｎ ｔｅｎ を部、要素データをｖａｌｕｅ部とした表
形式で表される。第３図（δ）、第４図ｆａｔはリスト
データＸ： （Ａ （Ｂ （Ｃ））Ｄ）を、第３図ｉ
ｂｌ 。
第４図（ｂｌはリストデータＹ： （Ｂ （Ｃ））を
それぞれ表現したもので、たとえばリストデータＸの要
素Ｎ″Ｃ″ばｃｏｎｔｅｎｔ ａｄｄｒｅｓｓ ２−２
−１ １で表される。またリストデータＸ、 Ｙは第
２図に示すように第１メモリ手段Ｉｌ内にそれぞれ連ｖ
ｔ領域に格納して先頭アドレスと大きさによって管理さ
れ、内部では第３図と同様の形式の表をすべて値として
持っている。
それぞれ表現したもので、たとえばリストデータＸの要
素Ｎ″Ｃ″ばｃｏｎｔｅｎｔ ａｄｄｒｅｓｓ ２−２
−１ １で表される。またリストデータＸ、 Ｙは第
２図に示すように第１メモリ手段Ｉｌ内にそれぞれ連ｖ
ｔ領域に格納して先頭アドレスと大きさによって管理さ
れ、内部では第３図と同様の形式の表をすべて値として
持っている。
＋１１ リストデータＸの要素“Ｂ”すなわちリスト
データＸのＣＤＲ部のＣＡＲ部のＣＡＲ部をアクセスす
る場合、第１メモリ手段１１内のリストデータ領域２１
の該当データは転送手段１３によって第２メモリ手段１
２に転送され、第４図ｆ８）に示すような連想メモリの
形式に変換して格納される。次に演算手段１４は第２メ
モリ手段１２に対してｃｏｎｔｅｎｔ ａｄｄｒｅｓｓ
２ １−１でアクセスすると、ｃｏｎ ｔｅｎ を部
４１とのマツチングが行われて第２要素が取り出される
。
データＸのＣＤＲ部のＣＡＲ部のＣＡＲ部をアクセスす
る場合、第１メモリ手段１１内のリストデータ領域２１
の該当データは転送手段１３によって第２メモリ手段１
２に転送され、第４図ｆ８）に示すような連想メモリの
形式に変換して格納される。次に演算手段１４は第２メ
モリ手段１２に対してｃｏｎｔｅｎｔ ａｄｄｒｅｓｓ
２ １−１でアクセスすると、ｃｏｎ ｔｅｎ を部
４１とのマツチングが行われて第２要素が取り出される
。
（２） リストデータＹを他のりストデータＺと比較
する場合、同様に第１メモリ手段１１内のりストデータ
領域２１の両データは転送手段１３によって第２メモリ
手段１２に転送され、それぞれ第４図に示すような連想
メモリの形式に変換して格納される。次に演算手段１４
は第２メモリ手段１２内のリストデータＹの各要素を順
に取り出し、それぞれのｃｏｎｔｅｎｔ ａｄｄｒｅｓ
ｓ部とｖａｌｕｅ部とをセントとして第２メモリ手段１
２内のリストデータＺの領域に対してアクセスし、マツ
チングを試みる。リストデータＹのすべての要素に対し
てマツチングが成功した場合に両データは等しいと判定
され、−要素でも一致しない場合にはその時点で等しく
ないと判定される。
する場合、同様に第１メモリ手段１１内のりストデータ
領域２１の両データは転送手段１３によって第２メモリ
手段１２に転送され、それぞれ第４図に示すような連想
メモリの形式に変換して格納される。次に演算手段１４
は第２メモリ手段１２内のリストデータＹの各要素を順
に取り出し、それぞれのｃｏｎｔｅｎｔ ａｄｄｒｅｓ
ｓ部とｖａｌｕｅ部とをセントとして第２メモリ手段１
２内のリストデータＺの領域に対してアクセスし、マツ
チングを試みる。リストデータＹのすべての要素に対し
てマツチングが成功した場合に両データは等しいと判定
され、−要素でも一致しない場合にはその時点で等しく
ないと判定される。
またリストデータＸのＣＡＤＲ部すなわちＣＤＲ部のＣ
ＡＲ部とリストデータＹを比較する場合、同様にして第
１メモリ手段１１内の両データは第２メモリ手段１２に
第４図ｆａｌ、 ｆｂｌに示すような連想メモリの形式
に変換して格納される０次に演算手段１４は第２メモリ
手段１２内のりストデータＹの各要素を順に取り出し、
それぞれのｃｏｎｔｅｎｔ ａｄｄｒｅｓｓ部に２−を
付加してｖａｌｕｅ部とともに第２メモリ手段１２内の
リストデータＸの領域に対してアクセスして同様の判定
を下す。
ＡＲ部とリストデータＹを比較する場合、同様にして第
１メモリ手段１１内の両データは第２メモリ手段１２に
第４図ｆａｌ、 ｆｂｌに示すような連想メモリの形式
に変換して格納される０次に演算手段１４は第２メモリ
手段１２内のりストデータＹの各要素を順に取り出し、
それぞれのｃｏｎｔｅｎｔ ａｄｄｒｅｓｓ部に２−を
付加してｖａｌｕｅ部とともに第２メモリ手段１２内の
リストデータＸの領域に対してアクセスして同様の判定
を下す。
（３）ガーベージが発生する場合、たとえばリストＸの
内容が更新されて以前に第１メモリ手段１１内にＸの値
として占めていたリストデータ領域２１が不要となった
場合は、その領域にマークを付加し、大きさを記録して
おく。第１メモリ手段１１の領域不足が生した時、マー
クを付加した領域のみを取り除いて有効なリストデータ
領域を集めることでガーベージコレクションが行える。
内容が更新されて以前に第１メモリ手段１１内にＸの値
として占めていたリストデータ領域２１が不要となった
場合は、その領域にマークを付加し、大きさを記録して
おく。第１メモリ手段１１の領域不足が生した時、マー
クを付加した領域のみを取り除いて有効なリストデータ
領域を集めることでガーベージコレクションが行える。
以上のように本実施例によれば、リストデータを表形式
で表現し、連想メモリ内に転送して演算手段で操作する
ことにより、ｆｉ＋リスト内部の個々の要素に対してト
ップからのりストたぐりを行わずにノード位置をアドレ
スとして直接アクセスすることができ、（２）リストの
マツチングをリスト分解を行わずに要素の数だけ連想メ
モリにアクセスするだけで処理でき、さらにリストの一
部に対するマツチングも部分リストを取り出すことなく
アドレスの補正のみで行うことができ、（３）ガーベー
７ジコレクシヨンを行う時に、ガーベージとなる個
々のリストはそれぞれ連続領域に格納されているので、
マーク付けのためのりストたぐりを行う必要がなく容易
にこれらを回収することができる。
で表現し、連想メモリ内に転送して演算手段で操作する
ことにより、ｆｉ＋リスト内部の個々の要素に対してト
ップからのりストたぐりを行わずにノード位置をアドレ
スとして直接アクセスすることができ、（２）リストの
マツチングをリスト分解を行わずに要素の数だけ連想メ
モリにアクセスするだけで処理でき、さらにリストの一
部に対するマツチングも部分リストを取り出すことなく
アドレスの補正のみで行うことができ、（３）ガーベー
７ジコレクシヨンを行う時に、ガーベージとなる個
々のリストはそれぞれ連続領域に格納されているので、
マーク付けのためのりストたぐりを行う必要がなく容易
にこれらを回収することができる。
発明の効果
以上のように本発明はリストデータのノードの位置をベ
クトルで表現した表形式のデータとして記憶する第一の
メモリ手段と、連想メモリで構成され、前記第一のメモ
リ手段に蓄えられた上記表形式のデータの一部を記憶す
る第二のメモリ手段と、上記第一のメモリ手段と第二の
メモリ手段との間でデータを転送する転送手段と、上記
第二のメモリ手段に蓄えられた表形式のデータを操作す
る演算手段とを備えたもので、リストデータを表形式デ
ータとして処理するようにしたものであり、要素データ
へのアクセスやリストの比較がリストたぐりやリスト分
解を行うことなしに実行することができるようにしたも
のであり、高速にリストデータの処理を行うことができ
る。
クトルで表現した表形式のデータとして記憶する第一の
メモリ手段と、連想メモリで構成され、前記第一のメモ
リ手段に蓄えられた上記表形式のデータの一部を記憶す
る第二のメモリ手段と、上記第一のメモリ手段と第二の
メモリ手段との間でデータを転送する転送手段と、上記
第二のメモリ手段に蓄えられた表形式のデータを操作す
る演算手段とを備えたもので、リストデータを表形式デ
ータとして処理するようにしたものであり、要素データ
へのアクセスやリストの比較がリストたぐりやリスト分
解を行うことなしに実行することができるようにしたも
のであり、高速にリストデータの処理を行うことができ
る。
第１図は本発明の一実施例におけるデータ処理装置の構
成図、第２図は第１図の第１メモリ手段におけるメモリ
領域の構成図、第３図は第１メモリ手段に蓄えられるリ
ストデータの図形表現した模式図、第４図は同データの
第２メモリ手段に蓄えられる連想メモリ内表現した模式
図である。 １１・・・・・・第１メモリ手段、１２・・・・・・第
２メモリ手段、１３・・・・・・転送手段、１４・・・
・・・演算手段、４１・・・・・・表形式ｃｏｎ ｔｅ
ｎ を部、４２・・・・・・表形式ｖａｌｕｅ部。 代理人の氏名 弁理士 中尾敏男 ほか１名ｃｙ 区 〜 ｑ 第３図 第 ４ 図
成図、第２図は第１図の第１メモリ手段におけるメモリ
領域の構成図、第３図は第１メモリ手段に蓄えられるリ
ストデータの図形表現した模式図、第４図は同データの
第２メモリ手段に蓄えられる連想メモリ内表現した模式
図である。 １１・・・・・・第１メモリ手段、１２・・・・・・第
２メモリ手段、１３・・・・・・転送手段、１４・・・
・・・演算手段、４１・・・・・・表形式ｃｏｎ ｔｅ
ｎ を部、４２・・・・・・表形式ｖａｌｕｅ部。 代理人の氏名 弁理士 中尾敏男 ほか１名ｃｙ 区 〜 ｑ 第３図 第 ４ 図
Claims (1)
- リストデータのノードの位置をベクトルで表現した表形
式のデータとして記憶する第一のメモリ手段と、連想メ
モリで構成され、上記第一のメモリ手段に蓄えられた上
記表形式のデータの一部を記憶する第二のメモリ手段と
、上記第一のメモリ手段と第二のメモリ手段との間でデ
ータを転送する転送手段と、上記第二のメモリ手段に蓄
えられた表形式のデータを操作する演算手段とを具備す
ることを特徴とするデータ処理装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61205412A JPS6361334A (ja) | 1986-09-01 | 1986-09-01 | デ−タ処理装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61205412A JPS6361334A (ja) | 1986-09-01 | 1986-09-01 | デ−タ処理装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS6361334A true JPS6361334A (ja) | 1988-03-17 |
Family
ID=16506416
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61205412A Pending JPS6361334A (ja) | 1986-09-01 | 1986-09-01 | デ−タ処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6361334A (ja) |
-
1986
- 1986-09-01 JP JP61205412A patent/JPS6361334A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Bunke et al. | Syntactic and structural pattern recognition: theory and applications | |
| van Emde Boas et al. | Design and implementation of an efficient priority queue | |
| Courtial et al. | A co-word study of artificial intelligence | |
| DE60318722T2 (de) | Eine programmierbare regelverarbeitungsvorrichtung für hochgeschwindigkeits-kontextsuchen und -erkennung von mustern in daten | |
| EP0365309B1 (en) | A data unification system and method | |
| JPS6361334A (ja) | デ−タ処理装置 | |
| Larson | Inductive inference in the variable valued predicate logic system vl21: methodology and computer implementation. | |
| JPS6361335A (ja) | デ−タ処理装置 | |
| JP2606305B2 (ja) | データ処理装置 | |
| JPS63118943A (ja) | デ−タ処理装置 | |
| JPS6365523A (ja) | デ−タ処理装置 | |
| JPS63292331A (ja) | デ−タ処理装置 | |
| JP2705166B2 (ja) | データ処理装置 | |
| JPS63291127A (ja) | デ−タ処理装置 | |
| Williams | A multiprocessing system for the direct execution of LISP | |
| JPH01145727A (ja) | データ処理装置 | |
| JPS63219037A (ja) | デ−タ処理装置 | |
| JPS63292330A (ja) | デ−タ処理装置 | |
| JPH01287745A (ja) | データ処理装置 | |
| JPS63276129A (ja) | デ−タ処理装置 | |
| JPH0231278A (ja) | データ処理装置 | |
| JPS63255741A (ja) | デ−タ処理装置 | |
| JPS63223826A (ja) | デ−タ処理装置 | |
| JPH0215332A (ja) | データ処理装置 | |
| JP2925216B2 (ja) | 画像処理装置およびその方法 |