データソート装置及び方法

トップ :: G 物理学 :: G06 計算;計数

【発明の名称】	データソート装置及び方法
【発明者】	【氏名】松井信明
【要約】	【課題】大規模なランダムデータのソートを、高速に処理可能とするる。【解決手段】メインメモリ１０４の指定されたメモリ空間の範囲にあるデータをソートするデータソート装置において、データ交換回路１０３は、指定されたメモリ空間の範囲内のデータを、基準データリードＤＭＡＣ１０５によって読み出された設定された基準値に基づいて移動して、上記指定された範囲を２つのグループ範囲に分ける。そして、繰り返し制御回路１０１が、データ交換回路１０３で得られた各グループ範囲のデータについてデータ交換回路１０３による処理を実行させ、データソートを実現する。

【特許請求の範囲】
【請求項１】指定されたメモリ空間上の範囲にあるデータをソートするデータソート装置であって、メモリ空間上の指定された範囲内のデータを、設定された基準値によって移動して、前記指定された範囲を２つのグループ範囲に分ける交換手段と、前記交換手段で得られた各グループ範囲について該交換手段を実行する制御手段とを備えることを特徴とするデータソート装置。
【請求項２】前記交換手段は、前記メモリ空間上の指定された範囲内のデータを下位アドレスから上位アドレスへ向かって読み出し、基準値との比較によって移動すべきデータを検出する第１検出手段と、前記メモリ空間上の指定された範囲内のデータを上位アドレスから下位アドレスへ向かって読み出し、前記基準値との比較によって移動すべきデータを検出する第２検出手段と、前記第１及び第２検出手段で検出されたデータを入れ替える入替手段と、前記第１検出手段で比較されるデータの読み出しアドレスが、前記第２検出手段で比較されるデータの読出アドレスよりも上位になった場合に、当該交換手段による処理の終了と判断する判断手段とを備えることを特徴とする請求項１に記載のデータソート装置。
【請求項３】前記交換手段において、前記第１及び前記第２検出手段は、同時に複数のデータを読み出して、前記基準値に基づいて移動すべきデータを検出することを特徴とする請求項２に記載のデータソート装置。
【請求項４】前記交換手段において、前記第１及び第２検出手段は、それぞれ読み出した複数のデータを一時的に保持するプリフェッチバッファと、該プリフェッチバッファより読み出され、前記基準値との比較対象となる複数のデータを保持する比較バッファを含み、前記入替手段は、前記第１及び第２検出手段で検出されたデータを入れ替えるとともに、該第１及び第２検出手段の比較バッファ同士でデータを入れ替えることを特徴とする請求項３に記載のデータソート装置。
【請求項５】前記交換手段において、前記第１及び第２検出手段は、それぞれ読み出した複数のデータを一時的に保持するプリフェッチバッファと、該プリフェッチバッファより読み出され、前記基準値との比較対象となる複数のデータを保持する比較バッファを含み、前記入替手段は、前記第１及び第２検出手段で検出されたデータを入れ替えるとともに、該第１及び第２検出手段間でプリフェッチバッファと比較バッファのデータを入れ替えることを特徴とする請求項３に記載のデータソート装置。
【請求項６】前記交換手段で得られたグループのメモリ空間上における範囲の大きさが所定サイズ以下となったかを判定する判定手段と、前記判定手段により、所定サイズ以下と判定されたグループ範囲に対して、所定のソート処理を適用して当該グループのソート処理を完了する手段とを更に備えることを特徴とする請求項１に記載のデータソート装置。
【請求項７】前記所定のソート処理は、バブルソート回路によって実行されることを特徴とする請求項６に記載のデータソート装置。
【請求項８】処理の対象となるグループ範囲のデータをキャッシュするキャッシュ手段を更に備えることを特徴とする請求項１乃至７のいずれかに記載のデータソート装置。
【請求項９】前記処理の対象となるグループ範囲のサイズに基づいて、前記キャッシュ手段の実行を制御する手段を更に備えることを特徴とする請求項８に記載のデータソート装置。
【請求項１０】請求項１乃至９のいずれかに記載のデータソート装置を複数有し、前記複数のデータソート装置にソートすべきメモリ空間の範囲を割り当てる割り当て手段を備えることを特徴とするデータソート装置。
【請求項１１】前記割り当て手段は、ソート処理情報を取得し、これに基づいてソートすべきメモリ空間の範囲を割り当てることを特徴とする請求項１０に記載のデータソート装置。
【請求項１２】前記データ交換手段において、前記第１及び第２検出手段のそれぞれが、基準値と比較対象のデータが等価であった場合に、該比較対象のデータに含まれるポインタ情報から更なる比較対象データを取得する取得手段を備え、前記取得手段で取得した更なる比較対象データと、これに対応した基準データとの比較によって移動すべきデータを検出することを特徴とする請求項２に記載のデータソート装置。
【請求項１３】指定されたメモリ空間上の範囲にあるデータをソートするデータソート方法であって、メモリ空間上の指定された範囲内のデータを、設定された基準値によって移動して、前記指定された範囲を２つのグループ範囲に分ける交換工程と、前記交換工程で得られた各グループ範囲について該交換工程を実行する制御工程とを備え、前記交換工程は、前記メモリ空間上の指定された範囲内のデータを下位アドレスから上位アドレスへ向かって読み出し、基準値との比較によって移動すべきデータを検出する第１検出工程と、前記メモリ空間上の指定された範囲内のデータを上位アドレスから下位アドレスへ向かって読み出し、前記基準値との比較によって移動すべきデータを検出する第２検出工程と、前記第１及び第２検出工程で検出されたデータを入れ替える入替工程と、前記第１検出工程で比較されるデータの読み出しアドレスが、前記第２検出工程で比較されるデータの読出アドレスよりも上位になった場合に、当該交換工程による処理の終了と判断する判断工程とを備えることを特徴とするデータソート方法。
【請求項１４】前記交換工程において、前記第１及び前記第２検出工程は、同時に複数のデータを読み出して、前記基準値に基づいて移動すべきデータを検出することを特徴とする請求項１３に記載のデータソート方法。
【請求項１５】前記交換工程において、前記第１及び第２検出工程は、それぞれ読み出した複数のデータをプリフェッチバッファに一時的に保持し、前記基準値との比較対象となる複数のデータを該プリフェッチバッファより読み出して比較バッファに保持することを含み、前記入替工程は、前記第１及び第２検出工程で検出されたデータを入れ替えるとともに、前記比較バッファ同士でデータを入れ替えることを特徴とする請求項１４に記載のデータソート方法。
【請求項１６】前記交換工程において、前記第１及び第２検出工程は、それぞれ読み出した複数のデータをプリフェッチバッファに一時的に保持し、前記基準値との比較対象となる複数のデータを該プリフェッチバッファより読み出して比較バッファに保持することを含み、前記入替工程は、前記第１及び第２検出工程で検出されたデータを入れ替えるとともに、該第１及び第２検出工程間のプリフェッチバッファと比較バッファのデータを入れ替えることを特徴とする請求項１４に記載のデータソート方法。
【請求項１７】前記交換工程で得られたグループのメモリ空間上における範囲の大きさが所定サイズ以下となったかを判定する判定工程と、前記判定工程により、所定サイズ以下と判定されたグループ範囲に対して、所定のソート処理を適用して当該グループのソート処理を完了する工程とを更に備えることを特徴とする請求項１に記載のデータソート方法。
【請求項１８】前記所定のソート処理は、バブルソート回路によって実行されることを特徴とする請求項１７に記載のデータソート方法。
【請求項１９】処理の対象となるグループ範囲のデータをキャッシュするキャッシュ手段を設け、前記処理の対象となるグループ範囲のサイズに基づいて、前記キャッシュ手段の実行を制御する工程を更に備えることを特徴とする請求項１３乃至１８のいずれかに記載のデータソート方法。
【請求項２０】請求項１３乃至１９のいずれかに記載のデータソート方法を実行する為の複数のデータソート処理を並列に実行する工程を有し、前記複数のデータソート処理にソートすべきメモリ空間の範囲を割り当てる割り当て工程を備えることを特徴とするデータソート方法。
【請求項２１】前記割り当て工程は、ソート処理情報を取得し、これに基づいて各データソート装置にソートすべきメモリ空間の範囲を割り当てることを特徴とする請求項２０に記載のデータソート方法。
【請求項２２】前記データ交換工程において、前記第１及び第２検出工程のそれぞれが、基準値と比較対象のデータが等価であった場合に、該比較対象のデータに含まれるポインタ情報から更なる比較対象データを取得する取得工程を備え、前記取得工程で取得した更なる比較対象データと、これに対応した基準データとの比較によって移動すべきデータを検出することを特徴とする請求項１４に記載のデータソート方法。

【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、メモリ上のデータをソートするデータソート装置及び方法に関する。
【０００２】
【従来の技術】従来、データソート装置は、小規模なデータを並べ替えるためのバブルソートアルゴリズムをとるソート装置か、大規模データベースに用いるインサートソートアルゴリズムを採用したソート装置しか存在しない。これらのデータソート装置は大規模なランダムデータのソートには適さず、大規模なランダムデータを処理する場合には、ソフトウェアでソート処理を行っていた。
【０００３】
【発明が解決しようとする課題】しかしながら、大規模なランダムデータをソートする場合には、ＣＰＵキャッシュのヒット率が低下してしまい、高速なソート処理が行えないという問題があった。
【０００４】本発明は上記の問題に鑑みてなされたものであり、クイックソートアルゴリズムによるソート処理をハードウエアにて実行可能とし、大規模ランダムデータのソート処理を高速に行えるようにすることを目的とする。
【０００５】
【課題を解決するための手段】上記の目的を達成するための本発明によるデータソート装置は以下の構成を備える。即ち、指定されたメモリ空間上の範囲にあるデータをソートするデータソート装置であって、メモリ空間上の指定された範囲内のデータを、設定された基準値によって移動して、前記指定された範囲を２つのグループ範囲に分ける交換手段と、前記交換手段で得られた各グループ範囲について該交換手段を実行する制御手段とを備える。
【０００６】また、上記の目的を達成するための本発明によるデータソート方法は例えば以下の工程を備える。即ち、指定されたメモリ空間上の範囲にあるデータをソートするデータソート方法であって、メモリ空間上の指定された範囲内のデータを、設定された基準値によって移動して、前記指定された範囲を２つのグループ範囲に分ける交換工程と、前記交換工程で得られた各グループ範囲について該交換工程を実行する制御工程とを備え、前記交換工程は、前記メモリ空間上の指定された範囲内のデータを下位アドレスから上位アドレスへ向かって読み出し、基準値との比較によって移動すべきデータを検出する第１検出工程と、前記メモリ空間上の指定された範囲内のデータを上位アドレスから下位アドレスへ向かって読み出し、前記基準値との比較によって移動すべきデータを検出する第２検出工程と、前記第１及び第２検出工程で検出されたデータを入れ替える入替工程と、前記第１検出工程で比較されるデータの読み出しアドレスが、前記第２検出工程で比較されるデータの読出アドレスよりも上位になった場合に、当該交換工程による処理の終了と判断する判断工程とを備える。
【０００７】
【発明の実施の形態】以下、添付の図面を参照して本発明の好適な実施形態を説明する。
【０００８】［実施形態１］図１は実施形態１によるデータソート装置の構成を示したブロック図である。以下、本実施形態のデータソート装置の動作について図１を参照しながら説明する。
【０００９】繰り返し制御回路１０１が起動されることによってソート処理が開始される。繰り返し制御回路１０１は初めにソートするエレメント範囲（被ソートデータ）を指定してデータ交換回路１０３を起動する。データ交換回路１０３が起動されると、制御回路１１７がまず、基準データリードＤＭＡＣ１０５、昇順データリードＤＭＡＣ１０７、降順データリードＤＭＡＣ１１１を起動する。基準データリードＤＭＡＣ１０５は、メインメモリ１０４から基準データを取得し、基準データバッファ１０６に格納する。なお、本例では、基準データとしてはエレメント範囲の中央値を用いるものとする。
【００１０】昇順データリードＤＭＡＣ１０７は、メインメモリ１０４から、ソートすべきエレメント範囲の最下位アドレス側から順にエレメントを取得してプリフェッチバッファ１０８に格納する。昇順データリードＤＭＡＣ１０７はプリフェッチバッファ１０８がフルになるまでデータリードを繰り返し、フルになったならば次にプリフェッチバッファ１０８が解放されるまで待ち、解放された後に再度データリードを再開する。
【００１１】プリフェッチバッファ１０８は、比較バッファ１０９が空いていればエレメントを比較バッファ１０９に送信する。比較バッファ１０９に保持されたエレメントは、比較器１１０によって基準データバッファ１０６に保持されたデータと比較され、もしエレメントの値が基準データよりも小さかったならば、次のエレメントが比較バッファ１０９にロードされ、次の比較が行われる。もしエレメントが基準データよりも大きかったならば、比較を停止し、降順データ比較器１１４が比較を停止するまで待機する。
【００１２】すなわち、以上の処理では、メインメモリ１０４の設定されたエレメント範囲の上位側アドレスから順にエレメントが取得され、各々が基準値と比較され、エレメントの値が基準値よりも大きい場合に、その時点のアドレスと値が保持される。
【００１３】同様に、降順データリードＤＭＡＣ１１１は、メインメモリ１０４から、ソートすべきエレメント範囲の最上位アドレス側から順にエレメントを取得し、プリフェッチバッファ１１２に格納する。降順データリードＤＭＡＣ１１１はプリフェッチバッファ１１２がフルになるまでデータリードを繰り返し、フルになったならば、次にプリフェッチバッファ１１２が解放されるまで待ち、解放された後に再度データリードを再開する。
【００１４】プリフェッチバッファ１１２は、比較バッファ１１３が空いていればエレメントを比較バッファ１１３に送信する。比較バッファ１１３に保持されたエレメントは、比較器１１４によって基準データバッファ１０６に保持されたデータと比較され、もしエレメントの値が基準データの値よりも大きかったならば、次のエレメントが比較バッファ１１３にロードされ、次の比較が行われる。もしエレメントが基準データよりも小さかったならば、比較を停止し、昇順データ比較器１１０が比較を停止するまで待機する。
【００１５】すなわち、以上の処理では、メインメモリ１０４の設定されたエレメント範囲の下位側アドレスから順にエレメントが取得され、各々が基準値と比較され、エレメントの値が基準値よりも小さい場合に、その時点のアドレスとエレメントが保持される。
【００１６】こうして比較器１１０、１１４が共に停止した状態になったならば、データライトＤＭＡＣ１１５は、メインメモリ１０４の比較バッファ１０９に保持されたデータが格納されているメモリアドレスに、比較バッファ１１３に保持されたデータをライトし、データライトＤＭＡＣ１１６はメインメモリ１０４の比較バッファ１１３に保持されたデータが格納されているメモリアドレスに、比較バッファ１０９に保持されたデータをライトすることで、データ交換を行う。データ交換が行われたならば、比較器１１０，１１４は比較を再開する。
【００１７】もし、データ交換する際に、昇順読み出しの被ソートデータアドレスと降順読み出しの被ソートデータアドレスがクロスしたならば、制御回路１１７はデータ交換を終了し、データ交換終了を繰り返し制御回路１０１に報せると共に、データ交換回路１０３内のシーケンスを終了し、次の起動を待つ状態となる。なお、データ交換の終了判定は、基準値との比較の対象となったエレメントのアドレスがクロスしていることの判断に基づいて行えばよい。
【００１８】繰り返し制御回路１０１は、データ交換回路１０３からデータ交換終了通知とクロスアドレスを受け取ると、次に行うデータ交換がクロスアドレスよりも上位側か下位側かを決定し、もし上位側を先に行うのであれば下位側のアドレスをスタックメモリ１０２に格納して、上位側のアドレスと共に再度データ交換回路１０３を起動する。この処理を繰り返し、データがすべてソートされるまでこの処理を続ける。
【００１９】図２は本実施形態の繰り返しシーケンスを示した模式図である。繰り返し制御回路１０１は、データ交換回路１０３を用いて、初めに全エレメントに対して交換処理を行い、基準データよりも大きいデータと小さいデータをクロスアドレスの上位、下位に振り分ける。つづいて繰り返し制御回路１０１は、振り分けられた領域を指定して再度データ交換回路１０３を用いて、さらに細分化された領域にエレメントを振り分ける。これを繰り返すことによってソートが行われる。以上のように、実施形態１によれば、大容量のデータを高速にソートすることが可能となる。
【００２０】［実施形態２］上記実施形態１では、昇順読み出し、降順読み出しのそれぞれで被ソートデータのエレメントを１つずつ読み出したが、実施形態２では、複数のエレメントを同時に読み出して基準値との比較を行い、処理速度を更に向上する。
【００２１】図３は実施形態２におけるデータ交換回路１０３の構成を示したブロック図である。実施形態１と同様に、繰り返し制御回路１０１からデータ交換回路１０３が起動されると、基準データリードＤＭＡＣ１０５、昇順データリードＤＭＡＣ１０７、降順データリードＤＭＡＣ１１１が起動される。
【００２２】基準データリードＤＭＡＣ１０５は、メインメモリ１０４から基準データを取得し、基準データバッファ１０６に格納する。
【００２３】昇順データリードＤＭＡＣ１０７は、メインメモリ１０４から、ソートすべきエレメント範囲の最下位アドレスから順に被ソートデータを取得し、プリフェッチバッファ１０８に格納する。このときリードされたデータは、リードトランザクションのバースト長に相当するエレメント数（本例では４とする）で並列化されてプリフェッチバッファ１０８のバッファ３０５に格納される。昇順データリードＤＭＡＣ１０７はプリフェッチバッファ１０８の残りバッファ３０３，３０４がフルになるまでデータリードを繰り返し、バッファがフルになったならば、次にバッファが解放されるまで待ち、バッファが解放された後に再度データリードを再開する。
【００２４】プリフェツチバッファ１０８は、比較バッファ１０９が空いていれば被ソートデータを比較バッファ１０９に送信する。このとき、並列にならべられたデータは一括して比較バッファ１０９へ送られる。
【００２５】比較バッファ１０９に保持された被ソートデータは、比較器１１０によって基準データバッファ１０６に保持されたデータと並列に比較され、もし並列に処理された全てのエレメントの値が基準データよりも小さかったならば、次のエレメントが比較バッファ１０９にロードされ、次の比較が行われる。もし並列に比較されたエレメントの中に基準データよりも大きい値を有するエレメントがあったならば、比較を停止し、降順データ比較器１１４が比較を停止するまで待機する。
【００２６】降順データリードＤＭＡＣ１１１は、メインメモリ１０４から、ソートすべきエレメント範囲の最上位アドレスから順にエレメントを取得し、プリフェッチバッファ１１２に格納する。このときリードされたデータは、リードトランザクションのバースト長に相当するエレメント数（本例では４とする）で並列化されてプリフェッチバッファ１１２のバッファ３０８に格納される。降順データリードＤＭＡＣ１１１はプリフェッチバッファ１１２の残りバッファ３０６，３０７がフルになるまでデータリードを繰り返し、バッファがフルになったならば、次にバッファが解放されるまで待ち、バッファが解放された後に再度データリードを再開する。
【００２７】プリフェッチバッファ１１２は、比較バッファ１１３が空いていれば４つのエレメントを一括に比較バッファ１１３に送信する。
【００２８】比較バッファ１１３に保持されたエレメントは、比較器１１４によって基準データバッファ１０６に保持されたデータと並列に比較され、もし比較バッファ１１３内の全てのエレメントが基準データよりも大きかったならば、次のエレメントが比較バッファ１１３にロードされ、次の比較が行われる。もし比較バッファ１１３内のエレメントに基準データよりも小さいデータが在ったならば、比較を停止し、昇順データ比較器１１０が比較を停止するまで待機する。
【００２９】こうして比較器１１０、１１４が共に停止したならば、データライトＤＭＡＣ１１５は比較バッファ１０９に保持されたデータに相当するメモリアドレスに、比較バッファ１１３に保持されたデータをメインメモリ１０４に対してライトし、データライトＤＭＡＣ１１６は比較バッファ１１３に保持されたデータに相当するメモリアドレスに、比較バッファ１０９に保持されたデータをメインメモリ１０４に対してライトすることで、データ交換を行う。データ交換が行われたならば、比較器１１０，１１４は比較を再開する。なお、ここで実行されるデータ交換は、同時に読み込んだ複数データのうち交換の必要のあるもののみが対象となる。
【００３０】もし、データ交換する際に、昇順の被ソートデータアドレスと降順の被ソートデータアドレスがクロスしたならば、制御回路１１７はデータ交換を終了し、データ交換終了を繰り返し制御回路１０１に報せると共に、データ交換回路１０３内のシーケンスを終了し、次の起動を待つ状態となる。
【００３１】以上のように、プリフェッチバッファ１０８、１１２及び比較バッファ１０９、１１３を並列にし、比較器１１０、１１４を１サイクルに複数のデータを比較できるようにすることにより、データ比較が高速化される。
【００３２】ただし、データ比較の並列化を行うことによって、データ交換したメインメモリ１０４の内容と、プリフェッチバッファ１０８、１１２、比較バッファ１０９、１１３との間に内容の不一致が起こるので、レジスタフォワードパス３０１、３０２を付加することによって整合を取る。以下、レジスタフォワードパス３０１、３０２の機能について説明する。
【００３３】図４Ａ、図４Ｂは本実施形態におけるデータ不一致が起きる状況を示した模式図である。昇順のデータ比較と降順のデータ比較が交差する近傍において、データ交換により、プリフェッチバッファ１０８、１１２及び比較バッファ１０９、１１３内のデータと、メインメモリ１０４に更新されたデータとに不一致が生じる。図４Ａに示すように比較バッファ１０９と比較バッファ１１３に同じアドレスのデータが保持された場合の不一致に対して、互いのバッファ内でデータを交換する必要がある。
【００３４】また図４Ｂに示すように、比較バッファ１０９の内容がプリフェッチバッファ３０８と、比較バッファ１１４の内容がプリフェッチバッファ３０５と一致する場合にも、プリフェッチバッファ１０８、１１２と比較バッファ１０９、１１３のバッファ間でデータの交換を行う必要がある。
【００３５】以上のように、実施形態２によれば、複数のエレメントについて並列して読み出し、基準値との比較が行われるので、実施形態１に比べ、処理速度を更に向上することができる。
【００３６】［実施形態３］実施形態３では、データ交換回路とバブルソート回路を併用することにより更にデータソート処理の高速化を実現する。
【００３７】図５Ａは、実施形態３の構成を示したブロック図である。繰り返し制御回路１０１が起動されることによってソート処理が開始される。繰り返し制御回路１０１は、初めにソートするエレメント範囲を指定してデータ交換回路１０３を起動する。なお、以下では実施形態１で説明したデータ交換回路を適用して実施形態３を説明するが、実施形態２で説明したデータ交換回路を用いてもよい。
【００３８】データ交換回路１０３が起動されると、制御回路１１７がまず、基準データリードＤＭＡＣ１０５、昇順データリードＤＭＡＣ１０７、降順データリードＤＭＡＣ１１１を起動する。基準データリードＤＭＡＣ１０５は、メインメモリ１０４から基準データを取得し、基準データバッファ１０６に格納する。昇順データリードＤＭＡＣ１０７は、メインメモリ１０４から、ソートすべきエレメントの最下位から順にエレメントを取得し、プリフェツチバッファ１０８に格納する。昇順データリードＤＭＡＣ１０７はプリフェッチバッファ１０８がフルになるまでデータリードを繰り返し、バッファがフルになったならば、次にバッファが解放されるまで待ち、バッファが解放された後に再度データリードを再開する。
【００３９】プリフェッチバッファ１０８は、比較バッファ１０９が空いていればエレメントを比較バッファ１０９に送信する。比較バッファ１０９に保持されたエレメントは、比較器１１０によってその値が基準データバッファ１０６に保持されたデータと比較される。もしエレメントの値が基準データよりも小さかったならば、次のエレメントが比較バッファ１０９にロードされ、次の比較が行われる。もしエレメントの値が基準データよりも大きかったならば、比較を停止し、降順データ比較器１１４が比較を停止するまで待機する。
【００４０】降順データリードＤＭＡＣ１１１は、メインメモリ１０４から、ソートすべきエレメントの最上位から順に被ソートデータを取得し、プリフェッチバッファ１１２に格納する。降順データリードＤＭＡＣ１１１はプリフェッチバッファ１１２がフルになるまでデータリードを繰り返し、バッファがフルになったならば、次にバッファが解放されるまで待ち、バッファが解放された後に再度データリードを再開する。
【００４１】プリフェッチバッファ１１２は、比較バッファ１１３が空いていれば被ソートデータを比較バッファ１１３に送信する。比較バッファ１１３に保持されたエレメントは、比較器１１４によって基準データバッファ１０６に保持されたデータと比較され、もしエレメントの値が基準データよりも大きかったならば、次のエレメントが比較バッファ１１３にロードされ、次の比較が行われる。もしエレメントの値が基準データよりも小さかったならば、比較を停止し、昇順データ比較器１１０が比較を停止するまで待機する。
【００４２】もし比較器１１０、１１４が共に停止したならば、データライトＤＭＡＣ１１５は比較バッファ１０９に保持されたデータに相当するメモリアドレスに、比較バッファ１１３に保持されたデータ（エレメント）をメインメモリ１０４に対してライトし、データライトＤＭＡＣ１１６は比較バッファ１１３に保持されたデータに相当するメモリアドレスに、比較バッファ１０９に保持されたデータをメインメモリ１０４に対してライトすることで、データ交換を行う。データ交換が行われたならば、比較器１１０、１１４は比較を再開する。
【００４３】もし、データ交換する際に、昇順の被ソートデータアドレスと降順の被ソートデータアドレスがクロスしたならば、制御回路１１７はデータ交換を終了し、データ交換終了を繰り返し制御回路１０１に報せると共に、データ交換回路１０３内のシーケンスを終了し、次の起動を待つ状態となる。
【００４４】繰り返し回路１０１は、データ交換回路１０３からデータ交換終了通知とクロスアドレスを受け取ると、次に行うデータ交換がクロスアドレスよりも上位側か下位側かを判断し、もし上位側を先に行うのであれば下位側のアドレスをスタックメモリ１０２に格納する。次に上位側のエレメント数がバブルソート回路５０１で処理可能かを判断し、バブルソート回路５０１の処理範囲を超えているようであれば、上位側のアドレスと共に再度データ交換回路１０３を起動する。もし次の処理のエレメント数がバブルソート回路５０１で処理可能であれば、上位側のアドレスと共にバブルソート回路５０１を起動する。
【００４５】バブルソート回路５０１が起動されると、制御回路５０７は、はじめにデータリードＤＭＡＣ５０２を起動してメインメモリ１０４より被ソートデータを取得する。次に制御回路６０７はセレクタ群５０３を切り替え、リードした被ソートデータをレジスタ群５０４へロードさせる。続いて制御回路５０７は、偶数・奇数判別信号をエレメント数回切り替えて、ソート処理を実行する。レジスタ群５０４に保持されたデータは比較器群５０５によって隣接したエレメント間の大小を比較される。比較器群５０５の比較結果と、制御信号５０７が生成する偶数回・奇数回判別信号によって、セレクタ群５０３は現在保持されているレジスタの内容と、上位に隣接するレジスタの内容と、下位に隣接するレジスタの内容を選択し、選択された結果をレジスタ群５０４に更新する。
【００４６】上記動作をエレメント数回繰り返すことにより、当該エレメント範囲内のソート処理が終了する。次に制御回路５０７はデータライトＤＭＡＣ５０６を起動して、レジスタ群５０４に保持されたデータをメインメモリ１０４に書き戻し、最後に処理の終了を繰り返し回路１０１へ通知する。
【００４７】バブルソート回路５０１の処理終了を受けた繰り返し回路１０１は、当該エレメント間のソートは終了したものと判断し、スタックメモリ１０２より未ソートの被ソートデータアドレスを取得し、そのエレメント数がバブルソート回路５０１で処理可能かを判断し、バブルソート回路５０１の処理範囲を超えているようであれば、上位側のアドレスと共に再度データ交換回路１０３を起動する。もし次の処理のエレメント数がバブルソート回路５０１で処理可能であれば、上位側のアドレスと共に再度バブルソート回路５０１を起動する。この処理を繰り返すことによってソート処理が行われる。
【００４８】図５Ｂは、実施形態２における繰り返し制御回路１０１の動作例を説明するフローチャートである。スタックメモリ１０２に格納された、設定されたエレメント範囲を読み出し、このエレメント範囲でデータ交換回路１０３を起動する（ステップＳ５０１、Ｓ５０２）。データ交換回路１０３の制御回路１１７から処理終了を受けると、そのクロスアドレスをスタックメモリ１０２に保持する（ステップＳ５０３）。そして、データ交換回路による交換が完了したエレメント範囲の１つについて、そのエレメント数がバブルソート可能な数であるかどうかを判断する（ステップＳ５０４）。バブルソート可能なエレメント範囲でなければ、ステップＳ５０４からステップＳ５０１へ戻り、当該エレメント範囲について更にデータ交換回路１０３による処理を施す。
【００４９】一方、エレメント範囲の１つがバブルソート可能となった場合は、当該エレメント範囲でバブルソート回路５０１を起動して、当該エレメント範囲のソートを完了させる（ステップＳ５０５）。そして、ソートが未完のエレメント範囲が存在するかどうかを調べ、未完のエレメント範囲があればステップＳ５０４へ戻って上述の処理を繰り返し、全エレメント範囲のソーティングを完成する。
【００５０】図６は、実施形態１のソート装置と、実施形態３のソート装置の繰り返し数を比較した模式図である。図６の（Ａ）は、実施形態１のソート装置を用いた場合の処理の繰り返しを示している。実施形態１のソート装置ではアルゴリズムを変えないためにくり返し数が多くなっている。これに対し、本実施形態では、図６（Ｂ）に示すように、エレメント数が少なくなってきた場合にバブルソート装置に処理を切り替えることによって、処理のくり返し数が少なくなっていることが判る。
【００５１】なお、実施形態３では、データ交換回路とバブルソート回路との組み合わせを説明したが他の方式のソート回路との組み合わせであってもよい。すなわち、本実施形態は、データ交換回路によってソート処理の対象範囲を狭めて、所定の方式のソート回路を適用可能とするものであり、データ交換回路と他の方式のソート回路とを組み合わせるようにしてもよいことは明らかである。
【００５２】［実施形態４］実施形態４では、実施形態３で説明したデータソート回路にキャッシュメモリを適用し、更に処理を高速化する。なお、実施形態１、２のデータソート回路にキャッシュメモリを適用できることは、実施形態４の説明から明らかである。
【００５３】図７は、実施形態４の構成を示したブロック図である。繰り返し制御回路１０１が起動されることによってソート処理が開始される。繰り返し制御回路１０１は初めにソートするエレメント範囲を判断し、キャッシュメモリに格納できる範囲であれば、キャッシュ制御回路を含むバスブリッジ回路７０１にキャッシュをオンにすることを知らせ、データ交換回路１０３を起動する。なお、データ交換回路１０３は上述した実施形態１乃至３のいずれかにおいて用いたものと同様である。また、バブルソート回路５０１は上述の実施形態３で用いたものと同様である。
【００５４】データ交換回路１０３は、くり返し制御回路１０１によって指定されたエレメント範囲内を、基準データよりも大きいデータと小さいデータのに振り分けてデータ交換処理を終了する。この振り分けの際に、データ交換回路１０３からリードトランザクションが発行されると、バスブリッジ回路７０１はキャッシュにヒットしているかを判断し、ヒットしていなければメインメモリ１０４から当該データを取得してデータ交換回路１０３にデータを送ると共にキャッシュメモリ７０２に当該データをキャッシュする。もしヒットしていれば、当該データをキャッシュメモリ７０２から取得し、データ交換回路１０３にデータを送る。データ交換回路１０３からライトトランザクションが発行されると、データは必ずヒットしているはずなので、バスブリッジ回路７０１はライトデータをキャッシュメモリ７０２にライトする。
【００５５】繰り返し回路１０１は、データ交換回路１０３からデータ交換終了通知とクロスアドレスを受け取ると、次に行うデータ交換がクロスアドレスよりも上位側か下位側かを判断し、もし上位側を先に行うのであれば下位側のアドレスをスタックメモリ１０２に格納し、次に上位側のエレメント数がバブルソート回路５０１で処理可能かを判断し、バブルソート回路５０１の処理範囲を超えているようであれば、上位側のアドレス（エレメント範囲）で再度データ交換回路１０３を起動する。
【００５６】もし次の処理のエレメント数がバブルソート回路５０１で処理可能であれば、上位側のアドレスでバブルソート回路５０１を起動する。バブルソート回路５０１が起動されると、エレメント範囲内の被ソートデータをソートして、処理を終了する。この際に、バブルソート回路５０１からリードトランザクションが発行されると、バスブリッジ回路７０１はキャッシュにヒットしているかを判断し、ヒットしていなければメインメモリ１０４から当該データを取得してデータ交換回路１０３にデータを送ると共にキャッシュメモリ７０２に当該データをキャッシュする。もしヒットしていれば、当該データをキャッシュメモリ７０２から取得し、バブルソート回路５０１にデータを送る。
【００５７】バブルソート回路５０１からライトトランザクションが発行されると、データは必ずヒットしているはずなので、バスブリッジ回路７０１はライトデータをキャッシュメモリ７０２にライトする。バブルソート回路５０１の処理終了を受けた繰り返し回路１０１は、当該エレメント間のソートは終了したものと判断し、スタックメモリ１０２より未ソートの被ソートデータアドレスを取得する。そして、そのエレメント数がキャッシュをオンにした際の範囲を超えているかを判断し、超えていなければそのエレメント数がバブルソート回路５０１で処理可能かを判断し、バブルソート回路５０１の処理範囲を超えているようであれば、上位側のアドレスと共に再度データ交換回路１０３を起動する。
【００５８】もし次の処理のエレメント数がバブルソート回路５０１で処理可能であれば、上位側のアドレスと共に再度バブルソート回路５０１を起動する。もしエレメント範囲がキャッシュをオンにした際の範囲を超えていれば、くりかえし回路１０１はキャッシュ制御回路を含むバスブリッジ回路７０１にキャッシュをオフにすることを通知してキャッシングされたデータをメインメモリ１０４にライトバックさせ、次に次のエレメント範囲がキャッシュメモリ７０２の範囲を超えていないかを判断し、超えていればキャッシュをオフのままデータ交換回路１０３を起動し、超えていなければ再度キャッシュをオンにしてデータ交換回路１０３もしくはバブルソート回路５０１を起動する。この処理を繰り返すことによってソート処理が行われる。
【００５９】図８は本実施形態のくり返しシーケンスの様子を示した模式図である。キャッシュメモリ７０２に、ソート対象範囲のデータが収まる場合にキャッシュオンとし、その範囲を超えた場合にキャッシュのデータをライトバックする。例えば、図８においては、繰り返し２のライトと、繰り返し３，４，５，６のリード及びライトはキャッシュヒットすることになり、メモリアクセスのレイテンシを削減できるため、くり返しシーケンスのエレメント数の少ない回の処理が高速化される。
【００６０】［実施形態５］図９は、本実施形態の構成を示したブロック図である。大規模なランダムデータのソート処理の場合には、ソート処理をする前に、あらかじめいくつかの範囲にグループ分けすることが、処理の高速化に有効であることが知られている。本実施形態では、グループ分けされたそれぞれのグループのソート処理を並行に処理を行うことによって高速な処理を行う。
【００６１】ディスパッチ回路９０１が起動されると、コマンドリードＤＭＡＣ９０４が起動され、メインメモリ１０４から処理すべきグループの情報を持ったコマンドを取得し、コマンドディスパッチ回路９０５へ送る。コマンドディスパッチ回路９０５はソート装置９０２および９０３の処理状態を判断し、処理を行っていないソート装置にコマンドに対応したグループのソート処理を割り当てる。コマンドリードＤＭＡＣはつづくコマンドを取得し、コマンドディスパッチ回路９０５へ送る。コマンドディスパッチ回路９０５はソート装置９０２および９０３の処理状態を判断し、処理を行っていないソート装置にコマンドに対応したグループのソート処理を割り当てる。もしどのソート装置も以前のコマンドを処理中であれば、どれかのソート装置が空くまで、コマンドに対応したソート処理の割り当てを待つ。もしコマンドの内容が終了を意味していたならば、コマンドディスパッチ回路９０５は全てのソート装置９０２，９０３の処理終了を待って全ての処理を終了する。
【００６２】図１０ＡはコマンドリードＤＭＡＣ９０４の処理シーケンスを示したフローチャートである。また、図１０Ｂは、コマンドディスパッチ回路９０５の処理シーケンスを示したフローチャートである。
【００６３】コマンドリードＤＭＡＣ９０４は、はじめにソート処理の起動待ちをし（ステップＳ１００１）、ソート処理が起動されたならばメインメモリ１０４に対してリードトランザクションを発行して（ステップＳ１００２）、メインメモリ１０４からのリードデータを待つ（ステップＳ１００３）。つづいてコマンドディスパッチ回路９０５がデータ受信可能か否かを判断し（ステップＳ１００４）、もし可能であればコマンドディスパッチ回路９０５へメインメモリ１０４からリードしたコマンドデータを送る（ステップＳ１００５）。次に、送ったコマンドが終了コマンドであったかどうかを示す情報をコマンドディスパッチ回路９０５から受信し、終了であるかを判断し（ステップＳ１００６）、もし終了でなければ次ノードトランザクションを発行し（ステップＳ１００２）、終了であればまた起動待ちに戻る（ステップＳ１００１）。
【００６４】コマンドディスパッチ回路９０５は、まずソート処理の起動待ちをし（ステップＳ１００７）、ソート処理が起動されたならばつぎにコマンドデータ待ちをする（ステップＳ１００８）。コマンドリードＤＭＡＣ９０４からコマンドデータを受け取ったならば、それが終了コマンドか否かを判断する（ステップＳ１００９）。終了コマンドでなければ、空いているソート装置にソート処理を割り当てる（ステップＳ１０１０）。その後、更に空いているソート装置が在るかを判断し（ステップＳ１０１１）、空いているソート装置があればステップＳ１００８へ戻りコマンドデータを待つ。
【００６５】ステップＳ１００９において、終了コマンドであったならば、コマンドリードＤＭＡＣ９０４に終了を通知し（ステップＳ１０１２）、つづいて全てのソート装置が処理を終了するのを待ち（ステップＳ１０１３）、全てのソート装置が終了したならば、またソート処理の起動待ちに戻る（ステップＳ１００７）。
【００６６】［実施形態６］図１１は、本実施形態の構成を示したブロック図である。実施形態６では、データを２つ以上の変数と比較し、比較の際に第１の変数が等価であった場合は第２の変数で比較し、第２の変数も等価であった場合には第３の変数で比較するという場合において、第１の変数は並べ替えるエレメントに内包され、第２、第３の変数は並べ替えるエレメントとは異なったメモリアドレスに存在する方が処理が高速である。
【００６７】実施形態６は、その様なデータ構造をとったデータソートのソート装置である。繰り返し制御回路１０１は初めにソートするエレメント範囲を指定してデータ交換回路１０３を起動する。データ交換回路１０３が起動されると、制御回路１１７がまず、基準データリードＤＭＡＣ１０５、昇順データリードＤＭＡＣ１０７、降順データリードＤＭＡＣ１１１を起動する。基準データリードＤＭＡＣ１０５は、メインメモリ１０４から基準データを取得し、基準データバッファ１０６に格納する。昇順データリードＤＭＡＣ１０７は、メインメモリ１０４から、ソートすべきエレメント範囲の最下位から順にエレメントを取得し、プリフェッチバッファ１０８に格納する。
【００６８】昇順データリードＤＭＡＣ１０７はプリフェッチバッファ１０８がフルになるまでデータリードを繰り返し、バッファがフルになったならば、次にバッファが解放されるまで待ち、バッファが解放された後に再度データリードを再開する。プリフェッチバッファ１０８は、比較バッファ１０９が空いていればエレメントを比較バッファ１０９に送信する。比較バッファ１０９に保持されたエレメントは、比較器１１０によって基準データバッファ１０６に保持されたデータと比較され、もしエレメントの値が基準データよりも小さかったならば、次のエレメントが比較バッファ１０９にロードされ、次の比較が行われる。もしエレメントの値が基準データよりも大きかったならば、比較を停止し、降順データ比較器１１４が比較を停止するまで待機する。
【００６９】もしエレメントの最初の変数ＫＥＹ１が基準データのＫＥＹ１と等価であった場合には、次にポインタリードＤＭＡＣ１１０１が起動され、メインメモリ１０４からＫＥＹ２，ＫＥＹ３を含むデータがリードされ、比較バッファ１１０２に格納され、比較器１１０３によって基準データのＫＥＹ２，ＫＥＹ３と比較される。もし被ソートデータのＫＥＹ２，ＫＥＹ３が基準データのＫＥＹ２，ＫＥＹ３よりも小さかったならば、次の被ソートデータが比較バッファ１０９にロードされ、次の比較が行われる。もし被ソートデータのＫＥＹ２，ＫＥＹ３が基準データのＫＥＹ２，ＫＥＹ３よりも大きかったならば、比較を停止し、降順データ比較器１１４が比較を停止するまで待機する。降順データリードＤＭＡＣ１１１は、メインメモリ１０４から、ソートすべきエレメントの最上位から順に被ソートデータを取得し、プリフェッチバッファ１１２に格納する。
【００７０】降順データリードＤＭＡＣ１１１はプリフェッチバッファ１１２がフルになるまでデータリードを繰り返し、バッファがフルになったならば、次にバッファが解放されるまで待ち、バッファが解放された後に再度データリードを再開する。プリフェッチバッファ１１２は、比較バッファ１１３が空いていればエレメントを比較バッファ１１３に送信する。比較バッファ１１３に保持されたエレメントは、比較器１１４によって基準データバッファ１０６に保持されたデータと比較され、もしエレメントの値が基準データよりも大きかったならば、次のエレメントが比較バッファ１１３にロードされ、次の比較が行われる。もしエレメントの値が基準データよりも小さかったならば、比較を停止し、昇順データ比較器１１０が比較を停止するまで待機する。
【００７１】もし被ソートデータの最初の変数ＫＥＹ１が基準データのＫＥＹ１と等価であった場合には、次にポインタリードＤＭＡＣ１１０４が起動され、メインメモリ１０４からＫＥＹ２，ＫＥＹ３を含むデータがリードされ、比較バッファ１１０５に格納され、比較器１１０６によって基準データのＫＥＹ２，ＫＥＹ３と比較される。
【００７２】もし被ソートデータのＫＥＹ２，ＫＥＹ３が基準データのＫＥＹ２，ＫＥＹ３よりも大きかったならば、次の被ソートデータが比較バッファ１０９にロードされ、次の比較が行われる。もし被ソートデータのＫＥＹ２，ＫＥＹ３が基準データのＫＥＹ２，ＫＥＹ３よりも小さかったならば、比較を停止し、降順データ比較器１１４が比較を停止するまで待機する。
【００７３】もし比較器１１０、１１４が共に停止したならば、データライトＤＭＡＣ１１５は比較バッファ１０９に保持されたデータに相当するメモリアドレスに、比較バッファ１１３に保持されたデータをメインメモリ１０４に対してライトし、データライトＤＭＡＣ１１６は比較バッファ１１３に保持されたデータに相当するメモリアドレスに、比較バッファ１０９に保持されたデータをメインメモリ１０４に対してライトすることで、データ交換を行う。データ交換が行われたならば、比較器１１０、１１４は比較を再開する。
【００７４】もし、データ交換する際に、昇順の被ソートデータアドレスと降順の被ソートデータアドレスがクロスしたならば、制御回路１１７はデータ交換を終了し、データ交換終了を繰り返し制御回路１０１に報せると共に、データ交換回路１０３内のシーケンスを終了し、次の起動を待つ状態となる。繰り返し回路１０１は、データ交換回路１０３からデータ交換終了通知とクロスアドレスを受け取ると、次に行うデータ交換がクロスアドレスよりも上位側か下位側かを判断し、もし上位側を先に行うのであれば下位側のアドレスをスタックメモリ１０２に格納して、上位側のアドレスと共に再度データ交換回路１０３を起動する。この処理を繰り返し、データがすべてソートされるまでこの処理を続ける。
【００７５】図１２は、本実施形態のデータ構造を示した模式図である。データを並べ替えるエレメントは、第一に比較するＫＥＹ１とＫＥＹ２以降の構造体のポインタから成る。ポインタのさす先の構造体は第二に比較する変数ＫＥＹ２および第三に比較する変数ＫＥＹ３から成っている。ＫＥＹ１は必ず比較するのに対し、ＫＥＹ２，ＫＥＹ３を比較する頻度は極低いことから、メモリアクセスを最小限に押さえ、キャッシュのヒット率を高くするこのデータ構造が、複数の変数で比較し、ソートする場合に、高速なソート処理に対して有効である。
【００７６】
【発明の効果】以上説明したように本発明によれば、大規模なランダムデータのソートを、高速に処理できる。

【出願人】	【識別番号】０００００１００７【氏名又は名称】キヤノン株式会社
【出願日】	平成１３年４月９日（２００１．４．９）
【代理人】	【識別番号】１０００７６４２８【弁理士】【氏名又は名称】大塚康徳（外３名）
【公開番号】	特開２００２－３１２１５９（Ｐ２００２－３１２１５９Ａ）
【公開日】	平成１４年１０月２５日（２００２．１０．２５）
【出願番号】	特願２００１－１１０２４５（Ｐ２００１－１１０２４５）