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

Abstract

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

Description

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

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

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

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

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

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

（例えば、参考文献ｒＬＩｓＰマシン」情報処理Ｖｏ１
．２３　　ｋ　８　　ｐｐ　７５２−７７２）しかしな
がら、前記したような言語の実行系に関する改善はなさ
れてきたものの、計算機内部における構造体データの表
現としては基本的には要素の順序関係と結合の方法をポ
インタで表現したもの（以下リストと呼ぶ）を使用して
いる。この方法では全てのリスト操作にポインタを遂次
たどっていく操作を伴うため、人工知能分野の応用プロ
グラムに頻繁に現れる以下の操作を行うには本質的に効
率が悪い。（イ）パターンマツチング；リストの分解操
作を伴うため非効率である。（ロ）任意の要素へのアク
セス、リストの分解、特定要素の置き換え；リストたぐ
りとなり効率が悪い。

上記の問題点を解決するために、リストデータの表現方
法をかえる提案がなされている。

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

ポインタ表現ではこの構造表現をそのままの形で全ての
ノードをアドレスで接続したセルで表現している。この
結果、各要素へのアクセスは常にアドレスの間接参照の
繰り返しが必要となっている。

しかし、葉のノードの位置を直接的にあらゎすことがで
きれば、リストノードの情報を持つ必要はない。したが
って、葉の位置情報と葉自身の情報を順次並べた表で、
等価なリストデータを表現することができる。葉のノー
ド位置を表現する方法としてＣＤＲ方向に順次番号を付
け、ＣＡＲ方向に順次項目を割り当てた一次元ベクトル
表現が提案されている。従ってリストデータは葉の位置
情報を示すベクトルと葉自身の情報を組としたデータの
集合で表現される。この表現法ではポインタ表現のよう
にリストの解釈を２進木リストに限る必要がない。

第３図にリストデータの表現例を示す。これは８式で表
記した場合（Ａ　（Ｂ　（Ｃ）　”）　Ｄ）となるリス
トデータの図式表現（ａｌ、および、表形式表現（ｂ）
を示したものである。図式表現において丸印はリストノ
ードを表し、四角で囲ったものは葉のノードを示してい
る。また各ノードの上に付記した数字列は上記した方法
に従って表したノード位置を示すものである。この葉の
部分を抜きだして表の形で表現したものが表形式表現（
ｂｌであって、アドレス部にノード位置ベクトルが、バ
リュ一部に葉の要素が入った表で構成されている。この
ような表現形式をとることにより、リストデータをポイ
ンタをたぐ°ることなく各要素に対し並列に処理するこ
とが可能になり、前述の操作を高速に行うことができる
。

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

第４図は従来の処理装置を示すものである。第４図にお
いて、１は表形式のリストデータを記憶するメモリ装置
、２は、表形式データの各要素を処理する複数の処理ユ
ニット３からなるリストデータ処理装置、４はアトムデ
ータ処理装置、５は前述のメモリ装置から前述のリスト
データ処理中の各処理ユニットへ表形式データの各要素
を順次割り当てる転送装置である。

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

まず、通常の数値データ、および文字データなどはアト
ムデータ処理装置４において処理される。

リストデータはメモリ装置１から各要素別にリストデー
タ処理装置内の各処理ユニット３に転送装置５により順
次転送され、各処理ユニットによって並列に処理される
。このようにアトムデータをリストデータとは別に処理
することにより、リストデータの効率的処理と、処理系
の構成の単純化を狙っている。

発明が解決しようとする問題点 しかしながら上記のような構成では、メモリ装置からり
ストデータ処理装置内の各処理ユニソトへのデータ転送
が多発するので、リストデータの並列処理におけるボト
ルネックが発生するという問題点を有していた。

本発明は上記問題点に鑑み、表形式のリストデータの並
列処理においてデータ転送量が少ないデータ処理装置を
提供するものである。

問題点を解決するための手段 上記問題点を解決するために本発明のデータ処理装置は
、リストデータの各ノードの位置をベクトルで表現した
表形式のデータとして記憶する主メモリ装置と、表形式
のリストデータの識別情報を記憶する複数のリストレジ
スタとリスト演算手段からなるリストデータ処理部およ
び複数個のレジスタと演算手段からなる非リストデータ
処理部からなる主演算装置と、表形式のリストデータの
各要素を記憶する複数の要素レジスータと演算手段と副
メモリ装置を持ち前記の主演算装置の制御のもとにリス
トデータの各要素を並列に処理する複数個の副演算装置
と、前記各副演算装置に対し前記主メモリ装置に蓄えら
れた表形式データの要素を順次割り当てる転送装置とを
、備えたものである。

作用 本発明は上記した構成によって、表形式のりストデータ
を処理する複数個の処理ユニット毎に固有のメモリを持
つことにより、各処理ユニットに対しメモリ装置からの
転送が一度行われた後は、その情報は各処理ユニットに
記憶され以後の処理に使用することができる。この結果
処理の度にデータを転送することを避けることができる
ため、全体のデータ転送量を著しく減らすことができる
。

実施例 以下本発明の一実施例のデータ処理装置について、図面
を参照しながら説明する。第１図は本発明の実施例にお
けるデータ処理装置の構成を示すものである。第１図に
おいて、１は主メモリ装置、２はリストレジスタ、３は
リスト演算手段であり、リストデータ処理部４は複数の
リストレジスタとリスト演算手段の総称である。５はレ
ジスタ、６は演算手段であり、アトムデータ処理部７は
複数のレジスタと演算手段の総称である。さらに主演算
装置８はリストデータ処理部およびアトムデータ処理部
の総称である。９は要素レジスタ、１０は要素演算手段
、１１は副メモリ装置である。副演算装置１２は要素レ
ジスタ、要素演算手段、および副メモリ装置の総称であ
る。１３は転送装置である。

第２図は上記実施例における副メモリ装置と主メモリ装
置のアドレス空間の関係を図示したものである。

第２図において２１は主メモリ装置のアドレス空間を表
し、２２は前記アドレス空間中のりストデータ領域であ
り、２３は副メモリ装置のアドレス空間である。

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

まず、リストデータの各要素のＶＡＬＵＥ部にはアトム
データへのリファレンスが格納される。

それらの実際の値である数値や文字のデータの処理は、
アトムデータ処理部７中のレジスタ５および演算手段６
を用いて行われる。これらのアトムデータは主記憶中に
格納される。

次にリストデータの処理は、主演算装置８内のリストデ
ータ処理部４と副演算装置１２によって行われる。

リストデータ処理部のひとつのリストレジスタ２に対し
、各副演算装置内の要素レジスタ９のひとつが対応する
。すなわち、リストレジスタ内にリストデータの識別情
報が格納され、対応する複数の要素レジスタ内にリスト
データの各要素がそれぞれ格納され、全体で一つのリス
トデータを表現している。

主メモリ装置１に蓄えられたリストデータが処理される
場合、まずリストデータ処理部内のリストレジスタにリ
ストデータの識別情報が転送され、それと同時にリスト
データの各要素が転送装置１３により各副演算装置の要
素レジスタに対し別々に転送される。そして前記リスト
レジスタに演算が施されると、対応する要素レジスタに
対し必要な演算が同時に施される。

一度転送された各要素のデータは各副演算装置の管理に
置かれ、各副演算装置の副メモリ装Ｗ１２に蓄えられ、
主メモリ装置と副演算装置間の不要なデータ転送は行わ
れない。各副メモリ装置のアドレス空間２３は図２に示
すように主メモリ装置のアドレス空間の一部分２２に置
かれており、さらに全ての各副メモリ装置のアドレス空
間２１は同一アドレスにある。この結果、ある特定のリ
ストデータの識別情報および各要素は、本データ処理装
置のアドレス空間の同一アドレス上に全て存在すること
になる。

この結果、リストデータ処理部において、主メモリ装置
のアドレス空間中のりストデータ領域を参照すると、同
時に全ての各副演算装置において対応するメモリ装置中
の領域が参照され、リストデータの処理は並列に行われ
る。

この様なアドレス空間を持つことにより、簡単な構成で
データの転送量を最小に抑えた処理装置を構成すること
ができる。

発明の効果 以上のように本発明はりストデータの各ノードの位置を
ベクトルで表現した表形式のデータとして記憶する主メ
モリ装置と、表形式のリストデータの識別情報を記憶す
る複数のレジスタと演算手段からなるリストデータ処理
部および複数個のレジスタと演算手段からなる非リスト
データ処理部からなる主演算装置と、表形式のリストデ
ータの各要素を記憶する複数のレジスタと演算手段と副
メモリ装置を持ち前記の主演算装置の制御のもとにリス
トデータの各要素を並列に処理する複数個の副演算装置
と、前記各副演算装置に対し前記主メモリ装置に蓄えら
れた表形式データの要素を順次割り当てる転送装置とを
具備し、表形式のりストデータの並列処理においてデー
タ転送量を小さく抑えることのできるデータ処理装置を
提供するものである。

【図面の簡単な説明】

第１図は本発明の一実施例におけるデータ処理装置のブ
ロック図、第２図は第１図の主メモリ装置および副メモ
リ装置のアドレス空間上の対応図、第３図（ａｌ　（ｂ
）はリストデータの表形式表現の一例を示す説明図、第
４図は従来のデータ処理装置のブロック図である。 １・・・・・・主メモリ装置、２・・・・・・リストレ
ジスタ、３・・・・・・リスト演算手段、４・・・・・
・リストデータ処理部、５・・・・・・レジスタ、６・
・・・・・演算手段、７・・・・・・アトムデータ処理
部、８・・・・・・主演算装置、９・・・・・・要素レ
ジスタ、１０・・・・・・要素演算手段、１１・・・・
・・副メモリ装置、１２・・・・・・副演算装置、１３
・・・・・・転送装置。

Claims (1)

【特許請求の範囲】
1. リストデータの各ノードの位置をベクトルで表現した表
   形式のデータとして記憶する主メモリ装置と、前記表形
   式のリストデータの識別情報を記憶する複数のリストレ
   ジスタとリスト演算手段からなるリストデータ処理部お
   よび複数個のレジスタと演算手段からなる非リストデー
   タ処理部からなる主演算装置と、前記表形式のリストデ
   ータの各要素を記憶する複数の要素レジスタと要素演算
   手段と副メモリ装置を持ち前記の主演算装置の制御のも
   とにリストデータの各要素を並列に処理する複数個の副
   演算装置と、前記各副演算装置に対し前記主メモリ装置
   に蓄えられた表形式データの要素を順次割り当てる転送
   装置とを備えたことを特徴とするデータ処理装置。