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

Abstract

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

Description

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

従来の技術 近年、コンピュータ応用の一つとして人工知能分野が盛
んに研究されている。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

まず、第６図は主メモリ装置と要素メモリ装置との関係
を示す図である。

第６図において、５１は主メモリ装置、６６は要素メモ
リ装置、６１はリストデータの識別情報であり、６２は
要素アドレス部、６３はバリュー部である。

リストデータは、識別情報と複数の要素データからなる
。リストデータの識別情報６１は、要素メモリ内のアド
レスであり、主メモリ装置６１に記憶されている。また
、リストの要素データは、各々要素アドレス部６２とバ
リュ一部６３からなり、同一のリストデータを構成する
複数の要素データは、複数の要素メモリ装置６６におい
てリストデータの識別情報６１に示される同一アドレス
に記憶されている。

同様に、主レジスタ装置６２と各要素レジスタ装置５ｅ
も対応関係を持つ。

リストデータに対する処理が必要なときには、リストデ
ータの識別情報６１を主メモリ装置５１から主レジスタ
装置５２に転送すると同時に、制御装置５９により各要
素処理部５８に対し同一のアドレスを流し、各要素処理
部５８において、要素メモリ装置５６の指示されたアド
レスから要素データを要素レジスタ装置ｓ６に転送する
。さらに、主演算装置５３に対する演算命令と同時に、
制御装置５９により各要素処理部６８に対し同一の演算
命令を流し、複数の要素演算装置５７により複数の要素
データに対し、並列に演算を施すことができる。

発明が解決しようとする課題 しかしながら上記のような構成では、表形式リストデー
タの要素の位置を表現する要素アドレス部の項目数に制
限があるため、要素アドレス部の項目数が不足する要素
データを含むリストデータ、つまり深さが要素アドレス
部の項目数を越えるようなリストデータは処理できない
という課題を有していた。

本発明は上記課題に鑑み、表形式のりストテ゛−タの並
列処理において、任意の深さのリストデータを処理でき
るようなデータ処理装置を提供するものである。

課題を解決するだめの手段 上記課題を解決するために本発明のテ゛−タ処理装置は
、リストデータの要素の格納位置情報を記憶する主メモ
リ装置と、上記主メモリ装置に記憶されたデータを転送
して記憶する主レジスタ装置と、上記主レジスタ装置に
記憶されたデータを演算する主演算装置とから構成され
る主データ処理部と、リストデータの各要素をノードの
位置を示す要素アドレス部とデータ値の格納位置を示す
バリュ一部とで構成して記憶する要素メモリ装置と、上
記要素メモリ装置に記憶された要素を転送して記憶する
要素レジスタ装置と、上記要素レジスタ装置に記憶され
た要素を演算する要素演算装置とから構成される複数の
要素データ処理部と、要素アドレス部の項目数が不足す
る要素データを含むリストデータのオーバーフロー情報
を記憶するオーバーフロー情報記憶装置と、制御装置と
を具備し、任意の深さのリストデータを処理できるよう
にしたものである。

作用 本発明は上記した構成によって、要素メモリ装置の要素
アドレス部の項目数が不足する要素データを含むリスト
データに対し、オーバーフロー情報記憶装置により指示
された要素メモリ装置のアドレスに、要素アドレスの続
きを記憶することにより、任意の深さのリストデータを
処理できるようにしたものである。

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

第１図は本発明の実施例におけるデータ処理装置の構成
を示すものである。

第１図において１は主メモリ装置、２は主レジスタ装置
、３は主演算装置、４は主メモリ装置１゜主レジスタ装
置２．主演算装置３よシ構成される主データ処理部、５
はオーバーフロー情報記憶装置、６は要素メモリ装置、
７は要素レジスタ装置、８は要素演算装置、９は要素メ
モリ装置θ、要素レジスタ装置７．要素演算装置８より
構成される複数の要素データ処理部、１ｏは制御装置で
ある。

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

まず、第２図は上記実施例のデータ処理装置において、
深さ方向にオーバーフローしているリストデータの記憶
方法を示す図である。

第２図において１は主メモリ装置、ｅは要素メモリ装置
、５はオーバーフロー情報記憶装置、２１はリスト識別
アドレス、２２はオーバーフローフラグ、２３は補助ア
ドレス部、２４は要素アドレス部であり、その項目数を
Ｎとする。さらに、２６はバリュ一部である。

第３図は深さ方向オーバーフローリストデータの例とし
て、８式で表記した場合 （（（（（（（（（λ　Ｂ）））））））））となるリ
ストデータの表表現（１）、および、上記実施例のデー
タ処理装置における上記リストデータの要素データを示
すものである。

リストを構成する複数の要素データのアドレス部が、全
て項目数の制限内に収まる場合には、オーバーフロー情
報メモリ６内のリスト識別アドレス２１のオーバーフロ
ーフラグ２２の値ば０であり、各要素メモリ装置６内の
リスト識別アドレス２１に、要素データが記憶されてお
り、要素データの記憶方法、処理方法は従来例と同じで
ある。

リストを構成する要素データのうち、そのアドレス部の
項目数が不足する要素データが存在する場合、オーバー
フロー情報メモリ５内のリスト識別アドレスのオーバー
フローフラグの値は１であり、各要素メモリ装置６内の
リスト識別アドレス２１には、要素データのアドレスの
うち要素アドレス部の項目数Ｎに収まるアドレスと、要
素の情報をバリュ一部２５に持つ。さらに、オーバーフ
ロー情報メモリ６内のリスト識別アドレス２１の補助ア
ドレス部２３には、要素データのアドレス部の続きの部
分を記憶する要素メモリ内のアドレスが書かれている。

このアドレス値と同一の各要素メモリ装置のアドレスに
は、同じ要素メモリ装置の要素データのアドレス部の続
きが要素アドレス部に書かれている。例えば、Ｎが８の
場合、第３図（１）の表表現で示されるリストデータは
、本実施例のデータ処理装置では、第３図（２）のよう
に表現される。

したがって上記の構成によって、任意の深さのリストデ
ータを処理できる。

発明の効果 以上のように本発明は、リストデータの要素の格納位置
情報を記憶する主メモリ装置と、上記主メモリ装置に記
憶されたデータを転送して記憶する主レジスタ装置と、
上記主レジスタ装置に記憶されたデータを演算する主演
算装置とから構成される主データ処理部と、リストデー
タの各要素をノードの位置を示す要素アドレス部とデー
タ値の格納位置を示すバリュ一部とで構成して記憶する
要素メモリ装置と、上記要素メモリ装置に記憶された要
素を転送して記憶する要素レジスタ装置と、上記要素レ
ジスタ装置に記憶された要素を演算する要素演算装置と
から構成される複数の要素データ処理部と、要素アドレ
ス部の項目数が不足する要素データを含むリストデータ
のオーバーフロー情報を記憶するオーバーフロー情報記
憶装置と、制御装置とを具備し、任意の深さのリストデ
ータを処理できるようになる。

【図面の簡単な説明】

第１図は本発明の一実施例におけるデータ処理装置の構
成図、第２図は深さ方向にオーバーフローしているリス
トデータの表示方法を示す説明図、第３図（１）は本発
明の一実施例の説明に用いるリストデータの表表現を示
すデータ表図、第３図（２）は本発明の一実施例におけ
るデータ処理装置での表現を示す説明図、第４図はリス
トデータの表表現の一例を示すデータ対応図、第５図は
従来のデータ処理装置の構成図、第６図は主メモリ装置
と要素メモリ装置の関係を示す説明図である。 １・・・・・・主メモリ装置、２・・・・・・主レジス
タ装置、３・・・・・・主演算装置、４・・・・・・主
データ処理部、６・・・・・・オーバーフロー情報記憶
装置、６・・・・・・要素メモリ装置、７・・・・・・
要素レジスタ装置、８・・・・・・要素演算装置、９・
・・・・・要素データ処理部、１ｏ・・・・・・制御装
置。 代理人の氏名　弁理士　中　尾　敏　男　ほか１名第４
図 （Ａ　　（Ｂ　（Ｃ））　Ｄ）

Claims (1)

【特許請求の範囲】
1. リストデータの要素の格納位置情報を記憶する主メモリ
   装置と、上記主メモリ装置に記憶されたデータを転送し
   て記憶する主レジスタ装置と、上記主レジスタ装置に記
   憶されたデータを演算する主演算装置とから構成される
   主データ処理部と、リストデータの各要素をノードの位
   置を示す要素アドレス部とデータ値の格納位置を示すバ
   リュー部とで構成して記憶する要素メモリ装置と、上記
   要素メモリ装置に記憶された要素を転送して記憶する要
   素レジスタ装置と、上記要素レジスタ装置に記憶された
   要素を演算する要素演算装置とから構成される複数の要
   素データ処理部と、要素アドレス部の項目数が不足する
   要素データを含むリストデータのオーバーフロー情報を
   記憶するオーバーフロー情報記憶装置と、制御装置とを
   具備し、任意の深さのリストデータを処理することを特
   徴とするデータ処理装置。