(57)【特許請求の範囲】
【請求項１】
入力端と、出力端と、前記入力端および前記出力端との間に一次元的にならべられたＮ（Ｎ≧２）個のＫウェイソートプロセッサと、Ｎ−１番目のＫウェイソートプロセッサに第１の入力ポートが接続され、Ｎ番目のＫウェイソートプロセッサに出力ポートが接続されたストリングセレクタとを有するソート・マージ回路を多段に配置し、前記ソート・マージ回路のストリングセレクタの第２の入力ポートは、１段下のソート・マージ回路の出力端に接続されていることを特徴とするソート・マージ処理装置。
【請求項２】
ソート・マージ回路の入力端は入力レコード制御回路に接続されており、前記入力レコード制御回路は、ストリングセレクタの出力ポートに接続される入力ポートを切換える切換え制御信号を入力することを特徴とする請求項１に記載のソート・マージ処理装置。
【請求項３】
ソート・マージ回路の入力端は入力レコード制御回路に接続されており、前記入力レコード制御回路は、ソート要求が出された複数のレコードを分割して１段目から高段にむかって順次入力するとともに、レコード入力終了後に、ストリングセレクタの出力ポートとの接続を第１の入力ポートから第２の入力ポートに切換える切換え制御信号を入力することを特徴とする請求項１に記載のソート・マージ処理装置。
【請求項４】
ソート・マージ回路の出力端は出力レコード制御回路に接続されており、前記出力レコード制御回路は入力レコード制御回路からの情報に基づいて、前記ソート・マージ回路から出力される出力結果を選択することを特徴とする請求項２または請求項３に記載のソート・マージ処理装置。
【請求項５】
入力端と、出力端と、前記入力端および前記出力端との間に一次元的にならべられたＮ（Ｎ≧２）個のＫウェイソートプロセッサと、第１の入力ポート、第２の入力ポート及び出力ポートを有するストリングセレクタとを備え、
前記第１の入力ポートにはＮ−１番目のＫウェイソートプロセッサが接続され、前記出力ポートにはＮ番目のＫウェイソートプロセッサが接続され、前記第２の入力ポートにはソート済みデータを外部から入力することを特徴とするソート・マージ回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、大小比較によるレコードの並び替えを行なうソート・マージ処理装置に関するものである。
【０００２】
【従来の技術】
データベースの要素であるレコードは複数のフィールドから構成され、そのうちのあるフィールドをキーとして、レコードを昇順あるいは降順に並び替える処理をソートという。また、ソート済みレコード列（以下、「ストリング」と称す）が複数ある場合に、それらを一つのストリングに再編成する処理をマージという。
【０００３】
このソートおよびマージをソフトウェア的に行なった場合には、プロセッサとメモリ・ディスクなどの補助記憶装置との間で大量のレコードが行き来するので、大量の時間を要してしまう。そこで、このソートおよびマージをハードウェア的に行なうことで高速化することを可能にしたパイプラインマージソータ回路等が現在存在している。
【０００４】
図５は、「ＶＬＳＩソートプロセッサ」（情報処理、Ｖｏｌ．３１、Ｎｏ．４、１９９０年）に記載された、従来の２ウェイのソートプロセッサを使用した２ウェイでのパイプラインマージソータ回路の構成図である。
図５において、パイプラインマージソータ回路は、第１のソートプロセッサ１０００、第２のソートプロセッサ１００１、第３のソートプロセッサ１００２、第４のソートプロセッサ１００３とが一次元的に接続されており、また各ソートプロセッサには、第１のメモリ１０１０、第２のメモリ１０１１、第３のメモリ１０１２、第４のメモリ１０１３がそれぞれ接続されている。
【０００５】
ここで、一般的な２ウェイのパイプラインマージソータ回路では、ｎ個目のソートプロセッサがｎ−１個目のソートプロセッサからそれぞれ２n-1レコードからなる２本のストリングを入力し、マージして２nレコードからなる１本のストリングを出力するように構成されており、ｎ個目のソートプロセッサには２n-1レコードを記憶できるメモリが接続されることになる。なお、各ソートプロセッサには構成上の相違はなく、また、１つのストリングに含まれるレコードは、ストリングの最初のレコードの前、および最後のレコードの後ろに付加された識別子で判断されている。
【０００６】
次に、図５のパイプラインマージソータ回路にレコードが入力された具体的動作について、図６に記載された表の上段のレコードが入力された場合に基づいて説明する。
まず、第１のソートプロセッサ１０００には、１番目のレコードである１４が入力されてメモリ１０１０に記憶される。次に、２番目のレコードである９が入力され、メモリ１０１０に記憶された１４と比較されて小さい方から９・１４という様に出力し、２レコードからなるストリングとなる。同様に、３番目のレコードである１０と４番目のレコードである７とから７・１０というストリング、５番目のレコードである３と６番目のレコードである２とから２・３というストリングというように、奇数番目と偶数番目にあるレコードが比較され、２レコードからなるストリングが出力されて、次々に、第２のソートプロセッサ１００１に送られる。
【０００７】
第２のソートプロセッサ１００１では、第１のソートプロセッサ１０００から送られた１番目のストリングである９・１４が第２のメモリ１０１１に記憶される。次に、２番目のストリングである７・１０が入力されるが、ここで、まず、７と第２のメモリに記憶された９とが比較されて小さい方である７を出力し、次に、１０と９とが比較されて小さい方である９を出力し、次に、１０と第２のメモリに記憶された１４とが比較されて小さい方である１０を出力し、最後に１４を出力するという動作がなされ、４レコードからなるストリングである７・９・１０・１４が出力されることになる。以降も、奇数番目の２レコードからなるストリングと偶数番目の２レコードからなるストリングのレコードが比較され、４レコードからなるストリングが出力され、次々に第３のソートプロセッサ１００２に送られる。
【０００８】
第３のソートプロセッサ１００２では、１番目の４レコードからなるストリングを第３のメモリ１０１２に記憶し、次に送られてくる２番目の４レコードからなるストリングの各レコードと、第３のメモリ１０１２に記憶された各レコードとを比較して小さい方から出力し、８レコードからなるストリングとして出力して、第４のソートプロセッサ１００３に送られる。同様に、３番目の４レコードからなるストリングと４番目の４レコードからなるストリングから、８レコードからなるストリングとして出力される。
【０００９】
第４のソートプロセッサ１００３では、１番目の８レコードからなるストリングを第４のメモリ１０１３に記憶し、次に送られてくる２番目の８レコードからなるストリングの各レコードと、第４のメモリ１０１３に記憶された各レコードとを比較して小さい方を出力し、１６レコードが昇順に並べられて出力されることになる。
【００１０】
なお、図５では２ウェイのパイプラインマージソータ回路を示したが、４ウェイや８ウェイ等のパイプラインマージソータ回路も製作されている。ここで、Ｋウェイのパイプラインマージソータ回路では、ｎ段目のソートプロセッサがｎ−１段目のソートプロセッサからそれぞれＫn-1レコードからなるＫ本のストリングを入力し、マージしてＫnレコードからなる１本のストリングを出力することになり、ｎ段目のソートプロセッサには（Ｋ−１）・Ｋn-1レコードを記憶できるメモリを接続する必要がある。
【００１１】
【発明が解決しようとする課題】
しかし、上述のパイプラインマージソータ回路においては、ハードウェアの構成によってソート可能なレコード量の上限が決められてしまう。すなはち、Ｎ個のＫウェイソートプロセッサから構成されるＫウェイのパイプラインマージソータ回路の場合には、ソート可能なレコード量はＫnレコードである。従って、もしこの量を超えるレコードをソートしようとした場合には、元レコードをソートできる分量に分割してソートした後に、全出力をソフトウェア等でマージしなければならず、処理時間は極端に遅くなるという問題があった。また、逆に、大量のレコードを処理できるパイプラインマージソータ回路を作成するには、大量のソートプロセッサを並べる必要があり、また、特に後方に位置するソートプロセッサには膨大な容量のメモリを接続させなければならずコストや、ＬＳＩ自体の大きさから現実的ではない。さらに、入力されるレコード量も多い場合や少ない場合等さまざまであり、仮に最大のレコード量を想定して処理できるものであったとしても、少量のレコードでのソート処理は頻繁に発生する場合には、後方に位置するソートプロセッサは結局使用されず、無駄となってしまう。
【００１２】
なお、特開平７−６０２１号公報には、ソートするレコードと同じ数のモジュール回路をカスケード構成で接続し、各モジュール回路で一つ上位の段階のモジュール回路から流れてきたレコードと、そのモジュール回路に記憶されたそれまでの最大（又は最小）のレコードとを比較し、大きい方（又は小さい方）を一つ下の段階のモジュール回路に流すことによってソート処理の実行効率を高めようとするレコード並び換え装置が記載されている。
しかし、この構成では、モジュール回路の数以下のレコードしかソートすることができない。
【００１３】
この発明は、上述の課題を解決するためになされたものであり、Ｋウェイのソートプロセッサを複数有する構成からなる回路を任意に複数組み合わせることを可能にし、処理できるレコード量を柔軟に増減させることができ、さらに、ソートプロセッサを効率的に使用することができるソート・マージ処理装置およびソート・マージ回路を提供することを目的としている。
【００１４】
【課題を解決するための手段】
この発明にかかるソート・マージ処理装置においては、入力端と、出力端と、入力端および出力端との間に一次元的にならべられた複数のＫウェイソートプロセッサ（Ｋ≧２）とを有するソート・マージ回路を複数有し、ソート・マージ回路の少なくとも１つは、出力ポートがＫウェイソートプロセッサの１つに接続されており、少なくとも１つの入力ポートが他のソート・マージ回路の出力端に接続されているストリングセレクタを有し、ストリングセレクタは出力ポートに接続される入力ポートを切換えことができるものとした。
【００１５】
また、この発明にかかるソート・マージ処理装置においては、入力端と、出力端と、入力端および出力端との間に一次元的にならべられたＮ（Ｎ≧２）個のＫウェイソートプロセッサと、Ｎ−１番目のＫウェイソートプロセッサに第１の入力ポートが接続され、Ｎ番目のＫウェイソートプロセッサに出力ポートが接続されたストリングセレクタとを有するソート・マージ回路を多段に配置し、ソート・マージ回路のストリングセレクタの第２の入力ポートは、１段下のソート・マージ回路の出力端に接続されているものとした。
【００１６】
さらに、ソート・マージ回路の入力端は入力レコード制御回路に接続されており、入力レコード制御回路は、ストリングセレクタの出力ポートに接続される入力ポートを切換える切換え制御信号を入力するものとした。
【００１７】
さらに、ソート・マージ回路の入力端は入力レコード制御回路に接続されており、入力レコード制御回路は、ソート要求が出された複数のレコードを分割して１段目から高段にむかって順次入力するとともに、レコード入力終了後に、ストリングセレクタの出力ポートとの接続を第１の入力ポートから第２の入力ポートに切換える切換え制御信号を入力するものとした。
【００１８】
さらに、ソート・マージ回路の出力端は出力レコード制御回路に接続されており、出力レコード制御回路は入力レコード制御回路からの情報に基づいて、ソート・マージ回路から出力される出力結果を選択するものとした。
【００１９】
また、この発明にかかるソート・マージ回路は、入力端と、出力端と、入力端および出力端との間に一次元的にならべられたＮ個（Ｎ≧２）のＫウェイソートプロセッサ（Ｋ≧２）と、出力ポートおよび複数の入力ポートを有するストリングセレクタとを備え、ストリングセレクタの出力ポートはＮ番目のＫウェイソートプロセッサに接続され、入力ポートの少なくとも１つはＮ−１番目のＫウェイソートプロセッサに接続されているものとした。
【００２０】
【発明の実施の形態】
実施の形態１．
図１は、この発明の実施の形態１におけるソート・マージ回路を示す構成図である。図中、ソート・マージ回路は、第１のソートプロセッサ１と、第２のソートプロセッサ２と、第３のソートプロセッサ３と、ストリングセレクタ４と、第４のソートプロセッサ５とが一次元的に並べられて接続されており、さらに、第１のソートプロセッサ１にはソート・マージ回路への入力端６が接続され、第４のソートプロセッサ５には、ソート・マージ回路からの出力端７が接続されている。
【００２１】
また、各ソートプロセッサには、第１のメモリ１１、第２のメモリ１２、第３のメモリ１３、第４のメモリ１４がそれぞれに接続されている。なお、このソート・マージ回路は通常は１枚の基板上に作成されている。また、ストリングセレクタ４は、第１の入力ポート４１と、第２の入力ポート４２と、出力ポート４３とを有しており、第１の入力ポート４１には第３のソートプロセッサ３が接続され、出力ポート４３には第４のソートプロセッサ５が接続されている。
【００２２】
次に、ストリングセレクタ４の内部構成について説明する。
図２は、ストリングセレクタ４の構成図である。
第１の入力ポート４１および第２の入力ポート４２からの入力は、セレクタ５１に接続されており、セレクタ５１の切換えによって入力ポート４１または入力ポート４２のどちらかが出力ポート４３と接続されることになる。また、セレクタ５１の制御は、制御回路５２によって行なわれており、制御回路５２では入力ポート４１から入力される切換え制御信号に基づいて切換え指示を行なっている。
【００２３】
次に、図１のソート・マージ回路を並列に多段にして構成したソート・マージ処理装置について、図３の構成図に基づいて説明する。
図３において、ソート・マージ処理装置は、第１のソート・マージ回路１００と、第２のソート・マージ回路２００と、第３のソート・マージ回路３００と、各ソート・マージ回路に入力するレコードを制御する入力レコード制御回路４００と、各ソート・マージ回路から出力されるレコードを制御する出力レコード制御回路５００と、入力レコード制御回路４００と出力レコード制御回路５００とを接続して情報の伝達を可能とする接続路６００とから主に構成されている。
【００２４】
なお、図３において、第１のソート・マージ回路１００を構成する図１に記載したソートプロセッサ等の番号には、識別子として先頭に１または１０を付加し、第２のソート・マージ回路２００を構成する図１に記載したソートプロセッサ等の番号には、識別子として先頭に２または２０を付加し、第３のソート・マージ回路３００を構成する図１に記載したソートプロセッサ等の番号には、識別子として先頭に３または３０を付加している。
【００２５】
また、第１のソート・マージ回路１００の出力端１０７は、ケーブル等により第２のソート・マージ回路２００上のストリングセレクタ２０４の第２の入力ポート２４２に接続され、また、第２のソート・マージ回路２００の出力端２０７は、ケーブル等により第３のソート・マージ回路３００上のストリングセレクタ３０４の第２の入力ポート３４２に接続されている。
【００２６】
次に、このソート・マージ処理装置の動作について説明する。
なお、簡単のために、各ソートプロセッサは２ウェイのソートプロセッサであるとし、入力されるレコードは、図４（ａ）に記載された３２個のレコードからなるものとする。入力レコード制御回路４００では、入力されたレコードの数をカウントし、この３２個のレコードのうち、１番目から１６番目までの１６（＝２4）個のレコード、すなはち、４個のソートプロセッサで処理できる最大数のレコードを入力端１０６に入力し、１７番目から２４番目までの８（＝１×２3）個のレコードを入力端２０６に入力し、２５番目から最後の３２番目までの８（＝１×２3）個のレコードを入力端３０６に入力する。なお、入力端２０６及び入力端３０６のレコードの最後には、ストリング切換えを指示する切換え制御信号を付加している。
【００２７】
また、入力レコード制御回路４００は、各ソート・マージ回路への入力端へのレコードの入力と同時に、このソート処理では第３のソート・マージ回路までを使用することを接続路６００を介して出力レコード制御回路５００に通知する。
【００２８】
第１のソート・マージ回路１００では、まず、第１のソートプロセッサ１０１に、１番目のレコードである６が入力されてメモリ１１１に記憶される。次に、２番目のレコードである２１が入力され、メモリ１１１に記憶された６と比較されて小さい方から６・２１という様に出力し、２レコードからなるストリングとなる。同様に、３番目のレコードである１１と４番目のレコードである３２とから１１・３２というストリング、５番目のレコードである１と６番目のレコードである１９とから１・１９というストリングというように、奇数番目と偶数番目にあるレコードが比較され、２レコードからなるストリングが出力され、次々に、第２のソートプロセッサ１０２に送られる。
【００２９】
第２のソートプロセッサ１０２では、第１のソートプロセッサ１０１から送られた１番目のストリングである６・２１が第２のメモリ１１２に記憶される。次に、２番目のストリングである１１・３２が入力されるが、ここではまず、１１と第２のメモリに記憶された６とが比較されて小さい方である６を出力し、次に、第２のメモリに記憶された２１と１１とが比較されて小さい方である１１を出力し、次に、２１と３２が比較されて小さい方である２１を出力し、最後に３２を出力するという動作がなされ、４レコードからなるストリングである６・１１・２１・３２が出力されることになる。
【００３０】
以降も、奇数番目の２レコードからなるストリングと偶数番目の２レコードからなるストリングのレコードが比較され、４レコードからなるストリングが出力され、次々に第３のソートプロセッサ１０３に送られる。
【００３１】
第３のソートプロセッサ１０３では、１番目の４レコードからなるストリングを第３のメモリ１１３に記憶し、次に送られてくる２番目の４レコードからなるストリングの各レコードと、第３のメモリ１１３に記憶されたレコードとを比較して小さい方から出力し、８レコードからなるストリングとして出力して、ストリングセレクタ１０４に送る。なお、ストリングセレクタ１０４では、制御回路が、既定として入力ポート１４１を出力ポート１４３に接続させるようにセレクタ１５１を制御しているので、ストリングセレクタ１０４から第４のソートプロセッサ１０５にストリングは送られる。同様に、３番目の４レコードからなるストリングと４番目の４レコードからなるストリングとがマージされて８レコードのストリングが出力される。
【００３２】
第４のソートプロセッサ１０５では、１番目の８レコードからなるストリングを第４のメモリ１１４に記憶し、次に送られてくる２番目の８レコードからなるストリングの各レコードと、第４のメモリ１１４に記憶されたレコードとを比較して小さい方を出力し、１６レコードが昇順に並べられ、出力端１０７から出力される。なお、図４（ｂ）は、各ソートプロセッサから出力されるレコードを表わしている。
【００３３】
次に、第２のソート・マージ回路２００での動作について説明する。なお、図４（ｃ）は、各ソートプロセッサから出力されるレコードを表わしている。
まず、第１のソートプロセッサ２０１から第３のソートプロセッサ２０３までの処理により、入力された８個のレコードを昇順に並べたストリングが、ストリングセレクタ２０４を通過してソートプロセッサ２０５に送られ、メモリ２１４に記憶される。また、第３のソートプロセッサ２０４から出力されるストリングの最後には、切換え制御信号が付加されているので、ストリングセレクタ２０４の制御回路は、この切換え制御信号に従いセレクタを切換え、第二の入力ポート２４２と出力ポート２４３とを接続させる。
【００３４】
これにより、第１のソート・マージ回路１００で処理された後のレコードが出力端１０７および第２の入力ポート２４２を経由して、第４のソートプロセッサ２４３に送られ、メモリ２１４に記憶されたレコードとマージされることになる。
なお、第２のソート・マージ回路における第１のソートプロセッサから第３のソートプロセッサまでの処理は、第１のソート・マージ回路での処理と平行的に行なわれている。
【００３５】
第３のソート・マージ回路３００でも、第２のソート・マージ回路２００と同様の動作が行なわれ、最終的には、第３のソート・マージ回路３００の出力端３０７から、ソートされた３２個のレコードが昇順に出力されることになる。なお、図４（ｄ）は、各ソートプロセッサから出力されるレコードを表わしている。
【００３６】
出力レコード制御回路５００では、第１のソート・マージ回路１００の出力端１０７、第２のソート・マージ回路２００の出力端２０７、第３のソート・マージ回路３００の出力端３０７からレコードが出力されるが、接続路６００を通じて第３のソート・マージ回路までレコードを入力したとの情報がきているので、出力端１０７および出力端２０７からのレコードは消去し、出力端３０７からのレコードのみを選択してソート・マージ処理装置から出力する。
【００３７】
その後、出力レコード制御回路５００から、接続路６００を介して入力レコード制御回路４００にソート処理終了情報が伝達され、入力レコード制御回路４００では、ストリングセレクタ２０４の第一の入力ポート２４１と出力ポート２４３とを接続させる切換え制御信号を入力端２０６に流し、ストリングセレクタ３０４の第一の入力ポート３４１と出力ポート３４３とを接続させる切換え制御信号を入力端３０６に流す。
【００３８】
また、ここでは、３２個のレコードを入力させたが、例えば２４個の場合には、第１のソート・マージ回路１００と第２のソート・マージ回路２００のみ使用すれば十分であり、よって、入力レコード制御回路４００は、次にソート処理を要求されたレコード数が１６以下の場合には、第３のソート・マージ回路を使用して、並列的に処理する。
【００３９】
次に、各ソートプロセッサが８ウェイのソートプロセッサである場合についての動作を説明する。なお、ソート・マージ処理装置に入力されるレコードの数は１１２６４レコードとする。まず、入力レコード制御回路４００は、第１のソート・マージ回路の入力端１０６に１番目から４０９６番目までの４０９６（＝８4）個のレコード、すなはち、４個のソートプロセッサで処理できる最大数のレコードを入力し、第２のソート・マージ回路の入力端２０６には、４０９７番目から７６８０番目までの３５８４（＝７×８3）個のレコードを入力し、第３のソート・マージ回路の入力端３０６には、７６８１番目から１１２６４番目までの３５８４（＝７×８3）個のレコードを入力する。なお、入力端２０６へ入力するレコードの最後および入力端３０６へ入力するレコードの最後には、ストリングセレクタの切換え制御信号を付加している。
【００４０】
第一のソート・マージ回路１００では、４０９６個のレコードがソートされて出力端１０７から出力される。
平行して第２のソート・マージ回路２００では、第３のソートプロセッサ２０６からソートされて昇順に並んだ３５８４個のレコードがストリングセレクタ２０４を介して、第４のメモリ２１４に記憶される。
【００４１】
また、第３のソートプロセッサ２０３から出力されるレコードの最後に付加された切換え制御信号により、制御回路が第２の入力ポート２４２を出力ポート２４３に接続するので、第１のソート・マージ回路１００から出力されたソートされて昇順に並んだ４０９６個のレコードからなるストリングが第４のプロセッサ２０５に送られてマージされて昇順に並んだ７６８０個のレコードからなるストリングが出力される。
【００４２】
また、第３のソート・マージ回路３００でも、第３のソートプロセッサ３０３からソートされて昇順に並んだ３５８４個のレコードからなるストリングがストリングセレクタ３０４を介して、第４のメモリ３１４に記憶される。
【００４３】
第３のソートプロセッサ３０３から出力されるレコードの最後に付加された切換え制御信号により、制御回路が第２の入力ポート３４２を出力ポート３４３に接続するので、第２のソート・マージ回路２００から出力されたソートされて昇順に並んだ７６８０個のレコードのストリングが第４のプロセッサ３０５に送られてマージされて昇順に並んだ１１２６４個のレコードが出力される。
【００４４】
なお、ここではソート・マージ回路を３段の構成にしたが、特に３段である必要はなく、４段・５段でも当然によい。この場合には、入力レコード制御回路に４段・５段目に位置するソート・マージ回路にレコードを入力する機能を組み込む必要がある。
【００４５】
また、設計においては、入力レコード制御回路および出力レコード制御回路を、ソート・マージ回路を有する基板を接続させることができるソケットを複数本持たせた構成にし、必要に応じてソート・マージ回路を有する基板をソケットに差し込むようにすることが有効であろう。
【００４６】
なお、ここでは２ウェイおよび８ウェイについて説明したが、とくにこれに限定されることはなく４ウェアや１６ウェア、さらにそれ以上のソートプロセッサを使用してもよい。
また、１つのソート・マージ回路に組み込むソートプロセッサ数も特に４個である必要はなく、幾つでもよい。
【００４７】
なお、Ｋウェアのソートプロセッサを１からＮ−１番目まで並べ、ストリングセレクタを介してＮ番目のソートプロセッサを一次元的に配置したソート・マージ回路をＬ段に並べることによってソート可能な最大レコード数はＫn＋（Ｋ−１）×Ｋn-1×（Ｌ−１）個である。この場合、１段目のソート・マージ回路の入力端にはＫn個のレコードを入力させ、それ以外の入力端には（Ｋ−１）×Ｋn-1個のレコードを入力させることになる。
【００４８】
このような構成においては、１つのソート処理で必要とされるソートプロセッサを、ソート処理の要求があった毎に柔軟に割り当てることができソートプロセッサを効率よく使用できる。例えば、ソート処理するレコード数が少なく、設置された全てのソート・マージ回路を使用しない場合には、余りのソートマージ回路では別のソート処理を行なうことができる。
【００４９】
また、ソート・マージ回路は、同じ構成でよいので、量産が可能であり生産性が向上する。さらに、必要となるソート・マージ回路をソート・マージ処理装置に組み込むことでソート処理するレコードの最大数を変更できるので、ユーザのニーズに合った柔軟な対応が可能である。
【００５０】
さらにまた、例えば、８ウェイで１つのソート・マージ回路に４個のソートプロセッサを載せている場合には、ソート・マージ処理装置に設置するソート・マージ回路の数に関係なく、すなはち、最大処理可能なレコード量に関係なく、１つのソートプロセッサには３５８４レコードを記憶できるメモリを接続すればよい。
【００５１】
また、接続路６００を通じて第３のソート・マージ回路までレコードを入力したとの情報がきているので、出力端１０７および出力端２０７からのレコードは消去し、出力端３０７からのレコードのみを選択してソート・マージ処理装置から出力でき、誤った結果をソート・マージ処理装置の外部に出力することはなくなる。
【００５２】
実施の形態２．
実施の形態２は、実施の形態１において、入力レコード制御回路の動作が異なるものであり、装置の構成は図３と同じである。
各ソートプロセッサが２ウェイの場合、入力レコード制御回路は、入力されたソート要求レコードの数を入力端１０６から入力しながらカウントし、１７（＝２4＋１)個目のレコードを入力した時点で、入力端２０６にストリングセレクタの切換え制御信号を入力する。また、３３（＝２5＋１)個目となった時点で、入力端３０６に切換え制御信号を入力するように構成されている。
【００５３】
次に、この入力レコード制御回路を使用した場合の動作について、３２個のレコードをソートする場合について説明する。
まず、入力レコード制御回路は、ソート要求があるレコードを入力端１０６に入力していくとともに、内部のカウンタでその入力したレコードをカウントし、１７になった時点で、入力端２０６にストリングセレクタの切換え制御信号を入力する。これにより、ストリングセレクタが切換わり、ソートプロセッサ２０５は、ソート・マージ回路１００の出力端１０７に接続されることになり、ソートプロセッサ１０５で出力された１６個のストリング２つがソートプロセッサ２０５でマージされて、昇順にならべられたレコードが出力端２０７から出力されるようになる。
【００５４】
このような構成においては、１つのソート処理で必要とされるソートプロセッサを、ソート処理の要求があった毎に柔軟に割り当てることができソートプロセッサを効率よく使用できる。例えば、ソート処理するレコード数が少なく、設置された全てのソート・マージ回路を使用しない場合には、余りのソートマージ回路では別のソート処理を行なうことができる。
【００５５】
また、ソート・マージ回路は、同じ構成でよいので、量産が可能であり生産性が向上する。さらに、必要となるソート・マージ回路をソート・マージ処理装置に組み込むことでソート処理するレコードの最大数を変更できるので、ユーザのニーズに合った柔軟な対応が可能である。
【００５６】
なお、この構成では、ソート・マージ回路の最後に位置するソートプロセッサに接続されたメモリは、ソート要求されたレコードの数に応じて大きくせざるをえないが、ストリングセレクタを特に最後のソートプロセッサとその前のソートプロセッサ間に配置されている必要はなく、どの位置に配置することもできる。
【００５７】
【発明の効果】
この発明にかかるソート・マージ処理装置においては、入力端と、出力端と、入力端および出力端との間に一次元的にならべられた複数のＫウェイソートプロセッサ（Ｋ≧２）とを有するソート・マージ回路を複数有し、ソート・マージ回路の少なくとも１つは、出力ポートがＫウェイソートプロセッサの１つに接続されており、少なくとも１つの入力ポートが他のソート・マージ回路の出力端に接続されているストリングセレクタを有し、ストリングセレクタは出力ポートに接続される入力ポートを切換えことができるものとした。
【００５８】
これにより、１つのソート処理で必要とされるソートプロセッサを、ソート処理の要求があった毎に柔軟に割り当てることができソートプロセッサを効率よく使用できる。
【００５９】
また、この発明にかかるソート・マージ処理装置においては、入力端と、出力端と、入力端および出力端との間に一次元的にならべられたＮ（Ｎ≧２）個のＫウェイソートプロセッサと、Ｎ−１番目のＫウェイソートプロセッサに第１の入力ポートが接続され、Ｎ番目のＫウェイソートプロセッサに出力ポートが接続されたストリングセレクタとを有するソート・マージ回路を多段に配置し、ソート・マージ回路のストリングセレクタの第２の入力ポートは、１段下のソート・マージ回路の出力端に接続されているものとした。
【００６０】
さらに、ソート・マージ回路の入力端は入力レコード制御回路に接続されており、入力レコード制御回路は、ストリングセレクタの出力ポートに接続される入力ポートを切換える切換え制御信号を入力するものとした。
【００６１】
これにより、ソートプロセッサの量産が可能となり生産性が向上する。さらに、必要となるソート・マージ回路をソート・マージ処理装置に組み込むことでソート処理するレコードの最大数を変更できるので、ユーザのニーズに合った柔軟な対応が可能である。
【００６２】
さらに、ソート・マージ回路の入力端は入力レコード制御回路に接続されており、入力レコード制御回路は、ソート要求が出された複数のレコードを分割して１段目から高段にむかって順次入力するとともに、レコード入力終了後に、ストリングセレクタの出力ポートとの接続を第１の入力ポートから第２の入力ポートに切換える切換え制御信号を入力するものとした。
【００６３】
さらに、ソート・マージ回路の出力端は出力レコード制御回路に接続されており、出力レコード制御回路は入力レコード制御回路からの情報に基づいて、ソート・マージ回路から出力される出力結果を選択するものとした。
【００６４】
これにより、誤った結果をソート・マージ処理装置の外部に出力することはなくなる。
【００６５】
また、この発明にかかるソート・マージ回路は、入力端と、出力端と、入力端および出力端との間に一次元的にならべられたＮ個（Ｎ≧２）のＫウェイソートプロセッサ（Ｋ≧２）と、出力ポートおよび複数の入力ポートを有するストリングセレクタとを備え、ストリングセレクタの出力ポートはＮ番目のＫウェイソートプロセッサに接続され、入力ポートの少なくとも１つはＮ−１番目のＫウェイソートプロセッサに接続されているものとした。
【００６６】
これにより、１つのソート処理で必要とされるソートプロセッサを、ソート処理の要求があった毎に柔軟に割り当てることができソートプロセッサを効率よく使用できる。さらに、ソートプロセッサの量産が可能となり生産性が向上する。
【図面の簡単な説明】
【図１】  この発明の実施の形態１にかかるソート・マージ回路の構成図である。
【図２】  ソート・マージ回路を構成するストリングセレクタの構成図である。
【図３】  この発明の実施の形態１にかかるソート・マージ処理装置の構成図である。
【図４】  この発明の実施の形態１にかかるソート・マージ処理装置での出力を示す表である。
【図５】  従来のパイプラインマージソータ回路を示す構成図である。
【図６】  従来のパイプラインマージソータ回路での出力を示す表である。
【符号の簡単な説明】
１  第１のソートプロセッサ（Ｋウェイソートプロセッサ）、
２  第２のソートプロセッサ（Ｋウェイソートプロセッサ）、
３  第３のソートプロセッサ（Ｋウェイソートプロセッサ）、
４  ストリングセレクタ、
５  第４のソートプロセッサ（Ｋウェイソートプロセッサ）、
６  入力端、
７  出力端、
４１  第１の入力ポート、
４２  第２の入力ポート、
４３  出力ポート、
１００  第１のソート・マージ回路、
２００  第２のソート・マージ回路、
３００  第３のソート・マージ回路、
４００  入力レコード制御回路、
５００  出力レコード制御回路
【図１】
0004158264.tif 000002
【図２】
0004158264.tif 000003
【図３】
0004158264.tif 000004
【図４】
0004158264.tif 000005
【図５】
0004158264.tif 000006
【図６】
0004158264.tif 000007