JPH02158836A - データ処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は主に人工知能分野等で使用するデータ処理装置
に関するものである。

従来の技術 近年、コンピュータ応用の一つとして人工知能分野が盛
んに研究されている。この分野においては構造を持った
データを処理する必要があシ、そのため構造データを取
り扱うことのできる言語であるＬＩＳＰが広く使用され
ている。Ｉ、ＩＳＰ　　言語を汎用のコンピュータで実
行するのは非効率であるため様々な工夫を施した専用マ
シンが開発されてきた。

これら専用マシンは主に言語的側面からアプローチを行
って改善を行ったものでその改善の内容の代表的なもの
を以下に示す。

（１）　　ＣＡＲ，ＣＤＲ等、原始的関数はマイクロプ
ログラムレベルで実行する。

に））　ジェネリックデータタイプを扱うためＴＡＧ付
きデータ形式とする。

（３）スタック処理を高速にするため〆１−ドウエアコ
ントロールスタックを設ケル。

（参考文献−Ｌｉ５ｐマシン′、情報処理。

Ｖｏｌ、　２３　、ムｓ　、　ｐＰ、７５２−７７２　
）しかしながら、上記゛したような言語の実行系に関す
る改善はなされてきたものの、計算機内部における構造
体データの表現としては基本的には要素の順序関係と結
合の方法をポインタで表現したもの（以下リストと呼ぶ
）を使用している。一般にリストは２進木で表現され、
始点のノードから始まって順次左右に分岐して行き葉の
ノードでそれぞれの分岐が終了する形をとる。葉の７−
ドにはアトムノードとＮＩＬノードの２種類がある。

葉のノードでないノードは分岐が続行している事を示す
リストノードである。このリストノードは葉のノードの
位置を間接的に表すためのものである。

ポインタ表現ではこのリスト構造をそのままの形で表現
し、全てのノードをアドレスで接続した七ルで表現して
いるために次のような問題がある。

（１）任意の位置にある要素のアクセス、リスト内での
任意の要素の検索、リストの分解・結合にリストたぐシ
を伴い効率が悪い。

（２）リストのマツチング、リスト内での任意のサブリ
ストの検索にリストの分解操作を伴うため非効率である
。

これらの問題点を解決するだめの一手法としてリストデ
ータを表形式で表現する方法がある。リストデータが表
す情報はその葉に位置する各要素の順序関係とその内容
である。したがって葉のノードの位置を直接的にあられ
すことができれば、リストノードの情報を持つ必要はな
い。そこで葉の位置情報と葉自身の情報を順次並べた表
で、等価なリストデータを表現することができる。この
葉のノード位置を表現する方法としてリストの長さ方向
に順次番号を付け、深さ方向に順次項目を割り当てた一
次元ベク）／Ｉ／表現を用いると、リストデータは葉の
位置情報を示すベク）／ｌ／と葉自身の情報を組とした
データの集合として表形式で表現される。

第５図にリストデータの表現例を示す。これは８式で表
記した場合（Ａ（Ｂ（Ｃ））Ｄ）となるリストデータの
図式表現（１）、および、表形式表現（２）を示したも
のである。図式表現において丸印はリストノードを表し
、四角で囲ったものは葉のノードを示している。また各
ノードの上に付記した数字列は上記した方法に従って表
したノード位置を示すものである。この葉の部分を抜き
だして表の形で表現したものが表形式表現であって、ア
ドレス部にノード位置ベク）　／Ｌ／が、バリュー部に
葉の要素が要素データのタイプを示すタグ値と共に入っ
た表で構成されている。

リストデータをこのような表形式で表現した場合、ポイ
ンタをたぐることなく各要素をアクセスすることができ
、さらに各要素の演算を並列に行うことによって、パタ
ーンマツチングなどのリスト処理を高速に行うことが出
来る。

以下図面を参照しながら上述した従来のデータ処理装置
の一例について説明する。

第６図は従来のデータ処理装置の構成を示すものである
。

第６図において１は主メモリ装置、２は主レジスタ装置
、３は主演算装置、６は要素メモリ装置、６は要素レジ
スタ装置、７は要素演算装置、１３は主制御装置であり
、主レジスタ装置、主メモリ装置、主演算装置より構成
される主データ処理部４と、要素メモリ装置、要素レジ
スタ装置、要素演算装置より構成される複数の要素デー
タ処理部８によって構成される。

以上のように構成されたデータ処理装置につき、以下第
６図を用いてリストデータをメモリ装置とレジスタ装置
間で転送するその動作を説明する。

リストデータは表形式によって表現され、タグ値および
各要素データに共通のアドレスを示す値から構成される
主データは主メモリ装置１に、ｎ個の要素データはそれ
ぞれ別々に要素メモリ装置６内の同一アドレスに格納さ
れている。このリストデータをレジスタＲｘに転送する
場合、主制御装置１３の制御によって、主メモリ装置１
内の主データは主レジスタ装置２内Ｒｘ転送され、その
値で示されるアドレスにある各要素メモリ装置５内の要
素データは各要素レジスタ装置６内Ｒｘに同時に転送さ
れる。またレジスタ内のリストデータに対して演算を行
う場合、主レジスタ装置２内Ｒｘのタグ値に対しては主
演算装置３が、各要素レジスタ装置６内の要素データに
対しては要素演算装置７が同時に処理を行う。また通常
の数値デ工タおよびアトムデータはタグ値によってリス
トデータとは区別され、同じく主制御装置３によって演
算を行う。

このようにリストデータを他のデータと区別し、さらに
その各要素を別々の処理装置によって並列に処理するこ
とによって、従来のポインタ表現形式に比較して効率的
なリスト処理が行える。

発明が解決しようとする課題 しかしながら上記のような構成では、予め定められた要
素データ処理部の構成および数にしたがって表形式表現
のアドレス部の大きさおよび桁数が決まり、この制限よ
り長いリストデータおよび深いリストデータを表現し、
処理ことかできない。

本発明は上記問題点に鑑み、表形式のリストデータの並
列処理において、要素データ処理部の構成および数を変
更せずにより大きなりストデータの処理を行うデータ処
理装置を提供するものである。

課題を解決するだめの手段 上記問題点を解決するために本発明のデータ処理装置は
、主データをタイプをあらわすタグ値と内容とで構成し
て記憶する主メモリ装置および、前記主メモリ装置に記
憶されたデータを転送して記憶する主レジスタ装置とか
ら構成される主データ処理部と、リストデータの各要素
データをノードの位置を示すアドレス部と要素のタグ値
と内容からなるバリュー部とで構成して記憶する要素メ
モリ装置および、前記要素メモリ装置に記憶されたデー
タを転送して記憶する要素レジスタ装置とから構成され
る複数の要素データ処理部と、リストの長さを拡張する
拡張アドレスとポインタから構成される拡張データを記
憶するリスト拡張メモリ装置および、前記拡張メモリ装
置に記憶されたデータを転送して記憶するリスト拡張レ
ジスタ装置とから構成されるリスト拡張データ処理部と
、前記主データ処理装置と要素データ処理装置とリスト
拡張データ処理部とを制御して要素データ処理部の構造
および数に依存しない大きさのリストデータを処理する
主制御装置を具備し、リストデータの大きさに制限なく
リスト処理を行えるようにしたものである。

作　　用 本発明は上記した構成によって、要素のアドレスを拡張
するアドレスデータを処理するリスト拡張データ処理部
を備えて、主制御装置によって拡張データのアドレスと
各要素データのアドレスを演算してリストの長さを拡張
することによって、長さがより大きいリストデータを表
現し、処理できるようにしたものである。

実施例 以下本発明の一実施例のデータ処理装置について、図面
を参照しながら説明する。

第１図は本発明の第１の実施例におけるデータ処理装置
の構成を示すものである。第１図において１は主メモリ
装置、２は主レジスタ装置、３は主演算装置、６は要素
メモリ装置、６は要素Ｖジスタ装置、７は要素演算装置
、９はリスト拡張メモリ装置、１．ｏはリスト拡張レジ
スタ装置、１１はリスト拡張演算装置である。４は主メ
モリ装置、主レジスタ装置、主データ転送装置、主演算
装置より構成される主データ処理部で、８は要素メモリ
装置、要素レジスタ装置、要素データ転送装置、要素演
算装置よシ構成される複数の要素データ処理部で、１２
はリスト拡張メモリ装置、リスト拡張レジスタ装置、リ
スト拡張演算装置より構成されるリスト拡張データ処理
部である。

第２図は上記実施例のデータ処理装置において、リスト
データをメモリ装置内に格納する構造を、第３図はデー
タの内部構造を示すものである。主メモリ装置１内の主
データ２１はリストデータのタグ部２２と値部２３で構
成され、各要素メモリ装置６内の要素データ２４はアド
レス部２５とバリュー部２６で構成され、リスト拡張メ
モリ装置９内の拡張データ２７は拡張アドレス部２８と
ポインタ部２９で構成される。

以上のように構成されたデータ処理装置につき、以下第
１図、第２図および第３図を用いてその動作を説明する
。

リストデータは表形式によって表現され、タグ値および
各要素データと拡張データに共通のアドレスを示す値か
ら構成される主データ２１は主メモリ装置１に、ｎ個の
要素データ２４（１）〜２４（ｎ）は別々に要素メモリ
装置６（１）〜５（ｎ）内の同一アドレスに、拡張、デ
ータ２７もリスト拡張メモリ装置９内の同じアドレスに
格納されている。さらにそのリスト内に異なる拡張アド
レスをもつ要素データが存在する場合、拡張データポイ
ンタ部によって示される別のアドレスに同様にその要素
データ２４と拡張データ２７が格納される。すなわち拡
張データのポインタ部によって１つのリスト内に複数の
拡張アドレスをもつことができる。

また第３図に示す例のデータ構造では、各要素データの
アドレス部は４フイールド、各フィールドは８ピツトで
表現するものとする。さらにリストの長さを拡張する拡
張アドレス部も各８ビツトの４フイールドアドレスとす
る。この場合、要素データのみでアドレスを表現すると
各フィーμドの値はビット幅８よシ最大２６６に制限さ
れ、これが表現可能なリストの長さの最大値となる。そ
こで各要素データに共通の拡張アドレスを各フィーＡ／
ドの上位ビットとして付加することによって各フィール
ドを１６ビツトに拡張したことになる。

すなわち拡張されたアドレスは、要素データのみのアド
レス（８１ａ２　　ａ３　　ａ４）に対して（ｅ　１Ｘ
２５６　＋　ａ　１ｅ　２Ｘ２５６　＋　ａ　２　　ｅ
　３Ｘ２５θ＋ａ３ｅ　　Ｘ　２５６　＋　ａ　４　）
となる。またこの方式では要素デ−タ処理部の構成を変
えることなく、拡張アドレス部のビット数を増加するだ
けでさらに長いリストを処理できるように拡張できる。

このように表現されたりストデータに対して演算を行う
場合、まずデータをレジスタＲ１に転送する。主制御装
置１３の制御によって、主メモリ装置１内の主データは
主レジスタ装置２内Ｒｘに転送され、その値部で示され
るアドレスにある要素メモリ装置δ内の各要素データ２
４およびリスト拡張メモリ装置９内の拡張データ２７は
要素レジスタ装置６およびリスト拡張レジスタ装置１゜
内のＦＬｘに同時に転送される。さらに拡張データのポ
インタ部によってつながれ、いくつかのアドレスにリス
トデータが分かれている場合は、この転送を繰り返して
複数のレジスタにデータを転送する。ただしレジスタ装
置の大きさの範囲内のデータのみを扱うものとする。

次にレジスタ内のリストデータに対して演算を行う場合
、主レジスタ装置２内Ｒ１のタグ値２１に対しては主演
算装置３が、各要素レジスタ装置ｅ内の要素データ２４
に対しては要素演算装置７が、リスト拡張レジスタ装置
１０の拡張アドレス２８に対してはリスト拡張演算装置
１１が同時に処理を行う。リストデータが複数レジスタ
に分かれている場合はこの処理を繰り返す。

このように拡張データとしてリストの長さを拡張するア
ドレスを付加し、これを処理するリスト拡張データ処理
部を設けることにより、より長いリストデータを表現し
、処理することができるようになる。

第２の実施例は、第１の実施例の拡張データのアドレス
部にリストの深さを拡張するアドレスをもつデータ処理
装置である。

前記の第３図の例で要素データのみでアドレスを表現す
ると、゛フィールドの数によってリストの深さが４に制
限され、これが表現可能なリストの深さの最大値となる
。そこで各要素の共通アドレスを各アドレスの上位フィ
ールドとして付加することによってアドレス部を８フイ
ールドに拡張したことになる。すなわち拡張されたアド
レスは、要素データのみのアドレス（１１ａ２　　ａ３
　ａ４］に対してｉ：ｅｌ　＠２　　＠３　＠４　＆１
　ａ２　　ａ３　ａ４）となる。またこの方式では要素
データ処理部の構成を変えることなく、拡張アドレス部
のフィールド数を増加するだけでさらに深いリストを処
理できるように拡張できる。

このように拡張データとしてリストの深さを拡張するア
ドレスを付加し、これを処理するリスト拡張データ処理
部を設けることにょシ、よシ深いリストデータを表現し
、処理することができるようになる。

第３の実施例は、第１の実施例の拡張データにさらに識
別フラグを付加したデータ処理装置である。第４図はそ
のデータ構造を示す。拡張アドレス部は長さの拡張アド
レスまたは深さの拡張アドレスをもち、識別フラグによ
っていずれの拡張アドレスが用いられているかを決定す
る。

このように拡張データとしてリストの長さまたは深さを
拡張するアドレスとこれを識別するフラグを付加し、こ
れを識別して拡張データに対する演算を行うリスト拡張
演算装置をもつリスト拡張データ処理部を設けることに
より、長さや深さの大きいリストデータを効率的に表現
し、処理することができるようになる。

発明の効果 以上のように本発明のデータ処理装置は、主データをタ
イプをあらわすタグ値と内容とで構成して記憶する主メ
モリ装置および、前記主メモリ装置に記憶されたデータ
を転送して記憶する主レジスタ装置とから構成される主
データ処理部と、リストデータの各要素データをノード
の位置を示すアドレス部と要素のタグ値と内容からなる
バリュー部とで構成して記憶する要素メモリ装置および
、前記要素メモリ装置に記憶されたデータを転送して記
憶する要素レジスタ装置とから構成される複数の要素デ
ータ処理部と、リストの長さまたは深さを拡張する拡張
アドレスとポインタと識別フラグから構成される拡張デ
ータを記憶するリスト拡張メモリ装置および、前記拡張
メモリ装置に記憶されたデータを転送して記憶するリス
ト拡張レジスタ装置とから構成されるリスト拡張データ
処理部と、前記主データ処理部置と要素データ処理装置
とリスト拡張データ処理部とを制御してリストデータを
処理する主制御装置を具備し、要素データ処理部の構成
や数を変更することなく、リスト拡張データ処理部によ
って各要素のアドレスを拡張するデータを付加して処理
することにより、長さや深さがより大きいリストデータ
を表現し、処理できるようになり、さらにリスト拡張デ
ータ処理部のみの変更によって必要な大きさのリストデ
ータを扱える処理装置を構成することができる。

【図面の簡単な説明】

第１図は本発明の実施例におけるデータ処理装置の構成
図、第２図は本実施例のデータ処理装置におけるリスト
データの格納方法を示す図、第３図は第１．第２の実施
例での拡張データの構造図、図は従来のデータ処理装置
の構成図である。 １・・・・・・主メモリ装置、２・・・・・・主レジス
タ装置、４・・・・・・主データ処理部、５・・・・・
・要素メモリ装置、６・・・・・・要素レジスタ装置、
８・・・・・・要素データ処理部、９・・・・・・リス
ト拡張メモリ装置、１ｏ・・・・・・リスト拡張レジス
タ装置、１１・・・・・・リスト拡張データ処理部、１
３・・・・・・主制御装置。 代理人の氏名　弁理士　粟　計重　孝　ほか１名城 糟 で 第 （？ン 城 図 ゾヌトテ゛−タ： （Ａ （Ｃ）） ρ） ７ｒシス常 バソ１−◆Ｕ

Claims (3)

【特許請求の範囲】
1. （１）主データをタイプをあらわすタグ値と内容とで構
   成して記憶する主メモリ装置および前記主メモリ装置に
   記憶されたデータを転送して記憶する主レジスタ装置と
   から構成される主データ処理部と、リストデータの各要
   素データをノードの位置を示すアドレス部と要素のタグ
   値と内容からなるバリュー部とで構成して記憶する要素
   メモリ装置および、前記要素メモリ装置に記憶されたデ
   ータを転送して記憶する要素レジスタ装置とから構成さ
   れる複数の要素データ処理部と、リストの長さを拡張す
   る拡張アドレスとポインタから構成される拡張データを
   記憶するリスト拡張メモリ装置および、前記拡張メモリ
   装置に記憶されたデータを転送して記憶するリスト拡張
   レジスタ装置とから構成されるリスト拡張データ処理部
   と、前記主データ処理装置と要素データ処理装置とリス
   ト拡張データ処理部とを制御して要素処理データ部の構
   造および数に依存しない大きさのリストデータを処理す
   る主制御装置を具備することを特徴とするデータ処理装
   置。
2. （２）リストの深さを拡張する拡張アドレスとポインタ
   から構成される拡張データを処理するリスト拡張データ
   処理部を有する請求項１記載のデータ処理装置。
3. （３）リストの深さを拡張する拡張アドレスとポインタ
   と識別フラグから構成される拡張データを処理するリス
   ト拡張データ処理部を有する請求項１記載のデータ処理
   装置。