JPH09231053A - 並列ソート装置 - Google Patents

Abstract

(57)【要約】 【課題】 対象データが全て主記憶に納まらない外部ソ
ートをマルチプロセスで並列実行する際に、ソート済み
ストリングの二次記憶からの読み出し量を各並列処理単
位で均等にすることで、並列処理時間を短縮する。 【解決手段】 並列処理プロセスに固有のソートマージ
用主記憶領域３１，３２で、ソート処理を行い、結果を
共有のソート済みストリング用主記憶領域５に格納す
る。作業領域８１，８２にストリングを書き出し、ソー
ト済みストリング用主記憶領域５がオーバーフローした
時、作業領域管理手段６がストリング置き換えブロック
を決定し、ソートフェーズ終了後にソート済みストリン
グ用主記憶５からソート／マージ用主記憶３１，３２に
ストリングを取り出しマージを行い、ストリング書き出
し／読み込み手段７が次に読むべきブロックを決定し、
作業領域８１，８２から読み込みを行う。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、ソート／マージ
処理の並列実行に関し、特に、ソート対象データが主記
憶の共有領域と複数の二次記憶に分離格納されている場
合のソーティングに関する。

【０００２】関係データベースシステム内部でソーティ
ングが利用される場合、関係データを格納する二次記憶
が分離格納されている場合や、導出された関係データを
格納する、中間的に利用される主記憶と二次記憶が分離
されている場合がある。

【０００３】近年実用化されている並列システムでは、
主記憶を処理モジュールが共有するｓｈａｒｅｄ ｅｖ
ｅｒｙｔｈｉｎｇ型のアーキテクチャで、この発明は利
用できる。さらに、主記憶を共有しないｓｈａｒｅｄ
ｎｏｔｈｉｎｇ型でも、分散共有メモリアーキテクチャ
を採用したシステムは、この発明を適用できる。

【０００４】

【従来の技術】この発明の関連分野の文献を挙げると、 ［１］特開平０３−０７１２２７ ［２］Ｂｉｔｔｏｎ Ｄ．，ｅｔ ａｌ：“Ｐａｒａｌ
ｌｅｌ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ Ｅｘ
ｅｃｕｔｉｏｎ ｏｆ ＲｅｌａｔｉｏｎａｌＤａｔａ
ｂａｓｅ ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ
Ｄａｔａ−ｂａｓｅ Ｓｙｓｔｅｍｓ，Ｖｏｌ８，Ｎｏ
３，Ｓｅｐｔｅｍｂｅｒ １９８３，ｐａｇｅｓ３２４
−３５３． ［３］樋川英治、渡部栄一：“ＮｏｎＳｔｏｐ ＳＱＬ
のアーキテクチャ”，情報処理，Ｖｏｌ３３，Ｎｏ１
２，ｐａｇｅｓ１４３６−１４４０がある。これらの文
献を引用して、従来技術を説明する。

【０００５】文献［１］によれば、主記憶（容量ｍ）に
ソート対象となるデータ（容量ｎ）がすべて収まらない
様な大容量のソート処理を外部的ソートと呼び、１回の
ソートフェーズとＬｏｇ（ｎ／ｍ）回のマージフェーズ
をもって構成される［文献１の４頁］。各フェーズで
は、その中で完全にソートされた結果をもつ、いくつか
のグループが生成する。このグループをストリングと呼
ぶこととする。たとえば、ソートフェーズ完了時のスト
リングの個数は、最大ｎ／ｍである。外部ソートの性能
は、ソートフェーズとマージフェーズあるいは各々のマ
ージフェーズ間でデータ受け渡しをする作業領域に対す
るデータ転送時間が全体性能を制限する傾向にある（つ
まり、作業領域にたいするＩ／Ｏｂｏｕｎｄである）
［文献１の８ページ］。［文献１］では、ソートフェー
ズとマージフェーズの受け渡しを、仮想記憶にマッピン
グすることで、仮想記憶をサポートするメモリ量が十分
にある場合、３０％から８０％この時間を縮小する方法
を開示している。この方法によれば、ソート処理に使用
するメモリをソート／マージ処理用と作業領域支援用に
等しく分割し、作業領域支援用のメモリは一つのストリ
ングが処理された時点で（すなわちソート／マージ処理
領域の全てのデータが処理された時点）、その都度、二
次記憶に書き出し、次のマージフェーズでは主記憶に残
っているストリングから処理することで作業領域からの
読み出し時に発生する二次記憶へのＩ／Ｏ回数を削減す
るものである。なお二次記憶への書きだしは入力データ
の読み込みとオーバラップさせている。

【０００６】一方、外部ソートを複数プロセッサの並列
マシンに適用した例が、文献［２］に示されている。図
５は［文献２の頁３３４］から引用した並列２ウェイマ
ージソートを説明する図で、ＳＵＢ ＯＰＴＩＡＭＬ
ＳＴＡＧＥとＯＰＴＩＭＡＬＳＴＡＧＥが一つのデータ
源に対する外部ソートに対応する。すなわち外部データ
９１乃至９４をプロセッサ９５乃至９８でソートし、そ
の結果を最終的に各プロセッサ９５乃至９８毎に１本の
ストリング９９にマージしている。並列２ウェイマージ
ソートでは、個々の外部ソートの結果をさらに多段階に
構成された複数プロセッサでマージすることで（ＰＯＳ
ＴＯＰＴＩＭＡＬ ＳＴＡＧＥ）、１本のソートされた
結果を得ることができる。

【０００７】関係データベースシステムにおける関係代
数演算処理を並列処理する場合、文献［３］によれば、
関係を複数の二次記憶装置に分離して格納しておき、各
々の分離した関係（パーティションと呼ぶ）に対して関
係代数演算を施し、その結果をまとめる場合がある。こ
の場合の一般的な考慮として、データの片寄りの問題が
ある。関係代数演算処理では、ソート処理の入力が通常
選択処理等の別の関係代数演算の結果生じるので、デー
タの片寄りは、単に各パーティションのデータ量が各々
異なるだけでなく、パーティション毎の選択率が異なる
ことによる片寄りもある。この様に並列処理する対象の
データ量に片寄りがある場合、並列ソートのＯＰＴＩＭ
ＡＬ ＳＴＡＧＥとＰＯＳＴＯＰＴＩＭＡＬ ＳＴＡＧ
Ｅ間で最もデータ処理量の多いプロセッサの処理終了を
待ち合わせる必要が発生することになり、全体性能を低
下させる。

【０００８】

【発明が解決しようとする課題】メモリ共有型、あるい
はクラスタ型のアーキテクチャを持つ並列マシン上で並
列ソート処理を実行する場合の問題は、ＳＵＢＯＰＴＩ
ＭＡＬ ＳＴＡＧＥ，ＯＰＴＩＭＡＬ ＳＴＡＧＥを個
々の外部ソートとみなし、単純に文献［１］の方法を適
用した場合、各外部ソートで発生する作業領域の二次記
憶へのＩ／Ｏ回数が異なり、最も多くのＩ／Ｏを必要と
する外部ソートの性能で、並列ソート全体の性能が抑制
されることである。これはメモリ共有型のアーキテクチ
ャの特徴を生かしていない。他の外部ソートのメモリを
融通することで、Ｉ／Ｏ回数のバランスをとることが可
能なはずだからである。

【０００９】外部ソートの場合、各フェーズで同一デー
タに関する二次記憶へのＩ／Ｏ回数は高々２度である。
１度は入力データの読み出し、あるいは前フェーズの作
業領域からの読み出しであり、１度は作業領域へのデー
タの書き込みである。したがって、Ｉ／Ｏ回数を削減す
る方法は、フェーズ数を削減するか、あるいは各フェー
ズの作業領域へのデータの読み書きを主記憶でバックア
ップするかのいずれかである。フェーズ数を削減するた
めには、ソート／マージ用に割り当てる主記憶量を調整
する必要がある。ソート／マージ用に割り当てられた主
記憶はランダムにアクセスする傾向にあり、作業領域用
に割り当てられた主記憶は順次アクセスとなる。

【００１０】この発明では、並列ソートのＳＵＢＯＰＴ
ＩＭＡＬ ＳＴＡＧＥ，ＯＰＴＩＭＡＬ ＳＴＡＧＥを
外部ソートとみなし、作業領域用に割り当てるメモリを
並列ソートの間で融通しあうことで、マージフェーズの
ストリングで２次記憶から読み出すブロック数を各スト
リングで均等にし、並列動作する外部ソートの終了時刻
をなるべく同じにする。

【００１１】

【課題を解決するための手段】この発明の目的は、関係
データベースの問合せ処理の並列化処理で、ソート処理
を並列実行する際、二次記憶に対する入出力回数のバラ
ツキで生じる処理時間の片寄りを均等に調整することに
よって、全体性能を向上させることにある。

【００１２】そのため、この発明の、ソート対象の入力
データを格納する第一の二次記憶と、前記第一の二次記
憶から読み出す入力データの所定数ブロックからなるス
トリングあるいはソート／マージ処理の中間段階で生成
されるストリングを保持するソート／マージ用主記憶領
域と、ソート／マージ処理の中間段階で生成されるスト
リングの格納領域をオーバフローするブロックを退避さ
せる作業領域を有する第二の二次記憶と、を各プロセス
それぞれで具備し、前記ソート／マージ用主記憶領域の
ストリングをソート／マージ処理して生成する新たなス
トリングを格納する前記格納領域からなるソート済スト
リング主記憶領域と、前記第一の二次記憶から入力デー
タの所定数ブロックからなるストリングを読み出して前
記ソート／マージ用主記憶領域に格納する入出力手段
と、前記ソート／マージ用主記憶領域のストリングをソ
ート／マージ処理して生成した新たなストリングを前記
ソート済ストリング主記憶領域に格納し、あるいは前記
ソート済ストリング主記憶領域のストリングをソート／
マージ処理して新たなストリングを前記ソート／マージ
用主記憶領域に移送するソート／マージ手段と、を全プ
ロセスで共有してなる並列ソート装置にあって、前記ソ
ート／マージ手段が前記ソート／マージ用主記憶領域の
ストリングをソート／マージ処理して生成する新たなス
トリングのブロックを前記ソート済ストリング主記憶領
域のストリングに追加して生じるオーバフローブロック
を前記作業領域に置き換えるとき、前記ストリングそれ
ぞれの置き換えられるブロック数を等しくするように制
御する作業領域管理手段と、前記ソート済ストリング主
記憶領域のオーバフローブロックを前記作業領域に前記
置き換えのため書き出し、あるいは前記ソート済ストリ
ング主記憶領域のストリングをソート／マージ処理する
とき、前記置き換えによる空きブロックを、前記作業領
域から読み出してストリングを復元するストリング書き
出し／読み込み手段と、を備えることを特徴とする。

【００１３】ソートの対象となるデータは、二次記憶の
入力データからソート／マージ用主記憶領域に入り切る
所定数のブロックをストリングとして取り出され、その
中で内部ソートされる。この処理は、別々のプロセス
（あるいはプロセッサ）によって並列に実施される。い
ったん内部ソートが完了して生成される新たなストリン
グは個々のプロセスでソート済ストリング用主記憶領域
に転送される。ソート済ストリング用主記憶のストリン
グのブロックは、二次記憶の作業領域に転送されて対応
付けられる。ソート／マージ用主記憶領域に各々のプロ
セスで新たな入力データが読み出されるが、この際の待
ち時間には、ストリング書きだし／読み出し手段がソー
ト／マージ用主記憶領域のストリング中のブロックを書
き出せるだけソート済ストリング主記憶領域と二次記憶
の作業領域に書き出す。前記動作中に、転送すべきソー
ト済ストリング用主記憶に空きがなくなった場合、作業
領域管理手段が、各ストリングで置き換えブロック数が
等しくなる様に置き換えるべきブロックを決定する。こ
の決定方法については、実施例で説明する。

【００１４】マージフェーズでは、ソート済ストリング
用主記憶領域の順次ソート済のストリングを順に取り出
し、マージ用主記憶領域に転送してマージ処理を行う。
これは、複数のプロセスで並列に実施される。この動作
を各プロセスが作成した全てのストリングに対して実施
する。マージ処理が完了したものは、従来技術で説明し
たＰＯＳＴＯＰＴＩＭＡＬ ＳＴＡＧＥの処理に渡され
る。これは、同一マシン内で実施してもよいし、別マシ
ンに転送して実施してもよい。

【００１５】上記動作中に、ソート済ストリング用主記
憶のブロックに空きができた場合、ストリング書き出し
／読み込み手段は二次記憶の作業領域から空きになった
ブロックと同じストリングで次に利用するブロックの読
み出し要求を出す。どのブロックを読み出すかについて
の方法を実施例で説明する。二次記憶の作業領域からブ
ロックの読み出しは、マージ処理実行中に行われる。マ
ージ処理は、ソート済ストリング主記憶領域中のストリ
ングがなくなった場合、ストリング書き出し／読み出し
手段が要求した読み出し要求の終了を待ち合わせる。こ
の動作によって、各プロセスが二次記憶の作業領域から
読み出すブロック数を均等にして、プロセス間で外部ソ
ートに必要な処理時間を合わせることができる。

【００１６】

【発明の実施の形態】次に、この発明について、図面を
参照して説明する。

【００１７】この発明の一実施例の構成を示す図１を参
照すると、並列ソート装置１が２つのプロセスで動作す
る構成を例示し、ソートの入力となる入力データ２１，
２２と、入力データをプロセス対応のソートマージ用主
記憶領域３１，３２に読み込むための入出力手段３と、
読み込んだ入力データをソート／マージ用主記憶領域３
１，３２上でソートあるいはマージして新しいストリン
グを生成するソート／マージ手段４と、ソート／マージ
手段４によってソートされた結果であるストリング５１
乃至５４を蓄えるソート済ストリング用主記憶領域５
と、入力データの量が多く、ソート済ストリング領域５
がオーバフローして、該主記憶領域５が不足した場合に
備えて、ストリング５１乃至５４でどのブロックを新た
なブロックの置き換え用として選択するかを決定する作
業領域管理手段６と、作業領域管理手段６が決定したブ
ロックをプロセス対応の作業領域８１，８２に書き出す
ストリング書き出し／読み込み手段７と、を備える。

【００１８】この実施例では、各並列処理のプロセスが
ソート結果を１本のストリングとしている。これは、従
来技術で述べた並列ソートのＳＵＢＯＰＴＩＭＡＬ Ｓ
ＴＡＧＥ，ＯＰＴＩＭＡＬ ＳＴＡＧＥに相当する。最
終的に各プロセスで処理したソート済ストリングから１
本のソート結果を得るには、さらにその結果をマージす
る必要がある。入力データ２１，２２とソート／マージ
用主記憶領域３１，３２と、作業領域８１，８２は並列
処理単位のプロセス毎に存在し、ソート済ストリング用
主記憶領域５のみが、並列処理のプロセスに共通した領
域であるものとしている。作業領域８１，８２や、ソー
ト／マージ用主記憶領域３１，３２を並列処理単位に共
通にする変更を加えることは可能である。

【００１９】次に、この実施例のソートマージ用主記憶
領域３１，３２と、ソート済ストリング用主記憶領域５
のサイズの決定方法を説明する。更に作業領域管理手段
６がソート済ストリング用主記憶領域５上のストリング
５１乃至５４のどのブロックを置き換えるかの決定方法
を説明し、更にソート済ストリング用主記憶領域５に空
きブロックが発生した場合、ストリング書き出し／読み
出し手段７がどのブロックを二次記憶の作業領域８１，
８２から復元するかの決定方法を説明する。

【００２０】先ず主記憶領域のサイズの決定方法を説明
する。ソート／マージ用主記憶はプロセス固有の領域で
あり、サイズは各プロセスで同じにする。各プロセスが
処理する入力データサイズをｎとし、ソート用主記憶の
サイズをｍとすると、一つのプロセスが生成するソート
済ストリングの数は最大でｎ／ｍとなる。一方、マージ
処理が必要とするメモリ量は、処理対象のストリング数
に依存して増加する。簡単のために、マージ対象のスト
リングは、そのプロセスが生成したストリングであると
する。マージ処理で必要な主記憶量をｆ（ｎ／ｍ）で表
わすと、 ｍ＝ｆ（ｎ／ｍ） なるメモリ量ｍを決定することが望ましい。たとえば、
ｆ（ｎ／ｍ）＝ｎ／ｍのケースを考えると、上式はｍ＝
ｎ／ｍとなり、ｍ＝ｒｏｏｔ（ｎ）となる。上述のよう
に、ソート／マージ用主記憶領域サイズは、マージアル
ゴリズムで使用するメモリ量と処理の入力データとから
決定することができる。入力データのデータ量の半分の
桁数のメモリ量を割り当てることになる。利用可能な主
記憶のうち、残りの主記憶をソート済ストリング用主記
憶領域に割り当てる。

【００２１】次に、作業領域管理手段６のブロック置き
換えの動作の流れ図３を参照し、ブロック置き換えの動
作を説明する図２（ａ），図２（ｂ），図２（ｃ），図
２（ｄ）を援用して、作業領域管理手段６による置き換
えアルゴリズムを説明する。図２（ａ）乃至図２（ｄ）
では、ソート処理結果としてストリング５１乃至５４の
４本が生成され、ソート済ストリング用主記憶領域５に
渡されるものとしている。ソート済ストリング用主記憶
領域５に存在するブロックは全部で１２ブロック分であ
るものとしている。また１２ブロックがオーバフローし
て、ブロックの置き換えが発生し、ソート済ストリング
用主記憶領域５から作業領域８１，８２に置き換えで追
い出されたブロックは黒の塗り潰しで示すことにする。
図２（ｃ），図２（ｄ）で、置き換え数とは、この黒塗
りのブロック数である。また、残りとは、図２（ａ），
（ｂ）で網点で示されているソート済ストリング主記憶
領域５の１２ブロック内に残っている数である。空白の
ブロックは、今後処理で生成される予定のストリングの
ブロックである。ストリング５１とストリング５２はプ
ロセス１５がソート処理したストリングであり、後のマ
ージ処理でもプロセス１５が使用する。ストリング５３
とストリング５４はプロセス１６がソート処理したスト
リングであり、後のマージ処理ではプロセス１６が使用
する。

【００２２】先ず図２（ａ）は、ストリング５３の生成
時に領域がオーバフローし、初めて置き換えが必要にな
った時点でソート済ストリング主記憶領域５の１２ブロ
ック内にストリングが納められた状況を示している。こ
の時点で、ストリング５１，５２，５３の全ての置き換
え数は０であるが、生成したブロックを該領域５に格納
するとき、図３によれば、自分以外（つまり処理対象と
なっているストリング５３以外）を優先的に選択するの
で、置き換え対象としてストリング５１が選ばれる（ス
テップ６１）。ストリング５１の１ブロックを置き換え
た場合にソート済ストリング用主記憶に残るブロックが
存在する（１以上である）ので、このストリングの最後
に転送された部分（図２の５１３）が置き換えの対象と
なったことを示している（ステップ６２のｎｏ）。な
お、ブロック１個を残すのは、全てのソートストリング
が生成された後のストリングのマージ処理を実行するた
めには、全てのストリングの最も小さい値を含むブロッ
クがソート済ストリング用主記憶領域５に存在する必要
があるからである。図３のアルゴリズムにしたがって、
４本全てのストリングの処理が終わった時点の状態を図
２（ｂ）に示す。ストリング５４のブロックは、自身の
ストリング書き出し中に発生した黒の塗潰し部分５１
２，５１３，５２２，５２３，５３６，５３７，５４
２，５４６の置き換えによって、１２ブロック内の網点
５１１，５２１，５３１乃至５３５，５４１，５４３乃
至５４５，５４７に納められている。この様な置き換え
は、図３のステップ６２の条件から、図２のブロック５
４１では発生しない。図２（ｂ）によれば最終的に全て
のストリングで置き換え数が２となり、読み出すべきブ
ロック数が同じになる様に調整されていることがわか
る。このことは、マージ処理時にプロセス１５およびプ
ロセス１６で必要な作業領域８１，８２からの読みだし
回数が等しくなり、各プロセスでのマージ処理終了時間
が均等になることを意味する。ソート済ストリング主記
憶領域５にストリングが生成されて、ブロックを置き換
えるためには、ソート済ストリング用主記憶５の置き換
え対象となるブロックをストリング書き出し／読みだし
手段７で作業領域８１，８２に書き出す必要がある。書
き出すタイミングを、置き換えが発生するタイミングと
したが、事前に書き出しておくこともできる。たとえ
ば、最初に置き換えが発生する一つ前（つまり、ソート
済ストリング用主記憶領域に１ブロックの空きがある時
点で）に、図３のアルゴリズムを適用し、次に置き換え
が発生した場合に置き換えるブロックの書き出し要求を
出しておくことで、入力データからの読み出しおよびソ
ート処理と作業領域８１，８２へのブロックの書き出し
処理をオーバラップさせて、処理時間を短縮することが
できる。マージフェーズでソート済ストリング領域５の
或るブロックの処理が完了し、そのブロックが再利用可
能となった場合、ストリング書き出し／読み込み手段７
がどのブロックを作業領域８１，８２から読み出すかを
説明する。

【００２３】先ず図２（ｂ）がマージ処理の開始時点で
ある。ストリング書き出し／読み込み手段７のブロック
選択基準を示すフローチャートである図４によれば図２
（ｂ）で、プロセス１６のマージ処理が進行し、ブロッ
ク５３１が空になったとする。ここで、図４の１のフロ
ーチャートに従うと、プロセス５６自身のマージ処理
で、空きのブロック５３１に読み出す作業領域のブロッ
クは、図２（ｂ）の５３６，５４２から置き換えられた
ブロックで、このうち５４２は距離１であり、５３６は
距離５であることから（ステップ７１，７２）、ストリ
ング書き出し／読み込み手段７はブロック５４２を読み
出す（ステップ７３）。この間、マージ処理は、図２
（ｂ）のブロック５４１，５３２の間で継続する。一
方、プロセス１５のマージ処理が進行しブロック５１１
が空になったとすると、次に読み出すべきブロックは図
２（ｂ）の５１２，５２２で置き換えられたブロックで
あり、各々距離は１なので、自分のストリングの次のブ
ロックである５１２が読み出しの対象となる。

【００２４】なお、この実施例では、ダブルバッファに
よる先読みを考慮していないが、図３のステップ２で、
残すバッファ数を調整することで、ダブルバッファによ
る先読みを実施することもできる。たとえば、図３のス
テップ２の判定条件を、「残りが１以下または、そのプ
ロセスの先読み用バッファが１以下」あるいは、「残り
が２以下」などと変更すればよい。この場合、図４のア
ルゴリズムはまったく変わりない。またこの実施例にお
いて、プロセスを共有メモリ型マルチプロセッサの各プ
ロセッサに割り当てる変更ができることは明きらかであ
る。

【００２５】

【発明の効果】以上説明した様に、この発明によれば、
並列に実行する外部ソートのマージフェーズで読み出す
べきブロック数を均等になるように調整することによっ
て、マージフェーズの終了時刻を各プロセスで同じにし
て、ソート／マージ処理全体の処理時間を短縮できる。
たとえば、図２（ｂ）の例では、プロセス毎に別々の作
業領域用の二次記憶を持つとすると、二次記憶へのＩ／
Ｏ回数は各プロセスで４回ずつである。これに対して、
各プロセスで均等にソート済ストリング用主記憶を割り
当てたとすると、プロセス１５は全てメモリに収まるた
めに、Ｉ／Ｏ回数は０であり、プロセス１６では８回の
Ｉ／Ｏが必要となり、この発明の装置の２倍のＩ／Ｏ回
数のプロセスが全体の処理時間を低下させる。

【００２６】また、この発明によれば、空きブロックに
読み出すブロックを決定する際に、現在使用しているブ
ロックからの距離を利用することで、最も必要度の高い
データを読み出しの対象とすることができ、Ｉ／Ｏ中に
マージ処理を並列して行うことができる。たとえば、図
２（ｂ）の例では、ブロック５３１が空となった場合に
ブロック５３６を読み出すと、次にブロック５４２が必
要になった場合に、ブロック５４２の読み出し完了まで
マージ処理を待つ必要がある。これは、ブロック５４２
がブロック５３６よりも前に必要となる可能性が高いか
ら各ストリングが均等なソートキーの分布を持つ場合に
は有効になる。

【図面の簡単な説明】

【図１】この発明の一実施例の構成を示す図である。

【図２】分図（ａ）は、ストリングに新たなブロックを
つなぐとき、置き換えるブロックを決定する説明図、分
図（ｂ）は、ソート済ストリングをマージするとき、読
み出すブロックを決定する説明図、分図（ｃ）は、分図
（ａ）の時点でのストリングの状況を説明する図、分図
（ｄ）は分図（ｂ）の時点でのストリングの状況を説明
する図である。

【図３】ソート済ストリングを主記憶領域で置き換える
際のフローチャートである。

【図４】ソート済ストリング用主記憶領域に空ができた
場合の二次記憶の作業領域からの読み出しのフローチャ
ートである。

【図５】従来の並列ソートを示す図である。

【符号の説明】

１ 並列ソート装置 ３ 入出力手段 ４ ソート／マージ手段 ５ ソート済ストリング主記憶領域 ６ 作業領域管理手段 ７ ストリング書き出し／読み込み手段 ２１，２２ 入力データ ３１，３２ ソート／マージ用主記憶領域 ８１，８２ 作業領域

Claims (2)

【特許請求の範囲】
1. 【請求項１】 ソート対象の入力データを格納する第一
   の二次記憶と、 前記第一の二次記憶から読み出す入力データの所定数ブ
   ロックからなるストリングあるいはソート／マージ処理
   の中間段階で生成されるストリングを保持するソート／
   マージ用主記憶領域と、 ソート／マージ処理の中間段階で生成されるストリング
   の格納領域をオーバフローするブロックを退避させる作
   業領域を有する第二の二次記憶と、 を各プロセスそれぞれで具備し、 前記ソート／マージ用主記憶領域のストリングをソート
   ／マージ処理して生成する新たなストリングを格納する
   前記格納領域からなるソート済ストリング主記憶領域
   と、 前記第一の二次記憶から入力データの所定数ブロックか
   らなるストリングを読み出して前記ソート／マージ用主
   記憶領域に格納する入出力手段と、 前記ソート／マージ用主記憶領域のストリングをソート
   ／マージ処理して生成した新たなストリングを前記ソー
   ト済ストリング主記憶領域に格納し、あるいは前記ソー
   ト済ストリング主記憶領域のストリングをソート／マー
   ジ処理して新たなストリングを前記ソート／マージ用主
   記憶領域に移送するソート／マージ手段と、を全プロセ
   スで共有してなる並列ソート装置にあって、 前記ソート／マージ手段が前記ソート／マージ用主記憶
   領域のストリングをソート／マージ処理して生成する新
   たなストリングのブロックを前記ソート済ストリング主
   記憶領域のストリングに追加して生じるオーバフローブ
   ロックを前記作業領域に置き換えるとき、前記ストリン
   グそれぞれの置き換えられるブロック数を等しくするよ
   うに制御する作業領域管理手段と、 前記ソート済ストリング主記憶領域のオーバフローブロ
   ックを前記作業領域に前記置き換えのため書き出し、あ
   るいは前記ソート済ストリング主記憶領域のストリング
   をソート／マージ処理するとき、前記置き換えによる空
   きブロックを、前記作業領域から読み出してストリング
   を復元するストリング書き出し／読み込み手段と、を備
   えることを特徴とする並列ソート装置。
2. 【請求項２】 前記プロセスそれぞれをメモリ共有型マ
   ルチプロセッサの各プロセッサに割り当てることを特徴
   とする請求項１記載の並列ソート装置。