(57)【要約】【課題】  １サイクルにマージ可能なレコード数Ｅを増加させる場合でも、従来と比べて簡単な回路構成でレコードをマージすることができるデータソート装置を提供することを目的とする。【解決手段】  データに付加された情報に応じてデータが並べられた第１のデータ列の先頭のデータに付加された情報と、第１のデータ列と異なる第２のデータ列の先頭のデータに付加された情報との比較に応じて、第１のデータ列または第２のデータ列を選択し、選択した第１のデータ列または第２のデータ列のうち先頭から所定数Ｅのデータを出力する選択部と、第１レジスタとソート部との一対を（Ｅ−１）個直列に接続したマージネットワークとを備え、ソート部は、第１レジスタに保持されたデータに付加された情報と、所定数Ｅのデータの各々に付加された情報とを所定の条件に応じて並び替え、並び替えられた順にデータを出力し、最後のデータを第１レジスタに保持させる。【選択図】    図１
2018156189.tif 000002
【特許請求の範囲】
【請求項１】
データに付加された情報に応じてデータが並べられた第１のデータ列の先頭のデータに付加された情報と、前記第１のデータ列と異なる第２のデータ列の先頭のデータに付加された情報との比較に応じて、前記第１のデータ列または前記第２のデータ列を選択し、選択した前記第１のデータ列または前記第２のデータ列のうち先頭から所定数Ｅのデータを出力する選択部と、
第１レジスタとソート部との一対を（Ｅ−１）個直列に接続したマージネットワークとを備え、
前記ソート部は、前記第１レジスタに保持されたデータに付加された情報と、前記所定数Ｅのデータの各々に付加された情報とを所定の条件に応じて並び替え、並び替えられた順にデータを出力し、最後のデータを前記第１レジスタに保持させる
ことを特徴とするデータソート装置。
【請求項２】
請求項１に記載のデータソート装置において、
前記マージネットワークは、前記（Ｅ−１）個の前記ソート部のうち少なくとも１つの前記ソート部の入力側に、前記所定数Ｅのデータを保持する第２レジスタをさらに備えることを特徴とするデータソート装置。
【請求項３】
請求項１または請求項２に記載のデータソート装置において、
前記ソート部は、前記情報が整数の場合、前記第１レジスタに保持されたデータに付加された整数と、前記所定数Ｅのデータの各々に付加された整数とを昇順または降順に並び替え、並び替えられた整数の順にデータを出力し、最大または最小の整数が付加されたデータを前記第１レジスタに保持させることを特徴とするデータソート装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データソート装置に関する。
【背景技術】
【０００２】
データに付加された整数に応じてデータ（以下、“レコード”とも称される）を並べるソーティングは、データ解析やデータベース処理等の様々なアプリケーションで用いられている。
【０００３】
また、ＦＰＧＡ（Field-Programmable Gate Array）やＡＳＩＣ（Application Specific Integrated Circuit）等を用いて、データに付加された整数に基づいてデータがソートされた２つのレコードの列を、１つのレコードの列にマージするマージネットワークが提案されている（例えば、非特許文献１、２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Susumu Mashimo, Thiem Van Chu, and Kenji Kise, "Cost-Effective and High-Throughput Merge Network Architecture for the Fastest FPGA Sorting Accelerator", International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies (HEART 2016), pp.7-12 (July 2016).
【非特許文献２】齋藤誠, 眞下達, Thiem Van Chu, 吉瀬謙二, "FPGAソーティングアクセラレータのためのマージネットワークの改良", 電子情報通信学会研究報告RECONF2016-42, pp.13-18 (November 2016).
【発明の開示】
【発明が解決しようとする課題】
【０００５】
マージネットワークのスループットは、マージネットワークの動作周波数と、１サイクルにマージ可能なレコードの数Ｅ（以下、“レコード数Ｅ”とも称される）との積に比例する。従来技術は、１サイクルにマージ可能なレコード数Ｅを増加させるに伴い、マージネットワークにおける１つのレコードが通過する回路が複雑になる。このため、マージネットワークにおけるクリティカルパス（Critical Path）が長くなり、動作周波数が低下し、スループットも低下する。
【０００６】
本発明は、１サイクルにマージ可能なレコード数Ｅを増加させる場合でも、従来と比べて簡単な回路構成でレコードをマージすることができるデータソート装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明を例示するデータソート装置の一態様は、データに付加された情報に応じてデータが並べられた第１のデータ列の先頭のデータに付加された情報と、第１のデータ列と異なる第２のデータ列の先頭のデータに付加された情報との比較に応じて、第１のデータ列または第２のデータ列を選択し、選択した第１のデータ列または第２のデータ列のうち先頭から所定数Ｅのデータを出力する選択部と、第１レジスタとソート部との一対を（Ｅ−１）個直列に接続したマージネットワークとを備え、ソート部は、第１レジスタに保持されたデータに付加された情報と、所定数Ｅのデータの各々に付加された情報とを所定の条件に応じて並び替え、並び替えられた順にデータを出力し、最後のデータを第１レジスタに保持させる。
【発明の効果】
【０００８】
本発明は、１サイクルにマージ可能なレコード数Ｅを増加させる場合でも、従来と比べて簡単な回路構成でレコードをマージすることができる。
【図面の簡単な説明】
【０００９】
【図１】データソート装置の一実施形態を示す図である。
【図２】図１に示したマージネットワークの一例を示す図である。
【図３】図２に示したマージネットワークにおけるマージ処理の一例を示す図である。
【図４】図３に示したマージ処理の続きを示す図である。
【図５】データソート装置の別の実施形態を示す図である。
【図６】図５に示したマージネットワークの一例を示す図である。
【図７】図６に示したマージネットワークにおけるマージ処理の一例を示す図である。
【図８】図７に示したマージ処理の続きを示す図である。
【図９】データソート装置の別の実施形態を示す図である。
【図１０】図９に示したマージネットワークの一例を示す図である。
【図１１】図１０に示したソート部およびレジスタ群の一例を示す図である。
【図１２】図１１に示したデータソート装置の評価結果の一例を示す図である。
【図１３】図９に示したデータソート装置を用いたマージツリーの一例を示す図である。
【発明を実施するための形態】
【００１０】
以下、図面を用いて実施形態について説明する。
【００１１】
図１は、データソート装置の一実施形態を示す。
【００１２】
図１に示したデータソート装置１００は、例えば、ＦＩＦＯ（First-In First-Out）１０、２０、選択部３０およびマージネットワーク４０を有するＦＰＧＡやＡＳＩＣ等である。
【００１３】
ＦＩＦＯ１０、２０は、例えば、外部のコンピュータ装置や、ハードディスク装置等の記憶装置、あるいはネットワーク等からレコードの列である第１レコード列および第２レコード列をそれぞれ受信し、受信した順序でレコードを保持する。ＦＩＦＯ１０、２０は、選択部３０による選択指示に基づいて、第１レコード列または第２レコード列のうち先頭からレコード数Ｅのレコードをマージネットワーク４０に出力する。
【００１４】
なお、レコードは、３２ビット等のデータ長の文字や数字等を含むデータが格納されるデータ領域と、３２ビット等のデータ長の整数が格納されるキー領域とを有する。
【００１５】
また、第１レコード列および第２レコード列は、各レコードのキー領域の整数に基づいて、予め昇順にレコードがソートされる。なお、第１レコード列および第２レコード列は、各レコードのキー領域の整数に基づいて降順にレコードがソートされてもよく、所定の順序でレコードがソートされてもよい。
【００１６】
また、第１レコード列および第２レコード列は、各レコードのキー領域に、浮動小数点や文字列等の情報が格納されてもよい。この場合、第１レコード列および第２レコード列は、予め決められた所定の順序でレコードがソートされることか好ましい。
【００１７】
選択部３０は、例えば、比較器３１およびマルチプレクサ（ＭＵＸ：multiplexer）３２を有する。比較器３１は、ＦＩＦＯ１０に保持された第１レコード列のうち先頭のレコードにおけるキー領域の整数と、ＦＩＦＯ２０に保持された第２レコード列のうち先頭のレコードにおけるキー領域の整数とを比較する。そして、比較器３１は、比較の結果をＭＵＸ３２に出力する。
【００１８】
なお、図１では、データソート装置１００が昇順にレコードをソートする場合を示し、比較器３１は、小さい方の整数がキー領域に格納されたレコード列を示す信号がＭＵＸ３２に出力される。また、データソート装置１００が降順にレコードをソートする場合、比較器３１は、大きい方の整数がキー領域に格納されたレコード列を示す信号をＭＵＸ３２に出力することが好ましい。また、レコードのキー領域に浮動小数点や文字列等の情報が格納されている場合、比較器３１は、第１レコード列の先頭の情報と第２レコード列の先頭の情報とを比較して、第１レコード列または第２レコード列を選択し、選択したレコード列を示す信号をＭＵＸ３２に出力してもよい。
【００１９】
ＭＵＸ３２は、比較器３１の比較の結果に基づいて、第１レコード列または第２レコード列を選択し、選択したレコード列のうち先頭からＥ個のレコードをマージネットワーク４０に出力する。
【００２０】
なお、選択部３０は、比較器３１およびＭＵＸ３２を用いたが、他の要素を用いて第１レコード列または第２レコード列を選択し、選択したレコード列のうち先頭からＥ個のレコードをマージネットワーク４０に出力してもよい。
【００２１】
マージネットワーク４０は、例えば、選択部３０により出力されたＥ個のレコード毎に所定の条件に応じてソートして、第１レコード列と第２レコード列とをマージする。マージネットワーク４０は、マージしたレコード列を外部のコンピュータ装置や記憶装置、またはネットワークに出力する。マージネットワーク４０の動作については、図２から図４で説明する。
【００２２】
図２は、図１に示したマージネットワーク４０の一例を示す。図２では、マージネットワーク４０に入力されるレコード数Ｅは、“４”とする。なお、４以外のＥ個のレコードが入力される場合でも、マージネットワーク４０は、４個の場合と同様にマージ処理を実行する。
【００２３】
図２に示したマージネットワーク４０は、ソート部５０（５０（１）−５０（３））とレジスタ８０（８０（１）−８０（３））との一対を３（＝４−１）個有する。
【００２４】
ソート部５０（１）は、比較器６０（６０（１）−６０（４））、２入力１出力のＭＵＸ７０（１）、７０（５）、および３入力１出力のＭＵＸ７０（２）−７０（４）を有する。なお、ソート部５０（２）、５０（３）は、ソート部５０（１）と同様の要素を有し、詳細な説明を省略する。
【００２５】
また、図２に示したソート部５０（１）は、昇順にレコードを並び替える場合を示すが、降順にレコードを並び替えてもよい。また、レコードのキー領域に浮動小数点や文字列等の情報が格納されている場合、ソート部５０（１）は、レコードの情報と所定の条件との比較に応じてレコードを並び替えてもよい。いずれの場合も、キー領域の情報および所定の条件に応じて動作するように比較器６０が設定されることが好ましい。
【００２６】
比較器６０（１）は、４個のレコードのうち１番目（先頭）のレコードにおけるキー領域の整数と、レジスタ８０（１）に保持されるレコードのキー領域の整数とを比較し、比較の結果を示す信号を、ＭＵＸ７０（１）、７０（２）に出力する。例えば、データソート装置１００が昇順にレコードをソートする場合、比較器６０（１）は、１番目のレコードの整数が、レジスタ８０（１）のレコードの整数より小さい場合、“１”を示す信号を出力する。また、比較器６０（１）は、１番目のレコードの整数が、レジスタ８０（１）のレコードの整数以上大きい場合、“０”を示す信号を出力する。
【００２７】
比較器６０（２）は、２番目のレコードにおけるキー領域の整数と、レジスタ８０（１）のレコードのキー領域の整数とを比較し、比較器６０（１）と同様に、比較の結果を示す“１”または“０”の信号を、ＭＵＸ７０（２）、７０（３）に出力する。また、比較器６０（３）は、３番目のレコードにおけるキー領域の整数と、レジスタ８０（１）のレコードのキー領域の整数とを比較し、比較の結果を示す“１”または“０”の信号をＭＵＸ７０（３）、７０（４）に出力する。また、比較器６０（４）は、４番目のレコードにおけるキー領域の整数と、レジスタ８０（１）のレコードのキー領域の整数とを比較し、比較の結果を示す“１”または“０”の信号をＭＵＸ７０（４）、７０（５）に出力する。
【００２８】
なお、４個のレコードのうち、整数が等しいレコードが２以上存在する場合、整数が等しいレコード同士をソートする順番に制限はない。この場合、各比較器６０は、“１”または“０”のいずれかを出力するかを互いに統一して設定されることが好ましい。
【００２９】
ＭＵＸ７０（１）は、比較器６０（１）における比較の結果に基づいて、１番目のレコードの整数と、レジスタ８０（１）のレコードの整数とのうち、小さい方の整数がキー領域に格納されたレコードをソート部５０（２）に出力する。例えば、ＭＵＸ７０（１）は、比較器６０（１）より“０”の信号を受信した、すなわち１番目のレコードの整数がレジスタ８０（１）のレコードの整数以上大きい場合、レジスタ８０（１）のレコードをソート部５０（２）に出力する。一方、ＭＵＸ７０（１）は、比較器６０（１）より“１”の信号を受信した、すなわち１番目のレコードの整数がレジスタ８０（１）のレコードの整数より小さい場合、１番目のレコードをソート部５０（２）に出力する。
【００３０】
ＭＵＸ７０（ｉ）は、比較器６０（ｉ−１）と比較器６０（ｉ）とにおける比較の結果に基づいて、（ｉ−１）番目のレコード、ｉ番目のレコード、レジスタ８０（１）のレコードのうちの１つをソート部５０（２）に出力する（ｉは、２、３、４）。例えば、ＭＵＸ７０（ｉ）は、比較器６０（ｉ−１）、６０（ｉ）の信号が共に“０”の場合、（ｉ−１）番目のレコードをソート部５０（２）に出力する。また、ＭＵＸ７０（ｉ）は、比較器６０（ｉ−１）、６０（ｉ）の信号が共に“１”の場合、ｉ番目のレコードをソート部５０（２）に出力する。また、ＭＵＸ７０（ｉ）は、比較器６０（ｉ−１）と比較器６０（ｉ）との信号が“０”と“１”との組み合わせの場合、レジスタ８０（１）のレコードをソート部５０（２）に出力する。
【００３１】
ＭＵＸ７０（５）は、比較器６０（４）における比較の結果に基づいて、ソート部５０（２）に出力されずに残った最も大きい整数がキー領域に格納されたレコードをレジスタ８０（１）に出力し、レジスタ８０（１）に保持させる。
【００３２】
図２に示すように、Ｅ（＝４）個のレコードの各々は、各ソート部５０においていずれか１つのＭＵＸ７０を通過する。そして、マージネットワーク４０は、レコード数Ｅを増す場合、３入力１出力のＭＵＸ７０を並列に接続して増加させることで対応でき、各ソート部５０においてレコードが通過するＭＵＸ７０の数は１つにできる。
【００３３】
図３および図４は、図２に示したマージネットワーク４０におけるマージ処理の一例を示す。図３（ａ）から図３（ｃ）は、データソート装置１００におけるソート処理の開始から１サイクル経過するまでのマージネットワーク４０の状態を示す。図４は、図３（ｃ）に示した状態から次の１サイクル経過するまでのマージネットワーク４０の状態を示す。なお、図３および図４では、マージネットワーク４０によりマージされるレコードを、レコードのキー領域に格納された整数で示す。
【００３４】
また、図３および図４では、ソート部５０の構成を省略する。また、図３（ａ）では、データソート装置１００の初期状態として、例えば、キー領域に整数“０”が格納されたＮＵＬＬデータが、マージネットワーク４０のレジスタ８０の各々に保持される。
【００３５】
また、図１に示したデータソート装置１００に入力される第１レコード列は、例えば、キー領域に格納される整数が１、３、５…、（２Ｎ＋１）の順に予めソートされたレコードの列である（Ｎは正の整数）。また、第２レコード列は、キー領域に格納される整数が２、４、６…、２Ｎの順に予めソートされたレコードの列である。すなわち、図３（ａ）に示すソート処理の開始時では、ＦＩＦＯ１０に保持される第１レコード列の先頭のレコードのキー領域の整数は“１”であり、ＦＩＦＯ２０に保持される第２レコード列の先頭のレコードのキー領域の整数は“２”である。このため、選択部３０は、先頭のレコードの整数が小さい第１レコード列を選択し、整数“１”、“３”、“５”、“７”の各々がキー領域に格納された４個のレコードをＦＩＦＯ１０からマージネットワーク４０に出力する。そして、ＦＩＦＯ１０に保持される第１レコード列の先頭のレコードの整数は、“９”となる。
【００３６】
図３（ａ）では、ソート部５０（１）の比較器６０（１）は、４個のレコードのうち１番目のレコードのキー領域の整数“１”と、レジスタ８０（１）に保持されているレコードのキー領域の整数“０”とを比較し、“０”の信号を出力する。比較器６０（２）は、２番目のレコードの整数“３”と、レジスタ８０（１）のレコードの整数“０”とを比較し、“０”の信号を出力する。比較器６０（３）は、３番目のレコードの整数“５”と、レジスタ８０（１）のレコードの整数“０”とを比較し、“０”の信号を出力する。比較器６０（４）は、４番目のレコードの整数“７”と、レジスタ８０（１）のレコードの整数“０”とを比較し、“０”の信号を出力する。
【００３７】
ソート部５０（１）のＭＵＸ７０（１）は、比較器６０（１）による比較の結果に基づいて、レジスタ８０（１）のレコードの整数“０”と１番目のレコードの整数“１”とのうち、整数“０”が付加されたレジスタ８０（１）のレコードをソート部５０（２）に出力する。
【００３８】
ＭＵＸ７０（２）は、比較器６０（１）と比較器６０（２）とにおける比較の結果に基づいて、整数“１”の１番目のレコードと、整数“３”の２番目のレコードと、レジスタ８０（１）の整数“０”のレコードとのいずれかをソート部５０（２）に出力する。図３（ａ）の場合、比較器６０（１）、６０（２）の信号が共に“０”であることから、ＭＵＸ７０（２）は、整数“１”がキー領域に格納された１番目のレコードをソート部５０（２）に出力する。
【００３９】
ＭＵＸ７０（３）は、比較器６０（２）、６０（３）の信号が共に“０”であることから、整数“３”がキー領域に格納された２番目のレコードをソート部５０（２）に出力する。また、ＭＵＸ７０（４）は、比較器６０（３）、６０（４）の信号が共に“０”であることから、整数“５”がキー領域に格納された３番目のレコードをソート部５０（２）に出力する。
【００４０】
ＭＵＸ７０（５）は、比較器６０（４）による比較の結果に基づいて、ソート部５０（２）に出力されずに残った最も大きい整数“７”をキー領域に格納したレコードをレジスタ８０（１）に出力し、レジスタ８０（１）に保持させる。
【００４１】
図３（ｂ）は、ソート部５０（１）におけるソート処理が終了した時点でのマージネットワーク４０の状態を示す。図３（ｂ）に示すように、ソート部５０（１）は、整数“０”、“１”、“３”、“５”の順にソートした４個のレコードを出力する。また、ソート部５０（１）は、レジスタ８０（１）に整数“７”を出力する。
【００４２】
その後、ソート部５０（２）、５０（３）の各々は、ソート部５０（１）と同様のソート処理を４個のレコードに対して実行する。
【００４３】
図３（ｃ）は、ソート部５０（３）におけるソート処理が終了した、すなわち１サイクル経過したマージネットワーク４０の状態を示す。図３（ｃ）に示すように、マージネットワーク４０は、整数“０”、“０”、“０”、“１”の順にマージした４個のレコードを出力する。また、レジスタ８０（２）は、整数“５”がキー領域に格納されたレコードを保持し、レジスタ８０（３）は、整数“３”がキー領域に格納されたレコードを保持する。
【００４４】
次に、選択部３０は、ＦＩＦＯ１０に保持される第１レコード列の先頭のレコードのキー領域の整数“９”と、ＦＩＦＯ２０に保持される第２レコード列の先頭のレコードのキー領域の整数“２”とを比較する。そして、選択部３０は、図４（ａ）に示すように、第２レコード列を選択し、整数“２”、”４”、“６”、“８”がキー領域に格納された４個のレコードを、ＦＩＦＯ２０からマージネットワーク４０に出力する。そして、ＦＩＦＯ２０に保持される第２レコード列の先頭のレコードの整数は、“１０”となる。
【００４５】
図４（ａ）では、ソート部５０（１）の比較器６０（１）は、４個のレコードのうち１番目のレコードのキー領域の整数“２”と、レジスタ８０（１）に保持されているレコードのキー領域の整数“７”とを比較し、“１”の信号を出力する。比較器６０（２）は、２番目のレコードの整数“４”と、レジスタ８０（１）のレコードの整数“７”とを比較し、“１”の信号を出力する。比較器６０（３）は、３番目のレコードの整数“６”と、レジスタ８０（１）のレコードの整数“７”とを比較し、“１”の信号を出力する。比較器６０（４）は、４番目のレコードの整数“８”と、レジスタ８０（１）のレコードの整数“７”とを比較し、“０”の信号を出力する。
【００４６】
ソート部５０（１）のＭＵＸ７０（１）は、比較器６０（１）による比較の結果に基づいて、１番目のレコードの整数“２”と、レジスタ８０（１）のレコードの整数“７”とうち、整数“２”がキー領域に格納されたレコードをソート部５０（２）に出力する。
【００４７】
ＭＵＸ７０（２）は、比較器６０（１）と比較器６０（２）とにおける比較の結果に基づいて、整数“２”の１番目のレコードと、整数“４”の２番目のレコードと、レジスタ８０（１）の整数“７” のレコードとのいずれかをソート部５０（２）に出力する。図４（ａ）の場合、比較器６０（１）、６０（２）の信号が共に“１”であることから、ＭＵＸ７０（２）は、整数“４”がキー領域に格納された２番目のレコードをソート部５０（２）に出力する。
【００４８】
ＭＵＸ７０（３）は、比較器６０（２）、６０（３）の信号が共に“１”であることから、整数“６”がキー領域に格納された３番目のレコードをソート部５０（２）に出力する。また、ＭＵＸ７０（４）は、比較器６０（３）の信号が“０”で、比較器６０（４）の信号が“１”であることから、レジスタ８０（１）の整数“７”がキー領域に格納されたレコードをソート部５０（２）に出力する。
【００４９】
ＭＵＸ７０（５）は、比較器６０（４）による比較の結果に基づいて、ソート部５０（２）に出力されずに残った最も大きい整数“８”をキー領域に格納したレコードをレジスタ８０（１）に出力し、レジスタ８０（１）に保持させる。
【００５０】
図４（ｂ）は、ソート部５０（１）におけるソート処理が終了した時点でのマージネットワーク４０の状態を示す。図４（ｂ）に示すように、ソート部５０（１）は、整数“２”、“４”、“６”、“７”の順にソートした４個のレコードを出力する。また、ソート部５０（１）は、レジスタ８０（１）に整数“８”を出力する。
【００５１】
その後、ソート部５０（２）、５０（３）の各々は、ソート部５０（１）と同様のソート処理を４個のレコードに対して実行する。
【００５２】
図４（ｃ）は、ソート部５０（３）におけるソート処理が終了した、すなわち２サイクル経過したマージネットワーク４０の状態を示す。図４（ｃ）に示すように、マージネットワーク４０は、整数“２”、“３”、“４”、“５”の順にマージした４個のレコードを出力する。また、レジスタ８０（２）は、整数“７”がキー領域に格納されたレコードを保持し、レジスタ８０（３）は、整数“６”がキー領域に格納されたレコードを保持する。
【００５３】
そして、データソート装置１００は、第１レコード列および第２レコード列が入力される度に、図３および図４に示したマージ処理をマージネットワーク４０に繰り返し実行させる。
【００５４】
以上、図１から図４に示した実施形態では、Ｅ個のレコードの各々は、各ソート部５０においてＭＵＸ７０のいずれか１つを通過する。そして、マージネットワーク４０は、各ソート部５０において３入力１出力のＭＵＸ７０を並列に接続して増加することで、入力するレコード数Ｅを増加でき、各レコードが通過する各ソート部５０のＭＵＸ７０の数を１つにできる。すなわち、データソート装置１００は、レコード数Ｅが増加しても、直列に接続されるソート部５０の数が増加するだけで、マージネットワーク４０の回路を複雑にすることはない。
【００５５】
図５は、データソート装置の別の実施形態を示す。図１で説明した要素と同一または同様の機能を有する要素については、同一または同様の符号を付し、これらについては、詳細な説明を省略する。
【００５６】
図５に示したデータソート装置１００Ａは、例えば、ＦＩＦＯ１０、２０、選択部３０およびマージネットワーク４０ａを有するＦＰＧＡやＡＳＩＣ等である。
【００５７】
マージネットワーク４０ａは、例えば、選択部３０により出力されたＥ個のレコード毎に昇順にソートして、第１レコード列と第２レコード列とをマージする。マージネットワーク４０ａは、マージしたレコード列を外部のコンピュータ装置や記憶装置、またはネットワークに出力する。マージネットワーク４０ａの動作については、図６から図８で説明する。
【００５８】
図６は、図５に示したマージネットワーク４０ａの一例を示す。図２で説明した要素と同一または同様の機能を有する要素については、同一または同様の符号を付し、これらについては、詳細な説明を省略する。図６では、マージネットワーク４０ａに入力されるレコード数Ｅは、“４”とする。なお、４以外のＥ個のレコードが入力される場合でも、マージネットワーク４０ａは、４個の場合と同様にマージ処理を実行する。
【００５９】
図６に示したマージネットワーク４０ａは、ソート部５０（５０（１）−５０（３））とレジスタ８０（８０（１）−８０（３））との一対を３個有する。また、マージネットワーク４０ａは、４個のレコードが各ソート部５０に入力される前に、４個のレコードを一時的に保持するレジスタ群９０（９０（１）−９０（３））を有する。
【００６０】
レジスタ群９０は、４個のレコードそれぞれを保持する４つのレジスタを有する。レジスタ群９０は、データソート装置１００Ａに含まれる水晶発振器等から出力される信号に基づいて、保持する４個のレコードをソート部５０に出力する。これにより、マージネットワーク４０ａは、第１レコード列および第２レコード列に対するマージ処理をパイプライン化する。そして、レジスタ群９０がソート部５０毎に配置されることにより、マージネットワーク４０ａにおいて１サイクルに実行できるマージ処理のクリティカルパスは、隣接するレジスタ群９０間、すなわち各ソート部５０に対応する距離となる。これは、図２に示したマージネットワーク４０のクリティカルパス（ソート部５０（１）からソート部５０（３）までの距離）と比べて短い。これにより、マージネットワーク４０ａの動作周波数を、図２に示したマージネットワーク４０と比べて引き上げることができ、マージネットワーク４０ａのスループットを向上させることができる。
【００６１】
なお、図６に示したマージネットワーク４０ａは、各ソート部５０の入力側にレジスタ群９０を配置したが、一部のソート部５０の入力側にレジスタ群９０を配置してもよい。いずれのソート部５０の入力側にレジスタ群９０を配置するかは、データソート装置１００Ａに要求される処理能力や回路規模等に応じて適宜決定されることが好ましい。また、レジスタ群９０は、マージネットワーク４０ａにおけるクリティカルパスが一定の長さとなるように、所定の数のソート部５０毎に１つ配置されることが好ましい。
【００６２】
図７および図８は、図５に示したマージネットワーク４０ａにおけるマージ処理の一例を示す。図７（ａ）から図７（ｃ）は、データソート装置１００Ａにおけるソート処理の開始から３サイクル経過するまでの各サイクルにおけるマージネットワーク４０ａの状態を示す。図８（ａ）および図８（ｂ）は、図７（ｃ）に示した状態から次の２サイクル経過するまでの各サイクルにおけるマージネットワーク４０ａの状態を示す。なお、図７および図８では、図３および図４と同様に、マージネットワーク４０ａによりマージされるレコードを、レコードのキー領域に格納された整数で示す。
【００６３】
また、図７および図８では、図３および図４と同様に、ソート部５０の構成を省略するとともに、レジスタ群９０の構成を省略する。また、図７（ａ）では、データソート装置１００Ａの初期状態として、例えば、図３（ａ）と同様に、キー領域に整数“０”が格納されたＮＵＬＬデータが、マージネットワーク４０ａのレジスタ８０の各々に保持される。
【００６４】
また、図５に示したデータソート装置１００Ａに入力される第１レコード列は、図３および図４と同様に、キー領域に格納される整数が１、３、５…、（２Ｎ＋１）の順に予めソートされたレコードの列である。また、第２レコード列は、キー領域に格納される整数が２、４、６…、２Ｎの順に予めソートされたレコードの列である。
【００６５】
図７（ａ）に示すように、データソート装置１００Ａがソート処理を開始した１サイクル目において、ＦＩＦＯ１０に保持される第１レコード列の先頭のレコードのキー領域の整数は“１”であり、ＦＩＦＯ２０に保持される第２レコード列の先頭のレコードのキー領域の整数は“２”である。このため、選択部３０は、先頭のレコードの整数が小さい第１レコード列を選択し、整数“１”、“３”、“５”、“７”の各々がキー領域に格納された４個のレコードをＦＩＦＯ１０からマージネットワーク４０ａに出力する。そして、レジスタ群９０（１）は、出力された４個のレコードを保持する。また、ＦＩＦＯ１０に保持される第１レコード列の先頭のレコードの整数は、“９”となる。
【００６６】
次に、図７（ｂ）に示した２サイクル目では、マージネットワーク４０ａのソート部５０（１）は、レジスタ群９０（１）から整数“１”、“３”、“５”、“７”がキー領域に格納された４個のレコードを読み出す。ソート部５０（１）は、図３（ａ）および図３（ｂ）と同様のソート処理を、レジスタ８０（１）に保持されたレコードと読み出した４個のレコードとに対して実行する。そして、ソート部５０（１）は、整数“０”、“１”、“３”、“５”がキー領域に格納された４個のレコードをレジスタ群９０（２）に出力し、整数“７”がキー領域に格納されたレコードをレジスタ８０（１）に保持させる。
【００６７】
また、２サイクル目では、マージネットワーク４０ａは、ＦＩＦＯ２０から出力された整数“２”、“４”、“６”、“８”がキー領域に格納された次の４個のレコードを選択部３０より受信し、受信した４個のレコードをレジスタ群９０（１）に保持する。
【００６８】
次に、図７（ｃ）に示した３サイクル目では、マージネットワーク４０ａのソート部５０（２）は、レジスタ群９０（２）から整数“０”、“１”、“３”、“５”がキー領域に格納された４個のレコードを読み出す。ソート部５０（２）は、図３（ａ）および図３（ｂ）に示したソート部５０（１）と同様のソート処理を、レジスタ８０（２）に保持されたレコードと読み出した４個のレコードとに対して実行する。そして、ソート部５０（２）は、整数“０”、“０”、“１”、“３”がキー領域に格納された４個のレコードをレジスタ群９０（３）に出力し、整数“５”がキー領域に格納されたレコードをレジスタ８０（２）に保持させる。
【００６９】
また、ソート部５０（１）は、レジスタ群９０（１）から整数“２”、“４”、“６”、“８”がキー領域に格納された４個のレコードを読み出す。ソート部５０（１）は、レジスタ８０（１）に保持されたレコードと読み出した４個のレコードとに対してソート処理を実行する。そして、ソート部５０（１）は、整数“２”、“４”、“６”、“７”がキー領域に格納された４個のレコードをレジスタ群９０（２）に出力し、整数“８”がキー領域に格納されたレコードをレジスタ８０（１）に保持させる。
【００７０】
また、３サイクル目では、マージネットワーク４０ａは、ＦＩＦＯ１０から出力された整数“９”、“１１”、“１３”、“１５”がキー領域に格納された次の４個のレコードを選択部３０より受信し、受信した４個のレコードをレジスタ群９０（１）に保持する。
【００７１】
次に、図８（ａ）に示した４サイクル目では、マージネットワーク４０ａのソート部５０（３）は、図７（ｃ）に示したレジスタ群９０（３）から整数“０”、“０”、“１”、“３”がキー領域に格納された４個のレコードを読み出す。ソート部５０（３）は、図３（ａ）および図３（ｂ）に示したソート部５０（１）と同様のソート処理を、レジスタ８０（３）に保持されたレコードと読み出した４個のレコードとに対して実行する。そして、ソート部５０（３）は、整数“０”、“０”、“０”、“１”がキー領域に格納された４個のレコードを外部のコンピュータ装置、記憶装置やネットワーク等に出力し、整数“３”がキー領域に格納されたレコードをレジスタ８０（３）に保持させる。
【００７２】
また、ソート部５０（２）は、図７（ｃ）に示したレジスタ群９０（２）から整数“２”、“４”、“６”、“７”がキー領域に格納された４個のレコードを読み出す。ソート部５０（２）は、レジスタ８０（２）に保持されたレコードと読み出した４個のレコードとに対してソート処理を実行する。そして、ソート部５０（２）は、整数“２”、“４”、“５”、“６”がキー領域に格納された４個のレコードをレジスタ群９０（３）に出力し、整数“７”がキー領域に格納されたレコードをレジスタ８０（２）に保持させる。
【００７３】
また、ソート部５０（１）は、図７（ｃ）に示したレジスタ群９０（１）から整数“９”、“１１”、“１３”、“１５”がキー領域に格納された４個のレコードを読み出す。ソート部５０（１）は、レジスタ８０（１）に保持されたレコードと読み出した４個のレコードとに対してソート処理を実行する。そして、ソート部５０（１）は、整数“８”、“９”、“１１”、“１３”がキー領域に格納された４個のレコードをレジスタ群９０（２）に出力し、整数“１５”がキー領域に格納されたレコードをレジスタ８０（１）に保持させる。
【００７４】
また、４サイクル目では、マージネットワーク４０ａは、ＦＩＦＯ２０から出力された整数“１０”、“１２”、“１４”、“１６”がキー領域に格納された次の４個のレコードを選択部３０より受信し、受信した４個のレコードをレジスタ群９０（１）に保持する。
【００７５】
次に、図８（ｂ）に示した５サイクル目では、ソート部５０（３）は、レジスタ群９０（３）から整数“２”、“４”、“５”、“６”がキー領域に格納された４個のレコードを読み出す。ソート部５０（３）は、レジスタ８０（３）に保持されたレコードと読み出した４個のレコードとに対してソート処理を実行する。そして、ソート部５０（３）は、整数“２”、“３”、“４”、“５”がキー領域に格納された４個のレコードを外部のコンピュータ装置、記憶装置やネットワーク等に出力し、整数“６”がキー領域に格納されたレコードをレジスタ８０（３）に保持させる。
【００７６】
また、ソート部５０（２）は、レジスタ群９０（２）から整数“８”、“９”、“１１”、“１３”がキー領域に格納された４個のレコードを読み出す。ソート部５０（２）は、レジスタ８０（２）に保持されたレコードと読み出した４個のレコードとに対してソート処理を実行する。そして、ソート部５０（２）は、整数“７”、“８”、“９”、“１１”がキー領域に格納された４個のレコードをレジスタ群９０（３）に出力し、整数“１３”がキー領域に格納されたレコードをレジスタ８０（２）に保持させる。
【００７７】
また、ソート部５０（１）は、レジスタ群９０（１）から整数“１０”、“１２”、“１４”、“１６”がキー領域に格納された４個のレコードを読み出す。ソート部５０（１）は、レジスタ８０（１）に保持されたレコードと読み出した４個のレコードとに対して実行する。そして、ソート部５０（１）は、整数“１０”、“１２”、“１４”、“１５”がキー領域に格納された４個のレコードをレジスタ群９０（２）に出力し、整数“１６”がキー領域に格納されたレコードをレジスタ８０（１）に保持させる。
【００７８】
また、５サイクル目では、マージネットワーク４０ａは、ＦＩＦＯ１０から出力された整数“１７”、“１９”、“２１”、“２３”がキー領域に格納された次の４個のレコードを選択部３０より受信し、受信した４個のレコードをレジスタ群９０（１）に保持する。
【００７９】
そして、データソート装置１００Ａは、第１レコード列および第２レコード列が入力される度に、図７および図８に示したマージ処理をマージネットワーク４０ａに繰り返し実行させる。
【００８０】
以上、図５から図８に示した実施形態では、Ｅ個のレコードの各々は、各ソート部５０においてＭＵＸ７０のいずれか１つを通過する。そして、マージネットワーク４０ａは、各ソート部５０において３入力１出力のＭＵＸ７０を並列に接続して増加することで、入力するレコード数Ｅを増加でき、各レコードが通過する各ソート部５０のＭＵＸ７０の数を１つにできる。また、各ソート部５０の入力側にレジスタ群９０を配置して、マージ処理をパイプライン化することにより、１サイクルに実行できるマージ処理のクリティカルパスを、隣接するレジスタ群９０間、すなわち１つのソート部５０に対応する距離に短くする。これにより、データソート装置１００Ａは、レコード数Ｅが増加しても、マージネットワーク４０ａの回路を複雑にすることなく、クリティカルパスにおける各レコードのゲート段数を一定にでき、動作周波数の低下を回避できる。そして、データソート装置１００Ａは、従来と比べて高速にレコードをマージすることができる。
【００８１】
図９は、データソート装置の別の実施形態を示す。図１で説明した要素と同一または同様の機能を有する要素については、同一または同様の符号を付し、これらについては、詳細な説明を省略する。
【００８２】
図９に示したデータソート装置１００Ｂは、例えば、ＦＩＦＯ１０、２０、選択部３０およびマージネットワーク４０ｂを有するＦＰＧＡやＡＳＩＣ等である。
【００８３】
マージネットワーク４０ｂは、例えば、選択部３０により出力されたＥ個のレコード毎に昇順にソートして、第１レコード列と第２レコード列とをマージする。マージネットワーク４０ｂは、マージしたレコード列をコンピュータ装置、記憶装置、またはネットワークに出力する。マージネットワーク４０ｂの動作については、図１０および図１１で説明する。
【００８４】
図１０は、図９に示したマージネットワーク４０ｂの一例を示す。図６で説明した要素と同一または同様の機能を有する要素については、同一または同様の符号を付し、これらについては、詳細な説明を省略する。図１０では、マージネットワーク４０ｂに入力されるレコード数Ｅは、“４”とする。なお、４以外のＥ個のレコードが入力される場合でも、マージネットワーク４０ｂは、４個の場合と同様にマージ処理を実行する。
【００８５】
図１０に示したマージネットワーク４０ｂは、ソート部５０ａ（５０ａ（１）−５０ａ（３））と、レコードのキー領域の整数を保持するレジスタ８０ａ（８０ａ（１）−８０ａ（３））およびデータ領域のデータを保持するレジスタ８０ｂ（８０ｂ（１）−８０ｂ（３））との一組を３個有する。また、マージネットワーク４０ｂは、各ソート部５０ａの入力側に、４個のレコードのうちキー領域の整数を一時的に保持するレジスタ群９０ａ（９０ａ（１）−９０ａ（３））と、データ領域のデータを一時的に保持するレジスタ群９０ｂ（９０ｂ（１）−９０ｂ（３））とを有する。すなわち、マージネットワーク４０ｂは、４個のレコードに対するソート処理を、各レコードのキー領域の整数とデータ領域のデータとを分けて実行する。
【００８６】
図１１は、図１０に示したソート部５０ａ（１）およびレジスタ群９０ａ（１）、９０ｂ（１）の一例を示す。図６で説明した要素と同一または同様の機能を有する要素については、同一または同様の符号を付し、これらについては、詳細な説明を省略する。また、ソート部５０ａ（２）、５０ａ（３）、およびレジスタ群９０ａ（２）、９０ａ（３）、９０ｂ（２）、９０ｂ（３）は、ソート部５０ａ（１）およびレジスタ群９０ａ（１）、９０ｂ（１）と同様の要素を有し、詳細な説明を省略する。
【００８７】
レジスタ群９０ａ、９０ｂは、４つのレジスタを有する。レジスタ群９０ａは、４個のレコードの各々のキー領域に格納される整数を保持し、データソート装置１００Ｂに含まれる水晶発振器等から出力される信号に基づいて、保持する整数をソート部５０ａに出力する。また、レジスタ群９０ｂは、４個のレコードの各々のデータ領域に格納されるデータを保持し、データソート装置１００Ｂの水晶発振器等から出力される信号に基づいて、保持するデータをソート部５０ａに出力する。これにより、マージネットワーク４０ｂは、第１レコード列および第２レコード列に対するマージ処理をパイプライン化する。そして、レジスタ群９０ａ、９０ｂがソート部５０ａ毎に配置されることにより、マージネットワーク４０ｂにおけるマージ処理のクリティカルパスは、隣接するレジスタ群９０ａ、９０ｂ間、すなわち各ソート部５０ａに対応する距離となる。これは、図２に示したマージネットワーク４０のクリティカルパスと比べて短く、マージネットワーク４０ｂの動作周波数を、図２に示したマージネットワーク４０と比べて引き上げることができ、マージネットワーク４０ｂのスループットを向上させることができる。
【００８８】
なお、図１０に示したマージネットワーク４０ｂは、各ソート部５０ａの入力側にレジスタ群９０ａ、９０ｂを配置したが、一部のソート部５０ａの入力側にレジスタ群９０ａ、９０ｂを配置してもよい。いずれのソート部５０ａの入力側にレジスタ群９０ａ、９０ｂを配置するかは、データソート装置１００Ｂに要求される処理能力や回路規模等に応じて適宜決定されることが好ましい。また、レジスタ群９０ａ、９０ｂは、マージネットワーク４０ｂにおけるクリティカルパスが一定の長さとなるように、所定の数のソート部５０ａ毎に１つ配置されることが好ましい。
【００８９】
ソート部５０ａ（１）は、比較器６０（６０（１）−６０（４））、２入力１出力のＭＵＸ７０ａ（１）、７０ａ（５）、７０ｂ（１）、７０ｂ（５）、３入力１出力のＭＵＸ７０ａ（２）−７０ａ（４）、７０ｂ（２）−７０ｂ（４）、およびレジスタ群９５を有する。
【００９０】
ＭＵＸ７０ａ（１）は、図２に示したＭＵＸ７０（１）と同様に、比較器６０（１）における比較の結果に基づいて、４個のレコードの１番目のレコードにおけるキー領域の整数と、レジスタ８０ａ（１）のレコードのキー領域の整数とのうち、小さい方の整数をレジスタ群９０ａ（２）に出力する。
【００９１】
ＭＵＸ７０ａ（ｉ）は、図２に示したＭＵＸ７０（ｉ）と同様に、比較器６０（ｉ−１）と比較器６０（ｉ）とにおける比較の結果に基づいて、（ｉ−１）番目のレコードの整数、ｉ番目のレコードの整数、レジスタ８０ａ（１）のレコードの整数のうちの１つをレジスタ群９０ａ（２）に出力する（ｉは、２、３、４）。例えば、ＭＵＸ７０ａ（ｉ）は、比較器６０（ｉ−１）、６０（ｉ）の信号が共に“０”の場合、（ｉ−１）番目のレコードの整数をレジスタ群９０ａ（２）に出力する。また、ＭＵＸ７０ａ（ｉ）は、比較器６０（ｉ−１）、６０（ｉ）の信号が共に“１”の場合、ｉ番目のレコードの整数をレジスタ群９０ａ（２）に出力する。また、ＭＵＸ７０ａ（ｉ）は、比較器６０（ｉ−１）と比較器６０（ｉ）との信号が“０”と“１”の組み合わせの場合、レジスタ８０ａ（１）のレコードの整数をレジスタ群９０ａ（２）に出力する。
【００９２】
ＭＵＸ７０ａ（５）は、図２に示したＭＵＸ７０（５）と同様に、比較器６０（４）における比較の結果に基づいて、レジスタ群９０ａ（２）に出力されずに残った最も大きい整数をレジスタ８０ａ（１）に出力し、レジスタ８０ａ（１）に保持させる。
【００９３】
一方、ＭＵＸ７０ｂ（１）は、ＭＵＸ７０ａ（１）と同様に、比較器６０（１）における比較の結果に基づいて、１番目のレコードのデータ領域のデータと、レジスタ８０ｂ（１）のレコードのデータ領域のデータとのうち、キー領域に格納された整数が小さい方のレコードのデータをレジスタ群９０ｂ（２）に出力する。
【００９４】
ＭＵＸ７０ｂ（ｉ）は、ＭＵＸ７０ａ（ｉ）と同様に、比較器６０（ｉ−１）と比較器６０（ｉ）とにおける比較の結果に基づいて、（ｉ−１）番目のレコードのデータ、ｉ番目のレコードのデータ、レジスタ８０ｂ（１）のレコードのデータのうちの１つをレジスタ群９０ｂ（２）に出力する。例えば、ＭＵＸ７０ｂ（ｉ）は、比較器６０（ｉ−１）、６０（ｉ）の信号が共に“０”の場合、（ｉ−１）番目のレコードのデータをレジスタ群９０ｂ（２）に出力する。また、ＭＵＸ７０ａ（ｉ）は、比較器６０（ｉ−１）、６０（ｉ）の信号が共に“１”の場合、ｉ番目のレコードのデータをレジスタ群９０ｂ（２）に出力する。また、ＭＵＸ７０ｂ（ｉ）は、比較器６０（ｉ−１）と比較器６０（ｉ）との信号が“０”と“１”の組み合わせの場合、レジスタ８０ｂ（１）のレコードのデータをレジスタ群９０ｂ（２）に出力する。
【００９５】
ＭＵＸ７０ｂ（５）は、ＭＵＸ７０ａ（５）と同様に、比較器６０（４）における比較の結果に基づいて、レジスタ群９０ｂ（２）に出力されずに残った最も大きい整数がキー領域に格納されたレコードのデータをレジスタ８０ｂ（１）に出力し、レジスタ８０ｂ（１）に保持させる。
【００９６】
レジスタ群９５は、例えば、１３個のレジスタを有し、データソート装置１００Ｂの水晶発振器等から出力される信号に基づいて、保持する整数やデータ、または比較の結果を出力する。例えば、レジスタ群９５は、１３個のうち、各比較器６０から出力される比較の結果を保持する４つのレジスタを有する。また、レジスタ群９５は、レジスタ８０ａ（１）と接続され、レジスタ８０ａ（１）から出力される整数を保持するレジスタを有する。また、レジスタ群９５は、レジスタ群９０ａ（１）と接続され、レジスタ群９０ａ（１）から出力される４個のレコードの整数をそれぞれ保持する４つのレジスタを有する。また、レジスタ群９５は、レジスタ群９０ｂ（１）と接続され、レジスタ群９０ｂ（１）から出力される４個のレコードのデータをそれぞれ保持する４つのレジスタを有する。
【００９７】
そして、レジスタ群９５の配置により、マージネットワーク４０ｂにおいて１サイクルに実行できるマージ処理のクリティカルパスを、レジスタ群９０ａ（１）、９０ｂ（１）とレジスタ群９５との間の距離と、レジスタ群９５とレジスタ群９０ａ（２）、９０ｂ（２）との間の距離にすることができる。これは、図６に示したマージネットワーク４０ａのクリティカルパス（ソート部５０に対応する距離）と比べて短く、マージネットワーク４０ｂの動作周波数を、図６に示したマージネットワーク４０ａと比べて引き上げることができ、マージネットワーク４０ｂのスループットを向上させることができる。
【００９８】
なお、図１１に示したマージネットワーク４０ｂでは、レジスタ８０ａ（１）は、レジスタ群９０ａ（１）が４個のレコードの整数を出力するタイミングで、保持するレコードの整数を出力する。また、レジスタ８０ｂ（１）は、レジスタ群９５が比較の結果や、レコードの整数およびデータを出力するタイミングで、保持するレコードのデータを出力する。
【００９９】
なお、図１１に示したマージネットワーク４０ｂにおけるマージ処理は、レコードがキー領域の整数とデータ領域のデータとに分けられ、レジスタ群９５の配置によりクリティカルパスが短くなることを除き、図７および図８に示したマージネットワーク４０ａのマージ処理と同様であり、詳細な説明を省略する。
【０１００】
以上、図９から図１１に示した実施形態では、Ｅ個のレコードの各々は、各ソート部５０ａにおいてＭＵＸ７０ａ、７０ｂのいずれか１つを通過する。そして、マージネットワーク４０ｂは、各ソート部５０ａにおいて３入力１出力のＭＵＸ７０ａ、７０ｂを並列に接続して増加することで、入力するレコード数Ｅを増加でき、各レコードが通過する各ソート部５０ａのＭＵＸ７０ａまたはＭＵＸ７０ｂの数を１つにできる。また、各ソート部５０ａの入力側にレジスタ群９０ａ、９０ｂを配置するとともに、ソート部５０ａにレジスタ群９５を配置することにより、マージ処理をパイプライン化し、１サイクルに実行できるマージ処理のクリティカルパスを、レジスタ群９０ａ、９０ｂとレジスタ群９５との間の距離に短くする。これにより、データソート装置１００Ｂは、レコード数Ｅが増加しても、マージネットワーク４０ｂの回路を複雑にすることなく、クリティカルパスにおける各レコードのゲート段数を一定にでき、動作周波数の低下を回避できる。そして、データソート装置１００Ｂは、従来と比べて高速にレコードをマージすることができる。
【０１０１】
図１２は、図１１に示したデータソート装置１００Ｂの評価結果の一例を示す。図１２は、データソート装置１００Ｂをツリー構造に配置したマージツリーにおける評価結果を示す。マージツリーについては、図１３で説明する。
【０１０２】
図１２（ａ）は、マージツリーに入力されるレコード数Ｅに対するマージツリーの動作周波数を示す。図１２（ａ）の縦軸は動作周波数を示し、横軸はレコード数Ｅを示す。また、図１２（ｂ）は、レコード数Ｅに対するマージツリーのスループットを示す。図１２では、データソート装置１００Ｂの評価結果を実線で示す。また、従来技術として、W. Song, D. Koch, M. Luj'an, and J. Garside, "Parallel hardware marge sorter", in FCCM, 2016のParallel Mage-Tree（ＰＭＴ）の結果を破線で示す。
【０１０３】
図１３は、図９に示したデータソート装置１００Ｂを用いたマージツリーの一例を示す。図１３に示したマージツリーＭＴは、例えば、レコード数Ｅが８の場合を示す。この場合、マージツリーＭＴは、入力される各レコードを２個の単位で結合する８個の結合器ＣＰ１と、結合された２個のレコード毎にマージする４個のデータソート装置１００Ｂ［Ｅ＝２］とを有する。また、マージツリーＭＴは、各データソート装置１００Ｂ［Ｅ＝２］によりマージされた２個のレコードの２組を結合する４つの結合器ＣＰ２と、結合された４個のレコード毎にマージする２個のデータソート装置１００Ｂ［Ｅ＝４］とを有する。また、マージツリーＭＴは、各データソート装置１００Ｂ［Ｅ＝４］によりマージされた４個のレコードの２組を結合する２つの結合器ＣＰ３と、結合された８個のレコード毎にマージする１つのデータソート装置１００Ｂ［Ｅ＝８］とを有する。
【０１０４】
なお、図１３に示したマージツリーＭＴは、８以外のレコード数Ｅの場合についても同様のツリー構造を有する。
【０１０５】
図１２（ａ）に示すように、図１３に示したマージツリーＭＴは、レコード数Ｅが３２の場合、３１１．７ＭＨｚで動作させることができ、従来のＰＭＴの動作周波数９９．２ＭＨｚと比べて３．１４倍高速化できる。そして、図１２（ｂ）に示すように、マージツリーＭＴのスループットは、レコード数Ｅが３２の場合、６１７．９Ｇｂ／ｓを示し、従来のＰＭＴのスループット１９７．１Ｇｂ／ｓと比べて３．１３倍増大できる。
【０１０６】
以上の詳細な説明により、実施形態の特徴点および利点は明らかになるであろう。これは、特許請求の範囲が、その精神および権利範囲を逸脱しない範囲で前述のような実施形態の特徴点および利点にまで及ぶことを意図する。また、当該技術分野において通常の知識を有する者であれば、あらゆる改良および変更に容易に想到できるはずであり、発明性を有する実施形態の範囲を前述したものに限定する意図はなく、実施形態に開示された範囲に含まれる適当な改良物および均等物によることも可能である。
【符号の説明】
【０１０７】
１０，２０…ＦＩＦＯ；３０…選択部；３１，６０（１）−６０（４）…比較器；３２，７０（１）−７０（５），７０ａ（１）−７０ａ（５），７０ｂ（１）−７０ｂ（５）…ＭＵＸ；４０，４０ａ，４０ｂ…マージネットワーク；５０（１）−５０（３），５０ａ（１）−５０ａ（３）…ソート部；８０（１）−８０（３），８０ａ（１）−８０ａ（３），８０ｂ（１）−８０ｂ（３）…レジスタ；９０（１）−９０（３），９０ａ（１）−９０ａ（３），９０ｂ（１）−９０ｂ（３），９５…レジスタ群；１００，１００Ａ，１００Ｂ…データソート装置；ＣＰ１，ＣＰ２，ＣＰ３…結合器；ＭＴ…マージツリー
【図１】
2018156189.tif 000003
【図２】
2018156189.tif 000004
【図３】
2018156189.tif 000005
【図４】
2018156189.tif 000006
【図５】
2018156189.tif 000007
【図６】
2018156189.tif 000008
【図７】
2018156189.tif 000009
【図８】
2018156189.tif 000010
【図９】
2018156189.tif 000011
【図１０】
2018156189.tif 000012
【図１１】
2018156189.tif 000013
【図１２】
2018156189.tif 000014
【図１３】
2018156189.tif 000015