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

Abstract

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

Description

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

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

（例えばｒＬＩｓＰマシン」　情報処理ｖｏ１．２３　
　Ｎｏ、　　８　　ｐｐ７５２−７７２）。

これら専用マシンは主に言語的側面からアプローチを行
ったもので、その改善の内容の代表的なものを以下に示
す。＋ＩＩＣＡＲ，ＣＤＲ等、原始的関数はマイクロプ
ログラムレベルで実行する。（２）ジェネリックデータ
タイプを扱うためＴＡＧ付きデータ形式とする。（３）
スタック処理を高速にするためハードウェアコントロー
ルスタックを設ける。

しかしながら、上記したような言語の実行系に関する改
善はなされてきたものの、計算機内部における構造体デ
ータの表現としては基本的には要素の順序関係と結合の
方法をポインタで表現したもの（以下リストと呼ぶ）を
使用しているため次のような問題があった。（１）任意
の要素へのアクセスがリストたぐりとなり効率が悪い。

（２）リストマツチングはリストの分解操作を伴うため
非効率である。（３）ガーベソジコレクションが困難で
ある。（４）メモリ参照の局所性が悪く、キャッシュの
ヒント率が下がる。また、基本的には共有構造をとるた
め以下の問題が生じた。１５１ＲＰＬＡＣＡ。

ＲＰＬＡＣＤ等、直接リスト操作を行うと陰に他のデー
タも変更してしまうといった思いがけない副作用が生じ
る。（６）並列処理時、変数のロックが困難である。一
方、これらの問題点を解決するためには、基本的にリス
トデータの表現をかえる試みが提案されている。

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

ポインタ表現ではこの構造表現をそのままの形で全ての
ノードをアドレスで接続したセルで表現している。

しかしながら、葉のノードの位置を直接的にあられすこ
とができれば、リストノードの情報を持つ必要はない。

したがって、葉の位置情報と葉自身の情報を順次並べた
表で、等価なりストデータを表現することができる。葉
のノード位置を表現する方法としてＣＤＲ方向に順次番
号を付け、ＣＡＲ方向に順次項目を割り当てた一次元ベ
クトル表現が提案されている。

（例えば、「構造を持ったデータの高速マツチング方式
」　情報処理学会　第３３口金国大会７Ｄ−２） 従ってリストデータは葉の位置情報を示すベクトルと葉
自身の情報を組としたデータの集合で表現される。

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

リストをこのような表形式で表現した場合、ポインタ表
現の多くの欠点は免れることができるが、当然、その演
算体系は従来のポインタ表現とは異なる。

第４図にＬＩＳＰの基本リスト操作関数における裏操作
の一例を示す。

第４図で明かなようにＣＡＲ関数はＡＤＩｌＲＥＳＳ部
の先頭が１の要素を抜き出し、２番目以下のＡＤ、ＤＲ
ＥＳＳを先頭方向にシフトすることにより（これを以下
ＣＡＲシフトと呼ぶ）実行することができる。ＣＤＲ関
数はＣＡＲ関数とは逆に先頭ＡＤＤＲＥＳＳが１の要素
を取り除き、残った要素の先頭ＡＤＤＲＥＳＳから１を
減じることにより　（以下これをＣＤＲシフトと呼ぶ）
実行される。

Ｃ０Ｎ５関数についてはもう少し複雑である。

まずＣ０Ｎ５関数の第一引数について、ＡＤＤＲＥＳＳ
部を先頭方向とは逆の方向にシフトし、先頭ＡＤＤＲＥ
ＳＳを１とする。これは前記したＣＡＲシフトとは逆の
演算であり、以下ＲＣＡＲシフトと呼ぶ。第二引数につ
いては先頭ＡＤＤＲＥＳＳに１を加算する（以下これを
ＲＣＡＲと同じ理由でＲＣＤＲシフトと呼ぶ）。次にこ
の二つの引数を一つの表としてまとめればＣ０Ｎ５関数
は実行される。

発明が解決しようとする問題点 しかしながら上記のような構成では、ポインタ表現では
極めて容易に行えるＣＡＲ，ＣＤＲ。

Ｃ０Ｎ５といったＬＴＳＰの基本関数が表形式では全て
の要素に対しての演算を必要とするので、リストデータ
処理に対するパフォーマンスが劣るという問題点を有し
ていた。

本発明は上記問題点に鑑み、簡単な構成で効率良く表形
式のリストデータを処理することのできるデータ処理装
置を提供するものである。

問題点を解決するための手段 上記問題点を解決するために本発明のデータ処理装置は
、リストデータをノードの位置を示すＡＤＤＲＥＳＳ部
とデータ値へのリファレンスを示すＶＡＬＵＥ部とで構
成した表形式のデータとして記憶するメモリ装置と、前
記表形式データの要素を記憶するレジスタ装置と、前記
メモリ装置から転送されるデータと前記レジスタ装置か
らのフｉ゛二下バ・ツクされるデータとを選択して出力
する入力選択回路と前記入力選択回路から出力されたデ
ータのＡＤＤＲＥＳＳ部データを左右方向へシフトする
バレルシフト回路と前記バレルシフト回路の出力に接続
されＡＤＤＲＥＳＳ部データの先頭値を１だけ増減する
加算回路から構成されるシフト装置とを具備したもので
ある。

作用 本発明は上記した構成によって、表形式のリストデータ
に対する操作、例えば前記したＣＡＲシフト、ＣＤＲシ
フト、ＲＣＡＲシフト、ＲＣＤＲＣＤ上などの操作をバ
レルシフト回路、加算回路を用いて効率良く実現できる
こととなる。

実施例 以下本発明の一実施例のデータ処理装置について、図面
を参照しながら説明する。第１図は本発明の実施例にお
けるデータ処理装置の構成を示すものである。

第１図において１はメモリ装置、２は転送装置、３はシ
フト装置、４はレジスタ装置である。第２図は上記実施
例におけるシフト装置の内部構成を示すものである。

第２図において２１は入力選択回路、２２はバレルシフ
ト回路、２３は加算回路である。

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

第１図においてメモリ装置１に蓄えられたりストデータ
は処理される場合、転送装置２によりレジスタ装置４ヘ
シフト装置３を通して転送される。

第２図において入力選択回路２１は、メモリ装置ｌから
の転送データとレジスタ装置４からのフィードハックさ
れたデータとを選択信号ＳＥＬにより切り替えて出力す
るもので、メモリ装置１からの転送時はＭ！をレジスタ
内演算の場合はＡＩの信号を出力する。入力選択回路２
１から出力されたデータはＡＤＤＲＥＳＳ部とＶＡＬＵ
Ｅ部に分離され、ＡＤＤＲＥＳＳ部データＡＤはバレル
シフト回路２２の入力となり、一方ＶＡＬＵＥ部データ
ＶＤはそのままシフト装置３の出力ＲＤの一部となる。

バレルシフト回路はＡＤＤＲＥＳＳ部のデータを左右方
向ヘシフトする回路で、シフト選択信号ＳＨＣにより制
御される。ＣＡＲシフト時には前記したように先頭方向
へのシフトであるが、この場合最後部のアドレスにはＯ
が入る。

ＲＣＡＲシフト時は反対に先頭部に０が入る。

ＣＤＲシフト、ＲＣＤＲＣＤ上はいわゆるシフト操作で
はなく、ＡＤＤＲＥＳＳ部の先頭値が１だけ増減する操
作であるから、バレルシフト回路でのシフトは受けず、
その出力に接続され、加算制御信号ＡＣにより制御され
る加算回路２３でこの処理が行われる。

以上のように本実施例によれば、リストデータをノード
の位置を示すＡＤＤＲＥＳＳ部とデータ値へのリファレ
ンスを示すＶＡＬＵＥ部とで構成した表形式のデータと
して記憶するメモリ装置と、前記表形式データの要素を
記憶するレジスタ装置と、前記メモリ装置から転送され
るデータと前記レジスタ装置からのフィードバックされ
るデータとを選択して出力する入力選択回路と前記入力
選択回路から出力されたデータのＡＤＤＲＥＳＳ部デー
タを左右方向へシフトするバレルシフト回路と前記バレ
ルシフト回路の出力に接続されＡＤＤＲＥＳＳ部データ
の先頭値を１だけ増減する加算回路から構成されるシフ
ト装置とを設けることにより、表形式で表現されたリス
トデータのシフト処理を効率よく行うことが出来る。

発明の効果 以上のように本発明はりストデータをノードの位置を示
すＡＤＤＲＥＳＳ部とデータ値へのリファレンスを示す
ＶＡＬＵＥ部とで構成した表形式のデータとして記憶す
るメモリ装置と、前記表形式データの要素を記憶するレ
ジスタ装置と、前記メモリ装置から転送されるデータと
前記レジスタ装置からのフィードバックされるデータと
を選択して出力する入力選択回路と前記入力選択回路か
ら出力されたデータのＡＤＤＲＥＳＳ部データを左右方
向へシフトするバレルシフト回路と前記バレルシフト回
路の出力に接続されＡＤＤＲＥＳＳ部データの先頭値を
１だけ増減する加算回路から構成されるシフト装置とを
設けることにより、表形式で表現されたリストデータの
シフト処理を効率よく行うことが可能となる。

【図面の簡単な説明】

第１図は本発明の一実施例におけるデータ処理装置の構
成図、第２図は第１図のシフト装置の内部構成図、第３
図はリストデータの表形式表現の一例を示す図、第４図
はＬＩＳＰの基本リスト操作関数における裏操作の一例
を示す図である。 ｌ・・・・・・メモリ装置、２・・・・・・転送装置、
３・・・・・・シフト装置、４・・・・・・レジスタ装
置、２１・・・・・・入力選択回路、２２・・・・・・
バレルシフト装置、２３・・・・・・加算回路。 代理人の氏名　弁理士　中尾敏男　はか１名第３図 （Ａ（日（Ｃ））Ｄ） 第４図

Claims (1)

1. 【特許請求の範囲】 リストデータをノードの位置を示すＡＤＤＲＥＳＳ部と
   データ値へのリファレンスを示すＶＡＬＵＥ部とで構成
   した表形式のデータとして記憶するメモリ装置と、前記
   表形式データの要素を記憶するレジスタ装置と、前記メ
   モリ装置から転送されるデータと前記レジスタ装置から
   のフィードバックされるデータとを選択して出力する入
   力選択回路と前記入力選択回路から出力されたデータの ＡＤＤＲＥＳＳ部データを左右方向へシフトするバレル
   シフト回路と前記バレルシフト回路の出力に接続されＡ
   ＤＤＲＥＳＳ部データの先頭値を１だけ増減する加算回
   路から構成されるシフト装置とを具備し、表形式で表現
   されたリストデータのシフト処理を行うことを特徴とす
   るデータ処理装置。