JPS63255741A - デ−タ処理装置 - Google Patents

Abstract

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

Description

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

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

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

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

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

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

（参考文献、ｒＬＩＳＰマシン」情報処理　Ｖｏｌ。

２３　　Ｎａ　８　　ｐｐ７５２−７７２　）しかしな
がら、上記したような言語の実行系に関する改善はなさ
れてきたものの、計算機内部における構造体データの表
現としては基本的には要素の順序関係と結合の方法をポ
インタで表現したもの（以下リストと呼ぶ）を使用して
いる。

一般にリストは２進木で表現され、始点のノードから始
まって順次左右に分岐して行き葉のノードでそれぞれの
分岐が終了する形をとる。葉のノードにはアトムノード
とＮＩＬノードの２種類がある。葉のノードでないノー
ドは分岐が続行している事を示すリストノードである。

このリストノードは葉のノードの位置を間接的に表すた
めのものである。

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

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

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

解操作を伴うため非効率である。

これらの問題点を解決するためには、基本的にリストデ
ータの表現をかえる必要がある。すなわち、葉のノード
の位置を直接的にあられすことができれば、リストノー
ドの情報を持つ必要はない。

したがって、葉の位置情報と葉自身の情報を順序並べた
表で、等価なリストデータを表現することができる。こ
の葉のノード位置を表現する方法としてリストの長さ方
向に順序番号を付け、深さ方向に順次項目を割り当オた
一次元ベクトル表現を用いると、リストデータは葉の位
置情報を示すベクトルと葉自身の情報を組としたデータ
の集合として表形式で表現される。

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

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

以下図面を参照しながら上述した従来のデータ処理装置
の一例について説明する。第４図は従来のデータ処理装
置の構成を示すものである。

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

以上のように構成されたデータ処理装置については、以
下その動作を説明する。

リストデータの処理を行う場合、まず主メモリ装置２１
に蓄えられたりストデータは、転送装置２２によって、
その識別情報はリスト処理部２８のリストレジスタ装置
２６に、各要素はそれぞれ別々の要素処理部３１の要素
レジスタ装置２９に転送される。

リストデータの演算は、リストレジスタ装置２６の識別
情報に対してはリスト演算装置２７、各要素レジスタ装
置２９の要素に対しては要素演算装置３０が行う。リス
ト処理部２８と要素処理部３１によって処理されたリス
トデータは、転送装置２２によって主メモリ装置２１に
転送され蓄えられる。また通常の数値データおよびアト
ムデータを処理する場合は、同様に主メモリ装置２１に
蓄えられたデータを実データ処理部２５の実データレジ
スタ装置２３に転送し、実データ演算装置２４によって
演算を行う。

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

発明が解決しようとする問題点 しかしながら上記のような構成では、レジスタ装置上で
のりストデータは要素毎に並列に処理することができる
が、主メモリ装置と要素レジスタ装置との間のリストデ
ータの転送が多゛発し、これによってリスト処理全体と
しての処理速度が低下する。

本発明は上記問題点に鑑み、表形式のリストデータの並
列処理において、リストデータの転送に要する時間を短
縮したデータ処理装置を提供するものである。

間５点を解決するための手段 上記問題点を解決するために本発明のデータ処理装置は
、リストデータの各要素をノードの位置を示すアドレス
部とデータ値へのリファレンスを示すバリュー部とで構
成して記憶する要素メモリ８を置と、上記要素メモリ装
置に記ｊＱされた要素を転送して記憶する要素レジスタ
装置と、上記要素レジスタ装置に記憶された要素に演算
を行う要素演算装置とから構成される複数の要素処理部
と、リストデータの識別情報を記憶するリストメモリ装
置と、上記リストメモリ装置に記憶された識別情報を転
送して記憶するリストレジスタ装置と、上記リストレジ
スタ装置に記憶された識別情報に演算を行うリスト演算
装置とから構成されるリスト処理部を具備し、リストデ
ータの転送及び演算を要素毎に並列に処理できるように
したものである。

作用 本発明は上記した構成によって、表形式のリストデータ
を各要素毎に処理する要素処理部に要素メモリ装置を備
えて、リストデータをこれに蓄えて要素メモリ装置と要
素レジスタ装置との間で並列に転送することにより、転
送時間を著しく短縮することができるようにしたもので
ある。

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

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

第２図は上記実施例のデータ処理装置において、リスト
データをメモリ装置とレジスタ装置間で転送する動作を
示すものである。リストメモリ装置５および要素メモリ
装置９のアドレスＭｎに格納されているリストデータの
識別情報が１３、各要素のデータが１４である。リスト
レジスタ装置６および要素レジスタ装置１０のレジスタ
Ｒｘに転送されるリストデータの識別情報が１５各要素
のデータが１６である。但し９　（ｎ）　、１０　（ｎ
）　、１４　（ｎ）、１６（ｎ）はそれぞれ第ｎ番目の
要素処理部１２（ｎ）の要素メモリ装置、要素レジスタ
装置、要素メモリ内データ、要素レジスタ内データであ
る。

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

リストデータは表形式によって表現され、その識別情報
はリストメモリ装置５の任意アドレスＭｎに１３として
、ｎ個の要素データは別々に要素処理部１２　（１）　
〜１２　（ｎ）内の要素メモリ装置９　（１）〜９　（
ｎ）の同一アドレスＭｎに１４　（１）　〜１４　（ｎ
）として格納されている。このデータに対して演算を行
うため、まずメモリ内のりストデータをレジスタＲｘに
転送する。すなわちリストメモリ装置５内の識別情？１
１３はリストレジスタ装置内Ｒｘの１５に、要素メモリ
装置９　（１）〜９　（ｎ）内の各要素データ１４（１
）〜１４（ｎ）はそれぞれ要素レジスタ装置１０（１）
〜１０（ｎ）内ＩＲｘの１６（１）〜１６（ｎ）に同時
に転送する。レジスタに転送されたりストデータに演算
を行う場合、リストレジスタ装置６内の識別情報１５に
対してはリスト演算装置７が、各要素レジスタ装置１０
内の要素データ１６に対しては要素演算装置１１が同時
に処理を行い、処理結果はリストレジスタ装置６および
要素レジスタ装置１０内の同一レジスタＲｘに格納され
る。

処理されたりストデータをメモリに再格納する場合、上
記の転送処理を逆方向に行う。すなわちリストレジスタ
装置６内の識別情報１５はリストメモリ装置ｓ内の１３
に、要素レジスタ装置１０（１）〜１０（ｎ）内の各要
素データ１６（１）〜１６（ｎ）はそれぞれ要素メモリ
装置９（１）〜９（ｎ）内の１４（１）〜１４（ｎ）に
同時に転送する。また通常の数値データおよびアトムデ
ータはリストデータとは区別され、実データメモリ装置
１に格納し、実データレジスタ装Ｎ２に転送されて実デ
ータ演算装置３によって演算を行う。

この結果レジスタ装置とメモリ装置間のリストデータの
転送は、リスト内の要素の数に依存することなく、１要
素データの転送時間で全てのデータ転送が完了する。し
たがって上記の構成によって、リストデータの表形式表
現におけるデータ転送時間は大幅に短縮され、さらに要
素データの演算をそれぞれ並列に処理することにより高
速なリスト処理が実現される。

なお本実施例ではレジスタ内のりストデータに対して演
算を行った結果を同一レジスタに格納しているが、この
結果は異なるレジスタに格納してもよい。

発明の効果 以上のように本発明は、リストデータの各要素をノード
の位置を示すアドレス部とデータ値へのリファレンスを
示すバリュー部とで構成して記憶する要素メモリ装置と
、上記要素メモリ装置に記憶された要素を転送して記憶
する要素レジスタ装置と、上記要素レジスタ装置に記憶
された要素に演算を行う要素演算装置とから構成される
複数の要素処理部と、リストデータの識別情報を記憶す
るリストメモリＷｉと、上記リストメモリ装置に記憶さ
れた識別情報を転送して記憶するリストレジスタ装置と
、上記リストレジスタ装置に記憶された識別情報に演算
を行なうリスト演算装置とから構成されるリスト処理部
を具備し、上記要素メモリ装置に蓄えた表形式のりスト
データの各要素を要素レジスタ装置との間で並列に転送
することによって、転送時間を著しく短縮し、リストデ
ータの並列処理をより高速に行うことができるようにな
る。

【図面の簡単な説明】

第１図は本発明の一実施例におけるデータ処理装置の構
成図、第２図は本実施例のデータ処理装置におけるリス
トデータ転送の動作図、第３図はりストデータの表形式
表現の一例を示す説明図、第４図は従来のデータ処理装
置の構成図である。 ５・・・・・・リストメモリ装置、６・・・・・・リス
トレジスタ装置、７・・・・・・リスト演算装置、８・
・・・・・リスト処理部、９・・・・・・要素メモリ装
置、１０・・・・・・要素レジスタ装置、１１・・・・
・・要素演算装置、１２・・・・・・要素処理部。 代理人の氏名　弁理士　中尾敏男　はか１名Ｘ　　　　
　　　　鍔 ｃ″　　　　　　　ミ　　　　　２ ４３図 （ｂ）

Claims (1)

【特許請求の範囲】
1. リストデータの各要素のノードの位置を示すアドレス部
   とデータ値へのリファレンスを示すバリュー部とで構成
   して記憶する要素メモリ装置と、上記要素メモリ装置に
   記憶された要素を転送して記憶する要素レジスタ装置と
   、上記要素レジスタ装置に記憶された要素に演算を行う
   要素演算装置とから構成される複数の要素処理部と、リ
   ストデータの識別情報を記憶するリストメモリ装置と、
   上記リストメモリ装置に記憶された識別情報を転送して
   記憶するリストレジスタ装置と、上記リストレジスタ装
   置に記憶された識別情報に演算を行うリスト演算装置と
   から構成されるリスト処理部を具備し、リストデータの
   転送及び演算を要素毎に並列に処理できるように構成し
   たことを特徴とするデータ処理装置。