JPH02227725A - 区画分割方法及び装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、ソートされた複数のリストを複数の処理装置
を使ってマージする方式、特にリストの最終的なソート
及びマージの間に全ての処理装置を利用するための、ソ
ートされたリストの効率的な分割に関する。

Ｂ、従来技術 ソート過程全体の間に複数の処理装置を最大限に利用し
てリストを昇順又は降順にソートする事は、多くの研究
の対象になってきた。Ｐ個の処理装置の各々で個々にソ
ートを行なうために、Ｎ個の要素のリストをＰ個のほぼ
等しいサイズのリストに最初に分割するのは比較的単純
なプロセスである。これらのリストがソートされると、
それらは１つのリストにマージされなければならない。

このマージを行なうのに必要な時間は処理装置の数Ｐに
関して線形である（即ち２台の処理装置は１台の処理装
置の２倍の性能を示し、４台の処理装置は１台の処理装
置の４倍の性能を示す）事が望ましい。言い換えると、
Ｐ個の処理装置を用いて全部でＮ個の要素をマージすべ
き場合、マージするための時間はＮ／Ｐに比例すべきで
ある。これは、従来技術が陥った一つの困難である。最
も効率的な従来の方法を用いてマージを行なう時間はＮ
　／　Ｐ　＊ｌｏｇ２Ｐに比例している。説明のために
、コンピュータ・システムが２処理装置から４処理装置
に増強された時にマージ性能になにが起きるかを考察す
る。もしマージ性能が線形であれば、２倍の性能の増加
によりマージ時間はＮ／２からＮ／４になるであろう。

もしマージ性能がＮ／Ｐ＊Ｉｏｇ２Ｐであれば、マージ
時間はＮ　／　２　＊ｌ　０ｇ２２Ｎ／２＊１　　＝　
Ｎ／２からＮ／４”’ｌｏｇ２４　＝　Ｎ／４＊２　＝
　Ｎ／２に変化し、２つの付加的な処理装置が使われた
にもかかわらず、性能の向上は存在しない。

Ａｋｌ、　Ｓ、　Ｇ、、及び５ａｎｔｒｏｏ、　Ｎ−＋
著”ＯｐｔｉｍａｌＰａｒａｌｌｅｌ　　Ｍｅｒｇｉｎ
ｇ　　ａｎｄ　　Ｓｏｒｔｉｎｇ　　Ｗｉｔｈｏｕｔ　
　ＭｅｍｏｒｙＣｏｎｆｌｉｃｔｓ”、　　ＩＥＥＥ　
Ｔｒａｎｓ、　　ｏｎ　Ｃｏｍｐｕｔｅｒｓ、　　Ｖｏ
ｌ。

Ｃ３６，Ｎｏ、　１１．　Ｎｏｖ、　１９８７．　ｐｐ
、　１３６７−６９は、同時に２つのリストに作用し、
２つのリスト中のある値よりも小さな要素の数の和が２
つのリスト中のその値よりも大きな要素の数の和に等し
いような値を見つけ出す事を開示している。従って、２
つのリストをその値の所で分割し、その分割点以下のリ
ストの組合せを１つの処理装置がソートし、その分割点
以上のリストの組合せを他の処理装置がソートするよう
にする事は単純な事である。２つのリストは、次に、正
しい順序にソートされた新しいリストを形成するために
連結される。もし一 ２よりも多くのリストが存在するならば、処理は各リス
ト対に関して同時に行なわれ、半数のリストがそのまま
残される。これらのリストは、再び分割され、」１記の
ようなリストの２つの対を生成するが、マージすべきリ
ストの数は元の半分なので、リストの２つの対の各々は
さらに他の時間に分割されなければならず、従ってリス
トの十分な対が、全ての処理装置をビジーに保つのため
に利用可能である。リストの対は最初に半分に分割され
、次りこ各々の半分は１／４及び３／４の分割を生成す
るように分割される。従って、各処理装置はマージすべ
きリストの対を有する。最終的にソートされたリストを
形成するためには複数のマージ・フェーズが必要なので
、これは明らかに不十分である。もし各処理装置が１回
だけのマージ・フェーズを行なう事ができるように全て
のリストを１回でＰ個の区画に分割する事が可能であれ
ば、大幅な性能の改善が生じ、マージされた区画の１回
の連結により、所望のソートされたリストを形成する事
ができる。これは、サンプル・ソート・キーに基ずいて
分割を行なう事により試みられてきた。他の参考文献Ｑ
ｕｉｎｎ、　Ｍ、　Ｊ、、　”ＰａｒａｌｌｅｌＳｏｒ
ｔｉｎｇ　　Ａｌｇｏｒｉｔｈｍｓ　　ｆｏｒ　　Ｔｉ
ｇｈｔｌｙ　　ＣｏｕｐｌｅｄＭｕｌｔｉ−ｐｒｏｃｅ
ｓｓｏｒｓ、　　Ｐａｒａｌｌｅｌ　　ＣｏｍｐｕＬｉ
ｎｇ、　　６゜１９８ｇ、　ｐｐ、　３４９−３６７は
、マージすべき最初のリストから、分割キー値を、それ
らのキーが最初のリストをＰ個の区画に分割するように
、選択する。

次に、それらのキーは、残りのリストを可能な限りサン
プル・キー値に近く分割するために使われる。これは、
近似的な分割による処理装置間の負荷の不平衡を生じ、
またそれに対応して線形のマージ性能からの劣化を生じ
る。さらに、もしリスト中のデータがランダムな分布か
らずれている場合（これはリレーショナル・データベー
スの操作において普通に生しる）、結果的に得られた近
似的な分割はサイズが大きく異なっている可能性が有り
、従って負荷の不平衡の問題を悪化させる。

またランダムに分布されたデータの場合であっても、ｉ
　ｏｏｏｏ件のレコードをソートする時、１０以上の処
理装置を用いても性能が向上しない事が文献に示されて
いる。これは近似的な分割区画化から生じる不平衡によ
るものである。

Ｃ６発明が解決しようとする課題 本発明の目的は、マルチ・プロセッサ・システムに於い
てデータをソート又はマージする時、処理装置の台数に
比例して性能が向上するような方式及び装置を提供する
事である。

００課題を解決するための手段 任意の数のソートされたリストがＰ個のリスト（区画）
に効果的に分割される。但しＰは、その結果得られたリ
スト（区画）をソートするのに利用可能な処理装置の数
を表す。ソートすべき大規模なリストが与えられた時、
そのリストは、最初にＰ個のリス１−に分割され、各処
理装置がそれらのリストの各々一つをソートする。次に
本発明に従ってリストが分割（区画化）される時、それ
により形成された新しいリスト（区画）中の要素の各々
は、それ以前の区画中のどの要素よりも小さくない値を
値を有し、又それ以後の区画中のどの要素よりも大きく
ない値を有する。次に各区画中のリストはＰ個の処理装
置によりマージされ且つ単に連結されて、全要素のソー
トされたリストを提供する。

第１の区画は、ある値よりも小さな全リストの全ての要
素より成り、Ｎ／Ｐ個の要素を含む区画を生しる。第２
の区画は、第１の値以上であって、第２の、より高い値
よりも小さな全ての要素より成り、再びＮ／Ｐ個の要素
を含む区画を生じる。

これは最も高い値の、Ｎ／Ｐ個の要素を含むＰ番目の区
画まで、継続する。区画中のリストは単一の処理装置し
こよりマージされ、Ｐ個の処理装置の各々が一つの区画
中のリストをマージするタスクに割当てられる。マージ
処理が終了すると、マージされたリストは単に連結され
、最終的なソートされたリストを形成する。時間のかか
るマージ操作は、従来技術におけるようにいくつかの区
画及びマージ操作においてではなく、全ての利用可能な
処理装置により同時に実行される。また各区画はほぼ同
じサイズなので、従来のような処理装置の負荷の不平衡
は起こらない。

良好な実施例において、区画の境界を決定するために、
空リストの集合で開始する。各リストのほぼ中央の要素
を見出す計算が行なわれ、この行が各リスト中の単一の
要素に先行する初期区画と共に考慮のために付加えられ
る。選択される最初の要素の行は、最長のリスト中の要
素の数よりも少ない最大の２のべき乗の整数値であるイ
ンデックスを有する。各リスト中に於いて区画の直前の
要素の内最大の要素が決定される。この最大要素よりも
小さい区画の直後の要素の数も決定される。

この値は、上側の区画の全ての要素が下側の区画の全て
の要素よりも小さい事を保証するように下側の区画から
上側の区画に移動させなければならない要素の数である
。この基準は、以降、大きさの要求と呼ぶことにする。

次に、区画のサイズが正しい比率になる事を保証するた
めに下側区画から上側区画に移動しなければならない要
素の数を決定する。この基準は、以降、区画サイズの要
求と呼ぶ。これら２つの値、即ち大きさの要求を保証す
るために移動しなければならない要素の数、及び区画サ
イズの要求を保証するために移動しなければならない要
素の数が比較される。この比較は、大きさの要求及び区
画サイズの要求の両者を保証するために上側区画から下
側区画へ又はその逆に要素を移動する必要があるか否か
を決定する。もし要素を上側の区画から下側へ移動する
必要があるならば、上側の区画から適当な数の最も大き
な要素が下側に移動されるように区画が調整される。も
し要素を下側の区画から上側へ移動する必要があるなら
ば、下側の区画から適当な数の最も小さな要素が上側に
移動されるように区画が調整される。この時、区画は、
現在リスト中で考慮されている要素に関しては正しい。

次のステップで、さらに２つの行、最初の行と中間の行
との間の行、及びの最後の行と中間の行との間の行が、
考慮のために付は加えられる。そして、区画境界の直前
のこれらの要素の最大値が再び決定される。このプロセ
スは上述のように継続し、その結果は、リスト中で現在
考慮中の要素に関する正しい区画である。継続するプロ
セスの各々の間に、新しい行が考慮のために付は加えら
れ、最終的に、Ｉ　ｏ　ｇ２　ｎのステップ（但しｎは
区画化されるべき最長のリスト中の要素の数である）の
後に、全ての行が付は加えられる。この最後の反復の後
、最終的に区画が決定される。

Ｐ−１個の区画境界を見出し、それにより各々１つ以上
のマージすべきリストを含むＰ個の区画を定義するため
に、Ｐ−１個の処理装置が並列にこの動作を実行する。

Ｐ個の区画の各々は元のソートされたリストの１つ以上
からの要素を含む事がある。動作は、各処理装置におい
て同一であるが、サイズの要求に対して重み因子が加え
られ、各処理装置はステップの各々に於いて異なった要
素を移動して終了する。従って、結果的に得られる計算
された区画境界は異なっている。

各々の結果的に生じる区画中の要素の数は他のものと高
々１要素だけしか異なっていないので、最終的なマージ
・フェーズに関して処理装置間で作業は均等に分割され
る。最終的なマージ・フェーズに於いて、Ｐ個の処理装
置の各々がその区画中のリストをマージして、Ｐ個のソ
ートされたリストを形成する。次に、リストは、単に連
結されて、最終的なソートされたリストを形成する。処
理装置が最大限に利用されるので、さらに処理装置を付
は加えた時にソート時間のほぼ線形の改善が得られる。

Ｅ、実施例 本発明の高水準の記述を最初に述べる。また１つの処理
装置において、どのようにして段階的に区画化が行なわ
れるかを示す例について述べる。

いくつかのソートされたリストを分割区画化する方法を
利用できる一つのコンピュータ・システムが第１図の１
０に一般的に示されている。１２．１４及び１６の番号
を付けられた複数の処理装置Ｐ１、Ｐ２・・・ＰＮが、
Ｉ１０バス１８に結合されているように示されている。

各処理装置は、直接結合又はＩ１０バス１８経由のいず
れかにより主記憶２０に対するアクセスを有している。

ソートすべきリストより成るデータは、やはりバス１８
に接続された種々の直接アクセス記憶装置ＤＡ５Ｄ２６
及び２８に記憶されている。各処理装置は、主記憶２０
に転送すべきデータをＤＡＳＤから要求する。本発明は
ある特定の構成に依存せず、他の並列処理装置アーキテ
クチャも本発明の実施に同様に適している事が認められ
る。各々がそれ自身の別個の主記憶又はキャッシュ付の
一連の主記憶を有する疎結合された処理装置も本発明を
実施するための候補者である。

複数の処理装置により大規模なリストをソートする時、
その目的は、最短の時間でソートを行なう事である。こ
れは、複数の処理装置の間でできるだけ等しく作業を分
割する事によって最も良く達成される。第１のステップ
は、リストを複数の等しいサイズのリストに分割する事
である。もし項目がアドレスによって表されているなら
ば、通常、１つの処理装置が他の処理装置の各々にアド
レスのリストを提供する。そのようなリストの数は利用
可能な処理装置の数に等しくあるべきである。次に、各
処理装置はリストを取得し、リスト中の全ての項目が所
望の順序に配列するように通常のリストのソートを行な
う。一つのそのまうな順序は、項目のディジタル表現の
値に基づいた昇順である。多くのそのようなソート・ル
ーチンが今日一般に実用されており、従ってこれ以上は
説明しない。

ソート・プロセスの第２の段階は、リストを区画に分割
する事である。区画の各々はほぼ同じ数の要素又は項目
を含んでいる。各々の利用可能な処理装置毎に１つの要
素の区画が存在すべきである。

第１の区画は元のリストの多くからの要素を含むが、そ
のような要素の全ては次の区画中の要素よりも小さいで
あろう。これは、後続の区画の各々に関しても真である
。

区画の境界を見つける事が区画化を行う処理装置のタス
クである。区画の境界は、リスト識別子、及びリストの
各々に関するリストへのインデックス値によって識別さ
れる。例えば、各々２１の要素を持つ３つのリストを想
定すると、区画の境界は、リスト１、インデックス７；
リスト２、インデックス９；リスト３、インデックス５
として識別しうる。これは、第１のリスト中の７番目の
要素を含んでそれよりも大きな全ての要素、第２のリス
ト中の９番目の要素を含んでそれよりも大きな全ての要
素、及び第３のリスト中の５番目の要素を含んでそれよ
りも大きな全ての要素が第１の区画中にある事を意味す
る。これは要素の１／３を第１の区画中に置く事になる
。というのは、区画境界は区画の最後の要素を定義する
からである。

第１の区画中には２１の要素が存在し、次の２つの区画
の各々の中には２１の要素が存在する。

２つだけの区画境界を決定する必要があり、ソート全体
を実行するのに３つの処理装置が利用可能である時、区
画化を実行するのに２つの処理装置しか必要でない。第
１の区画境界を決定する第１の処理装置は、区画定義を
、第２の境界を決定する第２の処理装置に渡す。これは
、第２の処理装置が第２の境界を決定した時、第２の処
理装置に第２の区画を明瞭に定義する。さらに第２の処
理装置は、第２の境界定義を、第３の区画を定義する第
３の処理装置に渡す。２つの境界の決定はほぼ同時に起
きるべきである。というのは、両方の決定における多く
のステップが実質的に同一であり、両方の処理装置が並
行して動作しているからである。

次に３つの処理装置の各々がマージ動作を実行する。こ
の共通の動作は、本質的には、その区画のリストの１つ
からの全ての要素を用いて開始し、区画中の残りのリス
トからの要素を適当な順序で挿入する事より成る。

リストを区画するために使われる方法は、例を用いて説
明するのが最も良い。正確な一般的方法は本明細書の実
施例の説明の末尾に記載されている。一般的には、事前
にソートされたリストから選択された要素に対して多数
の反復的ステップが実行される。各ステップは、考察中
の既存の要素の間に、リストからの要素を付加える。こ
のようにして、上側の区画中の新しい要素は常に」二側
の区画中に属する。というのは、それらは常に、以前の
反復動作による区画境界要素よりも大きくないからであ
る。問題の要素は区画境界のすぐ隣のものである。とい
うのは、それらは、上側区画の境界要素よりも小さいか
もしれないからである。

この方法は、各リスト中の１つ要素から始まる。

これらの小さな新しいリストは区画化され、次に現在の
要素の間に新しい要素が付加えられる。次に、このラン
は区画化され新しい要素がこれらの現在の要素の間に付
加される。この反復的プロセスは、各系列中の全ての要
素が処理されてしまうまで継続する。区画化の間、境界
は、以前の区画境界の上又は下の要素を含むように移動
される。

要素は、それらの大きさに基づき、また既に区画中に存
在する要素の数に基づき、移動される。最後の特性は、
複数の区画を確立する事を可能にするものである。要素
の数の因子は、単に、区画中の所望の要素の数に基づき
修正される。２ウ工イ区画の場合、２分の１の倍数が用
いられる。３ウ工イ区画の場合、１／３が最初の区画の
ために用いられ、２／３が第２の区画のために用いられ
る。

同じ事が、多数の区画に関しても成り立つ。

リストａ、ｂ及びＣの次の系列を想定する。

インデックス　　　ａ　　　　　ｂ　　　　　ｃｌ　　
　　　　１　　　６　　　６ Ｇ　　　　　　６　　　　　　　７ リストはサイズが等しくはない事に注意されたい。これ
は、元のリストの選択的なソートを行なっている以前の
ソート動作が原因となって起きる可能性がある。リスト
は、最終のソートされたリスト中に含まれる事が望まし
くない要素を有している可能性もある。１／２の区画が
見出されるべきである。初めに、何も付加されていない
ので、考察すべき要素は存在しない。最初の計算は、ど
のリストからのどの要素が考慮されるべきかを判定する
ために行なわれる。リストａは１２個の要素を有し、リ
ストｂは３個の要素を有し、そしてリストＣは１３個の
要素を有している。要素は、以前の要素の間の半分の所
に考察のために付加えられるので各リスト中の８番目の
要素が付加される。８番目の要素は、それが２のべき乗
であるので、最初に選択された。リストの少なくとも１
つには８個以上の要素が存在するが、全リスト中には１
６個よりも少ない要素しか存在していない。

２のべき乗に基づき、さらに要素を含める事は容易であ
る。第２のリストＣ中には３つの要素しか存在しないの
で、この時点ではリストＣ中の要素を考慮する必要はな
い。

最初の要素が考慮のために付加えられる時、それらは下
側区画の一部として付加される。例えば、区画境界は、
下記のように線で表される。

ａ　　　　　　　　ｂ　　　　　　　　ｃ上側の区画中
で考察される最大の要素が見出される。これは、上側の
区画中にどれ位の数の要素が置かれなければならないか
を決定するために必要である。というのは、それらは現
在そこに存在している最大値よりも小さいからである。

上側区画中には要素が存在しないので、最大値はマイナ
スの無限大又はより具体的には計算機で表現できる最小
の値であると考えられる。現在の境界の下には、境界の
上側の最大値よりも小さな考慮中の要素は存在しない。

従って、大きさの要求Ｓにより要素を移動させる必要性
はない。Ｓはゼロに等しい。次に、区画のサイズを等し
くするために上側区画に移動しなければならない要素の
数ｎが計算される。ｎは、１であることが見出される。

Ｓ及びｎの相対的な値は、区画境界をどのようにして移
動させるかを決定するために使われている。境界を移動
するのに、場合１、場合２、及び場合３＝２１ の３つの異なった方法が存在する。ｓｌＪ＜ｎよりも小
さい時、場合３が実行される。他の場合の動作は、この
例の中で出会った時に説明する。場合３は、上側区画中
にに下側区画からの最小Ｓ個の要素を含んでいる。次に
、下側区画中のｎ−８個の最小の要素が下側区画から追
出され、上側区画中に置かれる。Ｓはゼロなので、下側
区画から何の要素も上側区画に付加されない。ｎ−ｓは
１なので、リストから値８が上側区画に上昇する。区画
は、この時、次のようになる。

ａ　　　　　　ｂ　　　　　　ｃ 第２の繰返しの場合、再びリストａ及びｂだけが関係す
る。この結論に到達するために行なわれる計算は実施例
の説明の末尾に示されている。各リス）・からインデッ
クス４及び１２の要素が考察のために付加えられる。こ
れらの要素は、現在考察中の要素の中間にある。リスト
Ｃにおける区画境界は値１７よりも上にあるように考え
られ、第１の繰返しの後で事実上マイナス無限大である
。

従って、値７は境界の下に付加えられる。

ａ　　　　　　ｂ　　　　　　ｃ 区画よりも上の最大の値は８であり、現在考察中の区画
の下に１つのより小さな要素７が存在する事がわかる。

従って、大きさの要求及びｓ＝１を満足させるために７
が上側の区画に移動されなければならない。また、区画
サイズの要求、従ってｎ−１を満足させるために１つの
要素が上側の区画に移動しなければならない。

ｓ＝ｎは、場合１の状況である。＠合１は、下側の区画
からの最小のＳ個の要素を上側の区画中に含める。これ
が行なう必要のある全てである。

というのは、大きさの要求を満足させるためにＳ個の要
素が上側の区画中に置かれなければならず、そして区画
のサイズを等しくするために同数の要素がそこに置かれ
る必要があるからである。」二連のように、Ｓ及びｎは
両方１なので、１つの要素が上側の区画に移動されなけ
ればならず、結果的に得られる区画は下記のようになる
。

ａ　　　　　　ｂ　　　　　　ｃ 次の繰返し中しこ、インデックス２．６及び１０の要素
が考察のために付加えら九る。再び、既に考察中の要素
の中間に要素が存在する。これは考察中の要素を生じ、
境界は下記のようになる。

ａ　　　　　　ｂ　　　　　　ｃ よりも上の最大値は、リストａ、インデックス８中の８
である。Ｓは２であり、これは大きさの要求を満足させ
るために２つの要素が」二側の区画しこ移動されなけれ
ばならない事を示す。これらの要素は、ｂ２の６ｃ６の
７である。ｎは１であり、これは区画サイズの要求を満
足させるために上側区画に１つの付加的な要素が必要で
ある事を示している。Ｓはｎよりも大きく、従ってこれ
は場合２の例である。２つの要素が上側の区画に移動さ
れ、ｓ−ｎの要素、１つの要素が下側の区画に移動され
る。区画は、この時、次のようＬこなる。

ａ　　　　　　ｂ　　　　　　ｃ この時、リストｂが区画リストに加わる。区画最後は、
最終の繰返しの時である。というのは、この時、全ての
要素が考察されるからである。付区画は次のようになる
。

ｂ　　　　　　　ｃ ８　　　　　　　　　　　　　、　　１８区画より上の
最大の値は７であり、現在考察中の区画の下にはそれよ
り小さな要素はない事がわかる。また、区画の上下の要
素の数も等しいので、どの要素も移動させる必要はない
。５＝Ｏ１及びｎ＝ｏである。ｓ”ｎなので、これはも
う１つの、場合１の状況である。Ｓ及びｎは両方Ｏなの
で、区画に変更を行なう必要はない。

この時、上側の区画は１４個の要素を含んでおり、その
全ては、１４個の要素の下側の区画の最低の値の要素よ
りも小さいか又は等しい。この時、１つの処理装置が上
側の区画中の要素を取り出し、リストｂ１インデックス
１及び２からの２つの「６」がリストａにマージされ、
次にリストｃ１インデックス１〜６からの３つの「６」
及び３つの「７」がリストａにマージされる。同様のプ
ロセスは下側区画に関しても起き、２つのマージされた
区画が連結されて、最終的なソートされたリストが形成
される。

大きさＳ及びサイズｎの要求を決定するために使われる
プロセスは、実施例の説明の末尾に詳述されている。一
般的に、それらは、必要な記憶装置活動の量を最小化す
るように設計されている。

あるリストは非常に大きく、共有記憶域内に完全には入
り切らない。それらは、定期的に主記憶との間でページ
ングしなければならない。もしこれが避けられるならば
、時間が節約され、資源が他の処理装置に使えるように
なる。反復処理は以前の区画のいずれかの側に少数の項
目しか付は加えず、またしばしばリストからの要素が含
まれていない事があるので、どの要素を実際に見る必要
があるかをプロセスが決定する。従って、実際に主記憶
中に存在しなければならない要素の数が減少する。また
、処理装置の各々は異なった区画上で作業を行なってい
るので、データのアクセスにおけるコンフリクトは少し
しか存在しない。

区画化を行なう時、区画境界の直後に続くＰ個の要素が
、各反復時に検査される必要がある。例えば、上記の例
の最後の反復において、要素（１゜３．５．７．８．８
１がリストａから付加され、要素（６，２２１がリスト
ｂから付加され、要素（６，６，７，１６，１８，１８
，２２１がリストｃから付加される。付加された１５個
の要素のうち、区画境界の直後の要素（７，２２，１８
）のみが実際にページングされる必要がある。残りの要
素は全く検査又はページングの必要はない。

それらは既に適当な区画中にある事がわかっている。区
画化のための時間は、Ｐ＊（１＋１０ｇ２（Ｐ）Ｃｌｏ
ｇ２（Ｎ／　Ｐ　）に比例する。但し、Ｎはソートされ
るべき要素の総数である。Ｎ＞Ｐというソート動作に典
型的な場合、区画化のコストは重要なものではなく、マ
ージのコストに較べれば無視する事ができる。従って、
この方法は正確なリストの区画化を生じるので、処理装
置の負荷の不平衡は存在せず、マージ時間はＮ／Ｐにほ
ぼ比例する。

複数の区画の形成に関して、プロセスをより良く理解す
るために、２つの境界、従って３つの区画を形成するた
めに２つの処理装置により行なわれる反復動作を並置し
て説明する。最大値ｓ、ｎ及び場合（ＣＡＳＥ）番号が
示されている。再び、ｎは、所望の区画境界に依存する
値である。それは、特定の処理装置によって見出される
区画境界よりも上に含まれるべき要素のパーセンテージ
の関数である。この例では、処理装置１が、境界の上側
に約３３％の要素を有するような境界を見出し、処理装
置２が境界の上側に６６％の要素を有するよ反復２ 要素の付加 うな次の境界を見出す。

処理装置Ｙ 処理装置２ １／３区画 ２／３区画 反復１ 要素の付加 Ｓ：Ｏ Ｎニー１ ｋＳＥ２ Ｓ二〇 Ｎ二１ ＡＳＥ３ ｍａｘ＝８ ｍａｘ４ 新しい区画の形成 Ｓ：０ Ｎ＝１ ＡＳＥ３ Ｓ二〇 Ｎ＝１ ＡＳＥ　３ ｍａｘ　　” 新しい区画の形成 反復３ 要素の付加 反復４ 要素の付加 Ｎ＝１ ＡＳＥ３ Ｓ＝１ Ｎ＝１ ＣへＳＥＩ ｍａｘ＝４ ｍａｘ＝１３ 新しい区画の形成 Ｎ＝１ ＡＳＥ３ Ｎ＝１ ＣへＳＩＥ３ ｍａｘ＝６ ｍａｘ”１３ 最終区画の形成 処理装置１が区画境界を見つけるプロセスを終了すると
、それは区画境界の識別子を、リスト、インデックスの
形で（この場合はａ７、ｂｏ、ｃｏ）、処理装置２に渡
す。そこで処理装置２は第２の区画が、ａ８、ｂｌ、ｃ
ｌがら、それが見つけた境界ａ８、ｂ２、ｃ５までより
成る事を知る。

処理装置２は第２の区画定義を第３の処理装置に渡し、
そこで第３の処理装置はそれがマージしなければならな
い要素が何かを知る。処理装置の各々は次にマージ動作
を行なって、リストを得る。

これらは−緒になって最終的なソートされたリストを形
成するストリングでありうる。

上記の記述から、本発明は殆ど任意のサイズのリストを
並列に効果的に区画化する事が理解できる。処理装置の
付加により全体的なソート時間が大幅に改善される。と
いうのは、ステップの各々に複数の処理装置が関与し、
区画化フェーズは最大のリストのサイズが与えられると
、限られた数の所定の数のステップしか関係しないから
である。

下記の表１は区画化方法をコーディングするための良好
な方式を示している。第１にソートされたリストが取得
され、必要な反復の回数が計算される。次に、考察すべ
き要素ｓ、ｎが付加され、考察すべき要素に関するｍａ
ｘが計算され、場合番号が決定されそこに分岐が行なわ
れる。次に、以前の説明に従って要素が移動される。こ
れは全ての要素が考察されるまで反復される。表１は本
発明を実施しうる１つの方法を示しているだけであって
、他のコーディングも可能である。ハードウェアにまる
実施も可能であり、ずっと高速である。

複数の処理装置を用いてリストをソートする方法のブロ
ック図が第２Ａ図及び第２Ｂ図に示されている。複数の
処理装置１．２、・・・・Ｐ−１、Ｐが図面の上部に示
されており、それによって行なわれる動作は各処理装置
の下側の列に示されている。処理装置の１つ、処理装置
１は、Ｎ個の要素を含むソートすべきリストを取得する
。それはソート情報を他の処理装置に渡し、リストのど
の要素が各処理装置によりソートされるべきかを識別す
る。もし各処理装置が、リストのサイズを与えられた時
、所定の部分を探索するように前もってプログラムされ
ているならば、各処理装置によって、ソートすべき要素
を決定する事もできる。

次に、各処理装置はリストの部分をソートし、他の処理
装置がそのソートを完了するのを待機する。リストは、
クイックソート、トーナメント木等の従来のソート方法
を用いてソートされる。ソートに続いて、処理装置のＰ
−１が区画境界を決定し、区画情報を処理装置に渡す。

それらは次の区画境界を決定する。区画化の間に処理装
置は、反復プロセスの間にどの要素が境界を移動するか
を決定するためにソートも行なう必要がある。上述と同
様のソート方法を使用しうる。リストは既に個々にソー
トされているので、ソートの量は最小限である。

処理装置は、先行する処理装置からの区画境界情報を待
機する。両方の境界が識別されると、処理装置の各々は
境界により定義された区画の１つをマージする。指定さ
れた処理装置（この場合、処理装置１）は、他の処理装
置がその各々の区画のマージを完了するのを待機し、次
にマージされた区画を連結する。その結果は実際のリス
トである。この結果は単に正しい順序の要素のアドレス
のリストであっても、又正しい順序に実際に記憶装置中
に再配置された要素でも良い。

Ｅ−２，アルゴリズムの説明 ａｒ−ａｒ、１＋　　ａｒ、２＋　　ａｒ、３＋　”　
”＋　　ａｒ、Ｎｒをｍ個の昇順の系列（シーケンス）
であるとする。但し、１５１５ｍであり、Ｎｒ−ｌｌａ
、Ｉｆである。課題は、下記の条件を満足するｉｒを見
出す事である。但し、１≦ｒ≦ｍであり、ａ、ｒ’＝ａ
ｒ、１＋　　ａｒ、２＋ａｒ、３＋　””＋　　ａｒ、
ｌｒ＜ｌｒ二〇はａ　、　ｒが空の系列である事を意味
する。）であって１ 、但し０≦ｆ≦１　（区画サイズの要求）２、ｘｌ、ｓ
≦Ｖ　ｔ、　ｕ 、但しＸ　ｒ、　ｓＥａ　ｒ’＋　　Ｖ　ｔ、　ｕＥａ
　ｔ＋１≦ｒ≦ｍ、０≦Ｓ≦ｉｒ、１≦ｔ≦ｍ。

ｉ、ｔ＜ｕ≦Ｎえ（大きさの要求） 任意の分数ｆを許容しているので、区画サイズの要求は
】の差までは満足させる事ができる。

（ａｒ、１≦ｒ≦ｍ）のｆ次の区画化関数を（ｉ、。

１≦ｒ≦ｍ）と表す。

ＲＢは、ｐ−○、ｋｍａＸ−ｍａｘ １≦、５ｍ（ｋ、）にお いて、基本ステップが与えられた時に、ｐ−０゜１．２
，３．・・・、に□８Ｘ−１に関して順次に解（ｉ、−
ｐ。

１５１５ｍ）を得る事によって解決される。但し、ｋ、
＝ｆ１ｏｏｒ（ｌｏｇ２（Ｎ、））＋１及び（ｉ、ｐ、
１≦ｒ≦ｍ）は選択された系列の選択された部分系列の
１次の区画化関数である。反復のｐ番目のステップに於
いて、少なくとも２＊＊（ｋｍａＸ−ｐ−１）個の要素
を持つ系列だけが考察される。形式的に、系列（ａｒｐ
＋　　１≦ｒ≦ｍ）を考える。（＊＊はべき乗を表す） ｑ、″＞Ｏに関して次の事が定義される。但し、ｑ、’
＝ｐ−に、、、−、を十に、である。

・Ｍ、−２：ζ＊（ｋｒ）、系列ｒに属する要素に関す
る最大の可能なインデックス ・Ｍ（ｐ）−２＊＊（ｋｍ、Ｘ−ｐ）、この反復中に考
察されている系列ａ、からの要素間の間隔・Ｎ、’−Ｍ
、−Ｍ（ｐ）ｃｅｉｌ（（Ｍ、−Ｎ、）／Ｍ（ｐ））こ
れはｐ番目の反復中に考察される系列ａ、からの実際の
最後の要素を定義する。

・ａｒ”””ａｒ、Ｍ（ｐ）＋　ａｒ、２Ｍ（ｐ）＋　
　ａｒ、３Ｍ（ｃ＋）＋　”’ａ　ｒ　、　Ｎ”。

これはこの反復中考察される系列の実際の要素である。

全ての系列が考察されるわけではない。あまりに少ない
要素しか含まないものは、次のように除外される。即ち
、ｑ　、Ｄ≦０の場合、ａｒｐは空系列であり、Ｎ、’
、Ｍ（ｐ）、Ｍ、は定義されない。

この方法は、（ｉ、’、１≦ｒ≦ｍ）から（ｉｒｐ−１
１≦ｒ≦ｍ）を○（ｍｌｏｇｍ）の時間及びＯ（ｍ）の
■１０で導き出す技術である。Ｍ（ｐ）−２Ｍ（ｐ＋１
）隔たった少なくとも２　＊＊（ｋ　ｍ−Ｘｐ　　２　
）個の要素を含む部分系列の区画から、Ｍ（ｐ＋１）だ
け等しく隔離した少なくとも２；跡（ｋ、ｎａ、　−ｐ
　−Ｌ　）個の要素を含む部分系列に関するｆ次の区画
化が回出される。

５０＝（ｒ：ｌｑｒ”≧０．１≦ｒ≦ｍ）をステップｐ
で考察されるべき系列のインデックスの集合であるとす
る。以前のステップのｆ次の区画化の先行区画において
少なくとも１つの要素を有するものと考えられる系列に
関するインデックスの部分集合は、５ｌ−（ｒヨｉｒｐ
＞Ｏ，ｒＥＳｏ）として定義される。

もしｌｌｓ’１ｌ＝ｏならば、ａ、ｎ諜−ｏ。

もしｌｌｓ’１１≠０ならば、 ａ、。娶−ｒｎａＸ　（ａ　　’Ｄ） ｒＥＳ”　　ｒ、ｌｒ ａ　ｍ　ａｘはこのステップにおけるｆ次の区画化の最
大の境界要素である。それは繰返し中に０（１）時間で
見出す事ができる。

これらから、ｆ次の区画化中にその部分系列全体が含ま
れている系列を次のように区別する必要がある。

５２＝（ｒ　３　ｉ　、ｐ＜　Ｎ６−１．　ｒ　ＥＳｏ
）以前のステップの境界要素よりも大きいと考えられる
新しい要素の数は次のように計数される。

Ｓ３−（ｒヨａ　　　　　＜　ａ　ｌ’ｎａＭｌ　ｒ　
Ｃ３２）ｒ、　ｉ　ｒｖＩｖ”’） ｓ”’Ｓ３ もし以前のステップの先行区画を取り、区画中の２つの
要素の間の等距離の１つの新しい要素を考察すると、下
記のように、区画サイズの要求を満足させるのに近い状
態になる。

「Ｅｓ。

Ｓ３で識別されるような以前の最大の境界要素よりも小
さい境界要素の次の要素を含め、新しい区画を形成する
。次に、区画サイズの要求を検査する。新しい候補の先
行区画中の全ての要素が以前の最大境界要素よりも大き
く、反復ｐ−）ｉ中に考察される他の全ては同じ要素よ
りも小さくないので、大きさの要求は満足される。

場合１：ｓ＝ｎ 区画化要求は満足されている。

ｒＥＳ３ならば、ｉｒ”””　＝　ｌ　ｒ”　Ｍ　（ｐ
　＋１　）ｒ＃ｓ３ならば、ｌｒ″″″１；ｉｒｃ′場
合２：ｓ＞ｎ 候補の新しい先行区画はｓ−ｎの多すぎる要素を有して
おり、区画サイズの要求を満足させるために次のように
最大のｓ−ｎを除去する必要がある。

°°°゛・ａｒ、　ｔ、”・・ｒＥＳ”ｒＥＳ３ならば
、ｔ　ｒ””−１ｒｐ＋　Ｍ　（ｐ　＋１　）ｒＥＳ０
Δｒ＊ｓ３ならば、ｊ　ｒ’＝”　＝　ｌ　ｒｐ中のｓ
−ｎの最大の要素の１つ） 上記計算はＯ（ｍ）のＩｌｏ及びＯ（ｍｌｏｇｍ）のＣ
ＰＵ時間を上限としうる。

Ｓ、”（ｊヨｊＥ（Ｏ，Ｍ（ｐ＋１）、２Ｍ（ｐ＋１）
。

３ＭＣｐ＋１）、＝−、ｔ、。′″１）へ（ｒ　、　ｊ
　）ｆ’ｓ’）、ｒＥＳＯ ｒＥＳｏならば、ｌｒｐ″″１＝ｍａｘ（Ｓｒ’）ｒｆ
ｌｉｉ！Ｓ０ならば、１　ｒｐ−１”　ｌ　ｒ”場合３
　：　ｓｉｎ 候補の新しい先行区画はｎ−ｓの少なすぎる要素を有し
ており、区画サイズの要求を満足させるために次のよう
に、部分系列の残りから最大のｎ−５個を除去し、それ
らを候補先行区画に付加する必要がある。

”　”’　ａｒ、ｔ、、、、　Ｉ　ｒ　Ｅ　５３ｒＥＳ
３ならば、ｔ、”＝　ｉ、ｐ＋Ｍ（ｐ＋１）ｒＥＳＯＡ
ｒ＃Ｓ３ならば、ｔｒｐ′″１＝ｉｒ。

Ｓ６＝（（ｒ、ｊ）ヨ ができる。

中のｎ−ｓの最小要素の１つ） 上記計算はＯ（ｍ）のＩｌｏ及びＯ（ｍｌｏｇｍ）のＣ
ＰＵ時間を上限としうる。

Ｓ、７＝（ｊヨｊε（Ｏ，Ｍ（ｐ＋１）、２Ｍ（ｐ＋１
＞。

３Ｍ（ｐ＋１）、−、ｔ、”）Ｖ（ｒ、ｊ）εＳ６）。

ｒε５Ｏ ｒＥＳｏならば、ｌ　ｒ’＝”　＝　ｍａＸ　（Ｓ　ｒ
７）ｒ１５８０ならば、ｌ　ｒ”””　＝　１　ｒｐも
し上述の方法通りにインダクションが行なわれたならば
、ｉ＝ｉ　ｋ”′であることが証明できる。

ｒ 上記の手続は空系列から開始した。最初の反復時には、
考察される各系列から１つの要素を取り出し、それらを
分割する。ｐ＝＝Ｑにおけるこの手続に関する基本ステ
ップはｉ、、。＝Ｏである。

Ｆ０発明の効果 本発明を用いれば、複数の処理装置を用いて、効率的に
マージ及びソートを行なう事ができ、処理装置の台数に
比例してその性能を向上させる事表１

【図面の簡単な説明】

第１図は本発明の区画化方法を実行するためのマルチプ
ロセッサーシステムのブロック図、第２Ａ図及び第２Ｂ
図は複数プロセッサを用いたソート・プロセス全体の流
れ図である。 出願人　インターナショナル・ビジネスーマシーンズ・
コーポレーション

Claims (4)

【特許請求の範囲】
1. （１）Ｐ個のソートされたリストをＬ−１個の処理装置
   によりＬ個の区画に分割する方法であって、上記Ｐは３
   以上の数、上記Ｌは２以上の数であり、各々の後続した
   区画は先行する区画の全ての要素よりも大きな値の要素
   を含むものであって、ａ）上記リストから少なくとも１
   行の要素を考察のために選択し、 ｂ）要素の中間の行付近に区画の境界を定め、ｃ）区画
   境界の上側の考察中の全ての要素の最大値を決定し、 ｄ）上記最大値よりも小さい、上記区画境界の下側の考
   察中の要素を決定し、 ｅ）区画のサイズ及び考察中の要素の値に基ずき、上記
   境界に関して要素を移動し、 ｆ）継続した行が考察され且つ区画が各々ほぼ等しい数
   の要素を含むようになるまで、上記ステップａ、ｃ、ｄ
   及びｅを繰返す区画分割方法。
2. （２）Ｐ個の処理装置を用いて、Ｎ個の要素のリストを
   ソートする方法であって、上記Ｐは３以上の数であり、
   上記処理装置が協同して並列に、ソートされたリストを
   提供する方法であって、 ａ）リストをほぼＮ／Ｐ個の要素を含むサブリストＰ個
   に分割し、 ｂ）上記各処理装置で各サブリストをソートし、ｃ）Ｐ
   −１個の区画境界であって、各境界がＰ−１個の処理装
   置の１つにより定められ、上記境界がリストをほぼ等し
   い区画に分割し、区画中の要素が後続の区画中の全要素
   よりも小さな値を有するような区画境界を定め、 ｄ）上記各処理装置で上記区画の各々をマージするステ
   ップを含む ソート方法。
3. （３）複数の事前にソートされた要素のリストを区画化
   する装置であって、 事前にソートされたリストを含む記憶装置に対して各々
   アクセスを有する複数の処理装置と、リストから区画化
   リストに要素を選択的及び反復的に付加する手段と、 区画化リストに関して初期の区画境界を選択する手段と
   、 区画境界の上側の要素の所望の数と区画境界の上側の要
   素の実際の数との関係に基ずいてサイズの変更因子を決
   定する手段と、 区画境界の上側の最大の要素の大きさよりも小さな、区
   画境界の下側の要素の数に基ずき大きさの変更因子を決
   定する手段と、 要素の各反復的付加に引続いてサイズ変更因子と大きさ
   変更因子の関数として区画境界を変更する手段とを有す
   る 複数の事前にソートされた要素のリストを区画化する装
   置。
4. （４）複数の事前にソートされた要素のリストを区画化
   する装置であって、 事前にソートされたリストを含む記憶装置に対して各々
   アクセスを有する複数の処理装置と、リストから区画化
   リストに要素を選択的及び反復的に付加する手段と、 区画化リストに関して初期の区画境界を選択する手段と
   、 サイズの変更因子を決定する手段と、 大きさの変更因子を決定する手段と、 要素の各反復的付加に引続いてサイズ変更因子と大きさ
   変更因子の関数として区画境界を変更する手段とを有す
   る 複数の事前にソートされた要素のリストを区画化する装
   置。