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

Abstract

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

Description

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

従来の技術 近年、コンピュータ応用の一つとして人工知能分野が盛
んに研究されている。この分野においては構造を持った
データを処理する必要があり、そのため構造データを取
り扱うことのできる言語であるＬＩＳＰが広く使用され
ている。従来の計算機上での構造データの表現法は、要
素の順序関係と結合の方法をポインタで表現したもの（
以下リストと呼ぶ）を採用している。この方法では全て
のリスト操作にポインタを逐次たどって０夕操作を伴う
ため、人工知能分野の応用プログラムに頻繁に現れる、
パターンマツチングおよび任意要素へのアクセス等に関
し、米質的に効率が悪い。一般に、２進木リストは始点
のノードから始まって順次左右に分岐して行き葉のノー
ドでそれぞれの分岐が終了する形をとる。葉のノードに
はアトムノードとＮＩＬノードの２種類がある。葉のノ
ードでないノードは分岐が続行している事を示すリスト
ノードである。このリストノードは葉のノードの位置を
間接的にあられすためのものである。ポインタ表現では
この構造表現をそのままの形で全てのノードをアドレス
で接続したセルで表現している。

この結果、各要素へのアクセスには常にアドレスの間接
参照の繰り返しが必要となっている。この欠点を克服す
るためにリストデータの表現法を変える次のような方法
が提案されている。葉のノードの位置を直接的にあられ
すことができれば、リストノードの情報を持つ必要はな
い。したがって、葉の位置情報と葉自身の情報を順次並
べた表で、等価なリストデータを表現することができる
。葉のノード位置を表現する方法としてＣＤＲ方向に順
次番号を付け、ＣＡＲ方向に順次項目を割り当てた一次
元ベクトル表現が提案されている。第３図にリストデー
タの表現例を示す。これは３式で表記した場合（Ａ　（
Ｂ　（Ｃ）　）Ｄ）となるリストデータの図式表現第３
図（ａｌ、および、表形弐表現第３図（ｂ）を示したも
のである。図式表現において丸印はリストノードを表し
、四角で囲ったものは葉のノードを示している。また各
ノードの上に付記した数字列は上記した方法に従ってあ
られしたノード位置を示すものである。この葉の部分を
抜きだして表の形で表現したものが表形式表現第３図（
ｂｌであって、ＡＤＤＲＥＳＳ部にノード位置ベクトル
が、ＶＡＬＵＥ部に葉の要素が入った表で構成されてい
る。このような表現形式をとることにより、リストデー
タをポインタをたぐることなく各要素に対し並列に処理
することが可能になり、前述のパターンマツチング等の
リスト操作を高速に行うことができる。

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

第４図は従来の処理装置を示すものである。第４図にお
いて、１は表形式のりストデータを記憶すル主メモリ装
置、２は主演算装置、３はリストデータの各要素を処理
する要素演算手段、４はリストデータの各要素を記憶す
る副メモリ装置、５は前記副演算装置３と副メモリ装置
４とからなる副演算装置、６は複数の副演算装置３から
なるリストデータ処理装置、７は前記主メモリ装置１か
ら前記リストデータ処理装置６中の各副演算装置５へ表
形式データの各要素を順次割り当てる転送装置である。

以上のように構成されたデータ処理装置について、以下
その動作を説明する。まず、通常の数値データ、および
文字データなどは主演算装置のみによって処理される。

リストデータは主メモリ装置１から各要素別に転送装置
７によって副演算装置５に転送される。このとき、転送
装置７はリストデータ処理装置６内の各副演算装置５に
順次問い合わせを行ない空いている副演算装置を探し、
その副演算装置に対し転送を行う。転送終了後、リスト
データは各副演算装置によって並列に処理される。この
ように本発明は上記した構成によって、表形式のリスト
データを処理する複数個の副演算装置毎に固有のメモリ
を持つことにより、各副演算装置に対しメモリ装置から
の転送が一度行われた後は、その情報は各副演算装置に
記憶され以後の処理に使用することができる。この結果
処理の度にデータを転送することを避けることができる
ため、全体のデータ転送量を減らすことができる。

発明が解決しようとする問題点 しかしながら上記のような構成では、メモリ装置からリ
ストデータ処理装置内の各副演算装置へのデータ転送の
際に、転送装置から各副演算装置に順次問い合わせを行
っているため未使用の副演算装置を見つけ出すのに時間
がかかり、かつ転送作業が逐次処理となるため、リスト
データの転送の効率が悪いという問題点を有していた。

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

作用 本発明は上記した構成によって、転送先副演算装置の割
り当てと転送装置によるデータ転送を分離してパイプラ
イン処理により並列に行うことによって転送効率を著し
く改善できる。

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

１４は副演算装置割り当て回路であり、１５は転送装置
制御回路である。１６は副演算装置割り当て回路１４と
、転送装置制御回路１５よりなる転送制御装置である。

第２図は副演算装置割り当て回路のブロック図である。

２１は並列ルックアヘッド回路であり、複数個の入力端
子２２、入力端子２２と同数の出力端子２３、割り当て
開始信号入力端子２４、割り当て開始信号出力端子２５
および出力端子２３の内容を保持するためのラッチ２６
を有する。副演算装置割り当て回路は割り当て開始信号
の入力端子２４および出力端子２５を用いて複数の並列
ルックアヘッド回路を直列に接続したものであり、各並
列ルックアヘッド回路２１の入力端子２４及びラッチ２
６の出力端子金てが、副演算装置割り当て回路のそれぞ
れ入力端子および出力端子となっている。以上のように
構成されたデータ処理装置につき、以下第一図および第
二図を用いて説明する。まず、リストデータの各要素の
ＶＡＬＵＥ部にはアトムデータへのリファレンスが格納
される。それらの実際の値である数値や文字のデータの
処理は、アトムデータ処理部７中のレジス“り５および
演算手段６を用いて行われる。これらのアトムデータは
主記憶中に格納される。次にリストデータの処理は、主
演算装置８内のリストデータ処理部４と副演算装置１２
によって行われる。リストデータ処理部のひとつのリス
トレジスタ２に対し、各副演算装置内の要素レジスタ９
のひとつが対応する。すなわち、リストレジスタ内にリ
ストデータの識別情報が格納され、対応する複数の要素
レジスタ内にリストデータの各要素がそれぞれ格納され
、全体で一つのリストデータを表現している。前記リス
トレジスタに演算が施されると、対応する要素レジスタ
に対し必要な演算が同時に施される。主メモリ装置１に
蓄えられたリストデータが処理される場合は主演算装置
および副演算装置へのデータ転送が行われた後、並列に
処理が行われる。−度転送された各要素のデータは各副
演算装置の管理に置かれ、各副演算装置の副メモリ装置
１２に蓄えられ、主メモリ装置と副演算装置間の不要な
データ転送は行われない。副演算装置へのデータ転送は
次のように行われる。主メモリ装置１に蓄えられたリス
トデータのうち、リストデータの識別情報が主演算装置
内のリストデータ処理部内のリストレジスタに転送され
、それと同時にリストデータの各要素が転送装置１３に
より、転送制御装置１５により各要素毎に割り当てられ
た副演算装置の要素レジスタに対し、別々に転送される
。この割り当て操作は以下のように行われる。まず、各
副演算装置から出力された割り当て可能あるいは不可能
を示す信号が副演算装置割り当て回路中の各並列ルック
アヘッド回路の複数の入力端子へ並列に入力される。こ
の並列ルックアヘッド回路は複数の入力のうち最も下位
のＨ入力に対応する出力端子のみをＨとする回路である
。この回路の出力はＨレベルの時に対応する副演算装置
が割り当て可能であることを示す割り当て信号である。

各並列ルックアヘッド回路は下位の並列ルックアヘッド
回路からの割り当て開始信号がＨレベルの時のみ、自分
への入力から割り当て信号を生成し、割り当て信号の論
理和を上位への割り当て開始信号出力とする。下位から
の割り当て開始信号がＬのときは上位への割り当て開始
信号出力を含む全ての出力をＬとする。

最も下位の並列ルックアヘッド回路の割り当て開始信号
入力にＨを入力すると割り当てが開始される。この結果
副演算装置割り当て回路の高々１個の出力端子がＨとな
り、割り当て可能な最も下位の副演算装置が検出される
。その結果に従って転送制御回路は副演算装置に転送開
始を伝え、転送装置に要素データの転送を指示する。次
の割り当て操作と現在の転送動作は独立しているため、
転送すべき次の要素データが存在する時には、現在の転
送装置の完了を待たずに次の割り当てを決定することが
できる。このように転送制御装置と転送装置によるパイ
プライン処理を行えば、割り当て操作に要する時間は転
送に要する時間に比べ小さいので、多数の要素データを
転送する際には割り当て操作に要する時間を見掛は上Ｏ
とすることができる。以上のように本実施例によればデ
ータの転送に要する時間を最小に抑えることが可能とな
る。

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

【図面の簡単な説明】

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

Claims (1)

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