(57)【要約】  ソート処理を高速化した並列ソート装置を提供する。  基準値算出部１は、入力データを値の大きさよって振り分けるための区間の境界となる複数の基準値を算出する。入力データ集計部２は、入力データを複数の入力データ領域に区切り、区切った各入力データ領域内のデータを、基準値算出部１で算出された基準値を境界とする複数の区間に振り分けるための写像情報を並列処理で算出する。データ振分部３は、入力データ集計部２によって算出された写像情報に従って、各入力データ領域内のデータを並列処理で複数の区間に振り分ける。区間ソート部４は、データ振分部３により振り分けられた複数の区間のデータを並列処理でそれぞれにソートする。
2008078517.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータからなる入力データを並列処理によりソートする並列ソート装置であって、
前記入力データに基づいて、該入力データを値の大きさよって振り分けるための区間の境界となる複数の基準値を算出する基準値算出部と、
前記入力データを複数の入力データ領域に区切り、区切った前記各入力データ領域内のデータを、前記基準値算出部で算出された前記基準値を境界とする複数の前記区間に振り分けるための写像情報を並列処理で算出する入力データ集計部と、
前記入力データ集計部によって算出された前記写像情報に従って、前記各入力データ領域内のデータを並列処理で複数の前記区間に振り分けるデータ振分部と、
前記データ振分部により振り分けられた複数の前記区間のデータを並列処理でそれぞれにソートする区間ソート部と、を有する並列ソート装置。
【請求項２】
前記写像情報は、複数の前記入力データ領域に含まれるデータを複数の前記区間に振り分けるとき、複数の前記区間に振り分けられたデータを蓄積する、前記区間に対応した出力データ領域を決定するための情報であり、
前記入力データ集計部は、前記区間の各々に含まれるデータの個数を前記入力データ領域毎にカウントし、カウント結果を該入力データ領域毎に集計することにより、複数の前記出力データ領域の各々が、前記区間に振り分けられたデータを該データ同士が重なり合わないように蓄積できるサイズとなるように前記写像情報を算出する、請求項１に記載の並列ソート装置。
【請求項３】
前記入力データ領域の個数が、前記並列処理を実行する複数のプロセッサの個数と等しいかまたは前記プロセッサの個数の整数倍である、請求項１または２に記載の並列ソート装置。
【請求項４】
前記入力データ集計部は前記入力データを均等な前記入力データ領域に区切る、請求項１から３のいずれか１項に記載の並列ソート装置。
【請求項５】
前記区間ソート部は、複数の前記区間のそれぞれに振り分けられたデータの数に基づいて、前記並列処理を実行する複数のプロセッサの負荷が均等になるように、前記区間を前記プロセッサに割り当てる、請求項１から４のいずれか１項に記載の並列ソート装置。
【請求項６】
前記基準値によって区切られる前記区間の数が、前記並列処理を実行するプロセッサの数と等しいかまたは前記プロセッサの個数の整数倍である、請求項１から５のいずれか１項に記載の並列ソート装置。
【請求項７】
前記基準値算出部は、複数の前記区間に振り分けられるデータの数を均等にするように、前記入力データに対する統計処理によって前記基準値を算出する、請求項１から６のいずれか１項に記載の並列ソート装置。
【請求項８】
複数のデータからなる入力データを並列処理によりソートするための並列ソート方法であって、
前記入力データに基づいて、該入力データを値の大きさよって振り分けるための区間の境界となる複数の基準値を算出し、
前記入力データを複数の入力データ領域に区切り、
区切った前記各入力データ領域内のデータを、算出した前記基準値を境界とする複数の前記区間に振り分けるための写像情報を並列処理で算出し、
算出した前記写像情報に従って、前記各入力データ領域内のデータを並列処理で複数の整理番号前記区間に振り分け、
振り分けた複数の前記区間のデータを並列処理でそれぞれにソートする、並列ソート方法。
【請求項９】
前記写像情報は、複数の前記入力データ領域に含まれるデータを複数の前記区間に振り分けるとき、複数の前記区間に振り分けられたデータを蓄積する、前記区間に対応した出力データ領域を決定するための情報であり、
前記区間の各々に含まれるデータの個数を前記入力データ領域毎にカウントし、カウント結果を該入力データ領域毎に集計することにより、複数の前記出力データ領域の各々が、前記区間に振り分けられたデータを該データ同士が重なり合わないように蓄積できるサイズとなるように前記写像情報を算出する、請求項８に記載の並列ソート方法。
【請求項１０】
前記入力データ領域の個数が、前記並列処理を実行する複数のプロセッサの個数と等しいかまたは前記プロセッサの個数の整数倍である、請求項８または９に記載の並列ソート方法。
【請求項１１】
前記入力データを均等な前記入力データ領域に区切る、請求項８から１０のいずれか１項に記載の並列ソート方法。
【請求項１２】
複数の前記区間のそれぞれに振り分けられたデータの数に基づいて、前記並列処理を実行する複数のプロセッサの負荷が均等になるように、前記区間を前記プロセッサに割り当てて該区間のデータをソートさせる、請求項８から１１のいずれか１項に記載の並列ソート装置。
【請求項１３】
前記基準値によって区切られる前記区間の数が、前記並列処理を実行するプロセッサの数と等しいかまたは前記プロセッサの個数の整数倍である、請求項８から１２のいずれか１項に記載の並列ソート方法。
【請求項１４】
複数の前記区間に振り分けられるデータの数を均等にするように、前記入力データに対する統計処理によって前記基準値を算出する、請求項８から１３のいずれか１項に記載の並列ソート方法。
【請求項１５】
複数のデータからなる入力データを並列処理によりソートする処理をコンピュータに行なわせるための並列ソートプログラムであって、
前記入力データに基づいて、該入力データを値の大きさよって振り分けるための区間の境界となる複数の基準値を算出する手順と、
前記入力データを複数の入力データ領域に区切る手順と、
区切った前記各入力データ領域内のデータを、算出した前記基準値を境界とする複数の前記区間に振り分けるための写像情報を並列処理で算出する手順と、
算出した前記写像情報に従って、前記各入力データ領域内のデータを並列処理で複数の前記区間に振り分ける手順と、
振り分けた複数の前記区間のデータを並列処理でそれぞれにソートする手順と、をコンピュータに実行させるための並列ソートプログラム。
【請求項１６】
前記写像情報は、複数の前記入力データ領域に含まれるデータを複数の前記区間に振り分けるとき、複数の前記区間に振り分けられたデータを蓄積する、前記区間に対応した出力データ領域を決定するための情報であり、
前記区間の各々に含まれるデータの個数を前記入力データ領域毎にカウントし、カウント結果を該入力データ領域毎に集計することにより、複数の前記出力データ領域の各々が、前記区間に振り分けられたデータを該データ同士が重なり合わないように蓄積できるサイズとなるように前記写像情報を算出する、請求項１５に記載の並列ソートプログラム。
【請求項１７】
前記入力データ領域の個数が、前記並列処理を実行する複数のプロセッサの個数と等しいかまたは前記プロセッサの個数の整数倍である、請求項１５または１６に記載の並列ソートプログラム。
【請求項１８】
前記入力データを均等な前記入力データ領域に区切る、請求項１５から１７のいずれか１項に記載の並列ソートプログラム。
【請求項１９】
複数の前記区間のそれぞれに振り分けられたデータの数に基づいて、前記並列処理を実行する複数のプロセッサの負荷が均等になるように、前記区間を前記プロセッサに割り当てて該区間のデータをソートさせる、請求項１５から１８のいずれか１項に記載の並列ソートプログラム。
【請求項２０】
前記基準値によって区切られる前記区間の数が、前記並列処理を実行するプロセッサの数と等しいかまたは前記プロセッサの個数の整数倍である、請求項１５から１９のいずれか１項に記載の並列ソートプログラム。
【請求項２１】
複数の前記区間に振り分けられるデータの数を均等にするように、前記入力データに対する統計処理によって前記基準値を算出する、請求項１５から２０のいずれか１項に記載の並列ソートプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データのソートを並列処理する並列ソート装置、方法、およびプログラムに関する。
【背景技術】
【０００２】
データのソートを並列処理する方法の例が特許文献１、２に開示されている。【０００３】
図１は、特許文献１に開示された並列ソート方法を説明するための図である。図２は、特許文献１に開示された並列ソート装置の構成を示すブロック図である。これらの図を用いて特許文献１に開示された並列ソート技術について説明する。【０００４】
図２に示すように、ソートすべき入力データ８１が並列ソート装置に入力される。データ入力処理手段９２にて入力データ８１の入力処理がされ、主記憶領域９５に格納される。スレッド起動処理手段９３がスレッドプール９４内のスレッド（不図示）を起動されると、スレッドは主記憶領域９５からデータを読み込んで処理した後に書き戻すことを再帰的に繰り返す。スレッドプール９４による再帰処理によりソートが完了すると、データ出力処理手段９７が主記憶領域９５からデータを読み出して出力データ８５として出力する。【０００５】
図１を参照すると、１６個の値からなる入力データ８１が例示されている。スレッドは入力データ８１に対しキー８２を適当に選出する。ここではキー８２＝“１０”である。続いて、スレッドは、入力データ８１を、キー８２未満のデータ集合８３とキー以上のデータ集合８４に分類し、主記憶領域９５に格納する。その結果、（ａ）のように並んでいた入力データ８１は（ｂ）のように並べ替えられる。データ集合毎にキーを選択して分類する処理を再帰的に繰り返すことにより、最終的には（ｄ）のようにソートが完了する。【０００６】
図３は、特許文献２に開示された並列ソート方法を説明するための図である。特許文献２に開示された並列ソート技術では、（ａ）のように与えられたソートすべき入力データ１０１を、複数のプロセッサに対応させて、（ｂ）のように複数の部分に分割する。ここではプロセッサ０〜３という４個のプロセッサがあるとする。【０００７】
各プロセッサ０〜３は、割り当てられた部分の中のデータをソートする。その結果、（ｂ）のデータ１０２が（ｃ）のデータ１０３のように並べ替えられる。続いて、複数のプロセッサ０〜３により、部分内のソートが済んだデータ集合をマージする。ここでは、プロセッサ０に対応する部分とプロセッサ１に対応する部分とがマージされ、プロセッサ２に対応する部分とプロセッサ３に対応する部分とがマージされている。その結果、（ｃ）のデータ１０３が（ｄ）のデータ１０４のように並べ替えられる。このソートしてマージする処理を再帰的に繰り返すことにより、最終的には（ｅ）のようにソートが完了する。
【特許文献１】特開２００５−１８１５８号公報（第７−１２頁、図１）
【特許文献２】特許３４１５９１４号公報（第４−５頁、図１）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１に開示された並列ソート方法では、分類処理を実行すべきデータ集合毎にプロセッサが割り当てられるので、データ集合の数が多くならないと並列処理による効果が現れない。再帰処理の繰り返しにより分類が進んでいけばデータ集合の数が多くなるので徐々に並列処理による効果が現れるが、当初はデータ集合数がプロセッサ数よりも少ないので余ったプロセッサが待機している状態となる。例えば図１において、入力データ８１をデータ８３とデータ８４とに分類する処理は１台のプロセッサでのみ実行されるので他の全てのプロセッサは待機することになる。【０００９】
また、特許文献２に開示された並列ソート方法では、高速化のために、マージしたデータを主記憶領域上の別領域に格納しながら処理を進めるが、マージ処理の回数が多い。特許文献２の段落００７０にはマージ処理の一例としてトーナメント方式が用いられることが記載されている。トーナメント方式では何度もマージを繰り返すのでマージ処理の回数が多くなる。それ故、メモリシステムの動作速度が遅いコンピュータシステムでは、メモリへのアクセスを伴うマージ処理によりソートの高速化が妨げられる。【００１０】
本発明の目的は、ソート処理を高速化した並列ソート装置を提供することである。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明の並列ソート装置は、
複数のデータからなる入力データを並列処理によりソートする並列ソート装置であって、
前記入力データに基づいて、該入力データを値の大きさよって振り分けるための区間の境界となる複数の基準値を算出する基準値算出部と、
前記入力データを複数の入力データ領域に区切り、区切った前記各入力データ領域内のデータを、前記基準値算出部で算出された前記基準値を境界とする複数の前記区間に振り分けるための写像情報を並列処理で算出する入力データ集計部と、
前記入力データ集計部によって算出された前記写像情報に従って、前記各入力データ領域内のデータを並列処理で複数の前記区間に振り分けるデータ振分部と、
前記データ振分部により振り分けられた複数の前記区間のデータを並列処理でそれぞれにソートする区間ソート部と、を有している。【００１２】
本発明によれば、入力データを区切った複数の入力データ領域のデータを並列処理で複数の区間に振り分け、複数の区間のデータを並列処理でそれぞれにソートするので、時間が長くかかる処理を並列処理することにより全体のソート処理を高速化することができる。【００１３】
また、前記写像情報は、複数の前記入力データ領域に含まれるデータを複数の前記区間に振り分けるとき、複数の前記区間に振り分けられたデータを蓄積する、前記区間に対応した出力データ領域を決定するための情報であり、
前記入力データ集計部は、前記区間の各々に含まれるデータの個数を前記入力データ領域毎にカウントし、カウント結果を該入力データ領域毎に集計することにより、複数の前記出力データ領域の各々が、前記区間に振り分けられたデータを該データ同士が重なり合わないように蓄積できるサイズとなるように前記写像情報を算出することにしてもよい。【００１４】
これによれば、各入力データ領域のデータを振り分ける処理が互いに独立して実行できるようになり、複数の入力データ領域の処理を並列に実行できるようになる。【００１５】
また、前記入力データ領域の個数が、前記並列処理を実行する複数のプロセッサの個数と等しいかまたは前記プロセッサの個数の整数倍であるとしてもよい。【００１６】
これによれば、各入力データ領域に対応した処理をプロセッサに無駄なく割り当てることができ、プロセッサを効率よく利用できる。【００１７】
また、前記入力データ集計部は前記入力データを均等な前記入力データ領域に区切ることにしてもよい。【００１８】
これによれば、並列処理の負荷を均等にでき、並列処理の効率を高めることができる。【００１９】
また、前記区間ソート部は、複数の前記区間のそれぞれに振り分けられたデータの数に基づいて、前記並列処理を実行する複数のプロセッサの負荷が均等になるように、前記区間を前記プロセッサに割り当てることにしてもよい。【００２０】
これによれば、プロセッサの利用効率を高めて並列処理による高速化の効果を高めることができる。【００２１】
また、前記基準値によって区切られる前記区間の数が、前記並列処理を実行するプロセッサの数と等しいかまたは前記プロセッサの個数の整数倍であるとしてもよい。【００２２】
これによれば、区間毎の並列処理を行うプロセッサ間のばらつきによる処理時間の差を減らし易くなり、プロセッサの利用効率を高めることができる。【００２３】
また、前記基準値算出部は、複数の前記区間に振り分けられるデータの数を均等にするように、前記入力データに対する統計処理によって前記基準値を算出するとしてもよい。【００２４】
これによれば並列処理のプロセッサの利用効率がよくなる。
【発明の効果】
【００２５】
本発明によれば、時間がかかる処理を並列処理することによりソート処理を高速化することができる。
【発明を実施するための最良の形態】
【００２６】
本発明を実施するための形態について図面を参照して詳細に説明する。【００２７】
（第１の実施形態）
図４は、第１の実施形態による並列ソート装置の構成を示すブロック図である。図５は、第１の実施形態による並列ソート装置およびその各部の動作を説明するための模式図である。図４に示すように、並列ソート装置は、基準値算出部１、入力データ集計部２、データ振分部３、および区間ソート部４を有しており、それら各部が順次処理を実行することによりデータをソートする。図５に示すように並列ソート装置への入力が入力データ５である。並列ソート装置は入力データ５をソートし、ソートした結果を出力データ９として出力する。【００２８】
基準値算出部１は、入力データ５から、Ｌ−１個の基準値６−１〜６−（Ｌ−１）を選択する。これらの基準値６−１〜６−（Ｌ−１）は、入力データ５の各データを値の大きさよって振り分けるための境界となる。続いて、基準値算出部１は、Ｌ−１個の基準値６−１〜６−（Ｌ−１）を順序関係（値の大きさ）に従って並べることにより、Ｌ個の区間７−１〜７−Ｌを構成する。【００２９】
入力データ集計部２は、入力データ５をＭ個の入力データ領域５−１〜５−Ｍに区切る。このとき並列処理の効率を高めるには入力データ領域５−１〜５−Ｍのサイズが均等であることが好ましい。続いて、入力データ集計部２は、区切った各入力データ領域５−１〜５−Ｍ内のデータを、基準値算出部１により構成された区間７−１〜７−Ｌに振り分けるための写像情報８−１−１〜８−Ｍ−Ｌを算出する。【００３０】
この写像情報８−１−１〜８−Ｍ−Ｌを算出する際、入力データ集計部２は、各区間７−１〜７−Ｌに対応する処理を並列処理する。並列処理は、複数のプロセッサを各区間７−１〜７−Ｌに割り当てて振り分け処理を並列で実行してもよく、また複数のスレッドを定義して仮想的に並列処理を実行してもよい。【００３１】
また、この写像情報８−１−１〜８−Ｍ−Ｌを予め算出しておくことにより、入力データ領域５−１〜５−Ｍ毎に独立して振り分けの実行が可能となる。これにより各領域５−１〜５−Ｍの振り分けが並列処理できるようになる。【００３２】
データ振分部３は、入力データ集計部２によって算出された写像情報８−１−１〜８−Ｍ−Ｌに従って、入力データ領域５−１〜５−Ｍ内のデータを、区間７−１〜７−Ｌに対応した出力データ領域９−１〜９−Ｌに振り分ける。その際、データ振分部３は、各入力データ領域５−１〜５−Ｍを並列処理する。並列処理は、複数のプロセッサを各入力データ領域５−１〜５−Ｍに割り当てて振り分け処理を並列で実行してもよく、また複数のスレッドを定義して仮想的に並列処理を実行してもよい。【００３３】
区間ソート部４は、データ振分部３により振り分けられた出力データ領域９−１〜９−Ｌのデータをそれぞれソートする。その際、区間ソート部４は、各出力データ領域９−１〜９−Ｌを並列処理する。並列処理は、複数のプロセッサを各出力データ領域９−１〜９−Ｌに割り当てて振り分け処理を並列で実行してもよく、また複数のスレッドを定義して仮想的に並列処理を実行してもよい。区間ソート部４によるソートが完了するとソートされた出力データ９が得られる。【００３４】
図６は、第１の実施形態による並列ソート装置の動作を示すフローチャートである。図６を参照すると、まず、基準値算出部１は、入力データ５にあるデータ集合を用いて（Ｌ−１）個の基準値６−１〜６−（Ｌ−１）を算出する（ステップＡ１）。続いて、基準値算出部１は、基準値６−１〜６−（Ｌ−１）を順序関係に従って並べ、基準値６−１〜６−（Ｌ−１）が境界となるような区間７−１〜７−Ｌを算出する（ステップＡ２）。【００３５】
また、入力データ集計部２は入力データ５をＭ個の連続した入力データ領域５−１〜５−Ｍに区切る（ステップＡ３）。【００３６】
更に、入力データ集計部２は、入力データ領域５−１〜５−Ｍのそれぞれに対し、領域内の全てのデータの値を調べ、区間７−１〜７−Ｌに対応した領域にデータを振り分けるための写像情報８−１−１〜８−Ｍ−Ｌを算出する（ステップＡ４）。【００３７】
次に、データ振分部３は、入力データ領域５−１〜５−Ｍのそれぞれに対し、領域内の全てのデータの値を調べ、写像情報８−１−１〜８−Ｍ−Ｌに基づき各データを出力データ領域９−１〜９−Ｌに書き込む（ステップＡ５）。このようにすることにより、各出力データ領域９−１〜９−Ｌは、それぞれに対応する区間７−１〜７−Ｌ内の値のデータのみから構成された状態となる。【００３８】
最後に、区間ソート部４は、各出力データ領域９−１〜９−Ｌのそれぞれの内部のデータをソートする（ステップＡ６）。これにより全体がソートされた出力データ９が得られる。【００３９】
以上説明したように、本実施形態によれば、入力データ５を区切ったＭ個の入力データ領域５−１〜５−Ｍのデータを並列処理でＬ個の区間７−１〜７−Ｌに対応する領域に振り分け、Ｌ個の区間７−１〜７−Ｌ内のデータを並列処理でソートするので、時間が長くかかる処理を並列処理することにより全体のソート処理を高速化することができる。【００４０】
なお、本実施形態では、ステップＡ１による基準値を算出する処理、ステップＡ２による区間を算出する処理、およびステップＡ３による入力データ５を区切る処理は並列処理でない。しかし、ＬとＭを適切な値に設定することにより、ソート処理全体の処理時間に対するステップＡ１〜Ａ３の処理時間の割合を小さく抑えることができる。例えば、ＬおよびＭが入力データ５のデータ数よりも十分に小さければ、ステップＡ１〜Ａ３の処理時間は無視できる程に短くなる。【００４１】
また、本実施形態では、入力データ５の全体を複写する処理が、ステップＡ５による１回だけなので、メモリシステムの動作速度の影響を小さく抑えることができる。【００４２】
（第２の実施形態）
第１の実施形態では並列処理が複数のプロセッサによるものか仮想的なものかについて特に限定していなかったが、第２の実施形態ではマルチプロセッサによる並列処理を例示する。【００４３】
第２の実施形態では、複数のプロセッサを備えたマルチプロセッサシステムにより並列ソート装置を構成する。マルチプロセッサシステムはデータのソートを並列処理するためのプログラムを実行する。第２の実施形態は、第１の実施形態の並列ソート装置をマルチプロセッサシステムで構成したものであり基本的な機能に相違は無いので、主に第１の実施形態と異なる部分について説明する。【００４４】
第２の実施形態による並列ソート装置は、図４に示した第１の実施形態による並列ソート装置と同様の構成である。図７は、第２の実施形態による並列ソート装置およびその各部の動作を説明するための模式図である。ここではマルチプロセッサシステム７１はＰ台以上のプロセッサを有しているものとする。【００４５】
図７に示すように、第２の実施形態の並列ソート装置では、マルチプロセッサシステム７１が並列ソートプログラム７２を読み込んで実行する。これによりマルチプロセッサシステム７１は、第１の実施形態として示した並列ソート装置の基準値算出部１、入力データ集計部２、データ振分部３、および区間ソート部４として動作する。【００４６】
その際、マルチプロセッサシステム７１は、図６に示したステップＡ４〜Ａ６の動作における並列処理をＰ台のプロセッサを並列動作させることにより行う。【００４７】
本実施形態によれば、ステップＡ４〜Ａ６の時間が長くかかる処理を複数のプロッサで並列処理することにより全体のソート処理を高速化することができる。【００４８】
（第１の実施例）
上述した第１あるいは第２の実施形態による並列ソート装置の具体例を第１の実施例として説明する。【００４９】
図８は、第１の実施例における並列ソート装置の動作を説明するための模式図である。図８に示すように、入力データ３５として１６個の数値が並列ソート装置に与えられたとする。また、本実施例ではＭ＝４、Ｌ＝８であるとする。【００５０】
図８のフローチャートを参照すると、まず、基準値算出部１は、ステップＡ１においてＬ−１＝７個の基準値３６−１〜３６−７を算出する。続いて、基準値算出部１は、ステップＡ２において、基準値３６−１〜３６−７を用いて８個の区間３７−１〜３７−８を生成する。また、入力データ集計部２は、ステップＡ３において、入力データ３５をＭ＝４個の入力データ領域３５−１〜３５−４に分割する。【００５１】
次に、入力データ集計部２は、ステップＡ４において、入力データ領域３５−１〜３５−４のそれぞれに対し、区間３７−１〜３７−８に対応した領域にデータを振り分けるための写像情報３８−１−１〜３８−４−８を算出する。【００５２】
本実施例では、ステップＡ４の内部の詳細な動作についても説明する。図９は、ステップＡ４の内部の詳細な動作を示すフローチャートである。図１０は、ステップＡ４の内部の詳細な動作を説明するための模式図である。【００５３】
図９を参照すると、まず、入力データ集計部２は、入力データ領域３５−１〜３５−４に含まれる各データが区間３７−１〜３７−８に含まれる個数を入力データ領域および区間毎にカウントし、行列状のデータ個数５０−１−１〜５０−４−８として蓄える（ステップＡ４−１）。【００５４】
次に、入力データ集計部２は、１から８の値を取る全てのｊに対して、データ個数５０−１−ｊから５０−４−ｊの総和を算出し、区間総数５１−ｊとして蓄える（ステップＡ４−２）。区間総数５１−ｊは、入力データ３５の１６個の数値のうち区間３７−ｊに含まれる数値（データ）の個数を意味する。【００５５】
さらに、入力データ集計部２は、１から８の値を取る全てのｊに対して、区間総数５１−１から区間総数５１−（ｊ−１）までの総和を算出し、積算個数５２−ｊとして蓄える（ステップＡ４−３）。積算個数５２−ｊは入力データ３５の１６個の数値のうち、区間３７−ｊに含まれる最小の数値よりも小さい数値の総数を意味する。図６に示したステップＡ５では、データ振分部３が入力データ３５−１〜３５−４を並列処理で区間３７−１〜３７−８に対応する出力データ領域３９−１〜３９−８に振り分けることになる。そのときの出力データ領域３９−ｊの開始位置が｛（積算個数５２−ｊ）＋“１”｝番目となる。例えば、区間３７−３は「５以上１０未満」である。「５以上１０未満」の数が入る出力データ領域３９−３は、出力データ３９の中の５番目（（積算個数５２−３）＋“１”＝“５”）から開始され、９番目（（積算個数５２−４）＝“９”）までであることが分かる。これに従って出力データ領域３９−１〜３９−８を決めてデータを入れていけば、各区間のデータが互いに重ならないようにデータを振り分けることができる。これにより各入力データ領域のデータを振り分ける処理が互いに独立して実行できるので、複数の入力データ領域の処理を並列に実行することができる。【００５６】
図９に戻り、次に、入力データ集計部２は、１から８の値を取る全てのｊと１から４の値を取る全てのｉとに対して、積算個数５２−ｊにデータ個数５０−１−ｊからデータ個数５０−（ｉ−１）−ｊの総和を加算し、写像情報３８−ｉ−ｊとして蓄える（ステップＡ４−４）。【００５７】
なお、このとき、データ個数５０−ｉ−ｊが“０”であれば入力データ領域３５−ｉに区間３７−ｊに含まれるデータが存在しないことを意味するので、写像情報３８−ｉ−ｊとして何も蓄える必要がない。【００５８】
写像情報３８−ｉ−ｊの意味は次の通りである。ステップＡ５では、各入力データ領域３５−１〜３５−４に含まれるデータのうち区間３７−ｊに含まれるデータを出力データ領域３９−ｊに重なりなく振り分ける必要がある。そのときに入力データ領域３５−ｉに含まれるデータを｛（写像情報３８−ｉ−ｊ）＋“１”｝番目からの領域に複写していくことにすることにより、各入力データ領域３５−１〜３５−４のデータを複写する処理を並列処理してもデータを重ならないように出力データ領域３９−１〜３９−８に振り分けることができる。【００５９】
例えば、図１０を参照すると、写像情報３８−１−３は“４”、写像情報３８−２−３は“５”、写像情報３８−３−３は“７”、写像情報３８−４−３は“８”である。したがって、各入力データ領域３５−１に含まれる「５以上１０未満」のデータを出力データ３９の領域の５番目からの領域に振り分ければよい。また、入力データ領域３５−２に含まれる「５以上１０未満」のデータを出力データ３９の領域の６番目からの領域に振り分ければよい。また、入力データ領域３５−３に含まれる「５以上１０未満」のデータを出力データ３９の領域の８番目からの領域に振り分ければよい。また、入力データ領域３５−４に含まれる「５以上１０未満」のデータを出力データ３９の領域の９番目からの領域に振り分ければよい。【００６０】
図６に戻り、ステップＡ４の処理の後に、データ振分部３は、ステップＡ５において、各入力データ領域３５−ｉ内のそれぞれのデータについて、そのデータが含まれる区間３７―ｊを求め、出力データ３９の領域における、｛（写像情報３８−ｉ−ｊ）＋“１”｝番目からの領域に順に蓄える。【００６１】
最後に、区間ソート部４は、ステップＡ６において、出力データ領域３９−１〜３９−８のデータをそれぞれにソートする。これにより出力データ３９全体のソートが完了し、ソート結果が得られる。区間ソート部４による出力データ領域３９−１〜３９−８毎のソート処理には、例えばクイックソートなどの一般的な単一プロセッサ向けのソート処理を用いてもよい。【００６２】
（第２の実施例）
第２の実施形態による並列ソート装置の具体例を第２の実施例として説明する。第２の実施例では、図７に示したようにマルチプロセッサシステム７１が並列ソートプログラム７２を実行する。マルチプロセッサシステム７１はＰ台以上のプロセッサを備えているものとする。【００６３】
図１１は、並列ソートプログラムによる処理を示すフローチャートである。図１１では、図６のフローチャートにおけるステップＡ４の処理が、図９の詳細なフローチャートで示された処理となっている点に特徴がある。また、ステップＡ４〜Ａ６の処理が、Ｐ台のプロセッサによる並列処理となっている点にも特徴がある。【００６４】
図１１を参照すると、ステップＡ４の写像情報を作成する集計処理は、Ｐ台のプロセッサが同時並行で実行することにより高速化が図られている。【００６５】
ステップＡ４−１では、各入力データ領域５−１〜５−Ｍに対応するそれぞれの処理が複数のプロセッサに割り当てられる。ステップＡ４−２およびＡ４−４では、各区間７−１〜７−Ｌに対応するそれぞれの処理が複数のプロセッサに割り当てられる。【００６６】
例えば、図１０の例でプロセッサが４台で、Ｍ＝４、Ｌ＝８のとき、ステップＡ４−１では各入力データ領域３５−１〜３５−４のカウント処理を４台のプロセッサで同時に実行することができる。また、ステップＡ４−２ではデータ個数５０−１−１〜５０−４−８を集計する処理を４台のプロセッサで区間７−１〜７−８毎に独立して同時に実行することができる。また、ステップＡ４−４では写像情報３８−１−１〜３８−４−８を算出する処理を、４台のプロセッサで区間７−１〜７−８毎に独立して同時に実行することができる。【００６７】
また、図１１に戻り、ステップＡ５のデータ振り分け処理は、Ｐ台のプロセッサが同時並行で実行することにより高速化が図られている。【００６８】
例えば、図８の例でプロセッサが４台、Ｍ＝４、Ｌ＝８のとき、各入力データ領域３５−１〜３５−４のデータを４台のプロセッサを同時に振り分けることができる。【００６９】
さらに、図１１において、ステップＡ６のソート処理は、Ｐ台のプロセッサが同時並行で実行することにより高速化が図られている。【００７０】
例えば、図８の例でプロセッサが４台、Ｍ＝４、Ｌ＝８のとき、各出力データ領域３９−１〜３９−８について４台のプロセッサが同時にデータをソートすることができる。【００７１】
なお、図１１においてステップＡ１、Ａ２、Ａ３、およびＡ４−３の処理は、ＬおよびＭの値を適切に選択すれば、全体のソート処理時間への影響を小さく抑えることができるため本実施例では並列処理としていない。しかし、これらの処理についても複数のプロセッサで並列処理することにしてもよい。【００７２】
例えば、ステップＡ１、Ａ２では複数の基準値のそれぞれに対する処理を複数のプロセッサで並列処理することができる。また、ステップＡ３では複数の領域のそれぞれについての処理を複数のプロセッサで並列処理することができる。また、ステップＡ４−３の処理内容は総和演算なので、並列プロセッサによる既知の総和演算手法を用いることができる。【００７３】
また、上述した各実施形態および各実施例においてＭの値は任意に選択できる。しかし、並列処理による高速化の効果をより出すためには、Ｍの値をプロセッサ台数以上の値にするのが好ましい。例えば、Ｍをプロセッサ台数と等しいかまたはその整数倍の値にすれば、各入力データ領域５−１〜５−Ｍに対応した処理をプロセッサに無駄なく割り当てることができる。その結果、一部のプロセッサが待機した状態となるのを防止し、プロセッサを効率よく利用できる。【００７４】
また、上述した各実施形態および各実施例においてＬの値は任意に選択できる。しかし、並列処理による高速化の効果をより出すためには、Ｌの値をプロセッサ台数以上の値にするのが好ましい。ステップＡ５においてデータを振り分けた後、各出力データ領域９−１〜９−Ｌのサイズにばらつきが出る可能性がある。それ伴ってステップＡ６における出力データ領域９−１〜９−Ｌ毎の区間ソート処理においてプロセッサ毎の処理量にばらつきが出ると並列処理による高速化の効果が減少する。それ故に、Ｌをプロセッサ台数よりも大きな値にし、区間ソート部４は、ステップＡ６において出力データ領域９−１〜９−Ｌをプロセッサに割り当てるときプロセッサ間の負荷が均等になるよう調整することが好ましい。これによりプロセッサの利用効率を高めて並列処理による高速化の効果を高めることができる。【００７５】
例えば、出力データ領域９−１〜９−ＬをＰ個のプロセッサに割り当てるとき、それぞれのプロセッサに割り当てる領域のサイズの和が、全てのプロセッサにおいて均等になるよう調整すればよい。出力データ領域９−１〜９−Ｌのサイズは、対応する区間７−１〜７−Ｌに割り振られるデータ数に等しいので、各プロセッサの割り当てる領域のサイズの和を均等にすれば、各プロセッサが処理すべきデータ数が均等となる。これによりプロセッサ間の負荷が均等になる。【００７６】
また、Ｌをプロセッサ台数と等しいかあるいはその整数倍とするのが好ましい。整数の値としては１から５程度とする方法がある。出力データ領域９−１〜９−Ｌのサイズがおおよそ等しければ、Ｌをプロセッサの台数と同数か整数倍にしておくことで、ステップＡ６におけるプロセッサ間のばらつきによる処理時間の差を減らし易くなる。ただし、あまり整数の値が大きすぎると処理のオーバーヘッドが大きくなって逆に高速化が疎外される可能性がある。【００７７】
また、上述した各実施形態および各実施例において、ステップＡ１で選択する基準値ついては、出力データ領域９−１〜９−Ｌのサイズのばらつきが小さくなるように選択するのが好ましい。そのために統計処理などを用いて、できるだけ均等に分散した基準値を選択すると、並列処理のプロセッサの利用効率がよくなる。図８には、入力データ３５の中から等間隔で基準値を選択する例を示したが、これに限られるものではない。他の例として、図５においた、入力データ５の中からＬ−１個よりも多くのデータを取得してその分布を調べ、得られた分布に基づいて各区間のデータ数が均等になるようにＬ−１個の基準値を選択してもよい。【００７８】
また、上述した各実施形態および各実施例においては入力データ５の中から基準値を選択する例を示したが、本発明はこれに限定されるものではない。統計的に基準値を算出するとき入力データ５に無い値を基準値としてもよい。【００７９】
例えば、図５において入力データ５からＫ＊Ｌ個（Ｋは定数）のデータを取り出し、順序関係（値の大きさ）に従ってＫ個ずつの組にし、各組の間の数を基準値とする方法がある。【００８０】
また他の例として、入力データ領域５−１〜５−Ｍの各領域から取得した複数個のデータに対して統計的な分布推定やデータ数予測を行い、出力データ領域９−１〜９−Ｌのサイズのばらつきが最も小さくなるようにＬ−１個の基準値を選択する方法がある。統計的な分布推定やデータ数予測には既存の統計学の手法を用いることができる。特に入力データの分布が一様分布あるいは正規分布のように既知の分布となる場合に統計的手法が有効である。一様分布であれば最大値と最小値、正規分布であれば平均と分散を求め、それらに基づいて基準値を算出することができる。このように統計的手法で基準値を選択する場合、基準値を単純に選択する場合と比べてステップＡ１の処理時間が大きくなる。そこでステップＡ１の処理を複数台のプロセッサで実行することにより高速化を図ることにしてもよい。【００８１】
この出願は、２００６年１２月２２日に出願された日本出願特願２００６−３４５８０２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図面の簡単な説明】
【００８２】
【図１】特許文献１に開示された並列ソート方法を説明するための図である。
【図２】特許文献１に開示された並列ソート装置の構成を示すブロック図である。
【図３】特許文献２に開示された並列ソート方法を説明するための図である。
【図４】第１の実施形態による並列ソート装置の構成を示すブロック図である。
【図５】第１の実施形態による並列ソート装置およびその各部の動作を説明するための模式図である。
【図６】第１の実施形態による並列ソート装置の動作を示すフローチャートである。
【図７】第２の実施形態による並列ソート装置およびその各部の動作を説明するための模式図である。
【図８】第１の実施例における並列ソート装置の動作を説明するための模式図である。
【図９】ステップＡ４の内部の詳細な動作を示すフローチャートである。
【図１０】ステップＡ４の内部の詳細な動作を説明するための模式図である。
【図１１】並列ソートプログラムによる処理を示すフローチャートである。
【符号の説明】
【００８３】
１    基準値算出部
２    入力データ集計部
３    データ振分部
４    区間ソート部
５、３５    入力データ
５−１〜５−Ｍ、３５−１〜３５−４    入力データ領域
６−１〜６−（Ｌ−１）、３６−１〜３６−７    基準値
７−１〜７−Ｌ、３７−１〜３７−８    区間
８−１−１〜８−Ｍ−Ｌ、３８−１−１〜３８−４−８    写像情報
９、３９    出力データ
９−１〜９−Ｌ、３９−１〜３９−８    出力データ領域
５０−１−１〜５０−４−８    データ個数
５１−ｊ    区間総数
５２−ｊ    積算個数
７１    マルチプロセッサシステム
７２    並列ソートプログラム
Ａ１〜Ａ６、Ａ４−１〜Ａ４−４    ステップ
【図１】
2008078517.tif 000003
【図２】
2008078517.tif 000004
【図３】
2008078517.tif 000005
【図４】
2008078517.tif 000006
【図５】
2008078517.tif 000007
【図６】
2008078517.tif 000008
【図７】
2008078517.tif 000009
【図８】
2008078517.tif 000010
【図９】
2008078517.tif 000011
【図１０】
2008078517.tif 000012
【図１１】
2008078517.tif 000013
【手続補正書】
【提出日】平成21年8月11日(2009.8.11)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
上記目的を達成するために、本発明の並列ソート装置は、
複数のデータからなる入力データを並列処理によりソートする並列ソート装置であって、
前記入力データに基づいて、該入力データを値の大きさよって振り分けるための区間の境界となる複数の基準値を算出する基準値算出部と、
前記入力データを複数の入力データ領域に区切り、区切った前記各入力データ領域内のデータを、前記基準値算出部で算出された前記基準値を境界とする複数の前記区間に振り分けるための写像情報を並列処理で算出する入力データ集計部と、
前記入力データ集計部によって算出された前記写像情報に従って、前記各入力データ領域内のデータを並列処理で複数の前記区間に振り分けるデータ振分部と、
前記データ振分部により振り分けられた複数の前記区間のデータを並列処理でそれぞれにソートする区間ソート部と、を有し、
前記入力データ領域の個数が、前記並列処理を実行する複数のプロセッサの個数と等しいかまたは前記プロセッサの個数の整数倍である。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のデータからなる入力データを並列処理によりソートする並列ソート装置であって、
前記入力データに基づいて、該入力データを値の大きさよって振り分けるための区間の境界となる複数の基準値を算出する基準値算出部と、
前記入力データを複数の入力データ領域に区切り、区切った前記各入力データ領域内のデータを、前記基準値算出部で算出された前記基準値を境界とする複数の前記区間に振り分けるための写像情報を並列処理で算出する入力データ集計部と、
前記入力データ集計部によって算出された前記写像情報に従って、前記各入力データ領域内のデータを並列処理で複数の前記区間に振り分けるデータ振分部と、
前記データ振分部により振り分けられた複数の前記区間のデータを並列処理でそれぞれにソートする区間ソート部と、を有し、
前記入力データ領域の個数が、前記並列処理を実行する複数のプロセッサの個数と等しいかまたは前記プロセッサの個数の整数倍である並列ソート装置。
【請求項２】
前記写像情報は、複数の前記入力データ領域に含まれるデータを複数の前記区間に振り分けるとき、複数の前記区間に振り分けられたデータを蓄積する、前記区間に対応した出力データ領域を決定するための情報であり、
前記入力データ集計部は、前記区間の各々に含まれるデータの個数を前記入力データ領域毎にカウントし、カウント結果を該入力データ領域毎に集計することにより、複数の前記出力データ領域の各々が、前記区間に振り分けられたデータを該データ同士が重なり合わないように蓄積できるサイズとなるように前記写像情報を算出する、請求項１に記載の並列ソート装置。
【請求項３】
前記入力データ集計部は前記入力データを均等な前記入力データ領域に区切る、請求項１または２に記載の並列ソート装置。
【請求項４】
前記区間ソート部は、複数の前記区間のそれぞれに振り分けられたデータの数に基づいて、前記並列処理を実行する複数のプロセッサの負荷が均等になるように、前記区間を前記プロセッサに割り当てる、請求項１から３のいずれか１項に記載の並列ソート装置。
【請求項５】
前記基準値によって区切られる前記区間の数が、前記並列処理を実行するプロセッサの数と等しいかまたは前記プロセッサの個数の整数倍である、請求項１から４のいずれか１項に記載の並列ソート装置。
【請求項６】
前記基準値算出部は、複数の前記区間に振り分けられるデータの数を均等にするように、前記入力データに対する統計処理によって前記基準値を算出する、請求項１から５のいずれか１項に記載の並列ソート装置。
【請求項７】
複数のデータからなる入力データを並列処理によりソートするための並列ソート方法であって、
前記入力データに基づいて、該入力データを値の大きさよって振り分けるための区間の境界となる複数の基準値を算出し、
前記入力データを複数の入力データ領域に区切り、
区切った前記各入力データ領域内のデータを、算出した前記基準値を境界とする複数の前記区間に振り分けるための写像情報を並列処理で算出し、
算出した前記写像情報に従って、前記各入力データ領域内のデータを並列処理で複数の整理番号前記区間に振り分け、
振り分けた複数の前記区間のデータを並列処理でそれぞれにソートし、
前記入力データ領域の個数が、前記並列処理を実行する複数のプロセッサの個数と等しいかまたは前記プロセッサの個数の整数倍である並列ソート方法。
【請求項８】
前記写像情報は、複数の前記入力データ領域に含まれるデータを複数の前記区間に振り分けるとき、複数の前記区間に振り分けられたデータを蓄積する、前記区間に対応した出力データ領域を決定するための情報であり、
前記区間の各々に含まれるデータの個数を前記入力データ領域毎にカウントし、カウント結果を該入力データ領域毎に集計することにより、複数の前記出力データ領域の各々が、前記区間に振り分けられたデータを該データ同士が重なり合わないように蓄積できるサイズとなるように前記写像情報を算出する、請求項７に記載の並列ソート方法。
【請求項９】
前記入力データを均等な前記入力データ領域に区切る、請求項７または８に記載の並列ソート方法。
【請求項１０】
複数の前記区間のそれぞれに振り分けられたデータの数に基づいて、前記並列処理を実行する複数のプロセッサの負荷が均等になるように、前記区間を前記プロセッサに割り当てて該区間のデータをソートさせる、請求項７から９のいずれか１項に記載の並列ソート方法。
【請求項１１】
前記基準値によって区切られる前記区間の数が、前記並列処理を実行するプロセッサの数と等しいかまたは前記プロセッサの個数の整数倍である、請求項７から１０のいずれか１項に記載の並列ソート方法。
【請求項１２】
複数の前記区間に振り分けられるデータの数を均等にするように、前記入力データに対する統計処理によって前記基準値を算出する、請求項７から１１のいずれか１項に記載の並列ソート方法。
【請求項１３】
複数のデータからなる入力データを並列処理によりソートする処理をコンピュータに行なわせるための並列ソートプログラムであって、
前記入力データに基づいて、該入力データを値の大きさよって振り分けるための区間の境界となる複数の基準値を算出する手順と、
前記入力データを複数の入力データ領域に区切る手順と、
区切った前記各入力データ領域内のデータを、算出した前記基準値を境界とする複数の前記区間に振り分けるための写像情報を並列処理で算出する手順と、
算出した前記写像情報に従って、前記各入力データ領域内のデータを並列処理で複数の前記区間に振り分ける手順と、
振り分けた複数の前記区間のデータを並列処理でそれぞれにソートする手順と、をコンピュータに実行させ、
前記入力データ領域の個数が、前記並列処理を実行する複数のプロセッサの個数と等しいかまたは前記プロセッサの個数の整数倍である並列ソートプログラム。
【請求項１４】
前記写像情報は、複数の前記入力データ領域に含まれるデータを複数の前記区間に振り分けるとき、複数の前記区間に振り分けられたデータを蓄積する、前記区間に対応した出力データ領域を決定するための情報であり、
前記区間の各々に含まれるデータの個数を前記入力データ領域毎にカウントし、カウント結果を該入力データ領域毎に集計することにより、複数の前記出力データ領域の各々が、前記区間に振り分けられたデータを該データ同士が重なり合わないように蓄積できるサイズとなるように前記写像情報を算出する、請求項１３に記載の並列ソートプログラム。
【請求項１５】
前記入力データを均等な前記入力データ領域に区切る、請求項１３または１４に記載の並列ソートプログラム。
【請求項１６】
複数の前記区間のそれぞれに振り分けられたデータの数に基づいて、前記並列処理を実行する複数のプロセッサの負荷が均等になるように、前記区間を前記プロセッサに割り当てて該区間のデータをソートさせる、請求項１３から１５のいずれか１項に記載の並列ソートプログラム。
【請求項１７】
前記基準値によって区切られる前記区間の数が、前記並列処理を実行するプロセッサの数と等しいかまたは前記プロセッサの個数の整数倍である、請求項１３から１６のいずれか１項に記載の並列ソートプログラム。
【請求項１８】
複数の前記区間に振り分けられるデータの数を均等にするように、前記入力データに対する統計処理によって前記基準値を算出する、請求項１３から１７のいずれか１項に記載の並列ソートプログラム。
【国際調査報告】
2008078517.tif 000014
2008078517.tif 000015
2008078517.tif 000016