JP2000322236A - ソート処理装置 - Google Patents

Abstract

(57)【要約】 【課題】 ソート処理におけるソートキー毎の昇降順指
定を可能としつつ、ソートプロセッサの内部処理は昇順
または降順ソートのみで可能なようにして、ソートプロ
セッサの内部構成を簡素化することを目的とする。 【解決手段】 入力データストリングを格納するデータ
記憶装置と、前記データストリングの連続する比較対象
データの大小関係を比較する比較器と、前記データ記憶
装置および前記比較器を制御する制御部を有するソート
プロセッサを複数台直列に接続して、各ソートプロセッ
サが並列に動作して、各々の比較器を用いて繰返し比較
処理を行うことで、複数のデータのソート処理を行うソ
ート処理装置において、前記比較器の比較機能と異なる
指定のキー値について、このキー値のビットを反転させ
て、初段のソートプロセッサに伝送するキー値変換部を
備えた。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、データベース処
理、ビジネスデータ処理等における、大量データの並べ
替え、所謂ソート処理を行なうソートプロセッサ及びソ
ート処理装置に関するものである。なお、この明細書に
おいては、部分的なソート処理を行なうプロセッサをソ
ートプロセッサと称し、ソートプロセッサ複数個を、直
列に接続して、完全なソート処理を行なう装置をソート
処理装置と称して、区別するものとする。

【０００２】

【従来の技術】図６は、例えば「情報処理」Ｖｏｌ．３
３、Ｎｏ．１２、Ｐ１４１６ー１４２３、１９９２に開
示されている従来のソート処理装置を備えた計算機シス
テムの構成を示す図である。図において、１はソート処
理装置、２はホスト計算機のシステムバス、３はホスト
計算機の主記憶装置、４はホスト計算機のＣＰＵ、５は
ホスト計算機上でデータを格納するディスク装置、６は
ホスト計算機である。

【０００３】以下、図を参照しながら動作について説明
する。先ず、概略の動作について説明する。ホスト計算
機６においてデータ処理の要求が発生すると、ホスト計
算機６のＣＰＵ４は対象データが格納されているディス
ク装置５からデータを連続的に取り出して、これをシス
テムバス２を経由して連続的にソート処理装置１に送
る。なお、このとき、必要に応じてホスト計算機１の主
記憶装置３が入出力バッファ領域として用いられる。ソ
ート処理装置１においては、データが入力されると、ソ
ート処理を行い、結果を再びシステムバス２を経由して
ホスト計算機６に送り返す。ホスト計算機６は送り返さ
れた結果データを入力時と同様にしてディスク装置５に
格納する。なお、ソート処理装置１に対するデータの入
力と、ソート処理装置１からの結果データの出力は並列
に実行される。

【０００４】次にソート処理装置１の動作の詳細につい
て説明する。ソート処理装置１はホスト計算機６から送
られてくるデータの列を連続的に入力して、これを指定
された順序に並べ替えて、結果を再びホスト計算機６に
返す。この様子を、同じく上記「情報処理」に開示され
ている図５を用いて説明する。図７は、図６におけるソ
ート処理装置１の構成を示す図で、ソート処理装置１
は、ソートプロセッサ１１、１２、１３、及び１４を線
形に接続して構成される。各ソートプロセッサ１１〜１
４には、各々データ記憶装置１５、１６、１７、及び１
８が接続されている。また、２１はホスト計算機６との
データのやりとり、処理の指示のやりとりを行うための
ホスト計算機インタフェースであり、１９はソート処理
装置１全体を制御する制御部である。ソートプロセッサ
１１〜１４は、各々先頭から第１段目のソートプロセッ
サ、第２段目のソートプロセッサ、第３段目のソートプ
ロセッサ等と呼ばれる。第ｉ段目のソートプロセッサ
は、２^i-1データ分の容量の記憶装置を各々有してい
る。

【０００５】ここでは、”８、２、１、３、５、７、
６、４、・・・”の順にデータがソート処理装置１に入
力される場合を例にして、動作を説明する。先ず、先頭
の第１段目のソートプロセッサ１１は、入力されたデー
タを２つずつ取り出し、これを指定の順序に並び替えて
次段のソートプロセッサに送り出す。次段のソートプロ
セッサに、２つずつにソートされて入力されるデータは
（８、２）、（３、１）、（７、５）、（６、４）、・
・・・となる。このように、第１段目のソートプロセッ
サ１１では、”１、３”の順序で入力されたデータは順
序が入れ代わり、（３、１）の順でソートされた２つの
データの組みとなって出力されている。このように、ソ
ートされたデータの組みをデータストリングまたはスト
リングと以降呼ぶことにする。第２段目のソートプロセ
ッサ１２は、この２つずつにソートされたデータストリ
ングを入力して、これを２組ずつ取り出し、併合して、
４つずつにソートされたデータストリングを次段のソー
トプロセッサ１３に送り出す。その結果は、（８、３、
２、１）、（７、６、５、４）、・・・・となる。この
ように、第２段目のソートプロセッサ１２では、入力デ
ータストリング（８、２）と（３、１）がソート処理さ
れた結果、併合されて出力データストリング（８、３、
２、１）となる。第３段目のソートプロセッサ１３は、
この４つずつにソートされたデータストリングを入力し
て、これを２組みずつ取り出し、併合して、８つずつに
ソートされたデータストリングを次段のソートプロセッ
サ１４に送り出す。この結果は、（８、７、６、５、
４、３、２、１）、・・・・となる。第４段目のソート
プロセッサ１４以降も同様な処理を行う。

【０００６】ところで、各段のソートプロセッサは、図
８に示すように、前段のソートプロセッサがすべての処
理を終えない内に処理を開始することが可能であり、こ
れにより、データを連続的に入力すると若干の遅れ時間
を経てデータ入力と並列にソート結果が出力されること
がわかる。このようにして、ｎ個のソートプロセッサに
より２ⁿ個のデータの並び替え、即ちソート処理が行わ
れる。なお、各ソートプロセッサは、これら比較併合処
理において、各々に接続されたデータ記憶装置１５、１
６、１７、１８を記憶領域として使用する。

【０００７】次に、図９に示す「情報処理」Ｖｏｌ．３
１、Ｎｏ．４、Ｐ４５７ー４６５、１９９０に開示され
ている従来のソートプロセッサの構成図を参照しなが
ら、ソートプロセッサ内部における動作について説明す
る。なお、この図９においては、説明を簡単にするため
図７におけるソートプロセッサ１２のみの内部について
を示しているが、他のソートプロセッサの内部も同様な
構成である。図９において、１２０はデータストリング
を比較する比較器、１２１、１２２は各々比較されるデ
ータの一部を一次的に格納するラッチレジスタ、１２
３、１２４は比較器１２０のデータ入力ポート、１２５
はソートプロセッサの動作を制御する制御部である。ラ
ッチレジスタ１２１、１２２は、比較器１２０の比較デ
ータサイズ及び比較器の入力ポート１２３、１２４のデ
ータ幅と等しいデータサイズを有している。以下の説明
では、この大きさは４バイトとする。１２６は前段のソ
ートプロセッサ１１からのデータを入力する入力バス、
１２７は次段のソートプロセッサ１３にデータを出力す
る出力バス、１２８は接続されているデータ記憶装置１
６とのデータをやりとりするアドレス及びデータバスで
ある。

【０００８】以下、ソートプロセッサ１２のソート処理
の詳細について説明する。ソートプロセッサ１２に対し
て、前段のソートプロセッサ１１からデータストリング
（８、２）、（３、１）、・・・が順次入力されると、
ソートプロセッサ１２はこれを併合してデータストリン
グ（８、３、２、１）、・・・として次段のソートプロ
セッサ１３に出力する場合を例にとって説明する。

【０００９】先ず、最初に入力されるデータストリング
（８、２）はそのままの順序を保ちながら、ソートプロ
セッサ１２に接続されたデータ記憶装置１６に格納され
る。次に、データストリング（３、１）のデータ「３」
がソートプロセッサ１２に入力され、同様にデータ記憶
装置１６に記憶される。続いて、最初のデータストリン
グ（８、２）の先頭データ「８」と、データストリング
（３、１）の先頭データ「３」が４バイトずつデータ記
憶装置１６からラッチレジスタ１２１、１２２にロード
されて、比較器１２０において比較が行われる。この比
較はデータを４バイト毎に順に比較することにより行わ
れる。

【００１０】なお、このソート処理において、ソートキ
ーに対する順序指定として昇順が指定されている場合に
は、比較結果はいずれか小さい方が先に出力される。ま
た、同様に順序指定として降順が指定されている場合に
は、比較結果はいずれか大きい方が先に出力される。こ
れらの昇順降順に対する制御は、データの先頭バイトか
ら始まるソートキーに対して、制御部１２５が制御を行
う。比較結果が確定すると、データは次のソートプロセ
ッサ１３に出力される。この比較処理と並行して、２番
めのデータストリング（３、１）中の次のデータ「１」
がデータ記憶装置１６に格納される。この例の場合に
は、比較の結果、データ「８」が次段のソートプロセッ
サ１３に出力される。このため、続く比較では、データ
「３」と、データストリング（８、２）の「８」に続く
データ「２」が比較される。比較は、同様にデータ記憶
装置１６から、データ「３」とデータ「２」を４バイト
ずつ各々ラッチレジスタ１２１、１２２に入力して、４
バイトずつ比較を行うことにより処理される。

【００１１】

【発明が解決しようとする課題】従来のソート処理装置
は、以上のように構成されていたので、ソート処理にお
いては、一般にレコード内部の複数のフィールドを組合
せて、これらのフィールド各々に昇順降順を独立に指定
して、その指定によってデータを並びかえることが必要
となる。このため、ソートプロセッサの制御装置では、
これら複数のキーフィールド各々に対して各々昇順、降
順の別を解釈し、それに応じた処理を行う必要があり、
ハードウェア論理が複雑になるという問題があった。

【００１２】この発明は、以上のような問題点を解消す
るためになされたもので、ソート処理におけるソートキ
ー毎の昇降順指定を可能としつつ、ソートプロセッサの
内部処理は昇順または降順ソートのみで可能なようにし
て、ソートプロセッサの内部構成を簡素化することを目
的とする。

【００１３】

【課題を解決するための手段】この発明に係わるソート
プロセッサは、入力データストリングを格納するデータ
記憶装置と、前記データストリングの連続する比較対象
データの大小関係を比較する比較器と、前記データ記憶
装置および前記比較器を制御する制御部を有するソート
プロセッサを複数台直列に接続して、各ソートプロセッ
サが並列に動作して、各々の比較器を用いて繰返し比較
処理を行うことで、複数のデータのソート処理を行うソ
ート処理装置において、前記比較器の比較機能と異なる
指定のキー値について、このキー値のビットを反転させ
て、初段のソートプロセッサに伝送するキー値変換部を
備えるようにしたものである。

【００１４】また、前記比較器が比較するデータの大き
いほうを取り出すように構成されているときには、前記
キー値変換部は、降順指定のキー値のビットを反転させ
るようにしたものである。

【００１５】また、前記比較器が比較するデータの小さ
いほうを取り出すように構成されているときには、前記
キー値変換部は、昇順指定のキー値のビットを反転させ
るようにしたものである。

【００１６】

【発明の実施の形態】この実施の形態においては、一度
に比較するデータ数をＫ＝４、比較するデータ幅を４バ
イトとした場合について説明する。図１は、この発明に
よるソートプロセッサとソートプロセッサ間の接続関係
を示す図である。図において、１１、１２、１３はソー
トプロセッサ、１５、１６、１７は、ソート処理するデ
ータストリングを格納する各ソートプロセッサが有する
データ記憶装置である。各ソートプロセッサ１１〜１３
は、データのソートキー（以降、キー値と称す）を格納
する４個のキー格納領域１３０〜１３９、ラッチレジス
タ１４０、比較器１３０およびソートプロセッサ全体を
制御する制御部１２５から構成されている。なお、比較
器１３０は、特別の回路構成を採らずに２入力の比較器
を複数組み合わせることにより実現できる。また、ラッ
チレジスタ１４０は、一般的なレジスタで構成するよう
にしてもよい。

【００１７】また、１２６は前段のソートプロセッサ１
１からのデータを入力する入力バス、１２７は次段のソ
ートプロセッサ１３にデータを出力する出力バス、１２
８は接続されているデータ記憶装置１６とのデータをや
りとりするアドレス及びデータバスである。１３６〜１
４０は比較器１３０の入力ポートである。なお、ラッチ
レジスタ１４０は、比較器１３０で一度に比較するビッ
ト幅のレジスタであり、キー値格納部１３１〜１３４
は、データのキー値部分全てを格納できる容量を有する
レジスタファイルやメモリ素子等で構成されている。ま
た、キー値格納部１３１、１３２、１３３、１３４を便
宜上、各々１番目、２番目、３番目、４番目のキー値格
納部と称することにする。

【００１８】最初に、上記のように構成されたソートプ
ロセッサのソート処理における概略の動作について説明
する。 （１）ソートプロセッサの制御部１２５は、比較される
個々のデータのキー値を対応するキー値格納部（１３１
〜１３４）に格納する。 （２）比較の結果、一つのデータが出力された場合、次
にデータ記憶装置１６から入力するデータのキー値を、
例えば４バイト単位にラッチレジスタ１３５に入力し
て、比較を行い、同時に、空いているキー値格納部にも
同じデータを順次入力する。 （３）各ソートプロセッサで繰返し実行される比較処理
の最初の比較処理の開始において、比較対象となる４個
のデータの内の３個のデータのキー値各々を４個のキー
値格納部（１３１〜１３４）の内の３個のキー値格納部
（１３１〜１３３）に格納して、ソートプロセッサ内の
制御部は比較対象としてこれら３個のキー値格納部（１
３１〜１３３）に対応する入力ポート（１３６〜１３
８）と、ラッチレジスタ１３５に接続されている入力ポ
ート１４０を選択して、４個目のデータのキー値の先頭
部分がラッチレジスタ１３５に格納されると同時に比較
処理を開始する。並行して４個目のデータのキー値は、
４番目のキー値格納部１３４に格納する。 （４）各ソートプロセッサで繰返し実行される比較処理
の最初ではない比較処理においては、比較器１３０によ
る４個のデータのキー値の比較の結果、最も小さいデー
タ（昇順ソートの場合）を判定して、これを出力し、次
の比較において、出力されたデータにかわる次のデータ
のキー値をラッチレジスタ１３５に入力して、比較を開
始すると共に、並行して、出力されたデータのキー値が
格納されていたキー値格納部にこのデータのキー値を格
納することにより昇順のソートを行う。 （５）降順ソートの場合においては、比較の結果、最も
大きいデータを判定し、これを出力することにより、降
順のソートを実現する。 （６）ラッチレジスタ１３５に入力されて比較が行わ
れ、かつキー値格納部に同時に格納されているデータ
が、昇順または降順比較の結果選択され、出力された場
合、このデータにかわる次のデータに対しては、同様に
そのキー値の先頭をラッチレジスタ１３５に入力し、比
較を開始すると共に、並行して、出力されたデータのキ
ー値が格納されていたキー値格納部にこのデータのキー
値を入力し、このデータが比較の結果、選択されず、出
力されなかった場合には、このデータに代わって出力さ
れたデータにかわる次のデータのキー値をラッチレジス
タ１３５に格納して、比較を開始すると共に、並行し
て、出力されたデータのキー値が格納されていたキー値
格納部にこのデータのキー値を格納する。 （７）出力されていったデータにかわるデータがなくな
った場合、制御部１２５は、このデータのキー値が格納
されていたキー値格納部に対応する比較器１３０の入力
ポートをその後選択せず、その後の比較において比較対
象としないように制御する。

【００１９】図２は、この発明によるソートプロセッサ
を用いて構成されたソート処理装置を示す図で、ソート
処理装置１は、ソートプロセッサ１１〜１４、各ソート
プロセッサ用のデータ記憶装置１５から１８、ホスト計
算機とのデータのやりとり、処理の指示のやりとりを行
うためのホスト計算機とのインタフェース部２１、デー
タのキー部の値を変換するキー変換部２０およびソート
処理装置１全体の制御を行なうソート処理装置制御部１
９から構成されている。キー変換部２０は、先頭のソー
トプロセッサ１１に接続して構成されている。以下、図
を参照しながら、この実施の形態における動作について
説明するが、ホスト計算機からデータをソート処理装置
１に入力し、ソート処理装置１がこれをソートしてホス
ト計算機に返す部分は同一であり、説明を省略する。

【００２０】先ず、図２を参照しながら、この発明によ
るキー変換部２０について説明する。図２は、従来例で
説明した図６と類似した構成であるが、各ソートプロセ
ッサに付加されたデータ記憶装置１５、１６、１７、１
８の容量及び各ソートプロセッサの内部構成が異なって
いる。ソート処理装置１はホスト計算機から送られてく
るデータの列を連続的に入力して、これを指定された順
序に並べ替えて、結果を再びホスト計算機に返す。ソー
ト処理装置は、ソートプロセッサ群１１、１２、１３、
１４及びこれらソートプロセッサ群に各々付加されるデ
ータ記憶装置群１５、１６、１７、１８を線形に接続
し、更に先頭のソートプロセッサ１１の前にキー変換装
置２０を接続して構成される。

【００２１】ソート処理においては、データ中のキー値
を基にして、データの並べ変えを行なう。例えば、ソー
ト対象のデータの形式が以下のようになっていたとし
て、ソートプロセッサは降順ソートのみが可能である場
合について説明する。 ・データ形式：キー１＋キー２＋キー３＋非キーデータ ここで、キー１とキー３とは昇順指定で、キー２は降順
とする。制御部１９は、キー１からキー３までに関し
て、昇順か、降順かの指定をホスト計算機から受取り、
これを解釈して、キー変換部２０に対して、入力される
各データに対して、そのキー１とキー３に関しては、そ
のビットを反転して最初のソートプロセッサ１１にデー
タを送り出すように制御する。これによって、ソートプ
ロセッサは降順ソートのみの機能しか持っていなくて
も、例に示すような昇順と降順とが混じった複数のキー
に対するソートを実現することができる。

【００２２】以下に、具体例を示して説明する。例え
ば、２つのデータのキー１が”２”と”４”であった場
合、これらの２進数表記は”００１０”と”０１００”
であり、これらを昇順ソートすると、”２”、”４”の
順で出力することが必要である。一方、これらをビット
反転すると，１１０１”、”１０１１”であり、これら
は各々１０進数”１３”、”１１”である。従ってこれ
らを降順ソートしても同様な順序が得られる。同様に、
ソートプロセッサが昇順ソートのみの機能しか持ってい
ない場合には、この例では、キー２に対してビット反転
を行うように、制御部１９がキー変換部２０に対して指
示を行なうようにすればよい。

【００２３】次にソートプロセッサの動作について具体
的な例を用いて説明する。ソートプロセッサは、各々先
頭から第１段目のソートプロセッサ（Ｐ₁）、第２段目
のソートプロセッサ（Ｐ₂）、第３段目のソートプロセ
ッサ（Ｐ₃）等と呼ばれる。第ｉ段目のソートプロセッ
サは、(Ｋー１)Ｋ^i-1データ分の容量のデータ記憶装置
を各々有している。以下Ｋ＝４として動作の説明を行
う。動作の例として、ソート処理装置１に８、２、１、
３、５、７、６、４、９、０、８、５、１、１０、３、
４、・・・の順にデータが入力されると、まず先頭の第
１段目のソートプロセッサ１１は入力されたデータを４
つずつ取り出し、これを並び替えて次段のソートプロセ
ッサ１２に送り出す。

【００２４】なお、ここで、データ「８」、「２」、
「１」・・・は、１０進数の数字を意味するものではな
く、各々キー値とデータ本体部で構成されたデータ（但
し、キー値のみで構成される場合もある）であり、単に
データとしての大きさを表すものである。次段のソート
プロセッサ１２に４つずつにソートされて入力されるデ
ータは（８、３、２、１）、（７、６、５、４）、
（９、８、５、０）、（１０、４、３、１）、・・・・
となる。

【００２５】２段目のソートプロセッサ１２は、この４
つずつソートされたデータを入力して、これを４組ずつ
取り出し、併合して、１６ずつソートされたデータ列を
次段のソートプロセッサ１３に送り出す。その結果は
（１０、９、８、８、７、６、５、５、４、４、３、
３、２、１、１、０）、・・・となる。第３段目のソー
トプロセッサ１３以降も同様な処理を行う。この様子を
図３に示す。従来技術と同様に、図３に示すように、各
段のソートプロセッサは、前段のソートプロセッサがす
べての処理を終えない内に処理を開始することが可能で
あり、これにより、データを連続的に入力すると若干の
遅れ時間を経てデータの入力と並列にソート結果が出力
されることがわかる。

【００２６】このようにして、ｎ個のソートプロセッサ
によりＫⁿ個のデータの並び替え、即ちソート処理が行
われる。別の言い方をすると、Ｎ個のデータのソート
は、ｌｏｇ_KＮ個のソートプロセッサにより実現され
る。例えば２²⁰＝４¹⁰＝１００万個のデータのソートに
は、従来の２個のデータ比較による方式では、ソートプ
ロセッサは２０個必要であったが、Ｋ＝４とした本方式
ではソートプロセッサは１０個で済むことがわかる。な
お、各ソートプロセッサは、これら比較併合処理におい
て、各々に接続されたデータ記憶装置１５、１６、１
７、１８を記憶領域として使用する。

【００２７】次に、ソートプロセッサの内部動作につい
て、図１を参照しながら説明する。ソートプロセッサ１
２に対して、前段のソートプロセッサ１１からデータス
トリング（８、３、２、１）、（７、６、５、４）、
（９、８、５、０）、（１０、４、３、1）・・・が入
力され、ソートプロセッサ１２において、これが併合さ
れてデータストリング（１０、９、８、８、７、６、
５、５、４、４、３、３、２、１、１、０）、・・・と
して次段のソートプロセッサ１３に出力される場合を例
にとって説明する。

【００２８】まず、入力バス１２６からソートプロセッ
サ１２に入力されるてくるデータストリング（８、３、
２、１）、（７、６、５、４）、（９、８、５、０）
は、そのままの順序を保ちながら、ソートプロセッサ１
２に接続されたデータ記憶装置１６に格納される。この
とき、データ記憶装置１６へのデータの格納と平行し
て、データストリング（８、３、２、１）の先頭のデー
タ「８」、データストリング（７、６、５、４）の先頭
データ「７」、データストリング、（９、８、５、０）
の先頭データ「９」のキー値の部分が各々１番目、２番
目３番目のキー値格納部１３１、１３２、１３３に格納
される。この時点では、４個あるキー値格納部の内、４
番目のキー値格納部１３４は、まだ空きの状態である。
ここには、後に、４番目のデータストリング（１０、
４、３、１）のデータのキー値が格納される。即ち、 ・１番目のキー値格納部：１番目のデータストリングの
キー値 ・２番目のキー値格納部：２番目のデータストリングの
キー値 ・３番目のキー値格納部：３番目のデータストリングの
キー値 ・４番目のキー値格納部：４番目のデータストリングの
キー値 のように対応が決められ、固定される。以上の動作は制
御部１２５により制御される。

【００２９】次に、制御部１２５は、比較器１３０及び
そのデータ入力ポート１３６、１３７、１３８、１３
９、１４０の内、キー値が格納されているキー値格納部
の最初のＫー１個に相当する１番目、２番目および３番
目のキー値格納部１３６、１３７、１３８と、ラッチレ
ジスタ１３５に接続されたデータ入力ポート１４０から
入力されるデータ（キー値）を比較器１３０により比較
するように設定を行う。続いて、残っていた４番目のデ
ータストリング（１０、４、３、１）が前段のソートプ
ロセッサ１１から順に入力バス１２６に入力される。ソ
ートプロセッサ１２は、まずその先頭のデータ「１０」
のキー値４バイトづつ順にラッチレジスタ１３５に格納
し、比較を４バイトずつ行う。同時に、入力されるデー
タのキー値の部分は空いているキー値格納部１３４へ格
納する。

【００３０】少し補足を加えると、ラッチレジスタ１３
５にデータ「１０」のキー値の最初の４バイトが格納さ
れると同時比較器１３０での比較が開始され、この例の
場合には、データ「１０」が最も大きいので、データ
「１０」のキー値が４バイトずつ順番にラッチレジスタ
１３５に格納されていくことになる。また、データ「１
０」を他のデータストリングと同様にデータ記憶装置１
６に格納するようにしてもよい。

【００３１】比較器１３０においては、「８」、
「７」、「９」、「１０」が比較される。その結果、最
も大きいデータ「１０」が出力される。この例のよう
に、ラッチレジスタ１３５に入力されているデータがそ
のまま比較の結果次段に出力される場合には、まず、こ
のデータのキー部が比較器１３０から出力され、そのま
まデータ出力バス１２７を通じて次段のソートプロセッ
サ１３に出力される。続いて、このデータにキーでない
データ部分がある場合には、データ入力バス１２６から
入力されてくるこのデータの非キー値データの部分をそ
のままデータ出力バス１２７を通じて出力する。これら
の制御は制御部１２５によって行われる。

【００３２】続いて、４番目のデータストリングのデー
タ「１０」に続くデータ「４」が入力バス１２６から入
力されてくる。このデータは、データ「１０」の場合と
同様に、ラッチレジスタ１３５に４バイトづつ入力さ
れ、キー値格納部１３１、１３２、１３３中のデータ
「８」、「７」、「９」と４バイトずつ比較される。ま
た、ラッチレジスタ１３５への入力と同時に、このデー
タ「４」のキー値は空きとなっているキー値格納部１３
４に格納される。この比較においては、ラッチレジスタ
１３５に入力されてくるデータ「４」ではなく、キー値
格納部１３３に格納されているデータ「９」が比較の結
果出力される。従って、この場合には、まずこのデータ
「９」のキー値の部分が比較器１３０からデータ出力バ
ス１２７を経由して次段のソートプロセッサ１３に出力
される。続いて、このデータ「９」のキーでないデータ
部分がある場合には、データ記憶装置１６からこのデー
タ「９」の非キー値部分を読みだし、データ出力バス１
２７を経由してこれらを次段のソートプロセッサ１３に
出力する。また、キー値の比較が完了したときに、デー
タ「４」においてキー値に続くキーでないデータ部分が
ある場合には、データ入力バス１２６により前段のソー
トプロセッサ１１から送られてくるこれらデータ部分
は、データ記憶装置１６に送られて記憶される。

【００３３】この段階において、先程は空き（次段のソ
ートプロセッサに出力済みで不要のデータの残ってい
る）となっていたキー値格納部１３４には、データ
「４」のキー値が格納されており、一方、先程「９」の
キー値が格納されていたキー値格納部１３３が空きとな
っている。従って、制御部１２５は、比較器１３０に対
して、そのデータ入力ポート１３６、１３７、１３９、
１４０からのデータの比較するように設定を行う。設定
が終了すると、比較器１３０に接続されているラッチレ
ジスタ１３５には、データ記憶装置１６から、データス
トリング（９、８、５、０）のデータ「９」に続くデー
タ「８」のキー値が４バイトずつ読み出されて格納され
て、他のキー値格納部１３１、１３２、１３４にそれぞ
れ格納されているデータ「８」、「７」、「４」と比較
器１３０において４バイトずつ比較される。この比較動
作は、データ「８」のキー値の最初の４バイトがラッチ
レジスタ１３５に格納されると同時に始まる。データ
「８」のキー値のラッチレジスタ１３５への格納と同時
に空いているキー値格納部１３３に同じものが格納され
て行く。さらに、同時にデータ入力バス１２６により前
段のソートプロセッサ１１から送られてくる（１０、
４、３、１）中の「４」に続くデータ「３」をデータ記
憶装置１６に格納する。

【００３４】図４は、以上説明したソート処理におけ
る、データの流れを図示化したものである。図におい
て、１０_Kはデータ「１０」のキー値を示し、１０_Kー
１、１０_Kー２は各々データ「１０」のキー値の最初の
４バイト、次の４バイトを示している。 また、この図
の例では、キー値が８バイト（４バイト＊２）の場合を
示している。

【００３５】なお、上記の説明において、データ「９」
が出力された後に、データ「８」のキー値部分をデータ
記憶装置１６から読み出して、キー値格納部１３３に、
また、キー値を４バイトずつ順番にラッチレジスタに格
納するように説明したが、この動作は、図１に示したソ
ートプロセッサの構成においては、制御部１２５がキー
値格納部に接続されているバスを時分割に使用して行な
う。また、データ記憶装置１６と、キー値格納部１３１
〜１３４およびラッチレジスタ１３５と、を別のバスで
接続するようにしてもよい。

【００３６】以上の動作を繰り返して行くことによりソ
ート処理が完了する。ここで、ソート処理が完了に近づ
くと、４本あるデータストリングのデータがなくなって
行く。例えば、この例の場合には、データストリング
（８、３、２、１）、（７、６、５、４）、（９、８、
５、０）、（１０、４、３、１）・・・・が入力され、
ソートプロセッサ１２はこれを併合してデータストリン
グ（１０、９、８、８、７、６、５、５、４、４、３、
３、２、１、１、０）、・・・を出力するが、出力にお
いて、２つのデータ「４」が出力されてしまうと、２本
目のデータストリング（７、６、５、４）のデータは、
このソートプロセッサ１２からはなくなる。このような
データストリングに対しては、対応するキー値格納部か
らのデータを比較対象としないように制御部１２５が比
較器１３０を制御する。

【００３７】次に、データ記憶装置１５〜１８の構成に
ついて説明する。データ記憶装置１５〜１８は、通常Ｄ
ＲＡＭにより構成される。例えば、１００万件、６４Ｍ
Ｂのデータのソート処理を行なうことを考えると、従来
技術と本発明では図４に示すような差異が生じる。図５
は、一度に比較するデータを変化させたときのデータ記
憶装置と必要なＤＲＡＭの数量の比較を示す図である。
このように、従来技術に比較して、本発明は、ハードウ
ェア量の減少が可能であるが、更に、比較器で一度に比
較する個数ＫをＤＲＡＭの容量、例えば、容量１６Ｍｂ
ｉｔ、８ビット幅のＤＲＡＭ４つでの最小単位が８ＭＢ
であることに注目し、これの約数（この場合には４）を
選んで実現することで、ＤＲＡＭの個数が少なくなるハ
ードウェア実装が可能であることがわかる。

【００３８】以上のように、この実施の形態によれば、
ＬＳＩのピン数制限のために生じるソートプロセッサの
ＬＳＩ化の実装問題を解決することができる。また、Ｌ
ＳＩ化の実装問題を解決することにより、ソート処理装
置で必要とするソートプロセッサの数を減少させ、以っ
てソート処理装置のハードウェア規模を小さくし、一定
データ量をソートするソート処理装置を小型化すること
が可能となる。また、このようなソート処理装置内部で
用いられるデータ記憶装置のＤＲＡＭの個数を減少さ
せ、ソート処理装置を小型化することを可能とする。ま
た、ソートプロセッサを本発明による構成にしても、ソ
ートプロセッサのデータ記憶装置へのアクセス回数増加
による性能低下が発生しない。また、ソート処理装置に
対し入力されるデータが複数のソートキーを有し、それ
らソートキー各々に対して昇順降順のソート指定が独立
に指定されている場合にも、ソートプロセッサは単一の
キーに対して降順または昇順のソートのみ行えばよく、
ソートプロセッサのハードウェアを簡素化することがで
きる。

【００３９】

【発明の効果】以上のように、この発明によれば、キー
値データを反転させるキー値変換部を設けるようにした
ので、ソートプロセッサの有する比較器には比較するデ
ータのうち、最も大きいデータまたは最も小さいデータ
を選択する機能だけせれば良い。

【図面の簡単な説明】

【図１】 この発明による、ソートプロセッサの一実施
の形態を示す図である。

【図２】 この発明による、ソートプロセッサを用いて
構成したソート処理装置の構成を示す図である。

【図３】 ソート処理装置によるソートの様子を示す図
である。

【図４】 ソートプロセッサのソート処理におけるデー
タの流れを示す図である。

【図５】 一度に比較するデータを変化させたときのデ
ータ記憶装置と必要なＤＲＡＭの数量の比較を示す図で
ある。

【図６】 従来のソート処理装置のがホスト計算機との
接続形態を示す図である。

【図７】 従来のソート処理装置の構成を示す図であ
る。

【図８】 従来のソート処理装置によるデータのソート
の様子を示す図である。

【図９】 従来のソート処理装置内部で用いられている
ソートプロセッサを示す図である。

【図１０】 従来のソートプロセッサにおいて、一度に
比較するデータの数を２から２より大きい数に増加させ
た場合に発生する性能低下を説明するための図である。

【符号の説明】

１１、１２、１３、１４ ソートプロセッサ、１５、１
６、１７、１８ データ記憶装置、１９ ソート処理装
置の制御部、２０ キー変換装置、１２５ ソートプロ
セッサ内部の制御部、１３０ 比較器、１３１、１３
２、１３３、１３４ キー値格納部、１３５ ラッチレ
ジスタ、１３６、１３７、１３８、１３９１４０ 入力
ポート。

Claims (3)

【特許請求の範囲】
1. 【請求項１】 入力データストリングを格納するデータ
   記憶装置と、前記データストリングの連続する比較対象
   データの大小関係を比較する比較器と、前記データ記憶
   装置および前記比較器を制御する制御部を有するソート
   プロセッサを複数台直列に接続して、各ソートプロセッ
   サが並列に動作して、各々の比較器を用いて繰返し比較
   処理を行うことで、複数のデータのソート処理を行うソ
   ート処理装置において、前記比較器の比較機能と異なる
   指定のキー値について、このキー値のビットを反転させ
   て、初段のソートプロセッサに伝送するキー値変換部を
   備えたことを特徴とするソート処理装置。
2. 【請求項２】 前記比較器が比較するデータの大きいほ
   うを取り出すように構成されているときには、前記キー
   値変換部は、降順指定のキー値のビットを反転させるこ
   とを特徴とする請求項１に記載のソート処理装置。
3. 【請求項３】 前記比較器が比較するデータの小さいほ
   うを取り出すように構成されているときには、前記キー
   値変換部は、昇順指定のキー値のビットを反転させるこ
   とを特徴とする請求項１に記載のソート処理装置。