JPS5839340A - 関係代数演算装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は関係データベースの演算処理に必要な可変長デ
ータのソート処理を高速度に効率良く実行できる関係代
数演算装置に関する。

ソート処理は物の集まシ、つまシデータを特定の順序で
並べ換えるプロセスであシ、データ処理における基本的
操作である・これ故、そのアルゴリズムに関しては古く
から研究がなされておシ、代表的なものに単純選択法、
単純交換法、ビープソート法、分割ソート法、そしてマ
ージソート法等が知られている。

ところで、このソート処理は上記アルプリズムを汎用計
算機にプログラムして行なわれることが多い。しかし、
このようなソフトウェアによるソート処理ではその処理
時間が長くなると云う問題がある。しかも現在の殆んど
の計算機は数値計算を高速度に実行することを目的とし
て設計されておシ、文献検索等の大容量データを扱う関
係モデルに対してはアーキテクチャの本質的な異なシが
ある為、上記関係モデルを扱うには不向きである。この
為、ソート処理実行プログラムが相当複雑化し、その処
理に膨大な時間會貴すことが否め碌い。このような理由
から、関係モデルにおける連想処理を行なえるプロセッ
サや上記アルゴリズムを専用に実行するソーティングマ
シンの開発が強く望まれている。

本発明はこのような事情を考慮してなされたもので、そ
の目的とするところは、大容量で可変長データを扱う関
係データベースを高速度に効率良くソート処理すること
のできる実用性の高い関係代数演算装置を提供すること
にある。

即ち本発明はＦＩＦＯ機能を持つ２つのメモリとこれら
のメモリに格納されたデータをソート処理するグロセ、
すによりて構成される処理エレメントを複数個縦続に結
合してパイグライン動作させ、マージソート法からなる
アルゴリズムに従ってソート処理を実行させると共に、
各処理エレメントに入力データ語長に応じて入力データ
を次段の処理エレメントに通過させる手段をそれぞれ設
けることによって、大容量で可変長表データに対しても
高速度に且つ効率曳くソート処理を実行し得るようにし
たものである。

先ずマージソート法アルゴリズムによるデータのソート
処理につき説明する。今、８個のデータ（３，５，７，
１，８，４，２，６）がｒ６Ｊｒ２Ｊ・・・の順序で与
えられるものとし、これらのデータを値の小さいものか
ら順に並べ換えると云うソート処理を実行するものとす
る。

この場合、上記データ列は、２つのデータを持つ４つの
組、即ち〜 （６，２）（４，８）（１７）（５，３）に区分し、先
ず各組毎にソート処理する。これによって （２，６）（４，８）（１，７）（３，５）なるデータ
の組を得る。しかるのち、これらの組を２つづつマージ
し、４つのデータを持つ２つの組を形成し、その組にお
いてデータをソートする。この結果 （２，４，６１８）（１，３，５，７）なるデータの組
を得る◇その後、これらの組をマージして、その組にお
けるデータをソートすることによシ （１，２，３，４，５，６，７，８） なるソート処理結果を得る。つま夛、データの組をマー
ジするに際して、そのデータを所定の規則に従ってソー
ト処理することによシ、段階的にソート処理結果を得る
ものである。

このようなマージソート法によれば、ｎ個のデータに対
してＬｏｇ２ｎステップでソート処理を完了することが
できる。然し乍ら、このソート処理を従来の計算機を用
いたソフトウェアで実行する場合、上述したアルゴリズ
ムから明らかなように、メモリへのデータの書込みと読
出しを非常に多く繰返えさなければならない。

そこで本発明では、基本的には第１図に示すように多段
に縦続接続され要処理エレメントＰ１１　＊　ＰＥ２　
ｔ　ＰＩ３によシ、上記処理ステツブをノ母イブライン
的に実行させることにより、その処理速度の高速化を図
っている。即ち、１段目の処理ニレメン）　ＰＫ、にて
ソート処理された組のデータを２段目の処理エレメント
ＰＫ２に供給し、上記処理エレメントＰＥ、が次のｆ−
夕についてソート処理を実行している期間に処理ニレメ
ン）　ＰＥ２で次の段階でのソート処理を実行させる。

そして同様に３段目の処理エレメントＰＥｊでも同時に
ソート処ｍを実行させることによシ、パイプライン的に
高速麩理を行なわしめている。

ところが、関係データベースのデータ長は固定的に与え
られるとは限られない。従りてこれに対処する為には、
各段の処理ニレメン）ＰＫがそれぞれ可変長データを扱
うことができるようにする等の工夫が必要となる。然し
、各段のグロセ、サヤメモリのビット長は実用上１６ピ
、トするいは３２ピ、ト程度と限られる為、結局その大
きさを制限せざるを得ない。

そこで本発明装置では次のようにして、可変長データの
取扱いを可能としている。

第２図および第３図は、それぞれ実施例を示すものであ
り、各段の処理エレメントＰＥは、ＦＩＦＯ（Ｆｌｒｍ
ｔ　Ｉｎ　）’１ｒｓｔ　Ｏｕｔ　）機能を有する２つ
のメモリＭＡ　、　ＭＢと、これらのメモリ風。

ＭＢに格納されたデータを比較してソート処理するグロ
セ、すＰとによシ構成される。そして、第２図に示され
るものは、各プロセ、すＰは与えられたデータが処理能
力以上のデータ長である場合、入力データをそのまま次
段の処理エレメントＰＩに通過させる手段を備えたこと
を特徴としている。また第３図に示すものは各段の処理
エレメ／）ＰＫの入力をパスラインＢを介して共通に接
続し、各プロセッサＰは、処理能力以上のデータの受入
れを禁止するべく構成されたことを特徴としている。従
ってこの場合、入力データのｒ、ト長が大きく処理エレ
メントＰＫに受は入れられない場合にはパスラインＢを
介してその処理エレメントＰＫをバイパスし、次段の処
理エレメントに入力されるようになっている◎ これら第２図および第３図に示されるいずれの構成にし
ろ、入力データはそのピット長に応じて、適合する処理
エレメントＰＫからソート処理されることになる。かく
してこのように各段の処理ニレメン）Ｋ入力データを通
過させる手段を設けることによシ、可変長データに十分
対処することが可能となる。即ち、これらの第２図およ
び第３図に示される装置は、基本的にはｌワードのｒ−
夕を扱う如く構成されておシ、１段目の処理エレメント
ＰＥ、には、１ワード長のメモリＭＡ　、　ＭＢが設け
られている。そして２段目の処理エレメントＰＥ２には
、２ワード長のメそすＭＡ　、　Ｍｌが、まｆＦ３段目
の処理ニレメン）　ＰＫ３には４ワード長のメモｖＢｆ
ｌＡ　、　ＭＢが設けられている。そして各プロセッサ
は、これらのメモリＭＡ　、　ＭＢに格納されたデータ
をそれぞれ１ワードずつ読出し、両者を比較している。

しかるに、このような装置に（１２，５６〜）等の２ワ
ードのデータが与えられたとすれば、轟然１段目のノロ
セ、すではその比較を行なうことができなくなる。しか
し、２段目の処理エレメントでは、２ワードのデータを
メモリ鬼。

ＭＢに格納できることから、１段目の処理ノロセ、すＰ
ＩＣ，を通過させ、２段目の処理プロセッサｐＨ，２か
らそのデータ比較を行なうようにすればよい。そして、
ｆｃＩセ、すＰでは、上記２ワードデータの上位桁よシ
１ワードずつデータ比較を行なうようにすれば、データ
の正しいソート処理を実行することが可能となる。

例えば上位ワードのデータを比較し、その大小関係に従
って２ワードデータをソート出力すればよい◎また上位
ワードで大小比較結果が得られない場合、つまシ両デー
タが等しい場合には、その下位ワードデータを同時に読
出して比較し、その大小関係に応じて前記上位ワードデ
ータを伴ってソート出力するようにすればよい・このよ
うにすれば、構成段位に応じて設定されたメモリのワー
ド数を有効に利用してワード長の多いデータを効果的に
ソート処理することが可能となる。従りて、各段の処理
エレメントＰＩＨのデータ比較能力に冗長を持たせる必
要がなく、効果的に可変長データに対処することが可能
となる。

第４図は、このような多ワードからなるデータが与えら
れたとき、そのデータ比較を行なう処理エレメントの構
成を示すもので、各設問様に構成される。

ＦＩＦＯ機能を有する２つのメモリ（Ｍｌｍ　Ａｌｌ、
り１．２はそれぞれ１ワードのメモリ構成を有し、それ
ぞれ書込みアドレスカウンタ（ＷＡＣ）　！　。

４の制御を受けて入力データを順次メモリアドレスに交
互に書込む・ｔ−ｉ格納したデータの読出しは、読出し
アドレスカウンタ（ＲＡＣ）　５　。

６によシ制御されてお）、またその読出しアドレスカウ
ント値はレジスタ（ＲＥＧ　）　Ｆ　、　Ｊにそれぞれ
ラッチされるようになっている。またプロセッサ（Ｐ）
９は、ＲＡＣｊ　、　＃の制御を受けてメモリ１，２か
ら同時に続出される１ワードのデータを比較し、その結
果に従りて前記アドレスカウンタ５，６を制御する如く
構成されている。そして、この比較結果に従りてデータ
を１ワードずつソート処理して出力するべく構成されて
いる。

今、このように構成されたプロセッサに、１ワード長か
らなるデータが与えられた場合、プロセッサ９は上記デ
ータ（１ワード）を比較し、定められたソート処理アル
がリズムに従って上記データをソート出力する。

しかるに、今、このような１ワード処理を実行する処理
エレメントに２ワード長からなるデータが（２３）（２
１）（２５）（２４）の順序で入力されたとすると、与
えられたデータワード長情報に従って１データ毎に交互
にメ篭す１，２に書込まれることになる。この場合、初
段の処理エレメントＰＫ、では、そのメモリＩＩＡ　、
　ＭＢが１ワードのデータ格納能力しかないから、２段
目の処理ニレメン）　ＰＥ、からデータが２ワードを１
単位としてそれぞれ書込まれることになる。

そしてソート処理は、先ずカウンタ５．ｌによるアドレ
ス「０」の指定を受け、メモリ１゜２からは２ワードデ
ータの上位ワードデータがそれぞれ読出されて、グ四セ
ッサ９に供給する。

グロセッサ９は両データを比較する。この場合、両デー
タが共に（２）であ多、等号が成立するので、グ四セッ
サＰはメモリ１より与えられたデータ（２）を次段へ送
出する。そして、プ四セ、す９は、カウンタ１．ｌの値
をそれぞれインクリメントシ、今度は両メモリ１．２か
らデータの下位ワードデータを読出し、それを比較する
。この場合、（３）と（１）のデータのうち（１）なる
データが小さいので、これを次段の処理エレメントに送
出する。そして、カウンタ５にはレジスタ１のデータを
セ、トシて、元のアＰレス値に復帰させると共に、カウ
ンタ６の値をインクリメントして、それをレジスタ８に
セットする。これによってデータ（２３）と（２１）と
の比較を終了する。次のステップでは、メモリ１の１番
目のデータと、メモリ２の２番目のデータとを同様に比
較し、ソート処理結果としてメモリ１のデータ（２３）
を出力する。以下同様にして２ワーＰを１単位とし、そ
の上位ワードデータよｐ１ワードずつ比較を行ない、ノ
ート処理を実行し、最終に残されたデータについては、
無限大あるいは（０）なる特定の極限値ｒ−夕と比較し
てそれを出力する。

第５図はそのソート処理のタイミングを模式的に示した
もめで、カウンタ５，６とレジスタｒ、８にセットされ
るメモリ１，２に対するアドレスデータの変化と、プロ
セ、すＰに読出される１ワードデータ、そしてソート処
理出力されるデータ列をそれぞれ示しているＱ この動作によりて示されるように、例え２ワードデータ
が与えられたとしても、データ読出しのアドレスを制御
して、その上位ワードデータよＪ）　ＪＩ［に１ワード
ずつｒ−夕比較を行なわしめることによシ、十分にその
ソート処理を実行することが可能となる。またここでは
２ワードデータが与えられた場合につき説明したが、３
ワ一−以上からなるデータに対しても同様に処理できる
ことは云うまでもない。

かくして本装置によれば、ソートエンシンを構成する縦
続接続された各段の処理エレメントのメモリの記憶容量
に冗長性を持たせることなしに、入力データのピット長
（ワード長）に応じてその収納能力のある処理エレメン
トから演算′ｔ−実行するようにし、また入力データの
ピット長に応じてその上位ビット（ワード）′ｆ′−タ
からデータ比較を行なうので、高速度に、且つ効率良く
可変長データのソー）Ｍ理を行なうことができる。しか
もその制御グ冒セスが簡単であ）、メ４９構成等に無駄
がないので実用的利点に優れている。故に関係データベ
ースを有効に取扱うことができる等の優れた効果を奏す
る〇尚、本発明は上記実施例に限定されるものではない
。例えばデータのピット長に関する情報を、入力ｒ−夕
の一部に付されたピット長（ワード長）情報から認識し
てもよく、関係データベースの種類に応じて操作者から
マユ。アルで与えるようにしてもよい。また、このよう
な可変長データに対処するｆ−夕通過の制御や、メモリ
のアドレス制御の方式も種々変形できることは云うまで
もない。また処理エレメントの構成段数も特に限定され
ない。要するに本発明はその要旨を逸脱しない範囲で種
々変形して実施することができる・

【図面の簡単な説明】

第１図は本発明装置のソート処理実行の形態を模式的に
示す図、第２図および第３図は本発明装置の基本的な構
成例を示す図、第４図は実施例における処理エレメント
の概略構成図、第５図は処理エレメントのソート処理プ
ロセスのタイ７ングを模式的に示す図である。 ＰＥ・−処理エレメント、凧、ｌ／Ｉｎ−・・メモリ、
Ｐプロセ、す、Ｂ・・・ノ童スライン、１，２・・・メ
４す、ｊ　、　４−・・書込みアドレスカウンタ、１．
６−・・読出しアドレスカウンタ、７，８−・レジスタ
、９・−・ゾロセ、す。 出願人代理人　屏理士　鈴　江　武　彦第１図 第２図 第３図

Claims (1)

【特許請求の範囲】
1. ＦＩＦＯ機能を持つ２つのメモリおよびこれらのメモリ
   に格納されたデータを比較して所定の規則に従った順序
   で出力するプロセッサによ多構成された複数の処理エレ
   メントを縦続に接続してなシ、各処理エレメントは入力
   データの語長に応じて上記入力データを次段の処理エレ
   メントへ通過させる手段を備えて、可変長データのソー
   ト処理を実行することを特徴とする関係代数演算装置。