JP2000305751A - 並列ソート装置及び該装置のプログラムを記録した記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】ソートとマージ間でのデータの受け渡しを主記
憶領域上で行うことができ、また、入力ファイルの読み
込み処理中もソート処理の並列実行が可能な並列ソート
装置を提供する。 【解決手段】複数のプロセッサで共有可能な主記憶領域
５と、複数のソート処理スレッド１〜ｍからなり、各ス
レッドが主記憶領域５内の各ブロック毎にソート処理を
実行するソート処理手段３と、外部記憶装置からソート
対象の入力データ１を入力し、複数のブロックに分割し
て主記憶領域５に記憶するとともに、ソート処理手段３
の複数のスレッドによる主記憶領域５内の各ブロックに
対するソート処理を起動する入力処理スレッドを有する
データ入力処理手段２と、ソート処理が終了した主記憶
領域５内の全ブロックのデータに対してマージ処理を行
って、ソート結果を出力するマージ・データ出力処理手
段６とを備えている。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ソート処理を分割
して並列に実行する並列ソート装置に関する。

【０００２】

【従来の技術】ソート処理では、比較数がデータの組み
合わせ数に比例して増減する。したがって、１スレッド
でデータの入出力やソート処理を行っていた従来のソー
ト処理方式ではファイル内のデータが膨大になると、処
理時間がかかりすぎる問題があった。また、データの入
出力時にはデータのソート処理が行われていないため、
プロセッサが使用されていない状態が発生し、プロセッ
サの機能が有効に活用されない問題もあった。

【０００３】

【発明が解決しようとする課題】上記のような問題点を
鑑みて創案されたものとして、並列にソートを行う処理
方式が出てきた。例えば、特開平５−３５４４４号公報
「ソート処理方式」では、図６のようにソート対象ファ
イルを４つに分割し、それぞれを仮想ファイルとする。
次に分割したファイルを４つのソートプログラムで同時
に多重に並列ソートし、さらにソートが行われたデータ
をマージプログラムでマージすることにより全データの
ソートが行われる。この従来技術Ａには次のような欠点
がある。

【０００４】〔問題点Ａ−１〕この従来技術Ａは各ソー
トプログラムによって、各仮想ファイルの読み込みを行
うとともに、ソートを行い、仮想ファイルに書き込む。
次にソート済みの各仮想ファイルのマージを行う。この
時、各ソートプログラムとマージプログラムの受け渡し
は仮想ファイルによって行われるため、仮想ファイルが
外部記憶装置にある場合、主記憶領域と外部記憶装置の
間のデータ転送の時間の遅さによって全体のソートの時
間が遅くなる。また、仮想ファイルへの書き込みがデー
タ入出力用のキャッシュによって遅延書き込みされる場
合においても、キャッシュの空き容量がなくなると書き
込みを行ってキャッシュの空き領域ができるまで待たな
くてはならない。

【０００５】本発明は、以上の問題点を解決することを
第１の目的とし、ソートとマージ間でのデータの受け渡
しを主記憶領域上で行うことができる並列ソート装置を
提供する。

【０００６】次に特開平７−４４３５６号公報「ソート
処理装置および方法」では次の従来技術Ｂが記載されて
いる。図７において、使用可能な２台以上のプロセッサ
が存在する場合には、ソート処理プログラムがコピーさ
れて子タスク１０２が生成され、入力ファイル１５１の
読み込み処理および作業領域内データのトーナメントツ
リー作成処理が親タスク１０１に割り当てられ、再トー
ナメント処理および作業ファイル１５２への書き込み処
理が子タスク１０２に割り当てられる。親タスク１０１
および子タスク１０２は、それぞれ異なる２台のプロセ
ッサによって実行される。メインメモリ１３内の作業領
域は、作業領域１３１と１３２に２分割され、それらが
親タスク１０１および子タスク１０２によって、交互に
使用される。したがって、親タスク１０１と子タスク１
０２の処理が並行して実行され、内部ソート処理を効率
よく並列実行することが可能となる。

【０００７】なお、図７において、符号１０４は、親タ
スク１０１用のタスク制御ブロックであり、親タスク１
０１と作業領域１３１，１３２、および入力バッファ１
３３、１３４との結合を図るポインタや、そのタスクの
状態を管理するための種々の制御情報を持つものであ
る。また、符号１０５は、子タスク１０２用のタスク制
御ブロックであり、子タスク１０２と作業領域１３１，
１３２、および出力バッファ１３５，１３６との結合を
図るポインタや、そのタスクの状態を管理するための制
御情報を持つものである。

【０００８】この従来技術Ｂには次のような欠点があ
る。

【０００９】〔問題点Ｂ−１〕親タスクでの入力ファイ
ルの読み込み処理において、主記憶領域と外部記憶装置
との間のデータ転送時に外部記憶装置のデータ転送速度
が遅い場合、親タスクに割り当てられたプロセッサはデ
ータ転送が終わるまで、処理をしていない状態になり、
この間は実質２台のプロセッサにおいて並列実行が行わ
れていない。

【００１０】本発明では、上記の問題点を解決すること
を第２の目的とし、入力ファイルの読み込み処理中もソ
ート処理の並列実行が可能な並列ソート装置を提供す
る。

【００１１】

【課題を解決するための手段】上記課題を解決するた
め、請求項１記載の発明は、複数のプロセッサを有し、
ソート処理を複数に分割して並列に実行し、終了後マー
ジ処理を行ってソート結果を出力する並列ソート装置に
おいて、複数のプロセッサで共有可能な主記憶領域を有
し、該領域にソート対象のデータを複数のブロックに分
割して記憶する主記憶手段と、並列実行可能な複数の処
理単位からなり、各処理単位が主記憶手段内の各データ
ブロック毎にソート処理を実行するソート処理手段と、
外部記憶装置からソート対象のデータを入力し、複数の
ブロックに分割して主記憶手段に記憶するとともに、ソ
ート処理手段の複数の処理単位に対して主記憶手段内の
各データブロック毎にソート処理を行わさせるデータ入
力処理手段と、ソート処理が終了した主記憶手段内の全
ブロックのデータにマージ処理を行って、ソート結果を
出力するマージ・データ出力処理手段とを備えることを
特徴としている。

【００１２】また、請求項２記載の発明は、前記データ
入力処理手段が、１つのデータブロックを主記憶手段に
記憶する毎に、該記憶したデータブロックに対してソー
ト処理手段の１つの処理単位によるソート処理を起動す
ることによって、データの入力処理と複数のソート処理
とを並列実行することを特徴としている。また、請求項
３記載の発明は、分割したブロックのソート処理とソー
ト済みのブロックのマージ処理との間のデータの受け渡
しを前記主記憶領域を用いて行うことを特徴としてい
る。

【００１３】また、請求項４記載の発明は、請求項１〜
３のいずれか１項に記載の並列ソート装置が、コンピュ
ータシステムとそれによって実行されるプログラムとか
ら実現されるものであって、該プログラムを記録したコ
ンピューター読み取り可能な記録媒体である。

【００１４】すなわち、本発明は、ソート処理を複数の
処理単位（タスク、スレッド等）で並列に実行し、終了
後マージを行ってソートの結果を出す並列ソート装置に
おいて、主記憶領域を複数のプロセッサで共有でき、あ
らかじめ、１個以上のソート処理単位（以下、スレッド
とする）を用意し、データを複数のブロックに分けてお
き、データをブロック単位で主記憶領域に読み込み、読
み込んだブロックのソートはソート専用のスレッドで処
理することによって、データの読み込み処理と複数のソ
ート処理を並行に行うことを可能とする。この時、複数
のソート処理スレッドを用意することにより、データ入
力処理時に例えば周辺装置から主記憶領域へのデータ転
送待ちのプロセッサに、ソート処理を割り当てることが
可能になる。また、本発明によれば、ソート処理とマー
ジ処理の間のデータの受け渡しを主記憶領域で行う構成
を得ることができる。

【００１５】

【発明の実施の形態】以下、図面を参照して本発明の実
施の形態について説明する。図１は、本発明による並列
ソート装置の構成を説明するためのブロック図である。
図１において、データ処理手段２、ソート処理手段３、
全ソート処理終了待ち手段４、およびマージ・データ出
力処理手段６は、それぞれ、複数のプロセッサを有する
コンピュータシステムにおいて管理・実行されるタスク
に対応する。ソート・マージ用主記憶領域５は、コンピ
ュータシステムの主記憶内で割り当てられた所定の記憶
領域であり、そこにはソート処理およびマージ処理の際
に用いられるデータがブロックに分割されて格納され
る。入力データ１と出力データ７は、そのコンピュータ
システムと、外部記憶装置との間で入出力されるデータ
である。なお、コンピュータシステムの主記憶領域は、
複数のプロセッサで共有でき、この場合、主記憶領域の
サイズは入力データ１のサイズより大きいものとする。

【００１６】図１に示すように、本実施の形態では、ま
ず、記憶媒体、例えば外部ディスク装置に存在する入力
データ１をｎ個（ｎは自然数）のブロックに分割する。
また、ソート処理手段３内に、同時に起動可能な複数の
スレッドとして構成されるｍ個のソート処理スレッド１
〜ｍ（ｍは自然数）を用意する。主記憶内には、図３に
示すように、ソート処理の実行状態を示す実行フラグか
らなるソート実行情報１〜ｍ、当該スレッド処理を実行
可能かどうかを示す同期フラグからなる動作情報１〜
ｍ、ソート・マージ用主記憶領域５内のソート対象のデ
ータブロックの開始位置を示す情報であるデータブロッ
クの開始位置１〜ｍ、データブロックの終了位置を示す
情報であるデータブロックの終了位置１〜ｍを、各スレ
ッド１〜ｍごとに格納するソート処理スレッド管理テー
ブルが設定される。

【００１７】データ入力処理手段２は、入力処理スレッ
ドからなり、ブロックごとにデータをソート・マージ用
主記憶領域５に格納する。各ブロックのデータがソート
・マージ用主記憶領域５に格納されたら、ソート処理手
段３により、空いているソート処理スレッドでブロック
ごとにソートを行わせる。例えば、データ入力処理手段
２によって入力データ１のブロック１を読み込んで、ソ
ート・マージ用主記憶領域５にデータを格納し、つぎ
に、ソート処理スレッド１を動かし、データ入力処理手
段２は、すぐ、次のブロックであるブロック２を読み込
み始める。データ入力処理手段２では読み込みブロック
がなくなるまで以上の動作を繰り返す。一方、ソート処
理手段３では、各ソート処理スレッド１〜ｍがデータ入
力処理手段２によって動かされるまで待機中になってい
て、動作状態になると、与えられたブロックのソートを
行い、終了するとまた待機中になる。

【００１８】全ソート処理終了待ち手段４ではソート処
理手段３によるソート・マージ用主記憶領域５の各ブロ
ックのソートの終了を待つ。次にマージ・データ出力処
理手段６は、ソート済みの各ブロックデータをマージし
ながら、マージ後のデータを出力データ７として外部の
記憶装置に書き込む。

【００１９】以上の構成によって、本実施の形態は、図
１において入力データ１をｎ個のブロックに分割し、デ
ータ入力処理手段２の入力処理スレッドによってブロッ
クごとに読み込んで、ソート処理手段３の待機中のソー
ト処理スレッドに渡す。待機中のソート処理スレッドは
入力処理スレッドによってソートの開始を起動され、与
えられたブロックのソートが終了すると、また、待機中
の状態になる。全てのブロックのソートが完了するとマ
ージ・データ出力処理手段６によって全ブロックのマー
ジ処理を行いながら出力データ７へ出力し、ソートを完
了する。

【００２０】次に、図２、図３、図４、および図５を参
照して図１の実施の形態の動作について詳細に説明す
る。まず、記憶媒体、例えば外部ディスク装置に存在す
るソート対象データをｎ個のブロックに分割する。ま
た、ｍ個のソート処理スレッド１〜ｍを用意する。

【００２１】データ入力処理手段２による処理について
図４で説明をする。ステップＳ１において入力データ１
に未入力のブロックがあるかチェックし、あるならば、
ステップＳ２でソート・マージ用主記憶領域５へ読み込
む。ステップＳ３では、図３の各ソート処理スレッドを
管理するソート処理スレッド管理テーブルのソート実行
情報により実行中でないソート処理スレッドを検索す
る。もし、全てのソート処理スレッドが実行中であれ
ば、どれか１つが空きになるまで同期待ちを行う。空き
のスレッドが検索できたら（ここでは一例としてソート
処理スレッド１のソート実行情報１が実行中でなかった
とすると）、ステップＳ４で読み込んだブロックの開始
位置１とブロックの終了位置１の情報をソート処理スレ
ッド管理テーブルにセットする。ステップＳ５では、ソ
ート管理テーブルのソート実行情報１を実行状態にセッ
トし、動作情報１を動作可能状態にセットする。以上の
ステップＳ１からステップＳ５までの処理を未入力のブ
ロックがなくなるまで繰り返し続ける。そして、未入力
のブロックがなくなると全ソート終了待ち手段４へ処理
を移行する。

【００２２】次に、ソート処理手段３による処理につい
て図５を参照して説明する。ソート処理手段３ではあら
かじめ、それぞれが図５のように動作するソート処理ス
レッドをｍ個起動しておく。図５において、例えばソー
ト処理スレッド１の場合、ソート処理スレッド１は、ス
テップＳ６では最初にソート処理スレッド管理テーブル
の初期化を行い、ステップＳ７で動作情報１が動作可能
状態になるまで同期待ちを行う。そして、先に説明した
ようにデータ入力処理手段２によってブロックの読み込
みが行われ、ソートの準備が整うと、動作情報１が動作
可能状態にされ、ソート処理スレッド１は、次にステッ
プＳ８で読み込んだソート処理スレッド管理テーブルの
ブロックの開始位置１とブロックの終了位置１の各情報
に基づいてブロックのソートを行う。このときソート済
みの各ブロックのデータはソート・マージ用主記憶領域
５に格納されている。ソートが終了すると、ステップＳ
９でソート実行情報１を実行中でない状態にし、動作情
報１を動作できない状態にする。この後、また、ステッ
プＳ７で動作情報１が動作状態になるのを待ち、ステッ
プＳ７からステップＳ９までの処理を繰り返す。

【００２３】上記の構成によれば、データ入力処理手段
２とソート処理手段３は、図２のようにデータ入力とソ
ート処理を並列に実行する。なお、図２は、ブロック数
ｎを４、スレッド数ｍを３とした場合を一例として示し
たものである。

【００２４】全ソート終了待ち手段４では各ソート処理
スレッドのソート処理スレッド管理テーブルのソート実
行情報が全て実行状態でない状態になるまで同期待ちを
行う。そして実行フラグが全てオフになったらマージ・
データ出力処理手段６へ移行する。

【００２５】次にマージ・データ出力処理手段６では、
ソート・マージ用主記憶領域５にあるソート済みの各ブ
ロック１〜ｎをマージし、出力データ７としてデータの
書き込みを行う。

【００２６】上述した実施の形態によれば、入力データ
のサイズより主記憶領域のサイズが大きいコンピュータ
システム上において、第一に、図２のようにデータ入力
処理スレッドとソート処理スレッドを並列で実行するた
め、入力処理とソート処理を非同期に実行でき、入力処
理時に外部記憶装置から主記憶領域へのデータ転送待ち
でプロセッサが空き状態なってもソート処理スレッドへ
プロセッサを割り当てることができる。 第２に、図１
のようにソート処理手段３とマージ・データ出力処理手
段６の間のデータの受け渡しはソート・マージ用主記憶
領域５を使用して行うため、外部記憶装置を使用してデ
ータの受け渡しを行う場合と比べて主記憶領域と外部記
憶装置との間のデータ転送の時間を削減できるので高速
にデータの受け渡しを行うことができる。以上の効果に
よってソート処理全体の高速化を図ることができる。

【００２７】なお、本発明の実施の形態は、上記のもの
に限定されることなく、例えば、ソート処理を並列実行
するための処理単位を、スレッドではなく、タスクとす
る（すなわちソート処理手段自体を複数設ける）等、図
１の各手段２、３、４、および６をより分割したり、あ
るいは統合したりする等の変更が適宜可能である。ま
た、本発明による並列ソート装置は、コンピュータシス
テムとそれによって実行されるプログラムとによって実
現することができ、そのプログラムはコンピューター読
み取り可能な記録媒体に記録して配布することが可能で
ある。

【００２８】

【発明の効果】以上説明したように、本発明のソート装
置によれば、ソートとマージ間でのデータの受け渡しを
主記憶領域上で行うことができ、また、入力ファイルの
読み込み処理中もソート処理の並列実行が可能となるの
で、従来に比べ、ソート処理に要する時間の短縮やリソ
ースの低減を図ることができる。

【図面の簡単な説明】

【図１】 本発明による並列ソート装置を説明するため
のブロック図

【図２】 図１に示す入力処理スレッドとソート処理ス
レッドの動作を示すタイミング図

【図３】 図１の並列ソート装置で用いられるソート処
理スレッド管理テーブルを示す図

【図４】 図１のデータ入力処理手段２の動作を示すフ
ローチャート

【図５】 図１のソート処理手段３内の各ソート処理ス
レッドの動作を示すフローチャート

【図６】 従来のソート装置の一例を示すブロック図

【図７】 従来のソート装置の他の例を示すブロック図

【符号の説明】

１ 入力データ ２ データ入力処理手段 ３ ソート処理手段 ４ 全ソート処理終了待ち手段 ５ ソート・マージ用主記憶領域 ６ マージ・データ出力処理手段 ７ 出力データ

Claims (4)

【特許請求の範囲】
1. 【請求項１】 複数のプロセッサを有し、ソート処理を
   複数に分割して並列に実行し、終了後マージ処理を行っ
   てソート結果を出力する並列ソート装置において、 複数のプロセッサで共有可能な主記憶領域を有し、該領
   域にソート対象のデータを複数のブロックに分割して記
   憶する主記憶手段と、 並列実行可能な複数の処理単位からなり、各処理単位が
   主記憶手段内の各データブロック毎にソート処理を実行
   するソート処理手段と、 外部記憶装置からソート対象のデータを入力し、複数の
   ブロックに分割して主記憶手段に記憶するとともに、ソ
   ート処理手段の複数の処理単位に対して主記憶手段内の
   各データブロック毎にソート処理を行わさせるデータ入
   力処理手段と、 ソート処理が終了した主記憶手段内の全ブロックのデー
   タにマージ処理を行って、ソート結果を出力するマージ
   ・データ出力処理手段とを備えることを特徴とする並列
   ソート装置。
2. 【請求項２】 前記データ入力処理手段が、１つのデー
   タブロックを主記憶手段に記憶する毎に、該記憶したデ
   ータブロックに対してソート処理手段の１つの処理単位
   によるソート処理を起動し、 データの入力処理と複数のソート処理とを並列に実行す
   ることを特徴とする請求項１記載の並列ソート装置。
3. 【請求項３】 分割したブロックのソート処理とソート
   済みのブロックのマージ処理との間のデータの受け渡し
   を前記主記憶領域を用いて行うことを特徴とする請求項
   １記載の並列ソート装置。
4. 【請求項４】 請求項１〜３のいずれか１項に記載の並
   列ソート装置が、コンピュータシステムとそれによって
   実行されるプログラムとから実現されるものであって、
   該プログラムを記録したコンピューター読み取り可能な
   記録媒体。