(57)【要約】【課題】  特殊な環境を必要とせず、迅速かつ効率的にソート処理を行うことを可能とする並列ソートシステム等を提供する。【解決手段】  マスタ１０１は、各スレーブ１０２の分担範囲５０２を決定して各スレーブ１０２に通知し、各スレーブ１０２は、分担範囲５０４を保持する。マスタ１０１は、ソート対象データ５０１をブロードキャスト通信５０７でネットワークに送出し、各スレーブ１０２は、自身の分担範囲のソート対象データ５０５を取り込んでソート処理を行い、ソート済データ５０６をマスタ１０１に送信し、マスタ１０１は、各スレーブ１０２からソート済データ５０６を回収して結合し、ソート対象データ全体のソート結果（ソート済データ５０３）を得る。【選択図】  図５
2006048192.tif 000002
【特許請求の範囲】
【請求項１】
並列ソートサーバと複数のクライアントとがネットワークを介して接続され、複数のソート対象データをソートする並列ソートシステムであって、
前記並列ソートサーバは、
前記複数のソート対象データから前記クライアント毎にソートキーの分担範囲を決定する分担範囲決定手段と、
前記クライアントに前記分担範囲を通知する分担範囲通知手段と、
前記複数のソート対象データをブロードキャスト通信により前記ネットワークに送出するブロードキャスト手段と、
前記クライアントからソート済データを回収する回収手段と、
を具備し、
前記クライアントは、
前記ネットワークから前記分担範囲にある前記ソート対象データを選択して受信する選択受信手段と、
前記ソート対象データのソートを行うソート手段と、
を具備することを特徴とする並列ソートシステム。
【請求項２】
前記分担範囲決定手段は、前記ソートキーの度数分布に基づいて、前記クライアント毎に均等に、前記分担範囲を決定することを特徴とする請求項１に記載の並列ソートシステム。
【請求項３】
前記選択受信手段及び前記ソート手段は、互いに独立して処理を行うことを特徴とする請求項１に記載の並列ソートシステム。
【請求項４】
複数のクライアントにネットワークを介して接続され、複数のソート対象データをソートする並列ソートサーバであって、
前記複数のソート対象データから前記クライアント毎にソートキーの分担範囲を決定する分担範囲決定手段と、
前記クライアントに前記分担範囲を通知する分担範囲通知手段と、
前記複数のソート対象データをブロードキャスト通信により前記ネットワークに送出するブロードキャスト手段と、
前記クライアントからソート済データを回収する回収手段と、
を具備することを特徴とする並列ソートサーバ。
【請求項５】
前記分担範囲決定手段は、前記ソートキーの度数分布に基づいて、前記クライアント毎に均等に、前記分担範囲を決定することを特徴とする請求項４に記載の並列処理サーバ。
【請求項６】
複数のソート対象データをソートする並列ソートサーバにネットワークを介して接続される、クライアントであって、
前記並列ソートサーバから通知された分担範囲にある前記ソート対象データを、前記ネットワークから選択して受信する選択受信手段と、
前記ソート対象データのソートを行うソート手段と、
を具備することを特徴とするクライアント。
【請求項７】
前記選択受信手段及び前記ソート手段は、互いに独立して処理を行うことを特徴とする請求項６に記載のクライアント。
【請求項８】
並列ソートサーバと複数のクライアントとがネットワークを介して接続され、複数のソート対象データをソートする並列ソートシステムにおける、並列ソート方法であって、
前記並列ソートサーバが実行する、
前記複数のソート対象データから前記クライアント毎にソートキーの分担範囲を決定する分担範囲決定ステップと、
前記クライアントに前記分担範囲を通知する分担範囲通知ステップと、
前記複数のソート対象データをブロードキャスト通信により前記ネットワークに送出するブロードキャストステップと、
前記クライアントからソート済データを回収する回収ステップと、
を具備し、
前記クライアントが実行する、
前記ネットワークから前記分担範囲にある前記ソート対象データを選択して受信する選択受信ステップと、
前記ソート対象データのソートを行うソートステップと、
を具備することを特徴とする並列ソート方法。
【請求項９】
コンピュータを請求項４または請求項５に記載の並列ソートサーバとして機能させるためのプログラム。
【請求項１０】
コンピュータを請求項４または請求項５に記載の並列ソートサーバとして機能させるためのプログラムを記録したコンピュータ読取可能な記録媒体。
【請求項１１】
コンピュータを請求項６または請求項７に記載のクライアントとして機能させるためのプログラム。
【請求項１２】
コンピュータを請求項６または請求項７に記載のクライアントとして機能させるためのプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の処理装置をネットワークを介して接続した並列処理システムに関する。詳細には、複数のレコードからなるデータをソートする並列ソートシステム等に関する。
【背景技術】
【０００２】
従来、科学技術計算、事務処理、統計処理、シミュレーション等の情報処理分野において、データのソートが多用されている。商用データ処理については、例えば、ダイレクトメールを印刷する際、郵便番号順にソートする等、日常業務的に行われている。
そして、大量データのソートに関しては、複数の処理装置を用いて並列処理によりソートする手法が提案されている。
【０００３】
例えば、データを分割し、複数の処理装置によりソートを行い、結果をマージするソート処理方式が提案されている（例えば、［特許文献１］参照。）。
また、処理速度を改善する目的で、データを各処理装置に分割配布し、仮に処理分担範囲を決めておき、分担範囲とデータを相互に交換しつつソートを行う並列ソート処理方法が提案されている（例えば、［特許文献２］参照。）。
【０００４】
【特許文献１】特開平５−３５４４４号公報
【特許文献２】特許第２５０９９２９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、［特許文献１］に示す技術では、ソートとマージの２工程に分かれており、データ転送は往復の２回で済み、ソート工程は並列で行うので速度は向上するが、マージ工程では複数回の読み・書きが発生し、全体として処理速度の向上が望めないという問題点がある。
また、［特許文献２］に示す技術では、ソートとマージを同時に実行しようとしているので、処理速度は大幅に改善されるが、処理装置間でデータを大量に交換するので、通常１対１通信を基本とする日常的に用いられるネットワークでの利用を考慮すると実施は可能であるが、待ちや衝突が生じるため効率が低減するという問題点がある。
従って、処理装置を互いに立体格子網状に配置する等、通信がボトルネックとならないよう特殊なバス環境あるいはネットワーク環境を構築する必要があるという問題点がある。
【０００６】
本発明は、以上の問題点に鑑みてなされたものであり、特殊な環境を必要とせず、迅速かつ効率的にソート処理を行うことを可能とする並列ソートシステム等を提供することを目的とする。
【課題を解決するための手段】
【０００７】
前述した目的を達成するために第１の発明は、並列ソートサーバと複数のクライアントとがネットワークを介して接続され、複数のソート対象データをソートする並列ソートシステムであって、前記並列ソートサーバは、前記複数のソート対象データから前記クライアント毎にソートキーの分担範囲を決定する分担範囲決定手段と、前記クライアントに前記分担範囲を通知する分担範囲通知手段と、前記複数のソート対象データをブロードキャスト通信により前記ネットワークに送出するブロードキャスト手段と、前記クライアントからソート済データを回収する回収手段と、を具備し、前記クライアントは、前記ネットワークから前記分担範囲にある前記ソート対象データを選択して受信する選択受信手段と、前記ソート対象データのソートを行うソート手段と、を具備することを特徴とする並列ソートシステムである。
【０００８】
第１の発明の並列ソートシステムでは、並列ソートサーバは、複数のソート対象データから各クライアント毎にソートキーの分担範囲を決定して各クライアントに通知し、ソート対象データをブロードキャスト通信によりネットワークに送出し、各クライアントは、自身の分担範囲にあるソート対象データを選択して受信し、ソートを行い、並列ソートサーバは、各クライアントからソート済データを回収する。
【０００９】
ソート対象データは、ソート対象のデータ（レコード）あるいはそのソートキーである。
ソート済データは、ソート済のデータ（レコード）あるいはそのソートキーである。
データ全体を送受信することに代えて、ソートキー部を送受信することにより、通信量を軽減してシステムの安定化及び迅速処理を図ることができる。
【００１０】
第１の発明の並列ソートシステムでは、並列ソートサーバは、ソート対象データのソートキーを生成して各クライアント毎にソートキーの分担範囲を決定し、各クライアントは、自身の分担範囲にあるソート対象データについてソート処理を行うので、１のソート対象データにつき、データ転送は、並列ソートサーバ〜クライアント間の往復１回で済む。
【００１１】
また、ソート対象データは、ブロードキャストによりネットワークに送出され、一度の通信で全クライアントが同時に受信するので、通信の衝突を防止することができる。
また、並列ソートサーバ、クライアントとして、通常のパーソナルコンピュータ及びネットワーク設備を用いることができる。
従って、特別な環境を設けることなく、ソート処理を迅速かつ効率的に行うことができる。
【００１２】
また、各クライアントのソートキーの分担範囲の決定は、ソート対象データのソートキーの度数分布に基づいて行うことが望ましい。この場合、各クライアントにほぼ均等にソートキーの分担範囲を割り当てることにより処理負荷を均等にして、各クライアントの処理能力を無駄なく有効活用することにより、迅速かつ効率的な処理を実現することができる。
【００１３】
また、各クライアントは、ソート対象データの選択受信処理、ソート処理を別プロセスにより独立して行うことが望ましい。また、データ受信処理優先にてマルチタスク処理を行うことが望ましい。この場合、データ受信中もソート処理が可能であり、データ欠落等を防止しつつ、効率的かつ迅速にソート処理を行うことができる。
【００１４】
第２の発明は、複数のクライアントにネットワークを介して接続され、複数のソート対象データをソートする並列ソートサーバであって、前記複数のソート対象データから前記クライアント毎にソートキーの分担範囲を決定する分担範囲決定手段と、前記クライアントに前記分担範囲を通知する分担範囲通知手段と、前記複数のソート対象データをブロードキャスト通信により前記ネットワークに送出するブロードキャスト手段と、前記クライアントからソート済データを回収する回収手段と、を具備することを特徴とする並列ソートサーバである。
【００１５】
第２の発明は、第１の発明の並列ソートシステムにおける並列ソートサーバに関する発明である。
【００１６】
第３の発明は、複数のソート対象データをソートする並列ソートサーバにネットワークを介して接続される、クライアントであって、前記並列ソートサーバから通知された分担範囲にある前記ソート対象データを、前記ネットワークから選択して受信する選択受信手段と、前記ソート対象データのソートを行うソート手段と、を具備することを特徴とするクライアントである。
【００１７】
第３の発明は、第１の発明の並列ソートシステムにおけるクライアントに関する発明である。
【００１８】
第４の発明は、並列ソートサーバと複数のクライアントとがネットワークを介して接続され、複数のソート対象データをソートする並列ソートシステムにおける、並列ソート方法であって、前記並列ソートサーバが実行する、前記複数のソート対象データから前記クライアント毎にソートキーの分担範囲を決定する分担範囲決定ステップと、前記クライアントに前記分担範囲を通知する分担範囲通知ステップと、前記複数のソート対象データをブロードキャスト通信により前記ネットワークに送出するブロードキャストステップと、前記クライアントからソート済データを回収する回収ステップと、を具備し、前記クライアントが実行する、前記ネットワークから前記分担範囲にある前記ソート対象データを選択して受信する選択受信ステップと、前記ソート対象データのソートを行うソートステップと、を具備することを特徴とする並列ソート方法である。
【００１９】
第４の発明は、第１の発明の並列ソートシステムにおける、並列ソート方法に関する発明である。
【００２０】
第５の発明は、コンピュータを第２の発明の並列ソートサーバとして機能させるためのプログラム及び当該プログラムを記録したコンピュータ読み取り可能な記録媒体に関する発明である。
【００２１】
第６の発明は、コンピュータを第３の発明のクライアントとして機能させるためのプログラム及び当該プログラムを記録したコンピュータ読み取り可能な記録媒体に関する発明である。
【００２２】
尚、上記のプログラムをＣＤ−ＲＯＭ等の記録媒体に保持させて流通させてもよいし、このプログラムを通信回線を介して送受することもできる。
【発明の効果】
【００２３】
本発明によれば、特殊な環境を必要とせず、迅速かつ効率的にソート処理を行うことを可能とする並列ソートシステム等を提供することができる。
【発明を実施するための最良の形態】
【００２４】
以下、添付図面を参照しながら、本発明に係る並列ソートシステム等の好適な実施形態について詳細に説明する。なお、以下の説明及び添付図面において、略同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略することにする。
また、通常、サーバは処理を行う側、クライアントは処理を依頼する側の呼称で使われ、本処理モデルと合致しないため、以降の説明において、並列ソートサーバをマスタ、処理を行うクライアントをスレーブと称する。
【００２５】
まず、図１を参照しながら、本発明の実施の形態に係る並列ソートシステムの概略構成について説明する。
図１は、並列ソートシステム１００の概略構成を示す図である。
図１に示すように並列ソートシステム１００は、マスタ１０１、スレーブ１０２−１、１０２−２、１０２−３、…等がネットワーク１０３を介して接続されて構成される。
【００２６】
並列ソートシステム１００は、複数のソート対象データのソートを行う。
マスタ１０１は、ソート対象データ及びソート済データを保持し、各スレーブ１０２に処理及びデータを分配し、各スレーブ１０２から結果を回収する処理装置である。
スレーブ１０２は、実際にソート処理を行う処理装置である。
【００２７】
マスタ１０１及びスレーブ１０２から構成される並列ソートシステム１００としては、サーバ及びクライアントから構成されるクライアント−サーバシステム等を用いることができる。
この場合、マスタ１０１は、サーバコンピュータ（並列ソートサーバ）に相当し、スレーブ１０２は、クライアント（ソート実行クライアント）に相当する。
尚、マスタ１０１、スレーブ１０２として、通常のパーソナルコンピュータ等を用いることができる。
【００２８】
ネットワーク１０３は、ＬＡＮ（ローカルエリアネットワーク）、インターネット等のネットワークであり、有線、無線を問わない。また、安全かつ円滑な通信を担保するため、インターネット等の公衆が利用可能なネットワークではなく、専用線等を利用するようにしてもよい。
マスタ１０１〜スレーブ１０２間では、ネットワーク１０３を介して、各種データ等の送信及び受信が行われる。
【００２９】
図２は、マスタ１０１及びスレーブ１０２のネットワーク接続の一態様を示す図である。
図２に示すように、並列ソートシステム１００は、複数のパーソナルコンピュータをイーサネット（登録商標）、１００ＢＡＳＥ−Ｔ等のケーブルでＨＵＢ１０４等を介して接続して構成することができ、この場合、ＴＣＰ／ＩＰ、ＵＤＰ／ＩＰ等を用いて通信を行うことができる。
【００３０】
次に、図３を参照しながら、マスタ１０１のハードウェア構成について説明する。
図３は、マスタ１０１のハードウェア構成図である。
図３に示すように、マスタ１０１は、制御部３０１、入力部３０２、表示部３０３、記憶部３０４、入出力部３０５、通信部３０６等がシステムバス３０７を介して互いに接続されて構成される。
【００３１】
制御部３０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等を有する。
【００３２】
ＣＰＵは、記憶部、ＲＯＭ、記録媒体等に格納されるプログラムをＲＡＭ上のワークメモリ領域に呼び出して実行し、演算処理、動作制御等を行い、後述する各種機能（図４、図５等参照。）を実現する。
ＲＯＭは、不揮発性メモリであり、プログラム、データ等を恒久的に保持し、ＲＡＭは、揮発性メモリであり、プログラム、データ等を一時的に保持する。
【００３３】
入力部３０２は、データの入力を行い、例えば、キーボード、マウス等のポインティングデバイス、テンキー等の入力装置を有する。
入力部３０２を介して、マスタ１０１に対して、操作指示、動作指示、データ入力、維持管理等を行うことができる。
【００３４】
表示部３０３は、ＣＲＴモニタ、液晶パネル等のディスプレイ装置、ディスプレイ装置と連携してコンピュータのビデオ機能を実現するための論理回路等（ビデオアダプタ等）を有する。
記憶部３０４は、データを記憶する装置であり、ハードディスク、メモリ等を有する。記憶部には、ＣＰＵが実行するプログラム、プログラム実行に必要なデータ、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）等が格納される。
【００３５】
入出力部３０５は、データの入出力を行い、例えば、フロッピディスクドライブ、ＰＤドライブ、ＣＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＤＶＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＭＯドライブ等のメディア入出力装置等を有する。
【００３６】
通信部３０６は、マスタ１０１とネットワーク１０３間の通信を媒介する通信インタフェースであり、通信制御装置、通信ポート等を有する。
システムバス３０７は、各装置間の制御信号、データ信号等の授受を媒介する経路である。
【００３７】
尚、同様の構成を採るパーソナルコンピュータ、ワークステーション、サーバコンピュータ等をマスタ１０１として用いることができる。
また、同様の構成を採るパーソナルコンピュータ、ワークステーション、情報携帯端末（ＰＤＡ）等をクライアント１０２として用いることができる。
【００３８】
図３に示すように、マスタ１０１は、記憶部３０４にソート対象データ３１１、分担範囲情報３１２、ソート済データ３１３、実行プログラム３１４、ＯＳ３１５等を備える。
ソート対象データ３１１は、ソート対象のデータ（レコード）あるいはそのソートキーである。
分担範囲情報３１２は、スレーブ１０２毎のソート対象データ、ソートキーの分担範囲を示す。
ソート済データ３１３は、ソート済のデータ（レコード）あるいはそのソートキーである。
【００３９】
尚、マスタ１０１及びスレーブ１０２が記憶部に保持する情報は同様であるが、マスタ１０１は、全てのスレーブ１０２について、ソート対象データ、ソート済データを保持し、スレーブ１０２は、自己の分担範囲について、ソート対象データ、ソート済データを保持する。
【００４０】
次に、図４及び図５を参照しながら、並列ソートにおける、マスタ１０１、スレーブ１０２の動作について説明する。
図４は、並列ソートにおける、マスタ１０１、スレーブ１０２の動作を示すフローチャートである。
図５は、並列ソートにおける、マスタ１０１、スレーブ１０２の処理の流れを示す図である。
【００４１】
尚、マスタ１０１及びスレーブ１０２の制御部（ＣＰＵ等）は、記憶部（ハードディスク等）に格納するプログラム（実行プログラム、ＯＳのプログラム等）、プログラム実行に必要な各種データ等をワークメモリ（ＲＡＭ等）上にロードしてＣＰＵの制御の下に以下の各ステップを実行する。
【００４２】
また、理解の容易のため、マスタ１０１は、ソート対象データの保持、ソート済データの回収を行い、マスタ１０１自身はソート処理に参加せず、マスタ１０１以外のスレーブ１０２が実際のソート処理を行うものとして説明する。
【００４３】
マスタ１０１の制御部は、ソート対象データ５０１を読み込み、ソート対象データのソートキーを生成する（ステップ４０１）。
マスタ１０１の制御部は、ソートキーの度数データ（度数分布等）を作成し、ソートキーの総数及びスレーブ１０２の数に基づいて、各スレーブ１０２毎にソートキーの分担範囲５０２を決定する（ステップ４０２）。
尚、各スレーブ１０２の分担するソートキーの数は、均等とすることが望ましい。
【００４４】
マスタ１０１の制御部は、各スレーブ１０２に対して、ソートキーの分担範囲を通知する（ステップ４０３）。
各スレーブ１０２は、通知されたソートキーの分担範囲５０４を記憶部に保持する（ステップ４０４）。
マスタ１０１の制御部は、ブロードキャスト通信５０７により、ソート対象データ５０１を順次ネットワーク上に送出する（ステップ４０５）。
【００４５】
各スレーブ１０２の制御部は、ネットワーク１０３からの受信データを監視し、記憶部に保持する分担範囲５０４の範囲内であれば、当該ソート対象データ５０５を取り込み、現有データに加えて記憶部に保持し、ソート対象データ５０５についてソート処理を行い、ソート済データ５０６を記憶部に保持する（ステップ４０６）。尚、ソートアルゴリズムに関しては、任意の公知のアルゴリズムを用いることができる。
【００４６】
マスタ１０１の制御部は、全てのソート対象データ５０１を送信した後、最初の分担範囲５０４−１を担当したスレーブ１０２−１に対して、ソート済データ５０６−１の送信を依頼する（ステップ４０７）。
スレーブ１０２−１の制御部は、マスタ１０１からの送信依頼に応じて、ソート処理終了次第、ソート済データ５０６−１をマスタ１０１に送信する（ステップ４０８）。
【００４７】
マスタ１０１の制御部は、受信したソート済データ５０６−１を記憶部に保持し、次の分担範囲５０４−２を担当したスレーブ１０２−２に対して、ソート済データ５０６−２の送信を依頼する（ステップ４０７）。
スレーブ１０２−２の制御部は、マスタ１０１からの送信依頼に応じて、ソート処理終了次第、ソート済データ５０６−２をマスタ１０１に送信する（ステップ４０８）。
【００４８】
マスタ１０１の制御部は、全てのスレーブ１０２−１、１０２−２、…について上記の処理を繰り返し、全てのソート済データ５０６−１、５０６−２、…を取得し、回収したソート済データ５０６を結合し、ソート済データ５０３として保持する（ステップ４０９）。
【００４９】
以上の過程を経て、マスタ１０１は、各スレーブ１０２の分担範囲を決定して各スレーブ１０２に通知し、ソート対象データをブロードキャスト通信でネットワークに送出し、各スレーブ１０２は、自身の分担範囲のソート対象データを取り込んでソート処理を行い、マスタ１０１は、各スレーブ１０２からソート済データを回収して結合し、ソート対象データ全体のソート結果を得る。
【００５０】
このように、並列ソートシステムでは、マスタは、ソート対象データのソートキーを生成して各スレーブ毎にソートキーの分担範囲を決定し、各スレーブは、自身の分担範囲にあるソート対象データについてソート処理を行うので、１のソート対象データにつき、データ転送は、マスタ〜スレーブ間の往復１回で済む。また、ソート対象データは、ブロードキャストによりネットワークに送出され、一度の通信で全スレーブが同時に受信するので、通信の衝突を防止することができる。
従って、特別な環境を設けることなく、迅速かつ効率的にソート処理を行うことができる。
【００５１】
また、マスタでは、事前に各スレーブ毎の分担範囲を把握しているので、事後のマージ処理も不要となり、全体として処理速度の向上を図ることができる。
また、各スレーブは、データを受信しながらソート処理を行うので処理の効率化を図ることができる。
また、スレーブの処理能力が大きい場合、マスタからのデータ送出終了と同時にスレーブにおけるソート処理も終了していることが期待できる。
【００５２】
尚、上記では、図４及び図５について、マスタ１０１、スレーブ１０２間では、ソート対象データ及びソート済データの授受は、データ全体（レコード全体）を送受信するものとして説明したが、データ送受信はこれに限られない。
通常、ソートキー部はデータ（レコード）のごく一部であり、また、第２のソートキー、第３のソートキーが存在し、それぞれ昇順・降順を指定するので、ソートキーを生成し、データ全体を送受信することに代えてソートキー部を送受信することにより、通信量を軽減してシステムの安定化及び迅速処理を図ることができる。
【００５３】
次に、図６〜図９を参照しながら、マスタ１０１における、各スレーブ１０２の分担範囲の決定処理（図４：ステップ４０２）について説明する。
尚、図６〜図９では、ソートキーを用いて分担範囲の決定等の処理が行われるものとして説明する。
【００５４】
図６は、ソート対象データであるレコード６００の一態様を示す図である。
図６に示すように、ソート対象データとしてのレコード６００は、ソートキー６０１、内容６０２等から構成される。
ソートキー６０１は、レコード６００のソート順を示すキーであり、ソートする際に参照される。尚、ソートキーは、第１ソートキー、第２ソートキー等、複数設け、それぞれについてソート順を定めるようにしてもよい。
内容６０２は、レコード６００が保持するデータの内容である。
【００５５】
図７は、ソートキーツリー７００の一態様を示す図である。
図７に示すソートキーツリー７００は、多分木構造をなす。ソートキーツリー７００では、各ソートキー７０１は、ソートキー部分７０２が枝７０５により連結されて構成される
ソートキー７０１は、複数のソートキー部分７０２から構成され、例えば、ソートキー７０１「１２３」の場合、ソートキー部分７０２は、「１」「２」「３」である。尚、各桁の数字の大小がソート順を示す。
【００５６】
ソートキー部分７０２毎に、当該ソートキー部分を共通に有するソートキーの度数７０３、次のソートキー部分へのリンク７０４が付され、これを枝７０５で連結することによりソートキー７０１が構成される。例えば、ソートキー７０１−１「１２３」がソートキー部分「１」「２」「３」から構成され、ソートキー７０１−２がソートキー部分「１」「２」「５」から構成される場合、ソートキー部分「１」「２」について度数「２」が付され、異なるソートキー部分となることろで分岐７０６が形成され、ソートキー部分「３」「５」についてそれぞれ度数「１」が付される。
【００５７】
図８は、ソートキーツリー８００への新規ソートキーの挿入の過程を示す図である。
マスタ１０１の制御部は、順次、ソート対象データのソートキー８１１を読み込み（Ｓ８０１）、ソートキーの先頭部分から、ソートキーツリー８００が既に保持するソートキーとの比較を行い、同一部分は度数をカウントアップし、同一でない部分が現れたところで分岐８１２を生成する（Ｓ８０２）。
【００５８】
マスタ１０１の制御部は、ソートキー全体の分岐数が増大し、メモリ容量が不足する場合、ソートキー追加を一時中断し、数の少ない分岐の末端部分について取り纏め処理を行う（Ｓ８０３）。この場合、取り纏め後のソートキー部分は可変長とし、取り纏めた最大のキーを入れておく。取り纏め後は、当該キーよりも小さいキーがカウントに含まれていることとなる。
【００５９】
図９は、ソートキーツリー９００から分担範囲を決定する過程を示す図である。
マスタ１０１の制御部は、全てのソート対象データのソートキーをソートキーツリー９００に登録すると、ソートキーツリー９００を小さい順に探索しながら、末端（葉）における度数９０１をカウントし、各スレーブ１０２のソートキーの分担数が均等（≒（レコード数）／（参加スレーブ台数））となるように、ソートキーを選択し、各スレーブ１０２の分担範囲を決定する。
【００６０】
図９に示すソートキーツリー９００では、各スレーブ１０２の分担数が均等（「８」＝（ソートキーの総数「２４」）／（参加スレーブ台数「３」））になるように分担範囲が決定される。マスタ１０１の制御部は、スレーブ１０２−１について分担範囲「００００≦ｘ（分担ソートキー）≦１２５２」、分担数「９」、スレーブ１０２−２について分担範囲「１２５２＜ｙ（分担ソートキー）≦２２３０」、分担数「８」、スレーブ１０２−３について分担範囲「２２３０＜ｚ（分担ソートキー）≦３１８５」、分担数「７」と分担範囲を決定する。
【００６１】
以上の過程を経て、マスタ１０１は、ソート対象データについてソートキーツリーを作成してソートキーの度数分布を算出し、ソートキーの分担範囲を各スレーブ１０２毎に均等に割り当てる。
【００６２】
このように、マスタ１０１は、各スレーブ１０２毎にほぼ均等にソートキーの分担範囲を割り当てるので、各スレーブ１０２の処理能力を無駄なく有効活用することにより、迅速かつ効率的な処理を実現することができる。
【００６３】
次に、図１０を参照しながら、各スレーブ１０２における、ソート処理（図４：ステップ４０６）について説明する。
図１０は、インデクス付挿入ソート処理を示す図である。
尚、図１０では、ソートキーを用いてソート処理の実行等が行われるものとして説明する。
【００６４】
ソート処理としては、任意の公知アルゴリズムを用いることができる。以下、並列ソートシステム１００におけるソート処理の一態様として、インデクス付挿入ソート法について説明する。尚、インデクス付挿入ソート法は、順次、ソートキーが転送される場合に有効である。
【００６５】
図１０に示すように、各スレーブ１０２は、ソート処理において、インデクス表１００１及びソート済データリスト１００４を作成する。
インデクス表１００１は、インデクス１００２及びポインタ１００３を保持し、ソート済データリスト１００４において検索を行う際に参照される。
ソート済データリスト１００４は、ソートキー１００５及びポインタ１００６を保持し、ソート処理が施されたソートキーが順に並べられる。
【００６６】
インデクス１００２は、ソート済のソートキーを所定の数毎にブロック化（ブロック１００７）し、当該ブロック中で最大のソートキーを代表としてインデクス表１００１に登録したものである。尚、インデクス１００２は、検索効率を勘案し、抽出したソートキーの存在箇所ではなく、ブロックの先頭を指すポインタ１００３を保持する。
【００６７】
スレーブ１０２の制御部は、ソートキーを挿入する際、インデクス表１００１を参照して、挿入しようとするソートキーより大きいソートキーを検索し、ブロックへの先頭部分へのポインタを得て、インデクスが指し示す位置から順次、大小比較を行い、挿入位置を特定し、挿入処理を行う。
尚、スレーブ１０２の制御部は、ブロック数が所定の数を超えた場合、当該ブロックを分割し、インデクス表１００１を更新する。
【００６８】
次に、図１１を参照しながら、スレーブ１０２における、データ受信処理及びソート処理について説明する。
図１１は、スレーブ１０２の動作を示すブロック図である。
【００６９】
図１１に示すスレーブ１０２は、受信バッファ１１０１、データ受信部１１０２、共有メモリ１１０３、ソート処理部１１０４等を備える。データ受信部１１０２におけるデータ受信処理と、ソート処理部１１０４におけるソート処理とは、別プロセスとし、データの受け渡しは、共有メモリ１１０３上で行われる。
【００７０】
スレーブ１０２のデータ受信部１１０２は、ネットワーク１０３上のソート対象データを受信バッファ１１０１を介して監視し、自身の分担範囲のソート対象データ１１１１を取り込む。
スレーブ１０２のデータ受信部１１０２は、共有メモリ１１０３上の受渡テーブル１１１２の未処理フラグ１１１３がリセット（ＲＥＳＥＴ）されている領域に、順次ソート対象データ１１１４を配置し、未処理フラグ１１１３をセット（ＳＥＴ）する。
尚、フラグとは、２種類の状態を表現するものでセット（ＳＥＴ、「１」等）・リセット（ＲＥＳＥＴ、「０」等）で表現される情報を指す。初期状態では全てリセット状態とする。
【００７１】
スレーブ１０２のソート処理部１１０４は、共有メモリ１１０３上の受渡テーブル１１１２を参照し、未処理フラグのセットされているソート対象データを取得してソート処理を行い、当該メモリ領域について未処理フラグをリセットする。
【００７２】
尚、データ受信部１１０２における処理とソート処理部１１０４における処理は、非同期動作、マルチタスク処理である。また、データ受信部１１０２におけるデータ受信のハードウェア割り込みを最優先とすることが望ましい。
【００７３】
以上の過程を経て、スレーブ１０２は、データ受信処理を優先的に行いつつ、データ受信処理とは別プロセスでソート処理を行う。
このように、スレーブ１０２は、データ受信処理とソート処理とを非同期で行い、データ受信中もソート処理が可能であるので、効率的かつ迅速にソート処理を行うことができる。また、スレーブ１０２は、データ受信処理を最優先させ、データ受信の優先度を上げることにより、データ受信失敗やデータ欠落等を防止することができる。
【００７４】
以上、詳細に説明したように、本発明の実施の形態に係る並列ソートシステムでは、マスタは、ソート対象データのソートキーを生成して各スレーブ毎にソートキーの分担範囲を決定し、各スレーブは、自身の分担範囲にあるソート対象データについてソート処理を行い、ソート対象データは、ブロードキャストによりネットワークに送出され、各スレーブが同時に受信するので、特別な環境を設けることなく、迅速かつ効率的にソート処理を行うことができる。
また、マスタは、各スレーブ毎にほぼ均等にソートキーの分担範囲を割り当てるので、各スレーブの処理能力を無駄なく有効活用することができる。
また、スレーブは、データ受信処理とソート処理とを非同期で行い、データ受信中もソート処理が可能であるので、効率的かつ迅速にソート処理を行うことができる。
【００７５】
尚、図４、図５等では、マスタは、ソート対象データの保持、ソート済データの回収を行い、マスタ自身はソート処理に参加せず、マスタ以外のスレーブが実際のソート処理を行うものとして説明したが、マスタＰＣ以外がデータを保持してもよいし、マスタＰＣ以外がソート済結果を回収するか、あるいは、別の共有ハードディスク等に書き出すようにしてもよい。
また、図２等では、マスタ及びスレーブのネットワーク接続形態に関して、イーサネット（登録商標）等により一般のＰＣ（パーソナルコンピュータ）を接続する形態を説明したが、ＰＣに代えてワークステーションを用い、イーサネット（登録商標）に代えてトークンリング等を用いてもよい。
【００７６】
また、図６〜図９では、ソートキーツリーを用いて分担範囲を決定するものとして説明したが、分担範囲の決定はこれに限られず、いわゆる当業者による様々な変形等が可能である。
分担範囲の決定が全体の処理速度を決める１つのポイントとなるが、これは、様々な手法を採ることができる。最大値・最小値が判明している場合、分割数を１０００〜１００００程度の適度な大きさとし、最大値・最小値間を均等に割付けて度数調査を行い、処理台数で均等になる範囲を選択するようにしてもよい。
最大値・最小値が不明でデータ数が多い場合、ランダムに総数の一部（例えば、１％程度）を読み込み、全体の度数分布を類推するようにしてもよい。この場合、類推される度数分布の最小値以下、最大値以上の項目を加え、類推された範囲で度数を測定すればよい。
【００７７】
また、ソート対象データとしての元データは１箇所で管理されており、ソート結果も１ファイルにまとめるものとして説明したが、データが分散していてもよい。この場合、分散先の処理装置で度数データを生成し、１箇所で加算し、分担範囲を求め、各スレーブに通知する。また、データ送出は、どの処理装置から開始してもよい。
【００７８】
以上、添付図面を参照しながら、本発明に係る並列ソートシステム等の好適な実施形態について説明したが、本発明はかかる例に限定されない。当業者であれば、本願で開示した技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【００７９】
尚、図４、図５等に示す処理を行うプログラムをＣＤ−ＲＯＭ等の記録媒体に保持させて流通させてもよいし、このプログラムを通信回線を介して送受することもできる。
【図面の簡単な説明】
【００８０】
【図１】並列ソートシステム１００の概略構成を示す図
【図２】マスタ１０１及びスレーブ１０２のネットワーク接続の一態様を示す図
【図３】マスタ１０１のハードウェア構成図
【図４】並列ソートにおける、マスタ１０１、スレーブ１０２の動作を示すフローチャート
【図５】並列ソートにおける、マスタ１０１、スレーブ１０２の処理の流れを示す図
【図６】ソート対象データであるレコード６００の一態様を示す図
【図７】ソートキーツリー７００の一態様を示す図
【図８】ソートキーツリー８００への新規ソートキーの挿入の過程を示す図
【図９】ソートキーツリー９００から分担範囲を決定する過程を示す図
【図１０】インデクス付挿入ソート処理を示す図
【図１１】スレーブ１０２の動作を示すブロック図
【符号の説明】
【００８１】
１００………並列ソートシステム
１０１………マスタ
１０２………スレーブ
１０３………ネットワーク
５０１………ソート対象データ（マスタ）
５０２………分担範囲（マスタ）
５０３………ソート済データ（マスタ）
５０４………分担範囲（スレーブ）
５０５………ソート対象データ（スレーブ）
５０６………ソート済データ（スレーブ）
６００………レコード
６０１………ソートキー
６０２………内容
７００、８００、９００………ソートキーツリー
７０１………ソートキー
７０２………ソートキー部分
７０３………度数
７０４………リンク
７０５………枝
７０６………分岐
１１０１………受信バッファ
１１０２………データ受信部
１１０３………共有メモリ
１１０４………ソート処理部
１１１２………受渡テーブル
１１１３………未処理フラグ
【図１】
2006048192.tif 000003
【図２】
2006048192.tif 000004
【図３】
2006048192.tif 000005
【図４】
2006048192.tif 000006
【図５】
2006048192.tif 000007
【図６】
2006048192.tif 000008
【図７】
2006048192.tif 000009
【図８】
2006048192.tif 000010
【図９】
2006048192.tif 000011
【図１０】
2006048192.tif 000012
【図１１】
2006048192.tif 000013