(57)【要約】ソート済み集合のユニオン処理を、並列計算機を用いて高速に実行させることができる並列ユニオン制御技術を提供する。本発明の一態様に係る並列ユニオン制御装置１００は、Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御装置であって、前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御部１０１と、メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力部１０２と、並列で行うユニオン処理が終了したかどうかを判定する終了判定部１０３と、を備える。
2019156060.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御装置であって、
前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御手段と、
メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力手段と、
並列で行うユニオン処理が終了したかどうかを判定する終了判定手段と、
を備える並列ユニオン制御装置。
【請求項２】
前記ソート済み集合は要素が昇順に並んでいる集合であり、
前記要素比較制御手段は、前記比較の結果が等しくないとき、前記演算器に小さい方の入力要素を前記出力要素として選択させて、該小さい方の入力要素を指すポインタをインクリメントし、前記比較の結果が等しいとき、前記演算器に該入力要素を前記出力要素として選択させて、両方の入力要素を指すポインタをインクリメントする、
請求項１に記載の並列ユニオン制御装置。
【請求項３】
前記入力集合を複数の入力部分集合に分割して、前記要素比較制御手段に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合手段を更に有する、
請求項１又は２に記載の並列ユニオン制御装置。
【請求項４】
前記複数の入力部分集合の分割数を決定する分割数決定手段を更に有し、
前記集合分割結合手段は、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
請求項３に記載の並列ユニオン制御装置。
【請求項５】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御装置であって、
請求項１乃至４のいずれか１つに記載の並列ユニオン制御装置と、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成手段と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定手段と、
を備える複数ユニオン制御装置。
【請求項６】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御装置であって、
それぞれ、請求項１に記載の並列ユニオン制御装置である、第１の並列ユニオン制御装置と第２の並列ユニオン制御装置と、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成手段と、
前記第１の並列ユニオン制御装置と前記第２の並列ユニオン制御装置とを切り替えるユニオン制御装置切替手段と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定手段と、
を備え、
前記第２の並列ユニオン制御装置は、前記入力集合を複数の入力部分集合に分割して、前記要素比較制御手段に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合手段を更に有する、
複数ユニオン制御装置。
【請求項７】
前記第２の並列ユニオン制御装置は、前記複数の入力部分集合の分割数を決定する分割数決定手段を更に有し、
前記集合分割結合手段は、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
請求項６に記載の複数ユニオン制御装置。
【請求項８】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御方法であって、情報処理装置によって、
前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御を行い、
メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力を行い、
並列で行うユニオン処理が終了したかどうかを判定する終了判定を行う、
並列ユニオン制御方法。
【請求項９】
前記ソート済み集合は要素が昇順に並んでいる集合であり、
前記要素比較制御は、前記比較の結果が等しくないとき、前記演算器に小さい方の入力要素を前記出力要素として選択させて、該小さい方の入力要素を指すポインタをインクリメントし、前記比較の結果が等しいとき、前記演算器に該入力要素を前記出力要素として選択させて、両方の入力要素を指すポインタをインクリメントする、
請求項８に記載の並列ユニオン制御方法。
【請求項１０】
前記情報処理装置によって、前記入力集合を複数の入力部分集合に分割して、前記要素比較制御において、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、
請求項８又は９に記載の並列ユニオン制御方法。
【請求項１１】
前記情報処理装置によって、前記複数の入力部分集合の分割数を決定し、
前記集合を分割し結合することは、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
請求項１０に記載の並列ユニオン制御方法。
【請求項１２】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御方法であって、情報処理装置によって、
請求項８乃至１１のいずれか１つに記載の並列ユニオン制御方法を実施し、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納し、
ユニオン処理全体が完了したかどうかを判定する、
複数ユニオン制御方法。
【請求項１３】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御方法であって、情報処理装置によって、
それぞれ、請求項８に記載の並列ユニオン制御方法である、第１の並列ユニオン制御方法と第２の並列ユニオン制御方法とを実施し、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納し、
前記第１の並列ユニオン制御方法と前記第２の並列ユニオン制御方法とを切り替え、
ユニオン処理全体が完了したかどうかを判定し、
前記第２の並列ユニオン制御方法は、さらに、前記入力集合を複数の入力部分集合に分割して、前記要素比較制御において、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、
複数ユニオン制御方法。
【請求項１４】
前記第２の並列ユニオン制御方法は、情報処理装置によって、
前記複数の入力部分集合の分割数を決定し、
決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
請求項１３に記載の複数ユニオン制御方法。
【請求項１５】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、コンピュータに、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御用プログラムであって、
前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御処理と、
メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力処理と、
並列で行うユニオン処理が終了したかどうかを判定する終了判定処理と、
を前記コンピュータに実行させる並列ユニオン制御用プログラムを記憶する記憶媒体。
【請求項１６】
前記ソート済み集合は要素が昇順に並んでいる集合であり、
前記要素比較制御処理は、前記コンピュータに、前記比較の結果が等しくないとき、前記演算器に小さい方の入力要素を前記出力要素として選択させて、該小さい方の入力要素を指すポインタをインクリメントさせ、前記比較の結果が等しいとき、前記演算器に該入力要素を前記出力要素として選択させて、両方の入力要素を指すポインタをインクリメントさせる、
請求項１５に記載の記憶媒体。
【請求項１７】
前記入力集合を複数の入力部分集合に分割して、前記要素比較制御処理に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合処理を前記コンピュータに更に実行させる、
請求項１５又は１６に記載の記憶媒体。
【請求項１８】
前記複数の入力部分集合の分割数を決定する分割数決定処理を前記コンピュータに更に実行させ、
前記集合分割結合処理は、前記コンピュータに、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割させ、前記複数の出力部分集合を前記出力集合に結合させる、
請求項１７に記載の記憶媒体。
【請求項１９】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、コンピュータに、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御用プログラムであって、
請求項１５乃至１８のいずれか１つに記載の記憶媒体に格納されている並列ユニオン制御用プログラムを含み、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成処理と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定処理と、
を前記コンピュータに実行させる複数ユニオン制御用プログラムを記憶する記憶媒体。
【請求項２０】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、コンピュータに、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御用プログラムであって、
それぞれ、請求項１５に記載の記憶媒体に格納されている並列ユニオン制御用プログラムである、第１の並列ユニオン制御用プログラムと第２の並列ユニオン制御用プログラムと、
を含み、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成処理と、
前記第１の並列ユニオン制御用プログラムと前記第２の並列ユニオン制御用プログラムとを切り替えるユニオン制御用プログラム切替処理と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定処理と、
を前記コンピュータに実行させ、
前記第２の並列ユニオン制御用プログラムは、前記入力集合を複数の入力部分集合に分割して、前記要素比較制御処理に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合処理を前記コンピュータに更に実行させる、
複数ユニオン制御用プログラムを記憶する記憶媒体。
【請求項２１】
前記第２の並列ユニオン制御用プログラムは、前記複数の入力部分集合の分割数を決定する分割数決定部処理を前記コンピュータに更に実行させ、
前記集合分割結合処理は、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
請求項２０に記載の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソート済み集合のユニオン処理を並列に行う技術に関する。
【背景技術】
【０００２】
数あるグラフアルゴリズムのカーネル演算として、疎行列疎ベクトル積が注目されている。グラフアルゴリズムには、例えば、連結成分抽出や最短経路問題がある。連結成分抽出は、例えば、Twitter（登録商標）やFacebook（登録商標）などのＳＮＳ（social networking service）におけるユーザ間の関係（友達かどうか等）を示すグラフから、お互いに到達可能な頂点の集合（例えば、コミュニティ）を求める（抽出する）。一方、最短経路問題は、例えば、地図上の地点と、それらをつなぐ道路の関係を示すグラフから、ある頂点から別のある頂点へのもっとも近い経路を見つける問題（経路探索）である。【０００３】
グラフの探索は行列演算である。グラフの構造は疎行列で表される。グラフの探索は、疎行列と疎ベクトルとの積、すなわち、疎行列疎ベクトル積で表される。【０００４】
すなわち、疎行列疎ベクトル積は、疎行列と疎ベクトルとの積演算である。その疎行列及び疎ベクトルは、非零要素のインデックスと値とを保持する形式となっている。このような疎行列（疎ベクトル）表現を用いることで、零が大半になるようなデータを小容量のメモリで格納することができる。【０００５】
しかしながら、疎行列疎ベクトル積においては、複数のソート済み集合のユニオンを取る処理（以下、「ユニオン処理」という）の負荷が特に大きい。ユニオン処理については、後で説明する。【０００６】
ソート済み集合のユニオン処理は、グラフアルゴリズムに頻繁に出現する。例えば、そのようなグラフアルゴリズムは、データベースのテーブルのJoinを取る処理において出現する。ここで、「ソート済み集合」とは、集合の要素が昇順もしくは降順に並んでいるもののことである。また、「ソート済み集合のユニオン処理」とは、入力となる集合の入力要素を含み、かつ重複した入力要素を省いた状態でそれ以外の要素は含まないような、ソート済み集合から成る出力要素を出力として返す処理である。入力となるソート済み集合の数は３つ以上のことがある。【０００７】
なお、ユニオン処理と近似する処理として、マージ処理が知られている。ここで、「ソート済み集合のマージ処理」とは、入力となる集合の入力要素を含み、かつ重複した入力要素を残した状態でそれ以外の要素は含まないような、ソート済み集合から成る出力要素を出力として返す処理である。【０００８】
この技術分野において周知のように、ベクトル計算機などの並列計算機は計算処理を高速化することができる。ベクトル計算機は、数値を複数個格納できるレジスタ（ベクトルレジスタ）を持ち、そのレジスタ内の数値に同様の演算を並列に実行するベクトル演算器を有することを特徴とする計算機である。ベクトル演算器は、複数の演算器を含む。ベクトル計算機では、ベクトル演算器を効率的に活用することによって、一般的なプロセッサと比較して計算処理を高速に実行することが期待できる。【０００９】
換言すると、ベクトル計算機は、ベクトル演算（ＳＩＭＤ（Single Instruction Multiple Data））を行えるコンピュータである。ここで、ＳＩＭＤとは、コンピュータやマイクロプロセッサで並列処理を行なうための設計仕様の一つである。ＳＩＭＤは、一つの命令を同時に複数のデータに適用し、並列に処理する方式である。そのような処理方式は、ベクトル演算、ベクトル処理などと呼ばれる。【００１０】
本発明に関連する先行技術が種々知られている。【００１１】
例えば、特許文献１は、２つの整列済部分データ列対を入力とするマージ処理の並列化を可能とした、並列マージソート処理装置を開示している。この特許文献１に開示された並列マージソート処理装置は、マージ処理用並列プロセッサと、データ列対分割用並列プロセッサと、ソート処理用並列プロセッサと、管理用プロセッサと、データ記憶域とを有する。マージ処理用並列プロセッサは、複数のプロセッサを含み、複数のタスクを同時並列的に実行可能である。データ列対分割用並列プロセッサは、２組の整列済データ列の対を所定数の部分データ列に分割して、管理用プロセッサに返す。ソート処理用並列プロセッサは、指定された領域に存在する未整列のデータ列をソートする。【００１２】
特許文献１では、２つの整列済データ列の対を複数の部分データ列の対に分割することで並列度を向上させている。マージの入力となるデータ列の対を２分割することにより２組の入力データ列対を得て、それぞれを正順マージと逆順マージを行うことにより複数のプロセッサに同時に処理をさせることができる。データ列の対を４分割することにより４組の入力データ列を得て、それぞれを正順マージと逆順マージを行うことにより複数のプロセッサに同時に処理をさせることができる。【００１３】
特許文献２は、ソート処理の高速化を図るとともに、キャッシュヒット率を向上させた、ソート処理装置を開示している。特許文献２に開示されたソート処理装置では、全てのブロックについてブロック内ソートが完了すると、ブロック間マージ処理部が各ブロックのマージを行う。先ず、ブロック間マージ処理部は、ブロック内ソートされたＮ個のブロックの最小値によるデータ列を生成する。次に、ブロック間マージ処理部は、生成したデータ列をソートする。そして、ブロック間マージ処理部は、ソートされたデータ列の最小値をソート結果データの最小値として主記憶上に出力する。ブロック間マージ処理部は、出力されたデータが属していたブロックに次の最小値のデータがあるか否かを判断し、最小値のデータがあれば、これを最小値のデータ列に挿入するとともに、最小値のデータ列をソートする処理から繰り返して実行する。【００１４】
また、ブロック間マージ処理部は、出力したデータの属するブロックから次に小さい値の最小値のデータ列への挿入と、そのデータ列の最小値の主記憶装置への出力と、を繰り返す。繰り返しの結果、全てのブロックが空になった時点でソート対象データのソートが完了する。【００１５】
また、特許文献３は、効率的なレコードの入力を実現することができるマージ処理装置を開示している。特許文献３に開示されたマージ処理装置は、配置変換部と、入力部と、記憶部と、レコード列選択部と、を備えている。配置変換部には、ソートされた複数のレコードから構成されるレコード列が複数入力される。配置変換部は、入力された複数のレコード列を、少なくとも１のレコードを含むレコードブロックに分離し、それぞれのレコードブロックに含まれる複数のレコードの最後方に配置されている予測用レコードを、現在配置されている位置よりも前方に位置するようにレコードの順序を入れ替える。レコード列選択部は、複数のレコードブロックのそれぞれに含まれた予測用レコードに基づいて、入力部が配置変換部から取得するレコード列を選択する。レコード列選択部によって選択されたレコード列は、入力部における現在のレコード列の取得が完了後に、入力部によって配置変換部から取得される。【００１６】
さらに、特許文献４は、多数の要素からなる配列をソートする装置、方法およびプログラムを開示している。特許文献４は、マルチウェイ・マージを用いて多数のデータからなる配列に対してマージソートの処理を行っている。マルチウェイ・マージでは、複数の入力列をマージして、最終的に１個の出力列が生成される。その際、２ウェイ・マージが繰り返し実行される。特許文献４では、ＳＩＭＤ命令を用いることにより、マージ処理を並列に実行している。特許文献４において、昇順に整列させる場合、入力列の先頭であるペアの比較が行われ、値の小さいものから先に出力列に並べられる。【００１７】
また、特許文献５は、競合検出演算を実行するための装置および方法を開示している。特許文献５に開示された方法では、先ず、第１のセットのデータ要素が第１のソースベクトルレジスタ内に格納され、第２のセットのデータ要素が第２のソースベクトルレジスタ内に格納される。引き続いて、第１のソースレジスタ内の各データ要素が、第２のソースレジスタ内のデータ要素の指定されたセットと比較される。比較の結果がデスティネーションレジスタ内に格納される。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】国際公開第２００３／０９１８７２号
【特許文献２】特開２００６−１６３５６５号公報
【特許文献３】特開２０１１−２３３０１２号公報
【特許文献４】特開２０１６−１１５０９２号公報
【特許文献５】特表２０１７−５３９０１３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
上述した先行技術には、次に述べるような課題がある。【００２０】
特許文献１〜４はいずれも、マージ処理について記載しているに過ぎない。一方、特許文献５は、単に、２つのデータ要素を比較して競合を検出する技術を開示しているに過ぎない。また、特許文献１〜５のいずれも、並列計算機を用いて疎行列疎ベクトル積を並列化して実行する上での課題の認識がない。【００２１】
すなわち、特許文献１は、単に複数のタスクを同時並行的に実行することと、２つの整列済データ列の対を複数の部分データ列に分割することにより並列度を向上させた、並列マージソート処理装置を開示しているに過ぎない。【００２２】
特許文献２は、ソートされたデータ列の最小値をソート結果データの最小値として主記憶装置に出力し、出力されたデータが属していたブロックに次の最小値のデータがあるか否かを判断し、あれば最小値のデータ列に挿入し、全てのブロックが空になった時点で完了する、ソート処理装置を開示しているに過ぎない。【００２３】
特許文献３は、予測レコードに基づいてレコードブロックに含まれるレコードを全て取得する前に、レコード列を選択する処理を開始して、効率的なレコードの入力を実現した、マージ処理装置を開示しているに過ぎない。【００２４】
特許文献４は、単に複数配列のマージを扱っているに過ぎない。また、特許文献４では、ベクトル処理（ＳＩＭＤ）のような並列計算機を用いて疎行列疎ベクトル積を高速に実行する上での課題を認識してはいない。【００２５】
特許文献５は、単に、競合検出を実行するための方法および装置を開示しているに過ぎない。【００２６】
本発明の目的は、上述した課題を解決し、ソート済み集合のユニオン処理を、並列計算機を用いて高速に実行させることができる、並列ユニオン制御装置等を提供することにある。
【課題を解決するための手段】
【００２７】
本発明の一態様に係る並列ユニオン制御装置は、Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御装置であって、前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御手段と、メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力手段と、並列で行うユニオン処理が終了したかどうかを判定する終了判定手段と、を備える。【００２８】
本発明の一態様に係る並列ユニオン制御方法は、Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御方法であって、情報処理装置によって、前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御を行い、メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力を行い、並列で行うユニオン処理が終了したかどうかを判定する終了判定を行う。【００２９】
本発明の一態様に係る記憶媒体は、Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、コンピュータに、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御用プログラムであって、前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御処理と、メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力処理と、並列で行うユニオン処理が終了したかどうかを判定する終了判定処理と、を前記コンピュータに実行させる並列ユニオン制御用プログラムを記憶する。【００３０】
さらに、本発明の態様は、上述の記憶媒体に格納されているプログラムによっても実現される。
【発明の効果】
【００３１】
本発明によれば、ソート済み集合のユニオン処理を、並列計算機を用いて高速に実行させることができる。
【図面の簡単な説明】
【００３２】
【図１】ベクトル計算機を含む計算機システムの概略構成を示すブロック図である。
【図２】５１２個のソート済み集合（入力集合）から２５６組のペアを作り、図１に示したベクトル計算機に、２５６回のユニオン処理を並列に実行させる例を示す図である。
【図３】本発明の第１の実施の形態に係る並列ユニオン制御装置の構成を示すブロック図である。
【図４】図３に示す並列ユニオン制御装置に用いられる要素比較制御部が制御するベクトル演算器の演算器と、この演算器に入出力する入力集合および出力集合を格納するベクトルレジスタとの接続関係を示す図である。
【図５】図３に示す並列ユニオン制御装置に用いられる要素比較制御部の構成の一例を示す図である。
【図６】図３に示す並列ユニオン制御装置の処理全体の動作を説明するためのフローチャートである。
【図７】図３に示す並列ユニオン制御装置に用いられる要素比較制御部での比較処理制御の詳細を示すフローチャートである。
【図８】図３に示す並列ユニオン制御装置に用いられる終了判定部での終了判定の詳細を示すフローチャートである。
【図９】本発明の第２の実施の形態に係る複数ユニオン制御装置の構成を示すブロック図である。
【図１０】図９に示した複数ユニオン制御装置の処理全体の動作を説明するためのフローチャートである。
【図１１】本発明の第３の実施の形態に係る並列ユニオン制御装置を示したブロック図である。
【図１２】図１１に示した並列ユニオン制御装置の動作を説明するためのフローチャートである。
【図１３】本発明の第３の実施の形態に係る複数ユニオン制御装置の構成を示すブロック図である。
【図１４】図１３に示した複数ユニオン制御装置の処理全体の動作を説明するためのフローチャートである。
【図１５】本発明の第４の実施の形態に係る複数ユニオン制御装置の構成を示すブロック図である。
【図１６】図１５に示した複数ユニオン制御装置の処理全体の動作を説明するためのフローチャートである。
【図１７】本発明の第５の実施の形態に係る並列ユニオン制御装置の構成を示すブロック図である。
【図１８】図１７に示した並列ユニオン制御装置の動作を説明するためのフローチャートである。
【図１９】本発明の第５の実施の形態に係る複数ユニオン制御装置の構成を示すブロック図である。
【図２０】図１９に示した複数ユニオン制御装置の処理全体の動作を説明するためのフローチャートである。
【図２１】本発明の実施の形態に係る、並列ユニオン制御装置、及び、複数ユニオン制御装置として動作できるコンピュータのハードウェア構成の例を表す図である。
【発明を実施するための形態】
【００３３】
［前提技術］
本発明の実施の形態の説明に先立って、説明に必要な諸概念について記述する。
【００３４】
図１を参照して、ベクトル計算機Ａ１００について説明する。ベクトル計算機Ａ１００は、数値を複数個格納できるレジスタ（ベクトルレジスタ）Ａ１２０を持つ。ベクトルレジスタＡ１２０内の要素の数をベクトル長と呼ぶ。ベクトル計算機Ａ１００は、ベクトルレジスタＡ１２０内の複数の数値に同様の演算を並列に実行するベクトル演算器Ａ１１０を有する。ベクトル演算器Ａ１１０は、例えば、Ｎ（Ｎは２以上の整数）個の演算器（図示せず）を含む。Ｎは、例えば、２５６であってよい。
【００３５】
また、ベクトル計算機Ａ１００は、ベクトル演算器Ａ１１０の演算単位（演算器）を制御するマスクレジスタＡ１３０を備える。ベクトル計算機Ａ１００では、マスクレジスタＡ１３０のビットが１である演算単位（演算器）では演算を実行し、ビットが０である演算単位（演算器）では演算を実行しない、といった操作ができる。
【００３６】
ベクトル計算機Ａ１００には、メモリ（主記憶装置）Ｂ１００が接続される。ベクトル計算機Ａ１００とメモリＢ１００とは、制御装置Ｃ１００によって制御される。
【００３７】
なお、後述する本発明の実施の形態ではベクトル計算機を対象としているが、ＧＰＧＰＵ（General-Purpose computing on graphics processing units）のような命令レベルでの並列化を実行する計算機アーキテクチャにおいても本発明は効果を発揮する。
【００３８】
ここで、ＧＰＧＰＵとは、画像処理を専門とする演算装置であるＧＰＵ（Graphics Processing Unit）の演算資源を画像処理以外の目的に応用する技術である。ＧＰＵは元々グラフィックス演算を専門とするアクセラレータであるが、ＧＰＵの高い演算性能をグラフィックス演算だけでなく、より汎用的で自由度の高い計算に用いるのがＧＰＧＰＵである。以下、本明細書では、ベクトル計算機やＧＰＧＰＵを総称して、「並列計算機」と呼ぶことにする。
【００３９】
なお、この技術分野において周知のように、ＧＰＵは複数のコアを搭載しており、単一のコアでは複数の命令は実行できないが、単純な命令を実行できるコアを多く搭載することで演算性能を高めている。また、ＧＰＵはそれぞれのコアで、同一の命令を行うスレッドを同時に複数個実行できるＳＩＭＴ（Single Instruction Multiple Thread）アーキテクチャである。そのため、ＧＰＵは同一命令を何度も繰り返し実行するような演算や、Ｎ体問題や行列積などのメモリアクセス量に対して演算量の多い計算に適している。これらの計算はＧＰＵ上で高い演算性能を出すことができる。
【００４０】
次に、本発明の実施の形態が扱う処理である、ソート済み集合のユニオン処理について説明する。ここで、「集合」とは、要素の集まりのことであり、重複する要素を含まない。すなわち、集合では、その要素は互いに等しくはない、ことを特徴とする。また、本発明の実施の形態では集合の要素間に順序（大きい、もしくは、小さい、もしくは等しい）関係をつけることができると想定する。例えば、整数や小数には順序関係をつけることができる。また、「ソート済み集合」とは、集合の要素に順番が決まっており、前の順番の要素が後の順番の要素よりも大きいか等しい（記号で書くと≦、これを昇順という）、もしくは、小さいか等しい（記号で書くと≧、これを降順という）という関係が成り立つ集合を指す。ソート済み集合では、要素はインデックスもしくはポインタなどで指定される。昇順でも降順でも本質的には変わらない。そこで、以降の説明ではソート済み集合は、要素が昇順に並んでいる集合であるとする。
【００４１】
次に、ソート済み集合のユニオン処理について説明する。この処理は、前述したように、入力集合となるソート済み集合（２つ以上）に含まれる入力要素をすべて含み、かつ重複した入力要素を省いた状態でそれ以外の要素は含まない、出力要素から成るソート済み集合を出力集合として出力するような処理である。次に、具体例を挙げて説明する。
【００４２】
以下では、入力集合として次の３つのソート済み集合A1、A2、A3を考える。ここでは、A1、A2、A3を、それぞれ、第１乃至第３の入力集合と呼ぶことにする。これら入力集合はすべてソート済みであることに注意する。
A1: [1, 4, 6, 8],       A2: [4, 6, 7, 9],       A3: [2, 4, 8]
【００４３】
この入力集合に対するユニオン処理の結果である出力集合Bは以下のようになる。
B: [1, 2, 4, 6, 7, 8, 9]
【００４４】
ユニオン処理の出力集合Ｂを得るためには、第１乃至第３の入力集合A1、A2、A3に対してひとつずつユニオン処理を施していけばよい。すなわち、第１の入力集合A1と第２の入力集合A2とにユニオン処理を行い、その出力となるソート済み集合と第３の入力集合A3とについてユニオン処理を行うことによって、最終的な出力集合Bを得ることができる。第１乃至第３の入力集合A1, A2, A3のユニオン処理をする順番はどのようでも良い。
【００４５】
なお、上述した入力集合A1、A2、A3に対してマージ処理を施した場合、その結果である出力集合Cは次のようになる。
C: [1, 2, 4, 4, 4, 6, 6, 7, 8, 8, 9]
【００４６】
詳述すると、マージ処理では、重複した要素を削除しないので、入力集合の入力要素の総数と出力集合の出力要素の数とは等しい。これに対して、ユニオン処理では、重複した要素を削除するので、出力集合の出力要素の数が入力集合の入力要素の総数より少なくなる。したがって、ユニオン処理を繰り返すことによって、得られる出力集合の出力要素は数が徐々に少なくなってくる。これがユニオン処理とマージ処理との間の相違点である。
【００４７】
次に、本発明を実施するための形態について図面を参照して詳細に説明する。
【００４８】
＜第１の実施の形態＞
以下において、本発明の第１の実施の形態に係る並列ユニオン制御装置について説明する。並列ユニオン制御装置は、図１の制御装置Ｃ１００として使用されるものである。
【００４９】
並列ユニオン制御装置は、ベクトルレジスタＡ１２０の要素の数（ベクトル長）だけペアになったソート済み集合（入力集合）に対して、それぞれの入力集合のペアのユニオン処理（後述する）を、ベクトル演算器Ａ１１０を用いて並列に実行させる。尚、ベクトル長は、ベクトル演算器Ａ１１０の演算器の個数であるＮに等しい。例えば、ベクトル長Ｎは２５６であってよい。
【００５０】
この場合、図２に示されるように、並列ユニオン制御装置は、５１２個のソート済み集合（入力集合）から２５６組のペアを作り、ベクトル計算機Ａ１００に、２５６回のユニオン処理を並列に実行させる。ベクトルレジスタＡ１２０の各要素（２５６個ある）が、それぞれのソート済み集合（入力集合）のデータを管理する。
【００５１】
次に、並列ユニオン制御装置を用いてベクトル計算機Ａ１００で実行される、ソート済み集合（入力集合）のペアに対するユニオン処理について説明する。
【００５２】
並列ユニオン制御装置は、まず、両方の入力集合の入力要素を指すポインタを定義し、はじめに入力集合の先頭の入力要素を指すものとする。次に、並列ユニオン制御装置は、両方のポインタが指す、入力集合の２つの入力要素をベクトル演算器Ａ１１０の各演算器で比較させる。比較の結果、２つの入力要素が等しくないとき、並列ユニオン制御装置は、各演算器に小さい方の入力要素を出力要素として選択させ、選択された出力要素を出力のソート済み集合（出力集合）の末尾に追加し、小さい方の入力要素を指すポインタをインクリメントする。比較の結果、２つの入力要素が等しいとき、並列ユニオン制御装置は、その入力要素を選択された出力要素として出力集合の末尾に追加し、両方の入力要素を指すポインタをインクリメントする。並列ユニオン制御装置は、この比較の処理を各演算器に両方のポインタが入力集合の末尾の入力要素を指すまで続けさせる。
【００５３】
＜構成の説明＞
図３は、本発明の第１の実施の形態に係る並列ユニオン制御装置１００の構成を示すブロック図である。並列ユニオン制御装置１００は、要素比較制御部１０１と、レジスタ入出力部１０２と、終了判定部１０３と、を備える。
【００５４】
要素比較制御部１０１は、ベクトル演算器Ａ１１０の各演算器に、ユニオン処理の対象となる（すなわち、ユニオン処理すべき）一対のソート済み集合（入力集合）の２つの入力要素を比較させる。比較の結果、要素比較制御部１０１は、演算器に小さい方の入力要素を出力要素として選択させて、選択させた出力要素を出力のソート済み集合（出力集合）の末尾に追加させる。また、要素比較制御部１０１は、小さい方の入力要素を指すポインタをインクリメントして、そのポインタが入力集合の次の順番の入力要素を指すようにする。比較の結果、２つの入力要素が等しいとき、要素比較制御部１０１は、演算器にその入力要素を出力要素として選択させて、選択された出力要素を出力集合の末尾に追加させ、両方のポインタをインクリメントする。
【００５５】
図４は、要素比較制御部１０１が制御するベクトル演算器Ａ１１０の演算器Ａ１１００と、この演算器Ａ１１００に入出力する入力集合および出力集合を格納するベクトルレジスタＡ１２０との接続関係を示す図である。
【００５６】
演算器Ａ１１００は、比較器Ａ１１０２と選択器Ａ１１０４とから成る。比較器Ａ１１０２の一対の入力端子には、ベクトルレジスタＡ１２０の第１及び第２の入力オペランドレジスタＡ１２１およびＡ１２２が接続される。選択器Ａ１１０４の出力端子には、ベクトルレジスタＡ１２０の出力オペランドレジスタＡ１２４が接続される。比較器Ａ１１０２の比較の結果は、要素比較制御部１０１に供給される。
【００５７】
第１の入力オペランドレジスタＡ１２１は、一方の入力集合である第１の入力集合の入力要素を格納する。第２の入力オペランドレジスタＡ１２２は、他方の入力集合である第２の入力集合の入力要素を格納する。出力オペランドレジスタＡ１２４は、出力集合の出力要素を格納する。出力オペランドレジスタＡ１２４は、ＦＩＦＯ（first-in first-out）バッファから成る。
【００５８】
図５は、要素比較制御部１０１の構成の一例を示す図である。要素比較制御部１０１は、第１のポインタレジスタ１０１１と、第２のポインタレジスタ１０１２と、ポインタ制御部１０１４とを含む。
【００５９】
第１のポインタレジスタ１０１１は、第１の入力オペランドレジスタＡ１２１に格納されている第１の入力集合の入力要素を指す第１のポインタを格納する。第２のポインタレジスタ１０１２は、第２の入力オペランドレジスタＡ１２２に格納されている第２の入力集合の入力要素を指す第２のポインタを格納する。ポインタ制御部１０１４は、上記比較の結果に応答して、第１および第２のポインタレジスタ１０１１および１０１２を制御する。
【００６０】
換言すれば、要素比較制御部１０１は、演算器Ａ１１００を、比較器Ａ１１０２と選択器Ａ１１０４との組み合わせとして動作させるように制御する。
【００６１】
図３に戻って、レジスタ入出力部１０２は、要素比較制御部１０１の制御下で演算器Ａ１１００が比較する２つの入力要素から成る第１および第２の入力集合を、それぞれ、ベクトル計算機Ａ１００（図１）に接続されたメモリＢ１００からベクトルレジスタＡ１２０の第１及び第２の入力オペランドレジスタＡ１２１およびＡ１２２上にロードする。また、要素比較制御部１０１の制御下での演算器Ａ１１００での比較の処理が終了後に、レジスタ入出力部１０２は、ベクトルレジスタＡ１２０の出力オペランドレジスタＡ１２４に格納されている出力要素をベクトル計算機Ａ１００に接続されたメモリＢ１００にストアする。
【００６２】
終了判定部１０３は、ベクトル長分の並列に実行するユニオン処理を終了させるか否かを判定する。終了判定部１０３は、ソート済み集合（入力集合）のペアに対するユニオン処理が終了したかどうかを表す終了フラグを管理する。詳述すると、終了フラグは、ベクトル計算機Ａ１００のマスクレジスタＡ１３０上に保持される。ペアになったソート済み集合（入力集合）の入力要素を指すポインタ両方が、それぞれの入力集合の末尾を指すと判定されたとき、終了判定部１０３は、対応する終了フラグを１にする。
【００６３】
終了フラグが１であるとき、対応するソート済み集合（入力集合）のペアに対するユニオン処理は終了していることになるので、並列ユニオン制御装置１００は、ベクトル計算機Ａ１００にユニオン処理を実行させない。終了判定部１０３が、すべてのソート済み集合（入力集合）のペアに対する終了フラグが１であると判定したとき、並列ユニオン制御装置１００は、処理全体を終了する。
【００６４】
＜動作の説明＞
図６は、並列ユニオン制御装置１００の処理全体の動作を説明するためのフローチャートである。
【００６５】
処理の開始段階で、ベクトル長分Ｎの終了フラグが確保され、終了フラグの値はすべて０である。また、入力となるベクトル長分の終了フラグはマスクレジスタＡ１３０で保持される。ここでは、ユニオン処理を行うペアの入力集合の一方を「左集合」と呼び、他方を「右集合」と呼ぶ。また、左集合の入力要素を指すポインタを「左ポインタ」と呼び、右集合の入力要素を指すポインタを「右ポインタ」と呼ぶ。
【００６６】
尚、前述から明らかなように、左集合は第１の入力集合とも呼ばれ、右集合は第２の入力集合とも呼ばれる。また、左ポインタは第１のポインタとも呼ばれ、右ポインタは第２のポインタとも呼ばれる。
【００６７】
はじめに、左ポインタおよび右ポインタは、それぞれ、左集合および右集合の最初の入力要素を指すようになっている。ベクトル長分の左ポインタおよび右ポインタが格納されるレジスタを、それぞれ、「左ポインタレジスタ」および「右ポインタレジスタ」と呼ぶ。また、左集合および右集合の入力要素が格納されるベクトルレジスタを、それぞれ、「左要素レジスタ」および「右要素レジスタ」と呼ぶ。
【００６８】
尚、前述から明らかなように、左ポインタレジスタは第１のポインタレジスタ１０１１とも呼ばれ、右ポインタレジスタは第２のポインタレジスタ１０１２とも呼ばれる。また、左要素レジスタは、第１の入力オペランドレジスタＡ１２１とも呼ばれ、右要素レジスタは、第２の入力オペランドレジスタＡ１２２とも呼ばれる。
【００６９】
ステップＳ１１０１では、ベクトル長分のソート済み集合（入力集合）に係るループ（ループ番号iがそれぞれの左集合および右集合のペアに対応）のはじまりを表す。このループの中の処理はベクトル演算器Ａ１１０（図１）を用いて並列に実行され得る。
【００７０】
ステップＳ１１０２で、終了判定部１０３は、i番目のペアに対応する終了フラグが１かどうかを判定する。ステップＳ１１０２でＮｏのとき、並列ユニオン制御装置１００は次のステップＳ１１０３の比較処理制御にすすむ。ステップＳ１１０２でＹｅｓのとき、並列ユニオン制御装置１００はステップＳ１１０３，Ｓ１１０４の処理を実行しない。これは終了フラグをマスクレジスタＡ１３０に置き、ベクトル演算器Ａ１１０で判定することによって並列に実行され得る。
【００７１】
ステップＳ１１０３で、要素比較制御部１０１がベクトル演算器Ａ１１０の演算器Ａ１１００に比較処理を行うように制御する。
【００７２】
図７は、要素比較制御部１０１での比較処理制御の詳細を示すフローチャートである。
【００７３】
先ず、レジスタ入出力部１０２は、左ポインタpLおよび右ポインタpRが指す入力要素xLおよびxRを含む左集合および右集合を、メモリＢ１００から、それぞれ、左要素レジスタＡ１２１および右要素レジスタＡ１２２のi番目（図２参照）に格納する（ステップＳ１２０１）。
【００７４】
次に、ステップＳ１２０２で、要素比較制御部１０１は、「pRが右集合の末尾を指すまたはxL< xR」という条件の判定を行う。ステップＳ１２０２でＹｅｓのとき、要素比較制御部１０１は、演算器Ａ１１００に、左ポインタ１０１１が指す入力要素xLを出力要素として選択させる。さらに、要素比較制御部１０１は、演算器Ａ１１００に、出力要素として選択した入力要素xLを、出力のソート済み集合（出力集合）を格納する出力オペランドレジスタＡ１２４の末尾に追加させる。そして、要素比較制御部１０１は、左ポインタレジスタ１０１１の左ポインタpLをインクリメントする（ステップＳ１２０３）。
【００７５】
ステップＳ１２０２でＮｏのとき、要素比較制御部１０１は、「pLが左集合の末尾を指すまたはxR < xL」という条件の判定を行う（ステップＳ１２０４）。ステップＳ１２０４でＹｅｓのとき、要素比較制御部１０１は、演算器Ａ１１００に、右ポインタが指す入力要素xRを出力要素として選択させる。さらに、要素比較制御部１０１は、演算器Ａ１１００に、出力要素として選択した入力要素xRを、出力集合を格納する出力オペランドレジスタＡ１２４の末尾に追加させる。そして、要素比較制御部１０１は、右ポインタレジスタ１０１２の右ポインタpRをインクリメントする（ステップＳ１２０５）。
【００７６】
ステップＳ１２０４でＮｏのとき、xL=xRということになる。その場合、要素比較制御部１０１は、演算器Ａ１１００に、この入力要素を出力要素として選択させる。さらに、要素比較制御部１０１は、演算器Ａ１１００に、出力要素として選択した入力要素を、出力集合を格納する出力オペランドレジスタＡ１２４の末尾に追加させる。そして、要素比較制御部１０１は、左ポインタレジスタ１０１１の左ポインタpLと、右ポインタレジスタ１０１２の右ポインタpRと、をインクリメントする（ステップＳ１２０６）。以上で、比較処理制御Ｓ１１０３は終了である。
【００７７】
図６に戻って、次にステップＳ１１０４で、終了判定部１０３が終了判定を行う。
【００７８】
図８は、終了判定部１０３での終了判定の詳細を示すフローチャートである。
【００７９】
先ず、終了判定部１０３は、「pLが左集合の末尾を指すＡＮＤ pRが右集合の末尾を指す」との条件判定を行う（ステップＳ１３０１）。ステップＳ１３０１でＹｅｓのとき、終了判定部１０３は、i番目の終了フラグに１を代入し処理を終了する。一方、ステップＳ１３０１でＮｏのとき、終了判定部１０３は何もせずに、処理を終了する。以上が、ステップＳ１１０４の終了判定である。
【００８０】
図６に戻って、ステップＳ１１０５において、ループの処理が終了する。
【００８１】
次に、ステップＳ１１０６で、終了判定部１０３がすべての終了フラグが１であるかどうかを判定する。ステップＳ１１０６でＹｅｓであるとき、並列ユニオン制御装置１００は全体の処理を終了する。ステップＳ１１０６でＮｏであるとき、並列ユニオン制御装置１００はステップＳ１１０１のループの処理に戻る。
【００８２】
以上、図３を用いて並列ユニオン制御装置１００の処理全体の動作について説明した。以上の説明では、ユニオン処理の入力となるソート済み集合（入力集合）のペアがベクトル計算機Ａ１００のベクトル長Ｎだけあると想定したが、本発明の実施の形態では、ペアの数はそれ以下でも構わない。この場合、処理を行わない終了フラグをはじめから１に設定しておけば良い。
【００８３】
また、第１の実施の形態では、今回の並列ユニオン処理を一回行い、入力のソート済み集合（入力集合）の数２Ｎが、出力集合の数Ｎとして半分になった（図２のStep 1参照）。この並列ユニオン処理を繰り返すことによって、最終的に単一のソート済み集合から成る出力集合を出力として得ることができる（図２のStep 2および「繰り返し」参照）。詳しくは次の実施の形態で説明する。
【００８４】
＜効果の説明＞
次に、第１の実施の形態の効果について説明する。
【００８５】
第１の実施の形態によれば、ソート済み集合（入力集合）のユニオン処理を、ベクトル計算機（並列計算機）Ａ１００のベクトル演算器（コア）Ａ１１０を用いて高速に実行させることができる。
【００８６】
＜第２の実施の形態＞
次に、本発明の第２の実施の形態に係る複数ユニオン制御装置について説明する。
【００８７】
＜構成の説明＞
図９は、本発明の第２の実施の形態に係る複数ユニオン制御装置１０００の構成を示すブロック図である。
【００８８】
複数ユニオン制御装置１０００は、先に示した並列ユニオン制御装置１００を含む。複数ユニオン制御装置１０００は、並列ユニオン制御装置１００に加えて、プロセス完了判定部１０１０と、集合ペア作成部１０２０と、を更に備える。
【００８９】
次に、複数ユニオン制御装置１０００の働きを簡単に説明する。
【００９０】
複数ユニオン制御装置１０００は、並列ユニオン制御装置１００を繰り返し使用して、複数のソート済み集合を入力集合としてとり、そのユニオン処理の結果として、ただ１つのソート済み集合を出力集合として出力する。
【００９１】
プロセス完了判定部１０１０は、並列ユニオン制御装置１００での並列ユニオン処理の制御が繰り返されるなかで、残るソート済み集合（入力集合）の数が１つかどうかを判定し、複数ユニオン制御装置１０００の処理終了を決定する。
【００９２】
集合ペア作成部１０２０は、複数のソート済み集合から並列ユニオン制御装置１００の制御下で、ベクトルレジスタＡ１２０の第１および第２の入力オペランドレジスタＡ１２１およびＡ１２２の入力となるソート済み集合（入力集合）のペア（複数）を作成する。
【００９３】
＜動作の説明＞
図１０は、複数ユニオン制御装置１０００の処理全体の動作を説明するためのフローチャートである。
【００９４】
まず、Ｓを複数ユニオン制御装置１０００の対象となるすべてのソート済み集合とする（ステップＳ１４０１）。ここでは、すべてのソート済み集合Ｓの数は、２Ｎに等しいとする。
【００９５】
集合ペア作成部１０２０は、次のステップで並列ユニオン制御装置１００の制御下で、第１および第２の入力オペランドレジスタＡ１２１およびＡ１２２の入力とするソート済み集合（入力集合）のペアを、すべてのソート済み集合Ｓから作成する（ステップＳ１４０２）。入力集合のペアの数は、ベクトル長か、すべてのソート済み集合Ｓの属する集合の数２Ｎの半分Ｎのいずれか小さい方とする。
【００９６】
ここで、集合ペアの作成方法にはいくつか考えられる。まず一つの作成方法は、すべてのソート済み集合Ｓからランダムに入力集合のペアを作成する方法である。もう一つの作成方法は、作成するペアの数だけ、入力集合の入力要素の数が小さい方から、すべてのソート済み集合Ｓからソート済み集合（入力集合）を選び、ランダムに入力集合のペアを作成する方法である。
【００９７】
引き続いて、作成した入力集合のペアに対して、並列ユニオン制御装置１００によりユニオン処理を施す（ステップＳ１４０３）。この動作は上述した第１の実施の形態で説明した通りである。ユニオン処理のあと、複数ユニオン制御装置１０００は、入力集合をすべてのソート済み集合Ｓから削除して、出力されたソート済み集合（出力集合）をすべてのソート済み集合Ｓに追加する。
【００９８】
次に、プロセス完了判定部１０１０は、すべてのソート済み集合Ｓに含まれる集合が１つかどうかを判定する（ステップＳ１４０４）。ステップＳ１４０４でＹｅｓのとき、複数ユニオン制御装置１０００の動作は終了する。ステップＳ１４０４でＮｏのとき、複数ユニオン制御装置１０００は、ステップＳ１４０２に戻り処理を実行する。
【００９９】
＜効果の説明＞
次に、第２の実施の形態の効果について説明する。
【０１００】
第２の実施の形態によれば、ソート済み集合（入力集合）のユニオン処理を、ベクトル計算機（並列計算機）Ａ１００のベクトル演算器（コア）Ａ１１０を用いて高速に実行させることができる。
【０１０１】
＜第３の実施の形態＞
次に、本発明の第３の実施の形態に係る並列ユニオン制御装置について説明する。
【０１０２】
この並列ユニオン制御装置は、一つのソート済み集合（入力集合）のペアを、ベクトル計算機Ａ１００を用いて並列にユニオン処理を行わせ、一つのソート済み集合を出力集合として出力させる。具体的には、並列ユニオン制御装置は、ペアに属するソート済み集合（入力集合）をベクトル長分だけ分割し、ベクトル演算器Ａ１１０の演算単位（演算器Ａ１１００）がそれぞれの部分集合に対してユニオン処理を行う。最後に、並列ユニオン制御装置は、独立にユニオン処理したソート済み集合を結合して、出力集合として出力する。
【０１０３】
＜構成の説明＞
図１１は、本発明の第３の実施の形態に係る並列ユニオン制御装置２００を示したブロック図である。第３の実施の形態の並列ユニオン制御装置２００は、要素比較制御部２０１と、レジスタ入出力部２０２と、終了判定部２０３と、集合分割結合部２０４と、を備える。
【０１０４】
要素比較制御部２０１、レジスタ入出力部２０２、および終了判定部２０３は、それぞれ、上述した第１の実施形態の並列ユニオン制御装置１００の要素比較制御部１０１、レジスタ入出力部１０２、および終了判定部１０３と同じであるので、それらの説明を省略する。
【０１０５】
集合分割結合部２０４は、入力となるソート済み集合（入力集合）のペアを所定の数だけ入力部分集合として分割する。ここで、ソート済み集合（入力集合）のペアを分割するとは、ペアの左集合と右集合について所定の数だけ分割することを指す。また、ソート済み集合（入力集合）を分割するとは、分割前のソート済み集合（入力集合）において「所定の数−１」だけ境界を定めて、その境界の前後でソート済み集合（入力集合）を入力部分集合として分割することを指す。
【０１０６】
以下に、具体例を示す。ソート済み集合として入力集合A: [1,3,5,8,9,10,11] を３つの入力部分集合に分割する例を示す。この例では、一つめの境界を５と８の間、二つめの境界を９と１０の間にとることにする。このとき分割後のソート済み集合は、それぞれ、第１乃至第３の入力部分集合A1, A2,およびA3として、
A1:[1,3,5],     A2: [8,9],      A3:[10,11]
となる。これは一例であり他の分割もありうる。
【０１０７】
集合分割結合部２０４は、ソート済み集合（入力集合）のペアを分割するときに、左集合のj番目の分割と右集合のj番目の分割が取りうる値の範囲をRj とすると、すべてのjについてRjが重なりあっていてはいけない、という条件を満たす。これはソート済み集合（入力集合）を分割後に並列にユニオン処理を行った結果である複数の出力部分集合を結合するときに、単に複数の出力部分集合を連結すれば十分であるようにするためである。
【０１０８】
次に、具体例を見る。ソート済み集合（入力集合）のペア(A,B)である左集合および右集合をA:[ 1,3,5,8,9,10,11 ], B:[4,5,6,7,8,9,13]とする。このとき分割後のソート済み集合は、それぞれ、第１乃至第３の左部分集合A1, A2,およびA3および第１乃至第３の右部分集合B1, B2,およびB3として、
A1:[1,3,5],     A2: [8,9],      A3:[10,11]
B1:[4,5,6,7],   B2: [8,9],      B3:[13]
となる。分割後のソート済み集合AjとBjの入力要素の取りうる範囲が、他のjの範囲と重なり合っていない。これの分割は一例であり他の分割もありうる。ただし分割後のソート済み集合AjとBjの入力要素の数の和が、jにかけて等しくなるようにするのが望ましい。その理由は、並列ユニオン処理の負荷が均等になるからである。
【０１０９】
集合分割結合部２０４は、分割後ユニオン処理を行った結果である出力部分集合を所定の数だけ結合する。出力部分集合の結合は、分割がそれぞれのソート済み集合（入力集合）の入力要素の範囲が重なりあわないように行われているので、範囲が小さい方から単に連結すれは良い。
【０１１０】
次に、具体例をみる。ユニオン処理後のソート済み集合（出力部分集合）が、それぞれ、第１乃至第３の出力部分集合C1, C2,およびC3として、
C1:[1,3,4,5,6,7],              C2: [8,9]       C3: [10,11,13]
であるとする。このとき、結合後のソート済み集合である出力集合Cは、
C:[1,3,4,5,6,7,8,9,10,11,13]
となる。結合後のソート済み集合である出力集合Cは、ペアである分割前の左集合Aと分割前の右集合Bとをユニオン処理した結果になっている。
【０１１１】
＜動作の説明＞
図１２は、並列ユニオン制御装置２００の動作を説明するためのフローチャートである。ステップＳ２１０１とＳ２０１８を除き、図６に示した第１の実施の形態のフローチャートと同じであるので、それらの説明は省略する。
【０１１２】
ステップＳ２１０１で、集合分割結合部２０４は、ソート済み集合（入力集合）のペアを所定の数だけ入力部分集合に分割する。所定の数とはベクトル長を超えない数である。
【０１１３】
ステップＳ２１０８で、集合分割結合部２０４は、ユニオン処理したソート済み集合（出力部分集合）を結合し、ひとつのソート済み集合（出力集合）とする。
【０１１４】
＜効果の説明＞
次に、第３の実施の形態の効果について説明する。
【０１１５】
第３の実施の形態によれば、ソート済み集合（入力集合）のユニオン処理を、ベクトル計算機（並列計算機）Ａ１００のベクトル演算器（コア）Ａ１１０を用いて高速に実行させることができる。
【０１１６】
＜第４の実施の形態＞
次に、本発明の第４の実施の形態に係る複数ユニオン制御装置について説明する。
【０１１７】
複数ユニオン制御装置は、上述した第３の実施の形態の並列ユニオン制御装置２００を繰り返し使用することで、ベクトル計算機Ａ１００に、複数のソート済み集合（入力集合）に対してユニオン処理を行わせ、ひとつのソート済み集合を出力集合として出力させる。複数ユニオン制御装置は、繰り返しごとに、ソート済み集合（入力集合）のペアを生成し、ベクトル計算機Ａ１００に並列ユニオン処理を行わせる。複数ユニオン制御装置は、ソート済み集合がひとつになるまで、ペアの生成と、ベクトル計算機Ａ１００による並列ユニオン処理と、を繰り返す。
【０１１８】
＜構成の説明＞
図１３は、本発明の第４の実施の形態に係る複数ユニオン制御装置２０００の構成を示すブロック図である。
【０１１９】
複数ユニオン制御装置２０００は、並列ユニオン制御装置２００と、プロセス完了判定部２０１０と、集合ペア作成部２０２０と、を備える。
【０１２０】
並列ユニオン制御装置２００は、図１１に示す第３の実施の形態で説明したものと同じであるので、その説明を省略する。
【０１２１】
プロセス完了判定部２０１０は、ユニオン処理の対象となるソート済み集合が１つであるかどうかを判定し、１つであれば全体の処理を終了する。
【０１２２】
集合ペア作成部２０２０は、ユニオン処理の対象となるソート済み集合から、入力集合を２つ選びペアを作成する。
【０１２３】
＜動作の説明＞
図１４は、複数ユニオン制御装置２０００の処理全体の動作を説明するためのフローチャートである。
【０１２４】
図１４のフローチャートは基本的には、図１０と同じであるので、異なる部分のみを以下で言及する。
【０１２５】
ステップＳ２２０２で、集合ペア作成部２０２０は、すべてのソート済み集合Ｓから入力集合のペアをひとつだけ作成する。Ｓはユニオン処理の対象となるソート済み集合の集合である。
【０１２６】
ステップＳ２２０３では、１つの入力集合のペアに対して並列ユニオン制御装置２００を用いてベクトル計算機Ａ１００にユニオン処理を行わせる。
【０１２７】
＜効果の説明＞
次に、第４の実施の形態の効果について説明する。
【０１２８】
第４の実施の形態によれば、ソート済み集合（入力集合）のユニオン処理を、ベクトル計算機（並列計算機）Ａ１００のベクトル演算器（コア）Ａ１１０を用いて高速に実行させることができる。
【０１２９】
＜第５の実施の形態＞
次に、本発明の第５の実施の形態に係る複数ユニオン制御装置について説明する。この複数ユニオン制御装置は、第１の並列ユニオン制御装置１００と第２の並列ユニオン制御装置２００とを備え、並列ユニオン処理の繰り返しの途中で、第１の並列ユニオン制御装置１００による処理から第２の並列ユニオン制御装置２００の処理へ切り替える。
【０１３０】
＜構成の説明＞
図１５は、本発明の第５の実施の形態に係る複数ユニオン制御装置３０００の構成を示すブロック図である。
【０１３１】
複数ユニオン制御装置３０００は、複数のソート済み集合を入力集合として入力として、ベクトル計算機Ａ１００にそれらをユニオン処理させて得られた、ひとつのソート済み集合を出力集合として出力する。
【０１３２】
図１５に示されるように、複数ユニオン制御装置３０００は、第１の並列ユニオン制御装置１００と、第２の並列ユニオン制御装置２００と、プロセス完了判定部３０１０と、集合ペア作成部３０２０と、ユニオン制御装置切替部３１００と、を備える。
【０１３３】
ユニオン制御装置切替部３１００は、所定の条件に基づき、第１の並列ユニオン制御装置１００によるユニオン処理から第２の並列ユニオン制御装置２００によるユニオン処理に切り替える。ここで、所定の条件とは、例えば、対象となるソート済み集合の数がしきい値を超えているか否か、である。所定の条件はこれには限定されない。
【０１３４】
＜動作の説明＞
図１６は、複数ユニオン制御装置３０００の動作を説明するためのフローチャートである。
【０１３５】
ステップＳ３１０１で、Ｓをユニオン処理の対象となるすべてのソート済み集合とする。
【０１３６】
ステップＳ３１０２で、集合ペア作成部３０２０が、ベクトル長もしくは所定の数だけすべてのソート済み集合Ｓからソート済み集合（入力集合）のペアを作成する。
【０１３７】
ステップＳ３１０３で、第１の並列ユニオン制御装置１００を用いて、ベクトル計算機Ａ１００に先ほど作成したソート済み集合のペアに対して並列にユニオン処理を行わせる。ユニオン処理の入力集合をすべてのソート済み集合Ｓから削除して、出力集合をすべてのソート済み集合Ｓに追加する。
【０１３８】
ステップＳ３１０４において、ユニオン制御装置切替部３１００が、所定の条件を元にユニオン制御装置を切り替えるかどうかを判定する。ここで、所定の条件とは、Ｓに含まれる集合の数が所定のしきい値よりも小さいかどうか、等である。ステップＳ３１０４でＹｅｓのとき、処理はステップＳ３１０５に進む。ステップＳ３１０４でＮｏのとき、処理はステップＳ３１０２に戻る。
【０１３９】
ステップＳ３１０５では、すべてのソート済み集合Ｓからソート済み集合のペアをひとつ作成する。
【０１４０】
ステップＳ３１０６では、第２の並列ユニオン制御装置２００を用いて、ベクトル計算機Ａ１００に先ほど作成したペアに対して並列にユニオン処理を行わせる。また、ユニオン処理の入力集合をすべてのソート済み集合Ｓから削除し、出力集合をすべてのソート済み集合Ｓに追加する。
【０１４１】
ステップＳ３１０７において、プロセス完了判定部３０１０が、すべてのソート済み集合Ｓに属するソート済み集合の数が１であるかどうかを判定する。ステップＳ３１０７でＹｅｓのとき、複数ユニオン制御装置３０００は、全体の処理を終了する。ステップＳ３１０７でＮｏのとき、処理はステップＳ３１０５に戻る。
【０１４２】
＜効果の説明＞
次に、第５の実施の形態の効果について説明する。
【０１４３】
はじめ、ソート済み集合の数が（ベクトル長に比べて）多い。このため、第１の並列ユニオン制御装置１００を用いることによって、ベクトル演算器Ａ１１０を有効に活用できる。また、並列ユニオン処理が繰り返されると、ソート済み集合の数が少なるが、ひとつのソート済み集合の要素の数が（ベクトル長に比べて）多くなる。そのため、このとき第２の並列ユニオン装置２００を用いることによって、ベクトル演算器Ａ１１０を有効に活用することができる。したがって全体のユニオン処理において、ベクトル演算器Ａ１１０を有効に活用することができる。
【０１４４】
＜第６の実施の形態＞
次に、本発明の第６の実施の形態に係る並列ユニオン制御装置について説明する。
【０１４５】
この並列ユニオン制御装置は、複数のソート済み集合のペアに対して、ペアごとに適切な分割数を決定し、決定した分割数に基づき集合のペアを分割して、複数の分割された集合のペアに対してベクトル計算機Ａ１００に並列にユニオン処理を行わせる。
【０１４６】
入力となるソート済み集合のペアの数はベクトル長とは限らないが、分割されたあとの集合のペアの数（すなわち、すべての集合のペアに対する分割数の和）がベクトル長に等しいとベクトル演算器Ａ１１０を効率よく利用できる。
【０１４７】
＜構成の説明＞
図１７は、本発明の第６の実施の形態に係る並列ユニオン制御装置４００の構成を示すブロック図である。
【０１４８】
並列ユニオン制御装置４００は、要素比較制御部４０１と、レジスタ入出力部４０２と、終了判定部４０３、集合分割結合部４０４と、分割数決定部４０５と、を備える。
【０１４９】
集合分割結合部４０４と分割数決定部４０５とが、図３に示した第１の実施の形態のものと異なるので、以下では、集合分割結合部４０４と分割数決定部４０５とについて説明する。
【０１５０】
分割数決定部４０５は、ユニオン処理の対象となるソート済み集合のペアそれぞれに対して、分割数を決定する。分割数を決定する方法には、分割数をそれぞれのペアに属する両者の集合の要素数の和に比例させ、かつ、すべてのペアに対する分割数の和がベクトル長に等しくなる、ようにする方法がある。
【０１５１】
集合分割結合部４０４は、分割数決定部４０５が決定した分割数に基づいて、ソート済み集合（入力集合）のペアを複数の入力部分集合に分割する。ユニオン処理を行ったのち、集合分割結合部４０４は、分割前に同じソート済み集合のペアに属していた複数の出力部分集合を結合して、１つの出力集合を得る。
【０１５２】
並列ユニオン制御装置の動作を、具体例で見る。３つの集合の第１乃至第３のペア（XA, YA）, （XB, YB）, （XC, YD）が入力集合であるとする。それぞれのペアの要素数の和は、第１のペア（XA, YA）が１０００、第２のペア（XB, YB）が２０００、 第３のペア（XC, YC）が５０００であるとする。このとき、それぞれのペアの分割数を要素数の和に比例させ、かつ分割数の和がベクトル長（ここでは８とする）に等しくなるようにする。
【０１５３】
この場合、それぞれの分割数は、第１のペア（XA, YA）が１、第２のペア（XB, YB）が２、 第３のペア（XC, YC）が５、となる。第１のペア（XA, YA）は分割数１なので分割しない。第２のペア（XB, YB）は、（XB1, YB1）、（XB2, YB2）と２つに分割される。第３のペア（XC, YC）は（XC1, YC1）、…、（XC5, YC5）と５つに分割される。それぞれの分割ごとに並列にユニオン処理した結果を（XA, YA）->ZA、（XB1, YB1）->ZB1、…、（XC1, YC1）->ZC1、…とする。ユニオン処理した出力部分集合で、分割前に同じソート済み集合に属するものを結合する。これはつまり、ZB1とZB2とを結合してZBとすると共に、ZC1、…、ZC5を結合してZCとする。したがって、並列ユニオン制御装置４００は、入力集合として（XA, YA）, （XB, YB）, （XC, YC）を取り、ユニオン処理した結果としてZA, ZB, ZC を出力集合として出力する。
【０１５４】
＜動作の説明＞
図１８は、並列ユニオン制御装置４００の動作を説明するためのフローチャートである。
【０１５５】
ステップＳ４１０１で、分割数決定部４０５が、入力となるソート済み集合のペアそれぞれに対して、分割数を決定する。
【０１５６】
ステップＳ４１０２で、集合分割結合部４０４が、分割数決定部４０５が決定した分割数に基づき、ソート済み集合のペアを分割する。
【０１５７】
ステップＳ４１０３からステップＳ４１０８のループは、それぞれ、図６に示した第１の実施の形態のステップＳ１１０１からステップＳ１１０６と同じであるので、それらの説明を省略する。
【０１５８】
ステップＳ４１０９では、集合分割結合部４０４が、ユニオン処理したソート済み集合のなかで、分割前に同じソート済み集合に属していたものを結合する。
【０１５９】
＜効果の説明＞
次に、第６の実施の形態の効果について説明する。
【０１６０】
第６の実施の形態によれば、ソート済み集合（入力集合）のユニオン処理を、ベクトル計算機（並列計算機）Ａ１００のベクトル演算器（コア）Ａ１１０を用いて高速に実行させることができる。
【０１６１】
＜第７の実施の形態＞
次に、本発明の第７の実施の形態に係る複数ユニオン制御装置について説明する。
【０１６２】
複数ユニオン制御装置の働きを簡単に説明する。複数ユニオン制御装置は、並列ユニオン制御装置４００を繰り返し使用して、複数のソート済み集合を入力としてとり、そのユニオン処理の結果として、ただ１つのソート済み集合を出力する。
【０１６３】
＜構成の説明＞
図１９は、本発明の第７の実施の形態に係る複数ユニオン制御装置４０００の構成を示すブロック図である。
【０１６４】
複数ユニオン制御装置４０００は、並列ユニオン制御装置４００と、プロセス完了判定部４０１０と、集合ペア作成部４０２０と、を備える。
【０１６５】
プロセス完了判定部４０１０は、対象のソート済み集合の数が１つかどうかを判定して、１つであった場合は全体の処理を終了し、そうでない場合はユニオン処理を繰り返す。
【０１６６】
集合ペア作成部４０２０は、対象の複数のソート済み集合から所定の数だけソート済み集合のペアを作成し、並列ユニオン制御装置４００の入力とする。
【０１６７】
＜動作の説明＞
図２０は、複数ユニオン制御装置４０００の動作を説明するためのフローチャートである。
【０１６８】
図２０のフローチャートは基本的には、図１０と同じであるので、以下では異なる部分のみを言及する。
【０１６９】
ステップＳ４２０２で、集合ペア作成部４０２０は、すべてのソート済み集合Ｓから集合のペアを所定の数だけ作成する。Ｓはユニオン処理の対象となるソート済み集合の集合である。
【０１７０】
ステップＳ４２０３では、所定の数の集合のペアに対して並列ユニオン制御装置４００を用いてユニオン処理を行う。また、入力となったソート済み集合（入力集合）をすべてのソート済み集合Ｓから削除し、出力であるソート済み集合（出力集合）をすべてのソート済み集合Ｓへと追加する。
【０１７１】
＜効果の説明＞
次に、第７の実施の形態の効果について説明する。
【０１７２】
第７の実施の形態によれば、ソート済み集合（入力集合）のユニオン処理を、ベクトル計算機（並列計算機）Ａ１００のベクトル演算器（コア）Ａ１１０を用いて高速に実行させることができる。
【０１７３】
尚、上記第１、第３、および第６の実施の形態において、並列ユニオン制御装置１００、２００、および４００の各部は、ハードウェアとソフトウェアとの組み合わせを用いて実現可能である。ハードウェアとソフトウェアとを組み合わせた形態では、ＲＡＭ（random access memory）に並列ユニオン制御用プログラムが展開され、該並列ユニオン制御用プログラムに基づいてＣＰＵ（central processing unit）などの情報処理装置（コンピュータ）のハードウェアを動作させることによって、各部を各種手段として実現する。また、該並列ユニオン制御用プログラムは、記憶媒体に記録されて頒布されても良い。当該記憶媒体に記録された並列ユニオン制御用プログラムは、有線、無線、又は記憶媒体そのものを介して、メモリに読込まれ、処理部等を動作させる。尚、記憶媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。
【０１７４】
上記第１、第３、および第６の実施の形態を別の表現で説明すれば、並列ユニオン制御装置１００、２００、および４００として動作させるコンピュータを、ＲＡＭに展開された並列ユニオン制御用プログラムに基づき、要素比較制御部、レジスタ入出力部、終了判定部、集合分割結合部、および分割数決定部として動作させることで実現することが可能である。
【０１７５】
同様に、上記第２、第４、第５および第７の実施の形態において、複数ユニオン制御装置１０００、２０００、３０００、および４０００の各部は、ハードウェアとソフトウェアとの組み合わせを用いて実現可能である。ハードウェアとソフトウェアとを組み合わせた形態では、ＲＡＭ（random access memory）に複数ユニオン制御用プログラムが展開され、該複数ユニオン制御用プログラムに基づいてＣＰＵ（central processing unit）などの情報処理装置（コンピュータ）のハードウェアを動作させることによって、各部を各種手段として実現する。また、該複数ユニオン制御用プログラムは、記憶媒体に記録されて頒布されても良い。当該記憶媒体に記録された複数ユニオン制御用プログラムは、有線、無線、又は記憶媒体そのものを介して、メモリに読込まれ、処理部等を動作させる。尚、記憶媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。
【０１７６】
上記第２、第４、第５および第７の実施の形態を別の表現で説明すれば、複数ユニオン制御装置１０００、２０００、３０００、および４０００として動作させるコンピュータを、ＲＡＭに展開された複数ユニオン制御用プログラムに基づき、要素比較制御部、レジスタ入出力部、終了判定部、プロセス完了判定部、集合ペア作成部、集合分割結合部、および分割数決定部として動作させることで実現することが可能である。
【０１７７】
図２１は、本発明の第１、第３、および第６の実施の形態に係る並列ユニオン制御装置、及び、第２、第４、第５および第７の実施の形態に係る複数ユニオン制御装置として動作できるコンピュータのハードウェア構成の例を表す図である。
図２１を参照すると、コンピュータ１００００は、プロセッサ１０００１と、メモリ１０００２と、記憶装置１０００３と、Ｉ／Ｏ（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）インタフェース１０００４とを含む。また、コンピュータ１００００は、記憶媒体１０００５にアクセスすることができる。メモリ１０００２と記憶装置１０００３は、例えば、上述のＲＡＭ、ハードディスクなどの記憶装置である。記憶媒体１０００５は、例えば、ＲＡＭ、ハードディスクなどの記憶装置、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、可搬記憶媒体である。記憶装置１０００３が記憶媒体１０００５であってもよい。プロセッサ１０００１は、例えば、上述のＣＰＵである。プロセッサ１０００１は、メモリ１０００２と、記憶装置１０００３に対して、データやプログラムの読み出しと書き込みを行うことができる。プロセッサ１０００１は、Ｉ／Ｏインタフェース１０００４を介して、例えば、ベクトル計算機にアクセスすることができる。プロセッサ１０００１は、記憶媒体１０００５にアクセスすることができる。記憶媒体１０００５には、コンピュータ１００００を、上述の並列ユニオン制御装置として動作させるプログラム、又は、コンピュータ１００００を、上述の複数ユニオン制御装置として動作させるプログラムが格納されている。
【０１７８】
プロセッサ１０００１は、記憶媒体１０００５に格納されている、コンピュータ１００００を、並列ユニオン制御装置として動作させるプログラムを、メモリ１０００２にロードする。そして、プロセッサ１０００１が、メモリ１０００２にロードされたプログラムを実行することにより、コンピュータ１００００は、並列ユニオン制御装置として動作する。プロセッサ１０００１は、記憶媒体１０００５に格納されている、コンピュータ１００００を、複数ユニオン制御装置として動作させるプログラムを、メモリ１０００２にロードしてもよい。そして、プロセッサ１０００１が、メモリ１０００２にロードされたプログラムを実行することにより、コンピュータ１００００は、複数ユニオン制御装置として動作してもよい。
【０１７９】
要素比較制御部１０１、レジスタ入出力部１０２、終了判定部１０３は、例えば、記憶媒体１０００５からメモリ１０００２にロードされたプログラムを実行するプロセッサ１０００１によって実現できる。要素比較制御部２０１、レジスタ入出力部２０２、終了判定部２０３、集合分割結合部２０４は、例えば、記憶媒体１０００５からメモリ１０００２にロードされたプログラムを実行するプロセッサ１０００１によって実現できる。要素比較制御部４０１、レジスタ入出力部４０２、終了判定部４０３、集合分割結合部４０４、分割数決定部４０５は、例えば、記憶媒体１０００５からメモリ１０００２にロードされたプログラムを実行するプロセッサ１０００１によって実現できる。プロセス完了判定部１０１０、第１のポインタレジスタ１０１１、第２のポインタレジスタ１０１２、ポインタ制御部１０１４、集合ペア作成部１０２０は、例えば、記憶媒体１０００５からメモリ１０００２にロードされたプログラムを実行するプロセッサ１０００１によって実現できる。プロセス完了判定部２０１０、集合ペア作成部２０２０は、例えば、記憶媒体１０００５からメモリ１０００２にロードされたプログラムを実行するプロセッサ１０００１によって実現できる。プロセス完了判定部３０１０、集合ペア作成部３０２０は、例えば、記憶媒体１０００５からメモリ１０００２にロードされたプログラムを実行するプロセッサ１０００１によって実現できる。ユニオン制御装置切替部３１００、プロセス完了判定部４０１０、集合ペア作成部４０２０は、例えば、記憶媒体１０００５からメモリ１０００２にロードされたプログラムを実行するプロセッサ１０００１によって実現できる。
【０１８０】
要素比較制御部１０１、レジスタ入出力部１０２、終了判定部１０３の一部又は全部は、専用の回路によっても実現できる。
要素比較制御部２０１、レジスタ入出力部２０２、終了判定部２０３、集合分割結合部２０４の一部又は全部は、専用の回路によっても実現できる。要素比較制御部４０１、レジスタ入出力部４０２、終了判定部４０３、集合分割結合部４０４、分割数決定部４０５の一部又は全部は、専用の回路によっても実現できる。プロセス完了判定部１０１０、第１のポインタレジスタ１０１１、第２のポインタレジスタ１０１２、ポインタ制御部１０１４、集合ペア作成部１０２０の一部又は全部は、専用の回路によっても実現できる。プロセス完了判定部２０１０、集合ペア作成部２０２０の一部又は全部は、専用の回路によっても実現できる。プロセス完了判定部３０１０、集合ペア作成部３０２０の一部又は全部は、専用の回路によっても実現できる。ユニオン制御装置切替部３１００、プロセス完了判定部４０１０、集合ペア作成部４０２０の一部又は全部は、専用の回路によっても実現できる。
【０１８１】
尚、上述したように、本実施の形態に係る並列ユニオン制御装置１００、２００、４００や複数ユニオン制御装置１０００、２０００、３０００、４０００は、ソフトウェア関連発明であるとしても、ベクトル計算機Ａ１００に高速にユニオン処理を並列に実行させることができるという効果を奏するのであるから、コンピュータ関連技術を改善（向上）するものであり、抽象概念には該当しないのは明らかである。
【０１８２】
以上、本発明の実施の形態を、図面を参照しつつ説明してきたが、当業者であれば、他の類似する実施の形態を使用することができること、また、本発明から逸脱することなく適宜形態の変更又は追加を行うことができることに留意すべきである。
【０１８３】
上記の実施の形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１８４】
（付記１）
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御装置であって、
前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御手段と、
メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力手段と、
並列で行うユニオン処理が終了したかどうかを判定する終了判定手段と、
を備える並列ユニオン制御装置。
【０１８５】
（付記２）
前記ソート済み集合は要素が昇順に並んでいる集合であり、
前記要素比較制御手段は、前記比較の結果が等しくないとき、前記演算器に小さい方の入力要素を前記出力要素として選択させて、該小さい方の入力要素を指すポインタをインクリメントし、前記比較の結果が等しいとき、前記演算器に該入力要素を前記出力要素として選択させて、両方の入力要素を指すポインタをインクリメントする、
付記１に記載の並列ユニオン制御装置。
【０１８６】
（付記３）
前記入力集合を複数の入力部分集合に分割して、前記要素比較制御手段に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合手段を更に有する、
付記１又は２に記載の並列ユニオン制御装置。
【０１８７】
（付記４）
前記複数の入力部分集合の分割数を決定する分割数決定手段を更に有し、
前記集合分割結合手段は、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
付記３に記載の並列ユニオン制御装置。
【０１８８】
（付記５）
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御装置であって、
付記１乃至４のいずれか１つに記載の並列ユニオン制御装置と、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成手段と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定手段と、
を備える複数ユニオン制御装置。
【０１８９】
（付記６）
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御装置であって、
それぞれ、付記１に記載の並列ユニオン制御装置である、第１の並列ユニオン制御装置と第２の並列ユニオン制御装置と、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成手段と、
前記第１の並列ユニオン制御装置と前記第２の並列ユニオン制御装置とを切り替えるユニオン制御装置切替手段と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定手段と、
を備え、
前記第２の並列ユニオン制御装置は、前記入力集合を複数の入力部分集合に分割して、前記要素比較制御手段に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合手段を更に有する、
複数ユニオン制御装置。
【０１９０】
（付記７）
前記第２の並列ユニオン制御装置は、前記複数の入力部分集合の分割数を決定する分割数決定手段を更に有し、
前記集合分割結合手段は、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
付記６に記載の複数ユニオン制御装置。
【０１９１】
（付記８）
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御方法であって、情報処理装置によって、
前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御を行い、
メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力を行い、
並列で行うユニオン処理が終了したかどうかを判定する終了判定を行う、
並列ユニオン制御方法。
【０１９２】
（付記９）
前記ソート済み集合は要素が昇順に並んでいる集合であり、
前記要素比較制御は、前記比較の結果が等しくないとき、前記演算器に小さい方の入力要素を前記出力要素として選択させて、該小さい方の入力要素を指すポインタをインクリメントし、前記比較の結果が等しいとき、前記演算器に該入力要素を前記出力要素として選択させて、両方の入力要素を指すポインタをインクリメントする、
付記８に記載の並列ユニオン制御方法。
【０１９３】
（付記１０）
前記情報処理装置によって、前記入力集合を複数の入力部分集合に分割して、前記要素比較制御において、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、
付記８又は９に記載の並列ユニオン制御方法。
【０１９４】
（付記１１）
前記情報処理装置によって、前記複数の入力部分集合の分割数を決定し、
前記集合を分割し結合することは、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
付記１０に記載の並列ユニオン制御方法。
【０１９５】
（付記１２）
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御方法であって、情報処理装置によって、
付記８乃至１１のいずれか１つに記載の並列ユニオン制御方法を実施し、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納し、
ユニオン処理全体が完了したかどうかを判定する、
複数ユニオン制御方法。
【０１９６】
（付記１３）
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御方法であって、情報処理装置によって、
それぞれ、付記８に記載の並列ユニオン制御方法である、第１の並列ユニオン制御方法と第２の並列ユニオン制御方法とを実施し、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納し、
前記第１の並列ユニオン制御方法と前記第２の並列ユニオン制御方法とを切り替え、
ユニオン処理全体が完了したかどうかを判定し、
前記第２の並列ユニオン制御方法は、さらに、前記入力集合を複数の入力部分集合に分割して、前記要素比較制御において、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、
複数ユニオン制御方法。
【０１９７】
（付記１４）
前記第２の並列ユニオン制御方法は、情報処理装置によって、
前記複数の入力部分集合の分割数を決定し、
決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
付記１３に記載の複数ユニオン制御方法。
【０１９８】
（付記１５）
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、コンピュータに、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御用プログラムであって、
前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御処理と、
メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力処理と、
並列で行うユニオン処理が終了したかどうかを判定する終了判定処理と、
を前記コンピュータに実行させる並列ユニオン制御用プログラムを記憶する記憶媒体。
【０１９９】
（付記１６）
前記ソート済み集合は要素が昇順に並んでいる集合であり、
前記要素比較制御処理は、前記コンピュータに、前記比較の結果が等しくないとき、前記演算器に小さい方の入力要素を前記出力要素として選択させて、該小さい方の入力要素を指すポインタをインクリメントさせ、前記比較の結果が等しいとき、前記演算器に該入力要素を前記出力要素として選択させて、両方の入力要素を指すポインタをインクリメントさせる、
付記１５に記載の記憶媒体。
【０２００】
（付記１７）
前記入力集合を複数の入力部分集合に分割して、前記要素比較制御処理に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合処理を前記コンピュータに更に実行させる、
付記１５又は１６に記載の記憶媒体。
【０２０１】
（付記１８）
前記複数の入力部分集合の分割数を決定する分割数決定処理を前記コンピュータに更に実行させ、
前記集合分割結合処理は、前記コンピュータに、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割させ、前記複数の出力部分集合を前記出力集合に結合させる、
付記１７に記載の記憶媒体。
【０２０２】
（付記１９）
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、コンピュータに、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御用プログラムであって、
付記１５乃至１８のいずれか１つに記載の記憶媒体に格納されている並列ユニオン制御用プログラムを含み、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成処理と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定処理と、
を前記コンピュータに実行させる複数ユニオン制御用プログラムを記憶する記憶媒体。
【０２０３】
（付記２０）
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、コンピュータに、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御用プログラムであって、
それぞれ、付記１５に記載の記憶媒体に格納されている並列ユニオン制御用プログラムである、第１の並列ユニオン制御用プログラムと第２の並列ユニオン制御用プログラムと、を含み、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成処理と、
前記第１の並列ユニオン制御用プログラムと前記第２の並列ユニオン制御用プログラムとを切り替えるユニオン制御用プログラム切替処理と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定処理と、
を前記コンピュータに実行させ、
前記第２の並列ユニオン制御用プログラムは、前記入力集合を複数の入力部分集合に分割して、前記要素比較制御処理に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合処理を前記コンピュータに更に実行させる、
複数ユニオン制御用プログラムを記憶する記憶媒体。
【０２０４】
（付記２１）
前記第２の並列ユニオン制御用プログラムは、前記複数の入力部分集合の分割数を決定する分割数決定部処理を前記コンピュータに更に実行させ、
前記集合分割結合処理は、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
付記２０に記載の記憶媒体。
【０２０５】
この出願は、２０１８年２月８日に出願された日本出願特願２０１８−０２０９５３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０２０６】
Ａ１００    ベクトル計算機
Ａ１１０    ベクトル演算器
Ａ１１００    演算器
Ａ１１０２    比較器
Ａ１１０４    選択器
Ａ１２０    ベクトルレジスタ
Ａ１２１    第１の入力オペランドレジスタ
Ａ１２２    第２の入力オペランドレジスタ
Ａ１２４    出力オペランドレジスタ
Ａ１３０    マスクレジスタ
Ｂ１００    メモリ（主記憶装置）
Ｃ１００    制御装置
１００    並列ユニオン制御装置
１０１    要素比較制御部
１０２    レジスタ入出力部
１０３    終了判定部
２００    並列ユニオン制御装置
２０１    要素比較制御部
２０２    レジスタ入出力部
２０３    終了判定部
２０４    集合分割結合部
４００    並列ユニオン制御装置
４０１    要素比較制御部
４０２    レジスタ入出力部
４０３    終了判定部
４０４    集合分割結合部
４０５    分割数決定部
１０００    複数ユニオン制御装置
１０１０    プロセス完了判定部
１０１１    第１のポインタレジスタ
１０１２    第２のポインタレジスタ
１０１４    ポインタ制御部
１０２０    集合ペア作成部
２０００    複数ユニオン制御装置
２０１０    プロセス完了判定部
２０２０    集合ペア作成部
３０００    複数ユニオン制御装置
３０１０    プロセス完了判定部
３０２０    集合ペア作成部
３１００    ユニオン制御装置切替部
４０００    複数ユニオン制御装置
４０１０    プロセス完了判定部
４０２０    集合ペア作成部
１００００    コンピュータ
１０００１    プロセッサ
１０００２    メモリ
１０００３    記憶装置
１０００４    Ｉ／Ｏインタフェース
１０００５    記憶媒体
【図１】
2019156060.tif 000003
【図２】
2019156060.tif 000004
【図３】
2019156060.tif 000005
【図４】
2019156060.tif 000006
【図５】
2019156060.tif 000007
【図６】
2019156060.tif 000008
【図７】
2019156060.tif 000009
【図８】
2019156060.tif 000010
【図９】
2019156060.tif 000011
【図１０】
2019156060.tif 000012
【図１１】
2019156060.tif 000013
【図１２】
2019156060.tif 000014
【図１３】
2019156060.tif 000015
【図１４】
2019156060.tif 000016
【図１５】
2019156060.tif 000017
【図１６】
2019156060.tif 000018
【図１７】
2019156060.tif 000019
【図１８】
2019156060.tif 000020
【図１９】
2019156060.tif 000021
【図２０】
2019156060.tif 000022
【図２１】
2019156060.tif 000023
【手続補正書】
【提出日】令和2年7月8日(2020.7.8)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御装置であって、
前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御手段と、
メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力手段と、
並列で行うユニオン処理が終了したかどうかを判定する終了判定手段と、
を備える並列ユニオン制御装置。
【請求項２】
前記ソート済み集合は要素が昇順に並んでいる集合であり、
前記要素比較制御手段は、前記比較の結果が等しくないとき、前記演算器に小さい方の入力要素を前記出力要素として選択させて、該小さい方の入力要素を指すポインタをインクリメントし、前記比較の結果が等しいとき、前記演算器に該入力要素を前記出力要素として選択させて、両方の入力要素を指すポインタをインクリメントする、
請求項１に記載の並列ユニオン制御装置。
【請求項３】
前記入力集合を複数の入力部分集合に分割して、前記要素比較制御手段に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合手段を更に有する、
請求項１又は２に記載の並列ユニオン制御装置。
【請求項４】
前記複数の入力部分集合の分割数を決定する分割数決定手段を更に有し、
前記集合分割結合手段は、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
請求項３に記載の並列ユニオン制御装置。
【請求項５】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御装置であって、
請求項１乃至４のいずれか１つに記載の並列ユニオン制御装置と、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成手段と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定手段と、
を備える複数ユニオン制御装置。
【請求項６】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させることを繰り返して、最終的にひとつのソート済み集合から成る出力集合を出力させる複数ユニオン制御装置であって、
それぞれ、請求項１に記載の並列ユニオン制御装置である、第１の並列ユニオン制御装置と第２の並列ユニオン制御装置と、
並列ユニオン処理の入力となる入力集合のペアを作成して、作成した入力集合のペアを前記入力オペランドレジスタに格納する集合ペア作成手段と、
前記第１の並列ユニオン制御装置と前記第２の並列ユニオン制御装置とを切り替えるユニオン制御装置切替手段と、
ユニオン処理全体が完了したかどうかを判定するプロセス完了判定手段と、
を備え、
前記第２の並列ユニオン制御装置は、前記入力集合を複数の入力部分集合に分割して、前記要素比較制御手段に対して、前記一対の入力集合の代わりに一対の入力部分集合を使用して、前記Ｎ個の演算器から、前記出力集合の代わりに複数の出力部分集合を出力させるように制御させると共に、前記複数の出力部分集合を結合して前記出力集合を得る、集合分割結合手段を更に有する、
複数ユニオン制御装置。
【請求項７】
前記第２の並列ユニオン制御装置は、前記複数の入力部分集合の分割数を決定する分割数決定手段を更に有し、
前記集合分割結合手段は、決定した分割数に基づいて、前記入力集合を前記複数の入力部分集合に分割し、前記複数の出力部分集合を前記出力集合に結合する、
請求項６に記載の複数ユニオン制御装置。
【請求項８】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御方法であって、情報処理装置によって、
前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御を行い、
メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力を行い、
並列で行うユニオン処理が終了したかどうかを判定する終了判定を行う、
並列ユニオン制御方法。
【請求項９】
前記ソート済み集合は要素が昇順に並んでいる集合であり、
前記要素比較制御は、前記比較の結果が等しくないとき、前記演算器に小さい方の入力要素を前記出力要素として選択させて、該小さい方の入力要素を指すポインタをインクリメントし、前記比較の結果が等しいとき、前記演算器に該入力要素を前記出力要素として選択させて、両方の入力要素を指すポインタをインクリメントする、
請求項８に記載の並列ユニオン制御方法。
【請求項１０】
Ｎ（Ｎは２以上の整数）個の演算器とベクトルレジスタとを含む並列計算機を用いて、コンピュータに、各々がソート済み集合である２Ｎ個の入力集合を対ごとに並列にユニオン処理させて、各々がソート済み集合であるＮ個の出力集合を出力させる並列ユニオン制御用プログラムであって、
前記Ｎ個の演算器の各々に、前記ベクトルレジスタの入力オペランドレジスタに格納されているユニオン処理すべき一対の入力集合の入力要素を順次比較させ、比較の結果によって、前記入力要素の一方を出力集合の出力要素として選択させて前記ベクトルレジスタの出力オペランドレジスタに格納させると共に、前記入力要素を指すポインタを移動する要素比較制御処理と、
メモリから前記２Ｎ個の入力集合を前記入力オペランドレジスタにロードすると共に、前記Ｎ個の出力集合を前記出力オペランドレジスタから前記メモリにストアするレジスタ入出力処理と、
並列で行うユニオン処理が終了したかどうかを判定する終了判定処理と、
を前記コンピュータに実行させる並列ユニオン制御用プログラム。
【国際調査報告】
2019156060.tif 000024
2019156060.tif 000025
2019156060.tif 000026