JPH0744356A - ソート処理装置および方法 - Google Patents

Abstract

(57)【要約】 【目的】内部ソート処理を２分割してそれらを並列実行
できるようにし、ソート処理の高速化を図る。 【構成】使用可能な２台以上のＣＰＵが存在する場合に
は、ソート処理プログラムがコピーされて子タスク１０
２が生成され、入力ファイル１５１の読み込み処理およ
び作業領域内データのトーナメントツリー作成処理が親
タスク１０１に割り当てられ、再トーナメント処理およ
び作業ファイル１５２への書き込み処理が子タスク１０
２に割り当てられる。親タスク１０１および子タスク１
０２は、それぞれ異なる２台のＣＰＵによって実行され
る。作業領域は作業領域１３１と１３２に２分割され、
それらが親タスク１０１および子タスク１０２によって
交互に使用される。したがって、親タスク１０１と子タ
スク１０２の処理が並行して実行され、内部ソート処理
を効率良く並列実行することが可能となる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明はソート処理装置および
方法に関し、特に１以上のプロッセッサとこれらプロセ
ッサによった共有される主記憶とを有するコンピュータ
システムにおいて内部ソートを行うソート処理装置およ
びソート方法に関する。

【０００２】

【従来の技術】一般に、ソート処理は、内部ソート処理
と外部ソート処理の２種類により構成される。このう
ち、内部ソート処理は、入力ファイルのデータを昇順ま
たは降順に整列化してソートストリングを作成する処理
である。また、外部ソート処理は、内部ソート処理によ
って作成された複数のソートストリングをマージしてソ
ート結果を得る処理である。

【０００３】コンピュータシステムにおいてはソート対
象の入力ファイルはディスク装置などの２次記憶に格納
されているので、前述の内部ソート処理をＣＰＵによっ
て行う場合には、その内部ソート処理は、２次記憶から
主記憶の作業領域に入力ファイルを入力する入力フェー
ズと、その入力データからトーナメントツリーを作成し
た後に再トーナメントを行って整列化されたソートスト
リングを作成するソートフェーズと、その作成されたソ
ートストリングを２次記憶の作業ファイルに出力する出
力フェーズに分類される。

【０００４】従来では、これら入力フェーズ、ソートフ
ェーズおよび出力フェーズは１つのプログラムによって
実行管理されているので、それら処理は１つのＣＰＵに
よってシリアルに実行されていた。なぜなら、通常は、
１つのプログラムには１つのＣＰＵが割り当てられて処
理が実行されるためである。

【０００５】このため、従来では、たとえ複数のプロセ
ッサを持つコンピュータシステムであっても、ソート処
理を並列に実行することができず、ソート処理に時間が
かかる欠点があった。

【０００６】

【発明が解決しようとする課題】従来では、内部ソート
処理の入力フェーズ、ソートフェーズおよび出力フェー
ズが１つのＣＰＵによってシリアルに実行されており、
たとえ複数のプロセッサを持つコンピュータシステムで
あっても、その内部ソート処理を並列に実行することが
できずソート処理に時間がかかる欠点があった。

【０００７】この発明はこのような点に鑑みてなされた
もので、内部ソート処理を並列処理可能な２つの処理に
分割し、それらを異なる２つのプロセッサに割り当てる
ことによって内部ソート処理を並列実行できるように
し、ソート処理の高速化を実現できるソート処理装置お
よび方法を提供することを目的とする。

【０００８】

【課題を解決するための手段および作用】この発明は、
１以上のプロッセッサとこれらプロセッサによった共有
可能なメモリとを有するコンピュータシステムのソート
処理装置において、使用可能なプロッセッサ数を検出
し、少なくとも第１および第２の２台のプロセッサが使
用可能の際にソート処理の並列処理が可能であることを
検出する手段と、並列処理が可能であることが検出され
た際、入力ファイルからソート対象のファイルを作業領
域に入力してトーナメントツリーを作成する第１処理、
およびその作成されたトーナメントツリーを再トーナメ
ント処理してソートストリングを作成しそれを作業領域
から作業ファイルに出力する第２処理をそれぞれ前記第
１および第２プロセッサに実行させる手段と、前記第１
および第２プロセッサによる前記第１および第２処理が
並行して実行されるように、前記共有メモリの作業領域
を２分割してその分割された一方および他方をそれぞれ
交互に前記第１および第２プロセッサに割り当てる手段
とを具備することを特徴とする。

【０００９】このソート処理装置においては、２台以上
のプロセッサが存在する場合には、内部ソート処理が、
入力ファイルの読み込み処理および作業領域内データの
トーナメントツリー作成処理から構成される第１処理
と、再トーナメント処理および作業ファイルへの書き込
み処理から構成される第２処理に分割され、それら第１
および第２処理がそれぞれ第１および第２の２台の異な
るプロセッサに割り当てられて実行される。また、作業
領域が２分割され、それそらが第１および第２のプロセ
ッサによって交互に使用される。したがって、例えば第
１作業領域を利用して第２プロセッサが第２処理を実行
している間に、第２作業領域を利用して第１プロセッサ
が第１処理を行うことができ、内部ソート処理を並列実
行することが可能となる。

【００１０】

【実施例】以下、図面を参照してこの発明の実施例を説
明する。図１にはこの発明の一実施例に係わるソート処
理装置が実現されるコンピュータシステムの構成が示さ
れている。ここでは、２台のＣＰＵを含むマルチプロセ
ッサシステムを利用した場合を例にとってその構成を説
明する。

【００１１】すなわち、このマルチプロセッサシステム
は、システムバス１０、第１および第２の２台のＣＰＵ
１１，１２、メインメモリ１３、Ｉ／Ｏチャネル１４、
および磁気ディスク装置１５から構成されている。

【００１２】ＣＰＵ１１およびＣＰＵ１２はメインメモ
リ１３を共有し、そのメインメモリ１３に格納されたプ
ログラムを実行する。これらＣＰＵ１１，１２はそれぞ
れ独立して動作することができ、一方に障害が発生して
いる場合には他方のＣＰＵのみによって全ての処理が実
行される。また、これらＣＰＵ１１，１２各々の障害発
生状況や、ビジーステータス、およびアイドルステータ
スは、メインメモリ１３に格納されているオペレーティ
ングシステムによって管理されており、それらステータ
スはアプリケーションプログラムによって参照可能であ
る。

【００１３】メインメモリ１３はＣＰＵ１１およびＣＰ
Ｕ１２によってアクセス可能な共有メモリであり、そこ
には、ソート処理プログラムを初めとする実行対象の各
種プログラムや前述のオペレーティングシステムが格納
される。また、メインメモリ１３はそれらプログラムの
作業領域としても利用され、各種処理データが格納され
る。

【００１４】ソート処理プログラムを２台のＣＰＵ１１
およびＣＰＵ１２によって実行する場合には、それら２
台のＣＰＵの並行処理を可能とするために、図示のよう
に、メインメモリ１３の作業領域は第１および第２の２
つの作業領域１３１，１３２に分割される。また、メイ
ンメモリ１３には、第１および第２の２つの入力バッフ
ァ１３３，１３４、および第１および第２の２つの出力
バッファ１３３，１３４が定義される。２つの入力バッ
ファ１３３，１３４は、磁気ディスク装置１５の入力フ
ァイル１５１からの一方の入力バッファへのデータ入力
と、他方の入力バッファから作業領域へのデータ入力と
を並行して行うためのものである。同様に、２つの出力
バッファ１３３，１３４は、作業領域から一方の出力バ
ッファへのデータ出力と、他方の出力バッファから磁気
ディスク装置１５の作業ファイル１５２へのデータ出力
とを並行して行うためのものである。

【００１５】Ｉ／Ｏチャネル１４は、ＣＰＵ１１または
１２からのＩ／Ｏ要求に応じて磁気ディスク装置１５か
らのデータ読み出しおよび書き込みを行う。磁気ディス
ク装置１５には、ソート対象のファイルデータが保持さ
れる入力ファイル１５１、内部ソート処理で得られたソ
ートストリング列が保持される作業ファイル１５２、お
よびソートストリング列のマージなどによって得られた
ソート結果が保持される出力ファイル１５３が含まれて
いる。

【００１６】このシステムにおいてソート処理プログラ
ムを実行する場合、内部ソート処理は次のように行われ
る。すなわち、内部ソート処理は入力ファイル１５１の
データを昇順または降順に整列化してソートストリング
を作成する処理であるが、ここでは、この内部ソート処
理は、入力ファイル１５２からのデータ入力処理および
作業領域内データのトーナメントツリー作成処理から構
成される第１処理と、作業領域内データの再トーナメン
ト処理および作業ファイル１５２へのソートストリング
出力処理から構成される第２処理とに２分割される。第
１処理はＣＰＵ１１，１２の一方によって実行され、第
２処理はＣＰＵ１１，１２の他方によって実行される。

【００１７】ここで、第２処理はソート処理プログラム
をコピーすることによって得られる子タスクの処理であ
り、第１処理はそのコピー元の親タスクの処理である。
親タスクは、ＣＰＵ１１に割り当てられる。ＣＰＵ１１
は、まず、入力ファイル１５１からのデータ読み込みを
指示する命令を実行して、Ｉ／Ｏチャネル１４に入力フ
ァイル１５１のデータを入力バッファ１３４に転送させ
る。入力バッファ１３４が一杯になると、入力バッファ
１３３と１３４が切り替えられ、入力ファイル１５１の
データは入力バッファ１３３に転送され始める。ＣＰＵ
１１は、入力バッファ１３４，１３３から交互にデータ
を読み込んで作業領域１３１が一杯になるまでデータを
入力し、トーナメントツリーの作成処理を実行する。

【００１８】トーナメントツリー作成処理とは、入力さ
れた１組のレコード単位で所定のキーフィールドのキー
値を順次比較してマージし、最もキー値の大きい（また
は、小さい）レコードを選出する処理であり。これによ
って作成された中間ソート結果はトーナメントツリーと
称される。

【００１９】次に、ＣＰＵ１１によって使用される作業
領域が作業領域１３１から作業領域１３２に切り替えら
れ、今度は、その作業領域１３２が一杯になるまで入力
ファイル１５１からデータが入力されて、トーナメント
ツリーが作成される。これと同時に、子タスクが割り当
てられたＣＰＵ１２は、作業領域１３１のデータの再ト
ーナメント処理を行ってソートストリングを作成する。
ここで、再トーナメント処理は、トーナメントツリーの
データを再び１組のレコード単位でマージし、第２番
目、第３番目、……、にキー値の大きい（または、小さ
い）レコードを順次選出する処理である。そして、ＣＰ
Ｕ１２は、そのソートストリングを２つの出力バッファ
１３５，１３６に交互に出力すると共に、作業ファイル
１５２へのデータ書き込みを指示する命令を実行して、
Ｉ／Ｏチャネル１４に出力バッファから作業ファイル１
５２へのデータ転送を実行させる。

【００２０】このように、ＣＰＵ１２が作業領域１３２
を利用して第２処理（再トーナメント処理および出力処
理）を実行している間に、作業領域１３１を利用してＣ
ＰＵ１１が第１処理（入力処理およびト−ナメントツリ
ー作成処理）を行うことができるので、内部ソート処理
は、図２のタイミングチャートに示されているように、
ＣＰＵ１１，１２によって並列に実行される。

【００２１】次に、図３を参照して、内部ソート処理を
並列実行するための親タスクと子タスクとの関係を説明
する。前述したように、ソート処理プログラムは、子タ
スクを生成する機能を持つ。これは、ソート処理プログ
ラム内に、自身をコピーを作成するプログラム命令を用
意することによって実現される。この場合、コピー元の
タスクが親タスク１０１として機能し、コピー先のタス
クが子タスク１０２として機能する。これら２つのタス
クは、それぞれ自分が親タスクであるか子タスクである
かを判別するためのプログラム命令を持つ。親タスク１
０１は子タスク１０２の処理を待つプログラム命令を持
ち、同様に子タスク１０２も親タスク１０１の処理を待
つプログラム命令を持つ。親タスク１０１は、子タスク
１０２を消滅させるためのプログラム命令を持ってい
る。さらに、子タスク１０２は、親タスク１０１のソー
ト処理制御用データと作業領域を共有することができ
る。

【００２２】親タスク１０１は、子タスク１０２を生成
した後、入力ファイル１５１からデータを読み込み作業
領域１３１，１３２の一方を交互に使用してトーナメン
トツリー作成処理を行う。子タスク１０２は、作業領域
１３１，１３２の他方を交互に使用し、その作業領域内
で再トーナメント処理を行って整列化されたソートスト
リングを作成し、それを作業ファイル１５２に出力する
処理を行う。

【００２３】ソート処理制御用データセグメント１０３
は、親タスク１０１および子タスク１０２によって共有
可能なデータ領域であり、その領域内のデータは親タス
ク１０１と子タスク１０２のどちらからでも参照／更新
可能である。

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

【００２５】これらタスク制御ブロック１０４，１０５
により、２分割された２つの作業領域１３１，１３２の
一方が親タスク１０１、他方が子タスク１０２に割り当
てられ、そして、その割り当てが交互に切り替えられ
る。

【００２６】次に、図４および図５を参照して、ソート
処理プログラムによって実行されるソート処理全体の手
順を説明する。まず、ソート処理プログラムは、ＣＰＵ
１１またはＣＰＵ１２のいずれか一方によって実行さ
れ、そのコンピュータシステムにおけるＣＰＵの情報を
オペレーティングシステムから入手する（ステップＳ１
１）。この処理では、このコンピュータシステム内に存
在するＣＰＵの数、それらＣＰＵの動作状態（イネーブ
ル／アイドル）、障害発生状況等が調べられ、並列ソー
ト処理が可能か否か、すなわち２台以上のプロセッサを
同時使用可能であるか否かが判断される（ステップＳ１
２）。

【００２７】例えばＣＰＵ１２が他のプロセスを実行中
でビシーである場合には、２台のＣＰＵ１１，１２が存
在してもそれらを同時使用することができないので、並
列ソート処理は不可能であると判断される。この場合に
は、通常通り、１台のＣＰＵによって内部ソート処理が
行われ、入力処理、トーナメントツリー作成処理、再ト
ーナメント処理、出力処理がシリアルに実行される（ス
テップＳ１３）。

【００２８】一方、ＣＰＵ１１，１２を同時使用するこ
とができる場合には、並列ソート処理は不可能であると
判断され、以下の処理が行われる。すなわち、まず、子
タスク１０２の生成処理が行われる（ステップＳ１
４）。この処理では、ソート処理プログラムがコピーさ
れる。そして、コピー元のプログラムとコピー先のプロ
グラム間で作業領域１３１，１３２、およびソート処理
制御データセグメント１０３を共有できるようにし、そ
れらをタスクとして動作可能にする。この場合、コピー
元のプログラムは親タスク１０１、コピー先のプログラ
ムは子タスク１０２となり、それらは図３に示すように
各種資源と結合される。これは、親タスク１０１および
子タスク１０２の２つのプログラムがそれぞれＣＰＵ１
１，１２によって同時実行されている状態である。

【００２９】次いで、これら親タスク１０１および子タ
スク１０２の２つのプログラムは、それぞれ自分が親タ
スクであるか否かを判断するプログラム命令を実行し
（ステップＳ１５）、親タスクであれば、まず、入力フ
ァイルの入力準備処理（ステップＳ１６）を行う。この
入力準備処理では、親タスク１０１は、入力ファイル１
５１に対応するファイル管理情報を参照してファイル内
データの分割や転送命令の発行回数等を決定する。次
に、親タスク１０１は、第１の作業領域１３１にデータ
を入力してそれが一杯になったらトーナメントツリーを
作成する処理を行う（ステップＳ１７）。

【００３０】一方、子タスクであれば、まず、作業ファ
イル１５２の割り当て処理、および作業ファイルの準備
処理を行う（ステップＳ１８）。すなわち、子タスク１
０２は、作業ファイル１５２として使用するディスク装
置１５内の記憶領域を確保すると共に、その作業ファイ
ル１５２への転送命令の発行回数等を決定する。

【００３１】次に、親タスク１０１および子タスク１０
２の２つのプログラムは、それぞれ図４に示すステップ
Ｓ１９〜Ｓ２２のループ処理に移行する。ここで、図中
のｍ，ｎはそれぞれ作業領域の番号１または２を示すも
のであり、最初はｍ＝２、ｎ＝１であり、次のループで
はｍ＝１、ｎ＝２に切り替わる。この切り替わりは、ル
ープ毎に繰り返し行われる。

【００３２】すなわち、親タスクであれば、まず、第２
の作業領域１５２が一杯なるまで入力ファイル１５１か
らデータを入力し、そしてトーナメントツリーを作成す
る（ステップＳ２０，Ｓ２１）。そして、全てのソート
ストリング作成が終了、つまり入力対象のデータが無く
なるまで、使用する作業領域を切り替えながらデータ入
力処理およびトーナメントツリー作成処理を繰り返す。

【００３３】一方、子タスクであれば、まず、第１の作
業領域１５１のトーナメントツリーを再トーナメントす
ることによって整列化されたソートストリングを作成
し、それを作業ファイル１５２に出力する（ステップＳ
２２）。そして、全てのソートストリング作成が終了す
るまで、使用する作業領域を切り替えながら再トーナメ
ント処理および出力処理を繰り返す。

【００３４】全てのソートストリング作成が終了すると
（ステップＳ１９）、親タスク１０１は、子タスク１０
２を消滅させた後（ステップＳ２３，Ｓ２４）、処理を
完了する。

【００３５】以上のように、この実施例においては、使
用可能な２台以上のＣＰＵ１１，１２が存在する場合に
は、ソート処理プログラムがコピーされて子タスク１０
２が生成され、入力ファイル１５１の読み込み処理およ
び作業領域内データのトーナメントツリー作成処理が親
タスク１０１に割り当てられ、再トーナメント処理およ
び作業ファイル１５２への書き込み処理が子タスク１０
２に割り当てられる。そして、それら親タスク１０１お
よび子タスク１０２は、それぞれＣＰＵ１１およびＣＰ
Ｕ１２によって実行される。また、作業領域が作業領域
１３１と１３２に２分割され、それらが親タスク１０１
および子タスク１０２によって交互に使用される。

【００３６】したがって、例えば第１作業領域１３１を
利用して子タスク１０２が再トーナメント処理および作
業ファイル１５２への書き込み処理を行っている間に、
第２作業領域１３２を利用して親タスク１０１が入力フ
ァイル１５１の読み込み処理および作業領域内データの
トーナメントツリー作成処理を行うことができ、内部ソ
ート処理を効率良く並列実行することが可能となる。

【００３７】

【発明の効果】以上のように、この発明によれば、内部
ソート処理を並列処理可能な２つの処理に分割し、それ
らを異なる２つのプロセッサに割り当てることによって
内部ソート処理を並列実行できるようになり、ソート処
理の高速化を実現することが可能となる。

【図面の簡単な説明】

【図１】この発明の一実施例に係わるコンピュータシス
テムの構成を示すブロック図。

【図２】同実施例のシステムで実行される内部ソート処
理の並列動作を説明するタイミングチャート。

【図３】同実施例のシステムで内部ソート処理を並列実
行するための親タスクと子タスクとの関係を示す図。

【図４】同実施例のシステムにおいて親タスクおよび子
タスクによって実行される内部ソート動作の手順の一部
を説明するフローチャート。

【図５】同実施例のシステムにおいて親タスクおよび子
タスクによって実行される内部ソート動作の残りの手順
を説明するフローチャート。

【符号の説明】

１１，１２…ＣＰＵ、１３…メインメモリ、１４…Ｉ／
Ｏチャネル、１５…ディスク装置、１０１…親タスク、
１０２…子タスク、１３１…第１作業領域、１３２…第
２作業領域、１５１…入力ファイル、１５２…作業ファ
イル。

Claims (3)

【特許請求の範囲】
1. 【請求項１】 １以上のプロッセッサとこれらプロセッ
   サによって共有可能なメモリとを有するコンピュータシ
   ステムのソート処理装置において、 使用可能なプロッセッサ数を検出し、少なくとも第１お
   よび第２の２台のプロセッサが使用可能の際にソート処
   理の並列処理が可能であることを検出する手段と、 並列処理が可能であることが検出された際、入力ファイ
   ルからソート対象のファイルを作業領域に入力してトー
   ナメントツリーを作成する第１処理、およびその作成さ
   れたトーナメントツリーを再トーナメント処理してソー
   トストリングを作成しそれを作業領域から作業ファイル
   に出力する第２処理をそれぞれ前記第１および第２プロ
   セッサに実行させる手段と、 前記第１および第２プロセッサによる前記第１および第
   ２処理が並行して実行されるように、前記共有メモリの
   作業領域を２分割してその分割された一方および他方を
   それぞれ交互に前記第１および第２プロセッサに割り当
   てる手段とを具備することを特徴とするソート処理装
   置。
2. 【請求項２】 １以上のプロッセッサとこれらプロセッ
   サによって共有可能なメモリとを有するコンピュータシ
   ステムにおけるソート処理方法において、 使用可能なプロッセッサ数を検出し、少なくとも第１お
   よび第２の２台のプロセッサが使用可能の際にソート処
   理の並列処理が可能であることを検出し、 並列処理が可能であることが検出された際、入力ファイ
   ルからソート対象のファイルを作業領域に入力してトー
   ナメントツリーを作成する第１処理、およびその作成さ
   れたトーナメントツリーを再トーナメント処理してソー
   トストリングを作成しそれを作業領域から作業ファイル
   に出力する第２処理をそれぞれ前記第１および第２プロ
   セッサに実行させ、 前記第１および第２プロセッサによる前記第１および第
   ２処理が並行して実行されるように、前記共有メモリの
   作業領域を２分割してその分割された一方および他方を
   それぞれ交互に前記第１および第２プロセッサに割り当
   てることを特徴とするソート処理方法。
3. 【請求項３】 １以上のプロッセッサとこれらプロセッ
   サによって共有可能なメモリとを有するコンピュータシ
   ステムのソート処理方法において、 使用可能なプロッセッサ数を検出し、少なくとも第１お
   よび第２の２台のプロセッサが使用可能の際にソート処
   理の並列処理が可能であることを検出し、 並列処理が可能であることが検出された際、１つのソー
   ト処理プログラムをコピーすることによって親タスクと
   子タスクの２つのタスクを生成して、親タスクには入力
   ファイルからソート対象のファイルを作業領域に入力し
   てトーナメントツリーを作成する第１処理、子タスクに
   は作成されたトーナメントツリーを再トーナメント処理
   してソートストリングを作成しそれを作業領域から作業
   ファイルに出力する第２処理を割り当て、 前記親タスクおよび子タスクを前記第１および第２プロ
   セッサに実行させ、 前記第１および第２プロセッサによる前記第１および第
   ２処理が並行して実行されるように、前記共有メモリの
   作業領域を２分割してその分割された一方および他方を
   それぞれ交互に前記親タスクおよび子タスクに使用させ
   ることを特徴とするソート処理方法。