| 【発明の名称】 |
分散ソーティング方法および記録媒体 |
| 【発明者】 |
【氏名】佐々木 淳
|
| 【要約】 |
【課題】時間複雑度と通信要素数により評価される通信複雑度とを共に厳密に最適にするアルゴリズムの構築を行う。
【解決手段】ｗａｉｔ状態のプロセスがｌｅｆｔメッセージを受信したらｌｅｆｔへ、ｒｉｇｈｔメッセージを受信したらｒｉｇｈｔ状態へ、同時にｌｅｆｔメッセージとｒｉｇｈｔメッセージとを受信したらｒｅｌａｙ状態へ、ｌｅｆｔ状態のプロセスがｒｉｇｈｔメッセージを受信したらｒｅｌａｙ状態へ、ｒｉｇｈｔ状態のプロセスがｌｅｆｔメッセージを受信したらｒｅｌａｙ状態へと遷移し、毎ラウンド保持している要素のうち、ｌｅｆｔ状態のプロセスは、最大の要素をｒｉｇｈｔへ、ｒｉｇｈｔ状態のプロセスは、最小の要素をｌｅｆｔへ、２要素以上保持するｒｅｌａｙ状態のプロセスは、最大の要素をｒｉｇｈｔへ、最小の要素をｌｅｆｔへ、１要素のみを保持するｒｅｌａｙ状態のプロセスは、直近の端プロセスの方向へと送信する。 |
【特許請求の範囲】
【請求項１】 ｎ個のプロセスＰ１〜Ｐｎから構成される同期型の線形ネットワーク上でソートすべき最初の各プロセスに保持する要素の数とソート後の各プロセスが保持する要素の数が既知である場合に各要素を左のプロセスから昇順に並べ替える分散ソーティング方法において、各プロセスＰ１〜Ｐｎは、ｌｅｆｔ、ｒｉｇｈｔ、ｗａｉｔ、ｒｅｌａｙの４状態のいずれか一つの状態をとり、初期状態では、左端のプロセスＰ１はｌｅｆｔ状態、右端のプロセスＰｎはｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、プロセスＰ１が保持している要素とｌｅｆｔメッセージとをｒｉｇｈｔへ、プロセスＰｎが保持している要素とｒｉｇｈｔメッセージとをｌｅｆｔへと送信することで起動し、ｗａｉｔ状態のプロセスがｌｅｆｔメッセージを受信したらｌｅｆｔ状態へ、ｗａｉｔ状態のプロセスがｒｉｇｈｔメッセージを受信したらｒｉｇｈｔ状態へ、ｗａｉｔ状態のプロセスが同時にｌｅｆｔメッセージとｒｉｇｈｔメッセージとを受信したらｒｅｌａｙ状態へ、ｌｅｆｔ状態のプロセスがｒｉｇｈｔメッセージを受信したらｒｅｌａｙ状態へ、ｒｉｇｈｔ状態のプロセスがｌｅｆｔメッセージを受信したらｒｅｌａｙ状態へと遷移し、ｌｅｆｔ状態のプロセスは、毎ラウンド保持している要素のうちの最大の要素をｒｉｇｈｔへ、ｒｉｇｈｔ状態のプロセスは、毎ラウンド保持している要素のうちの最小の要素をｌｅｆｔへ、２要素以上保持するｒｅｌａｙ状態のプロセスは、毎ラウンド保持している要素のうち、最大の要素をｒｉｇｈｔへ、最小の要素をｌｅｆｔへ、１要素のみを保持するｒｅｌａｙ状態のプロセスは、毎ラウンド保持している要素を直近の端プロセスの方向へと送信する処理をｌｅｆｔ、ｒｉｇｈｔのそれぞれから受信した要素数と同じ数の要素をそれぞれの方向へ送信し終わるまで各プロセスが同期的に繰り返すことを特徴とする分散ソーティング方法。
【請求項２】 ｎ個のプロセスＰ１〜Ｐｎから構成される非同期型の線形ネットワーク上でソートすべき最初の各プロセスに保持する要素の数とソート後の各プロセスが保持する要素の数が既知である場合に各要素を左のプロセスから昇順に並べ替える分散ソーティング方法において、プロセスＰ１〜Ｐｎ相互間で同期メッセージを送受信し、各プロセスＰ１〜Ｐｎは、ｌｅｆｔ、ｒｉｇｈｔ、ｗａｉｔ、ｒｅｌａｙの４状態のいずれか一つの状態をとり、初期状態では、左端のプロセスＰ１はｌｅｆｔ状態、右端のプロセスＰｎはｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、プロセスＰ１が保持している要素とｌｅｆｔメッセージとをｒｉｇｈｔへ、プロセスＰｎが保持している要素とｒｉｇｈｔメッセージとをｌｅｆｔへと送信することで起動し、ｗａｉｔ状態のプロセスがｌｅｆｔメッセージを受信したらｌｅｆｔ状態へ、ｗａｉｔ状態のプロセスがｒｉｇｈｔメッセージを受信したらｒｉｇｈｔ状態へ、ｗａｉｔ状態のプロセスが同時にｌｅｆｔメッセージとｒｉｇｈｔメッセージとを受信したらｒｅｌａｙ状態へ、ｌｅｆｔ状態のプロセスがｒｉｇｈｔメッセージを受信したらｒｅｌａｙ状態へ、ｒｉｇｈｔ状態のプロセスがｌｅｆｔメッセージを受信したらｒｅｌａｙ状態へと遷移し、ｌｅｆｔ状態のプロセスは、毎ラウンド保持している要素のうちの最大の要素をｒｉｇｈｔへ、ｒｉｇｈｔ状態のプロセスは、毎ラウンド保持している要素のうちの最小の要素をｌｅｆｔへ、２要素以上保持するｒｅｌａｙ状態のプロセスは、毎ラウンド保持している要素のうち、最大の要素をｒｉｇｈｔへ、最小の要素をｌｅｆｔへ、１要素のみを保持するｒｅｌａｙ状態のプロセスは、毎ラウンド保持している要素を直近の端プロセスの方向へと送信する処理をｌｅｆｔ、ｒｉｇｈｔのそれぞれから受信した要素数と同じ数の要素をそれぞれの方向へ送信し終わるまで各プロセスが同期的に繰り返すことを特徴とする分散ソーティング方法。
【請求項３】 ｗａｉｔ状態で２要素以上保持するプロセスは、毎ラウンド保持している要素のうち、最大の要素をｒｉｇｈｔへ、最小の要素をｌｅｆｔへ、ｌｅｆｔ状態で２要素以上保持するプロセスは、毎ラウンド保持している要素のうち最小の要素をｌｅｆｔへ、ｒｉｇｈｔ状態で２要素以上保持するプロセスは、毎ラウンド保持している要素のうち最大の要素をｒｉｇｈｔへと送信する処理を追加して実行する請求項１または２記載の分散ソーティング方法。
【請求項４】 ｌｅｆｔメッセージに、それを送信したプロセスから左のプロセス集合の初期状態の総要素数と最終状態の総要素数との差を、ｒｉｇｈｔメッセージに、それを送信したプロセスから右のプロセス集合の初期状態の総要素数と最終状態の総要素数との差をそれぞれ添付し、ｗａｉｔ状態から他の状態に遷移するときに、その添付された値を利用して次のラウンドで送信するｌｅｆｔメッセージ、あるいは、ｒｉｇｈｔメッセージに添付する値を計算し、同種の計算により、ｌｅｆｔ、ｒｉｇｈｔから受信した要素数を記憶しているプロセス内部の局所変数を、最終状態で保持する要素数に応じて書き換えてｌｅｆｔ、ｒｉｇｈｔへ送信する要素数を調整する請求項１ないし３のいずれかに記載の分散ソーテイング方法。
【請求項５】 所定のハードウェアと、このハードウェアにインストールされれた所定の基本ソフトウェアとを備えたコンピュータ装置に、さらにインストールすることによりそのコンピュータ装置に請求項１ないし４のいずれかに記載の分散ソーティング方法を実行させるソフトウェアが記録された記録媒体。
|
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、分散システムにおける分散ソーティングに関する。なお、並列システムは分散システムの一種であるため、本発明は、並列システムでも分散システムでも使えるが、それぞれのシステムにおいては用語が異なるため、以下では、並列システムにおけるプロセッサ、ＣＰＵ、分散システムにおけるエージェント、プロセス、計算機等の用語を一括してプロセスと呼ぶ。
【０００２】
【従来の技術】ソーティングは、基本かつ重要な問題のひとつであるため、逐次、並列アルゴリズムだけでなく、分散アルゴリズムも研究されている。
【０００３】分散ソーティングの一般的な問題は、Ｇｅｒｓｔｅｌらによってビット複雑度の最適化を目指して解かれている(参考文献:[1]O.Gerstel and S.Zaks,The BitComplexity of Distributed Sorting,Algorithmica,Vol.18,No.3,pp.405-416,1997.)。しかし、彼らのアルゴリズムは、広い問題を解決できる反面、ビット複雑度のみを抑えるように構築した結果、ネットワーク上に構成した根付き木の根にすべての情報を収集し、そこでソートして配分するという、非常に逐次性の強いアルゴリズムとなっている。
【０００４】全要素を同時に収集できる場合には時間複雑度もｄｉａｍ（直径）程度で抑えられるが、そのためには局所メモリに全要素を格納する必要があるため、最大要素をＬ≧ｎとすると、少なくとも［数１］ビットの局所空間計算量を必要とする。
【数１】
この局所空間計算量を抑えようとすると、時間複雑度が増大してしまう。具体的には、局所空間計算量を［数２］に制限すると、時間複雑度は０（ｎ・ｄｉａｍ）必要になる。
【数２】
つまり、局所空間計算量を抑えると、多大な時間複雑度を要するアルゴリズムとなってしまう。
【０００５】一方、Ｈｏｆｓｔｅｅらは、逐次・並列アルゴリズムにおける問題に類似した分散ソーティング問題に対し、最適な時間複雑度を実現するアルゴリズムを構築している(参考文献:[2]H.Peter Hofstee,Alain J.Martin,and Jan L.A.Van De Snepscheut,Distributed Sorting,Science of Computer Programming,Vol.15,No.2-3,pp.119-133,1990.)。彼らのアルゴリズムは、時間最適であるだけでなく、局所空間計算量も小さく抑えられているが、対象とする問題が線形ネットワークにおいて、各プロセスが保持する要素数が２以上の場合に限定されており、多少不自然な問題になっている。また、通信複雑度は通信要素数により評価する場合の最適値の数倍になっている。
【０００６】さらに、並列ソーティングアルゴリズムにおいては、線形ネットワークに類似した線形アレイ上の問題があるが、そこでは、奇偶交換ソート（並列バブルソートとも呼ばれる）により、比較−交換処理のみに基づいた場合の最適な時間計算量ｎを実現している(参考文献:[3]F.Thomson Leighton,Introduction to Parallel Algorithms and Architectures:Arrays,Trees,Hypercubes,Morgan Kaufmann,1992.)。しかし、比較−交換処理のみには基づかない場合の時間計算量の下界はｎ−１である。このｎ−１という時間計算量は線形アレイ上の並列アルゴリズムでは実現されていない。
【０００７】
【発明が解決しようとする課題】前記の従来法で述べたように、従来の分散ソーティングアルゴリズムにおいては、局所空間計算量を制限した上で時間複雑度と通信要素数により評価される通信複雑度とが共に最適なアルゴリズムは存在しない。そこで、本発明においては、局所空間計算量を［数２］ビットに、１メッセージ長を［数３］ビットに制限した上で、時間複雑度と通信要素数により評価される通信複雑度とを共に厳密に最適にするアルゴリズムの構築を行う。
【数３】
【０００８】その際に対象とする問題は、時間最適なアルゴリズムが既に存在するＨｏｆｓｔｅｅらの扱った問題をより自然な形にした問題を対象とする。具体的には、線形ネットワーク上で各プロセスが丁度１要素ずつ保持する場合に左から順番に並べ替える分散ソーティングを扱う。そして、各プロセスの要素数に関して拡張した問題に対しても適用できるように拡張する。
【０００９】以下では、より具体的な問題の定義を行うが、その前に、分散システムとネットワークのモデルの説明を行う。本発明では、図１に示すような、プロセスＰ１、Ｐ２、…、ＰｎとＰｉ，１≦ｉ＜ｎと［外１］の間の双方向通信リンクから構成される線形ネットワークを対象とする。一般性を失うことなく、Ｐ１が左端となるように水平に置かれていると仮定する。このとき、各プロセスは左右の隣接プロセスをそれぞれ“ｌｅｆｔ”と“ｒｉｇｈｔ”という局所名でのみ認識する。但し、左右の認識は全プロセスで一致しており、端プロセスではこれらのうち対応する局所名がｎｕｌｌとなる。
【外１】
【００１０】また、プロセスＰｉは自身の識別子ｉとプロセス数ｎを知らないと仮定する。このような仮定の下で、各プロセスは隣接プロセスと適切な回数だけ通信を行うことで問題を解決する。このようなシステムのモデルには主に同期モデルと非同期モデルとがある。(参考文献:[4]亀田恒彦,山下雅史,分散アルコ゛リス゛ム,近代科学社、1994,[5]Nancy A.Lynch,Distributed Algorithms,Morgan Kaufmann、1996.)また、一般に、分散アルゴリズムの評価には時間複雑度と通信複雑度との二つの基準が存在する。前者は同期モデルではラウンド数、非同期モデルではメッセージの最長鎖に属するメッセージ数で表される。一方、後者にはメッセージ複雑度とビット複雑度とがあり、それぞれ総メッセージ数、メッセージの総ビット数で表される。
【００１１】最後に、本発明で扱う分散ソーティング問題を定義する。
【００１２】問題１：初期状態においてプロセスＰｉはソートの対象となる要素ｕｉを保持している。そして、最終状態において下記の条件［数４］を満たす要素ｕｉを保持するように各要素を移動させるのが問題である。
【数４】
【００１３】問題２：初期状態においてプロセスＰｉはソートの対象となるｋｉ個の要素の集合［数５］を保持している。そして、最終状態において下記の条件［数６］を満たす［外２］個の要素からなる集合Ｂｉを保持するように各要素を移動させるのが問題である。
【数５】
【数６】
【外２】
【００１４】問題３：初期状態においてプロセスＰｉはソートの対象となる［外３］個の要素の集合［数５］を保持している。
【外３】
そして、最終状態において、下記の条件［数８］を満たす［外２］個の要素からなる集合Ｂｉを保持するように各要素を移動させるのが問題である。ただし、全要素数をｍとしたとき［数７］であるとする。
【数７】
【数８】
【００１５】なお、問題３は動的な問題の一種である。(参考文献:[6]Doron Rotem,NicolaSantoro,and Jeffrey B.Sidney,Distributed Sortimg,IEEE Thonsactions on Computers,Vol.C-34,No.4,pp.372-376,1985.)また、問題３の条件のうち、［数９］が満たされない場合、つまり、［数１０］のときには、そのようなプロセスＰｉは通信を中継するだけになる。そのため、この条件は問題の本質とは関係ないが、問題の簡略化のために置いている。
【数９】
【数１０】
【００１６】
【課題を解決するための手段】［問題１を解決するための手段］前記問題１を解決するために、本発明の同期モデルにおける分散ソーティング方法は、初期状態では、左端のプロセスＰ１はｌｅｆｔ状態、右端のプロセスＰｎはｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、Ｐ１が保持している要素とｌｅｆｔメッセージとをｒｉｇｈｔへ、Ｐｎが保持している要素とｒｉｇｈｔメッセージとをｌｅｆｔへと送信することで起動し、ｗａｉｔ状態のプロセスがｌｅｆｔメッセージを受信したらｌｅｆｔ状態へ、ｗａｉｔ状態のプロセスがｒｉｇｈｔメッセージを受信したらｒｉｇｈｔ状態へ、ｗａｉｔ状態のプロセスが同時にｌｅｆｔメッセージとｒｉｇｈｔメッセージとを受信したらｒｅｌａｙ状態へ、ｌｅｆｔ状態のプロセスがｒｉｇｈｔメッセージを受信したらｒｅｌａｙ状態へ、ｒｉｇｈｔ状態のプロセスがｌｅｆｔメッセージを受信したらｒｅｌａｙ状態へと遷移し、ｌｅｆｔ状態のプロセスは、毎ラウンド保持している要素のうちの最大の要素をｒｉｇｈｔへ、ｒｉｇｈｔ状態のプロセスは、毎ラウンド保持している要素のうちの最小の要素をｌｅｆｔへ、２要素以上保持するｒｅｌａｙ状態のプロセスは、毎ラウンド保持している要素のうち、最大の要素をｒｉｇｈｒへ、最小の要素をｌｅｆｔへ、１要素のみを保持するｒｅｌａｙ状態のプロセスは、毎ラウンド保持している要素を直近の端プロセスの方向へと送信する、という処理を、ｌｅｆｔ，ｒｉｇｈｔのそれぞれから受信した要素数と同じ数の要素を、それぞれの方向へ送信し終わるまで各プロセスが同期的に繰り返す。
【００１７】このうち、状態遷移の仕方を図２に示した。図２は制御メッセージによるプロセスの状態遷移の仕方を示す。各楕円が各状態を表し、各矢印が各状態遷移を表す。そして、矢印に付与されているｌｅｆｔ、ｒｉｇｈｔは、その制御メッセージの受信により状態遷移が起ることを示している。なお、ｗａｉｔ状態からｒｅｌａｙ状態へ向かう矢印に付与されているｂｏｔｈは、ｌｅｆｔメッセージとｒｉｇｈｔメッセージとを同時に受信することを示している。各プロセスの初期状態は、Ｐ１がｌｅｆｔ状態、Ｐｎがｒｉｇｈｔ状態で、残りのすべてのプロセスがｗａｉｔ状態である。また、ｒｅｌａｙ状態に遷移しない限り、実行が終了することはない。
【００１８】本発明の分散ソーティング方法は、厳密に最適な時間複雑度ｎ−１と、通信要素数によって評価した場合の厳密に最適な通信複雑度［外４］とを実現することを特徴とする。
【外４】
【００１９】本分散ソーティング方法を非同期モデルにおいて適用するには、同期メッセージを使用すればよい。これにより、非同期モデルにおいても、厳密に最適な時間複雑度と最適な通信要素数とを実現することができる。
【００２０】［問題２を解決するための手段］前記問題２を解決するために、本発明の分散ソーティング方法は、問題１を解決する分散ソーティング方法に、さらに、ｗａｉｔ状態で２要素以上保持するプロセスは、毎ラウンド保持している要素のうち、最大の要素をｒｉｇｈｔへ、最小の要素をｌｅｆｔへ、ｌｅｆｔ状態で２要素以上保持するプロセスは、毎ラウンド保持している要素のうち最小の要素をｌｅｆｔへ、ｒｉｇｈｔ状態で２要素以上保持するプロセスは、毎ラウンド保持している要素のうち最大の要素をｒｉｇｈｔへ、と送信する処理を追加して実行する構成とすることもできる。
【００２１】［問題３を解決するための手段］前記問題３を解決するために、本発明の分散ソーティング方法は、問題２を解決する分散ソーティング方法に、さらに、ｌｅｆｔメッセージに、それを送信したプロセスから左のプロセス集合の初期状態の総要素数と最終状態の総要素数との差を、ｒｉｇｈｔメッセージに、それを送信したプロセスから右のプロセス集合の初期状態の総要素数と最終状態の総要素数との差を、それぞれ添付し、ｗａｉｔ状態から他の状態に遷移するときに、その添付された値を利用して次のラウンドで送信するｌｅｆｔメッセージ、あるいは、ｒｉｇｈｔメッセージに添付する値を計算し、さらに、同様の計算により、ｌｅｆｔ、ｒｉｇｈｔから受信した要素数を記憶しているプロセス内部の局所変数を、最終状態で保持する要素数に応じて書き換えてｌｅｆｔ、ｒｉｇｈｔへ送信する要素数を調整することにより構成することもできる。
【００２２】本発明の別の観点は、所定のハードウェアと、このハードウェアにインストールされた所定の基本ソフトウェアとを備えたコンピュータ装置に、さらにインストールすることによりそのコンピュータ装置に本発明の分散ソーティング方法を実行させるソフトウェアが記録された記録媒体である。
【００２３】
【発明の実施の形態】ここでは、前記分散ソーティング方法のより詳細な記述を示す。以下では、同期モデルにおけるアルゴリズムのみを示す。なお、非同期モデルにおける記述は、同期メッセージを加えて同期的に動作するだけであるため、問題１を解決するアルゴリズムでの同期メッセージの追加方法のみを簡単に説明し、問題２、３を解決するアルゴリズムでの追加方法は省略する。また、各問題を解決するアルゴリズムの骨格は同じであり、問題２、３を解決するアルゴリズムは問題１を解決するアルゴリズムの一部を変更して構築されているので、問題１を解決するアルゴリズムはアルゴリズム全体（１ラウンドあたりの処理）を詳細に示すが、問題２を解決するアルゴリズムは問題１を解決するアルゴリズムからの拡張法を、問題３を解決するアルゴリズムは問題２を解決するアルゴリズムからの拡張法を示すに止める。
【００２４】なお、いずれのアルゴリズムにおいても、文献［１］または下記文献［７］で述べられている要素のエンコード（圧縮）方法を用いると、通信するビット数を減らすことが可能になる。このときの問題１に対するビット複雑度は［数１１］となり、文献［１］と同様に、オーダーとしては最適である（参考文献:[7]Michael C.Loui,The Complexity of Sorting on Distributed Systems,Informationand Control,Vo1.60,No.1-3,pp.70-85、1984.)。
【数１１】
【００２５】［問題１を解決するアルゴリズムの詳細］
各命令の定義ｓｅｎｄ（（ｖ，ｍ），Ｐ）：メッセージ（ｖ，ｍ）をプロセスＰへ送信する。ただし、ｖは要素、ｍは制御メッセージ∈｛ｌｅｆｔ，ｒｉｇｈｔ，ｎｕｌｌ｝で、Ｐは隣接プロセスへのポインタ∈｛ｌｅｆｔ，ｒｉｇｈｔ｝である。ｓｌｅｅｐ：ｕｉ：＝ｖ∈Ｕとし、アルゴリズムの実行を終了する。なお、この命令が実行されるときには｜Ｕ｜＝１である。
【００２６】なお、実際の動作においてはｒｅｃｅｉｖｅ命令も必要になるが、本発明における記述においては、各ラウンドの最初に自動的にｒｅｃｅｉｖｅ命令が実行されて、適宜変数ｖＬ、ｖＲが更新され、受信したメッセージの制御メッセージと受信した方向とによって実行の選択を行う。
【００２７】［プロセスＰｉの各局所変数の定義］
ｕｉ：保持する要素の初期値あるいは解ｓｔａｔｅ：プロセスの状態で、ｗａｉｔ，ｌｅｆｔ，ｒｉｇｈｔ，ｒｅｌａｙのいずれか（初期値：ｗａｉｔ）。
Ｕ：保持する要素の集合（初期値：｛ｕｉ｝）。
ｖＬ，ｖＲ：ｌｅｆｔ，ｒｉｇｈｔから受信した要素（初期値：任意）。
ｕＬ，ｕＲ：直前にｌｅｆｔ，ｒｉｇｈｔへ送信した要素（初期値：一∞、∞）。
ｎｓ：送信が必要な要素数（初期値：０）。
ｄｉｒｅｃｔｉｏｎ：要素の送信を要する方向で、ｌｅｆｔ，ｒｉｇｈｔ，ｂｏｔｈ，ｎｕｌｌのいずれか（初期値：ｎｕｌｌ）。
【００２８】［ラウンド０における処理］ラウンド０においては、両端のプロセスのみが下記［数１２］のように実行する。他のプロセスはｗａｉｔ状態のまま何もしない。
【数１２】
【００２９】［ラウンド１以降の処理］Ｐｉは自身の状態（ｓｔａｔｅの値）に応じて、処理を下記［数１３］から選択して実行する。
【数１３】
【００３０】［問題１を解決するアルゴリズムにおける同期メッセージの追加方法］最も単純な方法は、毎回すべての通信リンクで通信が行われるように同期メッセージをやり取りする方法である。具体的には、上記アルゴリズムで何もメッセージが送信されない通信リンクに対して同期メッセージを送信する。なお、各プロセスが最初に送受信するメッセージは、起動メッセージとしても使用できる。
【００３１】一方、必要としない部分で同期メッセージを使用すると、同期メッセージに伝送の遅れが生じた場合にアルゴリズムの実行の遅れに結び付くという問題があるので、同期メッセージの数を必要最小限に抑えることが望ましい。そこで、（１）ｌｅｆｔ状態、またはｒｉｇｈｔ状態で要素を保持しなくなったプロセス、および（２）ｒｅｌａｙ状態になってから保持する要素数が１になったプロセスでは同期メッセージを送信しないようにする。ただし、同期メッセージを送信しなくなる直前のラウンドにおいて、次のラウンドからは同期メッセージを送信しないことを示す信号を隣接プロセスに送信する必要がある。これは、同期メッセージを２種類用意することで実現できる。このようにすると、同期メッセージ数を必要最小限に抑えることができる。
【００３２】［問題２を解決するアルゴリズムヘの拡張］問題２を解決するアルゴリズムは、問題１を解決するアルゴリズムの一部を変更することで構成される。以下にその変更点の概要を示す。なお、∀ｉ，ｋｉ≧２の場合には、このアルゴリズムは文献〔２〕のアルゴリズムと同一の動作をする。
【００３３】１．ｕｉを｛ｕｉ，１，ｕｉ，２，…，ｕｉ，ｋｉ｝に置き換え、［数５］とする。なお、Ｕの初期値もＢｉに変更される。これに伴い、ｓｌｅｅｐの定義とラウンド０における両端のプロセスの処理を下記のように変更する。ｓｌｅｅｐの定義：Ｂｉ：＝Ｕとし、アルゴリズムの実行を終了する。なお、この命令が実行されるときには、｜Ｕ｜＝ｋｉである。ラウンド０における両端のプロセスの処理：［数１４］
【数１４】
【００３４】２．ｗａｉｔ状態においてもｋｉ≧２のプロセスＰｉは要素の送信をラウンド０から開始する。つまり、ｋｉ≧２のプロセスＰｉは、ｍｉｎＵをｌｅｆｔへ、ｍａｘＵをｒｉｇｈｔへと送信する。このとき、ｌｅｆｔまたはｒｉｇｈｔからも要素が送信された場合には、送信した要素と受信した要素とを比較し、昇順となるような要素を保持する。つまり、ｌｅｆｔからｖＬを受信したとき、直前にｌｅｆｔへ送信した要素ｕＬと比較し、ｍａｘ｛ｕＬ，ｖＬ｝を保持する。ただし、ｕＬを保持することになった場合には、４の処理が加わる。ｒｉｇｈｔとの通信に関してはこの逆になる。
【００３５】３．ｌｅｆｔ，ｒｉｇｈｔ状態において、要素数が２以上の場合には中央方向への要素の送信とは別に、葉方向にも要素を送信する。但し、葉方向へ送信した要素は、相手側からも要素が送信され、かつ、それと交換される場合にのみ移動する。一方、中心方向へ送信した要素は、中心方向のプロセスからも要素が送られ、かつ、それら要素が交換されない場合にのみ、移動させずに残し、他の場合には中心方向のプロセスへ移動させる。各プロセスは、ｒｅｌａｙ状態になるときには制御メッセージを受信するため、直前のラウンドにおける隣接プロセスの状態を知ることができる。そのため、何も制御メッセージが送受信されないときに、これらの処理を行えば良い。
【００３６】４．問題１を解決するアルゴリズムにおける変数ｎｓの代わりに、変数ｎＬ，ｎＲを用意し、左右へ送信すべき要素数をそれぞれ計算して記憶する。ただし、これらの変数の値が負のときには、その絶対値の要素数を受信する必要があることを表す。そして、それらの値により、ｗａｉｔ状態とｒｅｌａｙ状態において、（ａ）隣接プロセス間で互いに要素を送信し合ったものの、それら要素の交換が起らない場合、（ｂ）保持する要素数が１の場合、に要素の移動を制御する。つまり、交換が起こらない場合には要素を交換する代わりに要素数の調整（要素の移動）を行い、要素数が１の場合にはｖＬ，ｖＲのうち値が正の方向に要素を送信する。値が共に負あるいは共に０ならば、要素の送信を行わない。一方が負で一方が０のときには、ｗａｉｔ状態では０の方向へ要素を送信し、ｒｅｌａｙ状態では要素の送信は行わない。なお、要素数が１の場合においては、値が共に正になることはあり得ない。そして、両方向に対する値ｎＬ，ｎＲが共に０になり、かつ、プロセス内で交換が起らなければ終了する。
【００３７】５．問題１を解決するアルゴリズムではすベてのプロセスが同時にソートを完了したが、問題２においては同時に完了する保証がない。そして、ソートが完了したプロセスは通信を行わなくなるため、ソートが完了した次のラウンドに、ソートが完了した旨を隣接プロセスへ通知する。これにより、その隣接プロセスからメッセージが送信されないようにする。なお、両隣からこの信号を受信したプロセスは自身の判断に関わらず実行を終了する。また、既にこの信号を受信した方向へは同信号を発信する必要はない。
【００３８】なお、２．、３．、４．の終了条件以外の変更に関しては、ソートの正当性とは関係なく、高速化にのみ影響する。つまり、１．、５．と４．の終了条件に関わる変更のみを施せば、上記すべての変更を施した場合よりも時間複雑度が上昇するものの、ソート自体は正しく実行される。
【００３９】［問題３を解決するアルゴリズムヘの拡張］問題３を解決するアルゴリズムは、問題２を解決するアルゴリズムの一部を変更することで構成される。以下にその変更点の概要を示す。
【００４０】まず、変数等の定義部分の変更を示す。問題２を解決するアルゴリズムにおけるｓｌｅｅｐの定義の注釈にあるｋｉを［外２］に置き換える。その他に、変数の定義におけるｋｉを［外３］に置き換える。
【００４１】次に、アルゴリズム部分の変更を示す。問題３においては、初期状態と最終状態とで各プロセスが保持する要素数が異なるため、単純に送受信した要素数から最終状態までに送信しなければならない要素数が求まるわけではない。初期状態と最終状態とで保持する要素数の差を端から順次隣接プロセスに送信し、それを基に送信要素数と送信方向とを判断する必要がある。具体的には、次のような処理を追加する。この処理はｗａｉｔ状態から他の状態へ遷移するときに行われる。
【００４２】１．端プロセスＰ１、Ｐｎ：ラウンド０において、Ｐｉ，ｉ＝１，ｎは［数１５］を他の送信メッセージと共に隣接プロセスへ送信する。
【数１５】
この値は、初期状態から最終状態までの間に隣接プロセスへ送信する要素数を表すので、Ｐ１ではｎＲに、ＰｎではｎＬに代入する。
【００４３】２．Ｐｉが一方の隣接プロセスからｋ′という値を受信した場合：このラウンドの受信が終了した時点でＰｉが保持している要素数を［外５］とする。
【外５】
また、受信した方向をＤ、逆方向を［外６］とし、ｎＤはｎＬかｎＲのいずれかであるとする。まず、ｎＤは［数１６］のように決まる。
【外６】
【数１６】
【００４４】次いで、［数１７］とし、［外７］を［外６］の方向に送信する。
【数１７】
【外７】
【００４５】３．左右の隣接プロセスからそれぞれｋＬ，ｋＲを同時に受信した場合：これが起こるのは、ｎが奇数の場合の［外８］だけである。この場合には、それぞれの方向に対し、［数１８］のようにｎＬ，ｎＲを決める。ただし、ｋＬ，ｋＲのどちらか一方のみに基づいて、その値のみを受信した場合の処理を行ってもｎＬ，ｎＲは同じ値が求まるはずである。
【外８】
【数１８】
そのため、そのような処理と本処理とを共に行うことで他プロセスの故障等のエラーの検出も可能となる。なお、ｋ′はその方向から受信した値で、ｋＬかｋＲのいずれかである。
【００４６】なお、この後隣接プロセスへはこの値を送信しない。
【００４７】４．２回目の受信（１回目とは逆方向からの受信）は無視する。ただし、これが起るのは、ｎが偶数の場合の［外９］と［外１０］だけである。
【外９】
【外１０】
上記のｎＬ、ｎＲの変更が影響するのはｒｅｌａｙ状態における要素の移動時だけなので、他の状態における動作は、問題２を解決するアルゴリズムと全く変わりない。ｒｅｌａｙ状態でも、値が変わっただけでアルゴリズム自体に変化はないため、［外１１］ラウンドまでの動作とそれ以降の動作とが対応しないことを除けば、両者の間に何ら違いはない。
【外１１】
【００４８】［具体例］以下では、上記方法を用いた具体的な実施例を示す。詳細なメッセージの内容まで示した例は例１でのみ扱い、それ以降の例においては、各ラウンドで各プロセスが保持する要素のみを表の形で示すに止める。文献［１］、［７］で述べられているエンコード方法を用いた場合の通信についても、例１でのみ示す。また、非同期モデルにおける動作は、同期メッセージが存在することを除けば本質的に同期モデルにおける動作と同一なので、具体的な例は省略する。なお、各プロセスの状態は、そのラウンドにおける送信処理（ｓｅｎｄ命令）の直前までの実行が終わった状態を示す。
【００４９】例１：問題１を解決するアルゴリズム（その１）
まず、本発明の基盤となる問題１を解決するアルゴリズムの例を示す。最初に、例１として、比較的小さなｎ＝５プロセスからなる線形ネットワークを取り上げ、詳細なメッセージの内容も含めた実行例を図を使用して示す。例１では、図３のような初期状態が与えられた場合の実行例を示す。ここで、各プロセスに記された数字は、そのプロセスが保持している要素を示す。
【００５０】ラウンド１：図４に示すように、左端プロセスＰ１が保持している要素“５”とｌｅｆｔメッセージをｒｉｇｈｔへ、右端プロセスＰ５が保持している要素“１”とｒｉｇｈｔメッセージをｌｅｆｔへ送信する。そして、Ｐ２がＰ１から上記メッセージを受信してｌｅｆｔへ遷移し、Ｐ４がＰ５から上記メッセージを受信してｒｉｇｈｔ状態へ遷移し、要素の配置は図５に示すようになる。
【００５１】ラウンド２：図６に示すように、ｌｅｆｔ状態になった直後のＰ２が、保持している要素のなかの最大値“５”とｌｅｆｔメッセージをｒｉｇｈｔへ、ｒｉｇｈｔ状態になった直後のＰ４が、保持している要素の中の最小値“１”とｒｉｇｈｔメッセージをｌｅｆｔへ送信する。なお、Ｐ１、Ｐ５は何も要素を持たないため、何もしない。そして、Ｐ３がＰ２、Ｐ４から上記メッセージを受信してｒｅｌａｙ状態へと遷移し、要素の配置は図７に示すようになる。
【００５２】ラウンド３：図８に示すように、ｌｅｆｔ状態のＰ２が、保持している要素“４”とｎｕｌｌメッセージをｒｉｇｈｔへ、ｗａｉｔ状態からｒｅｌａｙ状態になった直後のＰ３が保持している要素のなかの最小値“１”とｒｉｇｈｔメッセージをｌｅｆｔへ、保持している要素のなかの最大値“５”とｌｅｆｔメッセージをｒｉｇｈｔへ、ｒｉｇｈｔ状態のＰ４が、保持している要素“２”とｎｌｌメッセージをｌｅｆｔへ送信する。なお、ラウンド２のときと同様に、Ｐ１、Ｐ５は何も要素を持たないため何もしない。このとき、Ｐ２とＰ３、Ｐ３とＰ４の間で要素を互いに送り合っているので、各プロセスでは、それぞれの間で送り合った要素が昇順になるように、送信した要素か受信した要素かを保持する。
【００５３】なお、文献［１］、［７］で述べられているエンコード方法を利用した場合には、このラウンドにおける通信が図９に示すようになる。ここで、Ｐ２からＰ３へ送られている値“１”は、直前にＰ２からＰ３へ送信された要素“５”と、ここで送信する要素“４”の差分を示している。同様に、Ｐ４からＰ３へ送られている値“１”は、直前にＰ２からＰ３へ送信された要素“１”と、ここで送信する要素“２”の差分を示している。これにより、送信する値をより小さな値にすることができるため、ビット数を節約することが可能になる。エンコードを用いた場合でも用いない場合でも、このような通信により、要素の配置は図１０に示すようになる。また、Ｐ２はｒｉｇｈｔメッセージを、Ｐ４はｌｅｆｔメッセージを受信したことにより、共にｒｅｌａｙ状態へと遷移する。
【００５４】ラウンド４：図１１に示すように、ｌｅｆｔからｒｅｌａｙ状態へと遷移して１要素しか持たないＰ２が、唯一保持している要素“１”とｒｉｇｈｔメッセージをｌｅｆｔへ、ｒｅｌａｙ状態のＰ３が、保持している要素のなかの最小値“１”とｎｕｌｌメッセージをｌｅｆｔへ、保持している要素のなかの最大値“５”とｎｕｌｌメッセージをｒｉｇｈｔｆへ、ｒｉｇｈｔ状態からｒｅｌａｙ状態へと遷移して１要素しか持たないＰ４が、唯一保持している要素“５”とｌｅｆｔメッセージをｒｉｇｈｔへ送信する。なお、エンコード方法を利用した場合には、ラウンド３と同様に、図１２に示すような通信が行われる。そして、Ｐ１はｒｉｇｈｔメッセージを、Ｐ５はｌｅｆｔメッセージを受信することでｒｅｌａｙ状態へと遷移し、要素の配置は図１３に示すようになり、さらに、すべてのプロセスにおいてｎｓ＝０となり、ソートが完了する。
【００５５】例２：問題１を解決するアルゴリズム（その２）
例１では比較的小さなネットワークにおける詳細な実行例を示したが、例２では、もう少し大きなｎ＝１４プロセスからなる線形ネットワークを取り上げ、各ラウンドにおいて各プロセスが保持している要素のみを提示することで実行例を示す。なお、例３、４でも例２と同様の表現による実行例を示す。
【００５６】例２では、同一の１４プロセスからなる線形ネットワークにおける初期状態が異なる二つの例を図１５、図１６で示す。図１５、図１６では、各プロセス（横軸）の各ラウンド（縦軸）において保持している要素を示す。なお、見やすくするために各要素は１６進数を用いて一文字で示す。降順の要素列を入力したときの動作を図１５に示す。ランダムな要素列を入力したときの動作を図１６に示す。
【００５７】例３：問題２を解決するアルゴリズム例３では、問題２を解決するアルゴリズムの実行例を示す。要素数がプロセス数よりも多くなる分だけ複雑になるため、例２よりも小さなｎ＝９プロセスの線形ネットワークにおける例を示す。なお、ｎＬ、ｎＲが要素の移動と終了判定に用いられるため、各プロセスが保持している要素だけでなく、各プロセスの該変数の内容も合わせて示す。なお、該変数の値は、保持している要素の両隣に小さく示す。そのうち左にあるのがｎＬの値で、右にあるのがｎＲの値である。例３の動作を図１７に示す。
【００５８】ラウンド９では、１要素のみを保持するどのプロセスにおいてもｎＬ＝ｎＲ＝０であり、かつ、２要素以上保持するどのプロセスにおいても、ｎＬ＝ｎＲ＝０かつ、このラウンドではプロセス内部で要素の交換が起こらなかったため、この時点ですべてのプロセスにおいて同時にアルゴリズムの実行を終了する。なお、Ｐ６はラウンド８の時点でソートが完了しているように見えるがラウンド８ではＰ６の内部でａとｂが交換されているため、Ｐ６はソート完了を認識していない。この例３においては、アルゴリズムは最適な時間でソートを完了している。
【００５９】例４：問題３を解決するアルゴリズム例４では、問題３を解決するアルゴリズムの実行例を示す。本アルゴリズムと問題２を解決するアルゴリズムとの違いは、変数ｎＬ，ｎＲによる送信要素数の制御の部分だけなので、例３と同様に、各プロセスが保持している要素だけでなく、各プロセスの該変数の内容も合わせて示す。また、問題３では、初期状態と最終状態とで各プロセスが保持する要素数が異なるので、最終状態で保持する要素数をプロセス番号の表示の後ろの括弧内に提示する。
【００６０】例４では、例３と対比できるように、例３と同じｎ＝９プロセスの線形ネットワークにおいて、例３と同じ初期状態の例を挙げる。さらに、この例４においては、各プロセスのソート完了時刻が例３のように同時ではないので、図１８においてソート完了時刻を明示的に示すために、ソート完了後には要素と変数の値の表示を行わないようにする。例４の動作を図１８に示す。
【００６１】例５、６：問題３を解決するアルゴリズム−特殊な例例４では問題３の一般的な形の問題例を取り上げたが、例５、６では特殊な形の問題例を取り上げる。
【００６２】まず、例５で取り上げる問題は、線形ネットワークの右半分にのみ要素があり、それをソートしながらネットワークの左半分に移動させるという問題である。この問題は、一見、今までのソーティングとは異なっているように見えるが、実際には、問題３の特殊な場合にすぎない。つまり、ネットワークの左半分のプロセスＰｉは［数１９］で、ネットワークの右半分のプロセスＰｊでは［数２０］の場合である。
【数１９】
【数２０】
このように、このアルゴリズムにより、線形ネットワーク上のデータをソートしつつ移動させることも可能である。例５で取り上げる問題では、ｎ＝１４プロセスで要素数７の場合を取り上げる。なお、見やすくするために、例３、４のようなｎＬ、ｎＲの表示は行わない。また、各プロセスＰｉが最終状態で保持する要素数［外２］は、［数１９］のプロセスでは［数２１］とし、［数２２］のプロセスでは［数２０］とする。例５の動作を図１９に示す。
【数２１】
【数２２】
【００６３】次に、例６では、例５とは異なり、移動元のプロセスと移動先のプロセスとに重複がある場合を取り上げる。具体的には、Ｐｎ−ｉ＋１からＰｎまでにひとつずつ要素があり、それらをＰ１からＰｉへソートさせつつ移動させる問題を扱う。ここで、ｎ＜２ｉの場合に移動元のプロセスと移動先のプロセスとに重複が生じる。例６では、ｎ＝１０、ｉ＝７の例を示す。例６の動作を図２０に示す。
【００６４】例５の形式の問題だけであれば、右から順次小さい値を左へ送信していくことで要素をソートさせつつ移動させることができるが、その方法では、この例６には対応できない。しかし、問題３を解決するアルゴリズムを利用するとどちらの問題に対してもひとつのアルゴリズムで対応することができる。これらの例に限らず、様々な形式の要素をソートさせつつ移動させる問題に対応することが可能である。
【００６５】本発明の分散ソーティング方法は、所定のハードウェアと、このハードウェアにインストールされた基本ソフトウェアとを備えたコンピュータ装置に、さらにインストールすることによりそのコンピュータ装置に本発明の分散ソーティング方法を実行させるソフトウェアが記録された記録媒体を用いてコンピュータ装置に当該ソフトウェアをインストールすることにより実現する。
【００６６】
【発明の効果】本発明により、ｎプロセスから構成される線形ネットワークにおいて、ソートすべき要素を左のプロセスから１プロセスあたり１要素ずつ昇順に並べ替える分散ソーティングを、厳密に最適な時間複雑度ｎ−１と、通信要素数によって評価した場合の厳密に最適な通信複雑度［外４］とで実行できる。
【００６７】また、同ネットワークにおいて、各プロセスが初期状態と最終状態で保持する要素数が１以上の場合の分散ソーティングを、高速に解決することができる。
【００６８】さらに、同ネットワークにおいて、初期状態と最終状態とで各プロセスが保持すべき要素数が異なる分散ソーティングを、高速に解決することができる。
【００６９】これらのアルゴリズムでは、文献［１］、［７］で述べられているエンコード方法を用いることで、オーダーとして最適なビット複雑度［数１１］を実現することが可能である。
|
| 【出願人】 |
【識別番号】０００００４２２６
【氏名又は名称】日本電信電話株式会社
|
| 【出願日】 |
平成１２年１０月２６日（２０００．１０．２６） |
| 【代理人】 |
【識別番号】１０００７８２３７
【弁理士】
【氏名又は名称】井出 直孝 （外１名）
|
| 【公開番号】 |
特開２００２−１３２４９３（Ｐ２００２−１３２４９３Ａ） |
| 【公開日】 |
平成１４年５月１０日（２００２．５．１０） |
| 【出願番号】 |
特願２０００−３２７２３６（Ｐ２０００−３２７２３６） |
|