(57)【要約】      （修正有）【課題】高い動作周波数でレコードをマージする。【解決手段】データに付加された情報に応じてデータが並べられた第１のデータ列と、第１のデータ列と異なる第２のデータ列とのうち第１のデータ列または第２のデータ列のうち先頭からＥ個のデータを出力し、第１のデータ列のＥ個のデータのうち第１の条件を満たす情報が付加された（Ｅ−１）個のデータを第１レジスタに保持し、第２のデータ列のＥ個のデータのうち第１の条件を満たす情報が付加された（Ｅ−１）個のデータを第２レジスタに保持し、付加された情報に基づいて、第１レジスタの（Ｅ−１）個と第２レジスタの（Ｅ−１）個のデータとのうち第１の条件を満たす（Ｅ−１）個のデータを第１ソート部より出力し、付加された情報に基づいて、出力部からのＥ個のデータと、第１ソート部からの（Ｅ−１）個のデータとのうち第１の条件と異なる第２の条件を満たすＥ個のデータを第２ソート部より出力する。【選択図】図１
2018194994.tif 000002
【特許請求の範囲】
【請求項１】
データに付加された情報に応じてデータが並べられた第１のデータ列と、前記第１のデータ列と異なる第２のデータ列とのうち、外部からの指示に応じて前記第１のデータ列または前記第２のデータ列のうち先頭からＥ個のデータを出力する出力部と、
出力された前記第１のデータ列の前記Ｅ個のデータのうち、第１の条件を満たす前記情報が付加された（Ｅ−１）個のデータを保持する第１レジスタと、
出力された前記第２のデータ列の前記Ｅ個のデータのうち、前記第１の条件を満たす前記情報が付加された（Ｅ−１）個のデータを保持する第２レジスタと、
付加された前記情報に基づいて、前記第１レジスタに保持された（Ｅ−１）個と前記第２レジスタに保持された（Ｅ−１）個のデータとのうち、前記第１の条件を満たす（Ｅ−１）個のデータを出力する第１ソート部と、
付加された前記情報に基づいて、前記出力部により出力された前記Ｅ個のデータと、前記第１ソート部により出力された前記（Ｅ−１）個のデータとのうち、前記第１の条件と異なる第２の条件を満たすＥ個のデータを出力する第２ソート部と
を備えることを特徴とするデータソート装置。
【請求項２】
請求項１に記載のデータソート装置において、
前記出力部と前記第２ソート部との間に、少なくとも１つの第３レジスタをさらに備え、
前記第１ソート部は、ソート対象のデータを保持する少なくとも１つの第４レジスタをさらに備え、
前記第２ソート部は、ソート対象のデータを保持する少なくとも１つの第５レジスタをさらに備え、
前記第３レジスタの数と前記第４レジスタの数とは同じである
ことを特徴とするデータソート装置。
【請求項３】
請求項１または請求項２に記載のデータソート装置において、
前記第１の条件は、前記情報として整数がデータに付加され、前記データソート装置が付加された前記整数の昇順または降順にデータをソートする場合、最も大きいまたは最も小さい前記整数であり、
前記第２の条件は、前記情報として整数がデータに付加され、前記データソート装置が付加された前記整数の昇順または降順にデータをソートする場合、最も小さいまたは最も大きい前記整数である
ことを特徴とするデータソート装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データソート装置に関する。
【背景技術】
【０００２】
データに付加された整数に応じてデータ（以下、“レコード”とも称される）を並べるソーティングは、データ解析やデータベース処理等の様々なアプリケーションで用いられている。
【０００３】
また、ＦＰＧＡ（Field-Programmable Gate Array）やＡＳＩＣ（Application Specific Integrated Circuit）等を用いて、データに付加された整数に基づいてデータがソートされた２つのレコードの列を、１つのレコードの列にマージするマージネットワークが提案されている（例えば、非特許文献１−３参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Susumu Mashimo, Thiem Van Chu, and Kenji Kise, "High-Performance Hardware Marge Sorter ", IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM 2017), (April 2017).
【非特許文献２】齋藤誠, 眞下達, Thiem Van Chu, 吉瀬謙二, "FPGAソーティングアクセラレータのためのマージネットワークの改良", 電子情報通信学会研究報告RECONF2016-42, pp.13-18 (November 2016).
【非特許文献３】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).
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来では、動作周波数の各サイクルにおいて、マージされなかったレコードは、フィードバックされ、次のサイクルに入力されるレコードと合わせてマージされる。そして、フィードバックの処理は、フィードバックされたレコードと次のサイクルに入力されるレコードとに付加された整数を比較する処理を含むため、マージネットワークの動作周波数を制限するクリティカルパス（Critical Path）となる場合がある。
【０００６】
このため、マージネットワークのスループットは、マージネットワークの動作周波数と、１サイクルにマージ可能なレコードの数Ｅ（以下、“レコード数Ｅ”とも称される）との積に比例することから、フィードバックの処理により低下することがある。
【０００７】
本発明は、従来と比べて高い動作周波数でレコードをマージできるデータソート装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明を例示するデータソート装置の一態様は、データに付加された情報に応じてデータが並べられた第１のデータ列と、第１のデータ列と異なる第２のデータ列とのうち、外部からの指示に応じて第１のデータ列または第２のデータ列のうち先頭からＥ個のデータを出力する出力部と、出力された第１のデータ列のＥ個のデータのうち、第１の条件を満たす情報が付加された（Ｅ−１）個のデータを保持する第１レジスタと、出力された第２のデータ列のＥ個のデータのうち、第１の条件を満たす情報が付加された（Ｅ−１）個のデータを保持する第２レジスタと、付加された情報に基づいて、第１レジスタに保持された（Ｅ−１）個と第２レジスタに保持された（Ｅ−１）個のデータとのうち、第１の条件を満たす（Ｅ−１）個のデータを出力する第１ソート部と、付加された情報に基づいて、出力部により出力されたＥ個のデータと、第１ソート部により出力された（Ｅ−１）個のデータとのうち、第１の条件と異なる第２の条件を満たすＥ個のデータを出力する第２ソート部とを備える。
【発明の効果】
【０００９】
本発明は、従来と比べて高い動作周波数でレコードをマージできる。
【図面の簡単な説明】
【００１０】
【図１】データソート装置の一実施形態を示す図である。
【図２】図１に示した第１ソート部の一例を示す図である。
【図３】図１に示した第２ソート部の一例を示す図である。
【図４】既存の回路の一例を示す図である。
【図５】図１に示したデータソート装置におけるマージ処理の一例を示す図である。
【図６】図５に示したマージ処理の続きを示す図である。
【図７】図６に示したマージ処理の続きを示す図である。
【図８】図７に示したマージ処理の続きを示す図である。
【図９】データソート装置の別の実施形態を示す図である。
【図１０】図９に示した第１ソート部の一例を示す図である。
【図１１】図９に示した第２ソート部の一例を示す図である。
【図１２】図１および図９に示したデータソート装置の評価結果の一例を示す図である。
【発明を実施するための形態】
【００１１】
以下、図面を用いて実施形態について説明する。
【００１２】
図１は、データソート装置の一実施形態を示す。
【００１３】
図１に示したデータソート装置１００は、例えば、ＦＩＦＯ（First-In First-Out）１０、２０およびマージ部３０を有するＦＰＧＡやＡＳＩＣ等である。
【００１４】
ＦＩＦＯ１０、２０は、例えば、外部のコンピュータ装置や、ハードディスク装置等の記憶装置、あるいはネットワーク等からレコードの列である第１レコード列および第２レコード列をそれぞれ受信し、受信した順序でレコードを保持する。そして、ＦＩＦＯ１０、２０は、例えば、マージ部３０の動作に応じて、第１レコード列または第２レコード列のうち先頭からレコード数Ｅのレコードをマージ部３０に出力する。
【００１５】
なお、図１に示したＦＩＦＯ１０、２０は、レコード数Ｅが“４”の場合を示し、４つのレコードを並列にマージ部３０に出力する。しかしながら、ＦＩＦＯ１０、２０は、レコード数Ｅが４以外のレコード数Ｅのレコードを並列にマージ部３０に出力してもよい。
【００１６】
また、レコードは、３２ビット等のデータ長の文字や数字等を含むデータが格納されるデータ領域と、３２ビット等のデータ長の整数が格納されるキー領域とを有する。
【００１７】
また、第１レコード列および第２レコード列は、各レコードのキー領域の整数に基づいて、予め昇順にレコードがソートされる。なお、第１レコード列および第２レコード列は、各レコードのキー領域の整数に基づいて降順にレコードがソートされてもよく、所定の順序でレコードがソートされてもよい。
【００１８】
また、第１レコード列および第２レコード列のレコードのキー領域には、浮動小数点や文字列等の情報が格納されてもよい。この場合、第１レコード列および第２レコード列は、予め決められた所定の順序でレコードがソートされることか好ましい。
【００１９】
マージ部３０は、例えば、マルチプレクサ（ＭＵＸ：multiplexer）４０、レジスタ５０、６０、第１ソート部７０および第２ソート部８０を有する。
【００２０】
ＭＵＸ４０は、データソート装置１００に含まれるプロセッサ等の制御部による制御指示の信号や、外部のコンピュータ装置等からの指示の信号に基づいて、ＦＩＦＯ１０またはＦＩＦＯ２０に対して、第１レコード列または第２レコード列のうち先頭から４個（レコード数Ｅ）のレコードをマージ部３０に出力させる。そして、ＭＵＸ４０は、受信した４個のレコードを第２ソート部８０に出力する。ＭＵＸ４０は、出力部の一例である。
【００２１】
なお、データソート装置１００の制御部や外部のコンピュータ装置等は、ＦＩＦＯ１０およびＦＩＦＯ２０に保持される第１レコード列および第２レコード列を監視し、各レコード列のレコードの各々におけるキー領域の整数を示す情報を予め取得することが好ましい。そして、データソート装置１００の制御部や外部のコンピュータ装置等は、取得した情報に基づいて先頭のレコードのキー領域に格納された整数が小さい第１レコード列または第２レコード列を示す制御指示の信号をＭＵＸ４０に出力する。そして、ＭＵＸ４０は、ＦＩＦＯ１０またはＦＩＦＯ２０に対して、第１レコード列または第２レコード列のうち先頭からレコード数Ｅのレコードをマージ部３０に出力させる。
【００２２】
また、データソート装置１００は、ＦＩＦＯ１０に保持された第１レコード列における先頭のレコードの整数と、ＦＩＦＯ２０に保持された第２レコード列における先頭のレコードの整数とを比較器等を有してもよい。そして、ＭＵＸ４０は、比較器等により比較の結果に基づいて、ＦＩＦＯ１０またはＦＩＦＯ２０に対し、第１レコード列または第２レコード列のうち先頭からレコード数Ｅのレコードをマージ部３０に出力させてもよい。
【００２３】
レジスタ５０は、図１に示したデータソート装置１００が昇順にレコードをソートする場合、ＦＩＦＯ１０により出力された４個のレコードのうち、最も大きい整数がキー領域に格納されたレコード数（Ｅ−１）、すなわち３個のレコードを保持する。そして、レジスタ５０は、保持する３個のレコードを第１ソート部７０に出力する。レジスタ５０は、第１レジスタの一例である。また、最も大きい整数の条件は、第１の条件の一例である。
【００２４】
なお、レジスタ５０は、レコードのキー領域に浮動小数点が格納されている場合にも、最も大きい浮動小数点がキー領域に格納されたレコード数（Ｅ−１）のレコードを保持することが好ましい。
【００２５】
また、データソート装置１００が降順にレコードをソートする場合、レジスタ５０は、ＦＩＦＯ１０により出力されたレコード数Ｅのレコードのうち、最も小さい整数や浮動小数点がキー領域に格納されたレコード数（Ｅ−１）のレコードを保持することが好ましい。また、レコードのキー領域に文字列等の情報が格納されている場合、レジスタ５０は、ＦＩＦＯ１０により出力されたレコード数Ｅのレコードのうち、データソート装置１００に設定された所定の条件を満たすレコード数（Ｅ−１）のレコードを保持することが好ましい。
【００２６】
レジスタ６０は、レジスタ５０と同様に、ＦＩＦＯ２０により出力された４個のレコードのうち、最も大きい整数がキー領域に格納された３個のレコードを保持する。そして、レジスタ６０は、保持する３個のレコードを第１ソート部７０に出力する。レジスタ６０は、第２レジスタの一例である。
【００２７】
第１ソート部７０は、レコードのキー領域に格納された整数に基づいて、レジスタ５０に保持された３個のレコードと、レジスタ６０に保持された３個のレコードとを、キー領域の整数が最も大きい順にソートする。そして、第１ソート部７０は、ソートしたレコードのうち最も大きい整数がキー領域に格納された３個のレコードを第２ソート部８０に出力する。第１ソート部７０の動作については、図２、図５から図８で説明する。
【００２８】
第２ソート部８０は、レコードのキー領域に格納された整数に基づいて、ＭＵＸ４０から受信した４個のレコードと、第１ソート部７０から受信した３個のレコードとを、キー領域の整数が最も小さい順にソートする。そして、第２ソート部８０は、ソートしたレコードのうち最も小さい整数がキー領域に格納された４個のレコードを、送信先である外部のコンピュータ装置やネットワーク等に出力する。第２ソート部８０の動作については、図３から図８で説明する。また、最も小さい整数の条件は、第２の条件の一例である。
【００２９】
図２は、図１に示した第１ソート部７０の一例を示す。図２（ａ）は、第１ソート部７０の回路の一例を示し、図２（ｂ）は、第１ソート部７０に含まれるロジック回路の一例を示す。なお、図２は、入力されるレコード数（Ｅ−１）が３個の場合を示すが、第１ソート部７０は、３以外のレコード数（Ｅ−１）の場合でも同様に動作する。
【００３０】
図２（ａ）に示すように、第１ソート部７０は、６つのロジック回路７１（７１（１）−７１（６））と、６つのロジック回路７２（７２（１）−７２（６））とを有する。ロジック回路７１（１）とロジック回路７２（１）、ロジック回路７１（２）とロジック回路７２（２）、およびロジック回路７１（３）とロジック回路７２（３）との一対の各々は、協働して動作する。また、ロジック回路７１（４）とロジック回路７２（４）、ロジック回路７１（５）とロジック回路７２（５）、およびロジック回路７１（６）とロジック回路７２（６）との一対の各々は、協働して動作する。
【００３１】
図２（ｂ）に示すように、例えば、ロジック回路７１は、比較器９０およびＭＵＸ９１を有し、ロジック回路７２は、比較器９２およびＭＵＸ９３を有する。
【００３２】
比較器９０は、一対のロジック回路７１、７２の各々に入力された２つのレコードのキー領域に格納された整数を比較する。そして、比較器９０は、小さい整数がキー領域に格納されたレコードを示す信号をＭＵＸ９１に出力する。ＭＵＸ９１は、比較器９０からの信号に基づいて、小さい整数がキー領域に格納されたレコードを出力する。一方、比較器９２は、一対のロジック回路７１、７２の各々に入力された２つのレコードのキー領域に格納された整数を比較する。そして、比較器９２は、大きい整数がキー領域に格納されたレコードを示す信号をＭＵＸ９３に出力する。ＭＵＸ９３は、比較器９２からの信号に基づいて、大きい整数がキー領域に格納されたレコードを出力する。
【００３３】
すなわち、一対のロジック回路７１、７２は、入力された２つのレコードのうち小さい整数がキー領域に格納されたレコードをロジック回路７１から出力し、大きい整数がキー領域に格納されたレコードをロジック回路７２から出力する。これにより、第１ソート部７０は、６組のロジック回路７１、７２を用いて、レジスタ５０からの３個のレコードと、レジスタ６０からの３個のレコードとを、キー領域に格納された整数が大きい順にソートする。第１ソート部７０は、ソートしたレコードのうち最も大きい整数がキー領域に格納された３個のレコードを第２ソート部８０に出力する。
【００３４】
なお、ロジック回路７１（１）、７１（２）、７１（６）は、小さい整数がキー領域に格納されたレコードを出力するが、第１ソート部７０のソート処理に用いられないことを示す。また、２つのレコードのキー領域に格納された整数が同じ場合、ロジック回路７１は、一方のレコードを出力し、ロジック回路７２は、他方のレコードを出力することが好ましい。
【００３５】
また、データソート装置１００が降順にレコードをソートする場合、ロジック回路７１は、入力された２つのレコードのうち大きい整数がキー領域に格納されたレコードを出力し、ロジック回路７２は、小さい整数がキー領域に格納されたレコードを出力することが好ましい。また、レコードのキー領域に文字列等が格納される場合、ロジック回路７１は、入力された２つのレコードのうち、予め設定された条件に応じた一方のレコードを出力し、ロジック回路７２は、他方のレコードを出力することが好ましい。
【００３６】
図３は、図１に示した第２ソート部８０の一例を示す。図３に示すように、第２ソート部８０は、例えば、図２に示したロジック回路７１とロジック回路７２とを用い、７組のロジック回路７１（７１（７）−７１（１３））とロジック回路７２（７２（７）−７２（１３））とを有する。
【００３７】
第２ソート部８０は、ＭＵＸ４０からの４個のレコードと、第１ソート部７０からの３個のレコードとのうち、キー領域に格納されている整数が小さい順にソートする。第２ソート部８０は、ソートしたレコードのうち最も小さい整数がキー領域に格納された４個のレコードを、送信先である外部のコンピュータ装置やネットワーク等に出力する。
【００３８】
なお、第２ソート部８０は、例えば、A. Farmahini-Farahani, H.J. Duwe III, M.J. Schulte, and K. Compton, "Modular design of high-throughput, low-frequency sorting units", IEEE Transcriptions on Computers, vol. 62, no. 7, pp. 1389-1402, 2013等の回路（以下、“既存の回路”とも称される）を用いて動作させてもよい。しかしながら、図３に示すように、第２ソート部８０において、ＭＵＸ４０からのレコードのレコード数Ｅと、第１ソート部７０からのレコードのレコード数（Ｅ−１）との数が異なる。一方、既存の回路は、ＭＵＸ４０からのレコードのレコード数Ｅを受信する入力端子の数と、第１ソート部７０からのレコードのレコード数（Ｅ−１）を受信する入力端子の数とが同じ場合がある。
【００３９】
図４は、既存の回路の一例を示す。図４に示すように、既存の回路は、例えば、図３に示した第２ソート部８０の回路に、ロジック回路７１（１４）、７２（１４）の一組がさらに設けられ、第１ソート部７０からの３個のレコードを受信する入力端子を４つ有する。そこで、既存の回路を第２ソート部８０として動作させるために、ロジック回路７２（１４）に接続された入力端子には、例えば、ソートされるレコードのキー領域の整数と比べて十分大きな整数がキー領域に格納されたダミーのレコードが常に入力されることが好ましい。
【００４０】
図５から図８は、図１に示したデータソート装置１００におけるマージ処理の一例を示す。図５は、マージ処理の開始時におけるデータソート装置１００の初期状態を示す。図６から図８は、マージ処理の開始から１サイクル経過する毎のデータソート装置１００の状態を示す。なお、図５から図８では、データソート装置１００によりマージされるレコードを、レコードのキー領域に格納された整数で示す。また、図５から図８では、第１ソート部７０および第２ソート部８０の構成を省略する。
【００４１】
図５に示すように、データソート装置１００の初期状態は、例えば、キー領域に整数“０”が格納されたＮＵＬＬデータが、レジスタ５０、６０の各々に保持される。
【００４２】
また、データソート装置１００に入力される第１レコード列は、例えば、キー領域に格納される整数が１、３、５…、（２Ｎ＋１）の順に予めソートされたレコードの列である（Ｎは正の整数）。また、第２レコード列は、キー領域に格納される整数が２、４、６…、２Ｎの順に予めソートされたレコードの列である。すなわち、図５に示すように、マージ処理の開始時では、ＦＩＦＯ１０に保持される第１レコード列の先頭のレコードのキー領域の整数は“１”であり、ＦＩＦＯ２０に保持される第２レコード列の先頭のレコードのキー領域の整数は“２”である。
【００４３】
図６に示すように、マージ処理の開始から１サイクル目において、ＭＵＸ４０は、データソート装置１００の制御部や外部のコンピュータ装置等からの指示に基づいて、先頭のレコードの整数が小さい第１レコード列を選択する。そして、ＭＵＸ４０は、整数“１”、“３”、“５”、“７”の各々がキー領域に格納された４個のレコードをＦＩＦＯ１０からマージ部３０に出力させる。ＭＵＸ４０は、受信した４個のレコードを第２ソート部８０に出力する。また、ＦＩＦＯ１０は、出力した４個のレコードのうち、整数“３”、“５”、“７”がキー領域に格納された３個のレコードを、レジスタ５０にも出力する。
【００４４】
第１ソート部７０は、レジスタ５０に保持され整数“０”、“０”、“０”がキー領域に格納された３個のレコードと、レジスタ６０に保持され整数“０”、“０”、“０”がキー領域に格納された３個のレコードとを、キー領域の整数が大きい順にソートする。そして、第１ソート部７０は、ソートしたレコードのうち最も大きい整数がキー領域に格納された３個のレコードを第２ソート部８０に出力する。なお、マージ処理の開始時において、レジスタ５０、６０に保持されるレコードのキー領域の整数は、全て“０”であることから、第１ソート部７０は、いずれか３個のレコードを第２ソート部８０に出力する。
【００４５】
第２ソート部８０は、ＭＵＸ４０から受信した整数“１”、“３”、“５”、“７”の各々がキー領域に格納された４個のレコードと、第１ソート部７０から受信した整数“０”、“０”、“０”の各々がキー領域に格納された３個のレコードとを、キー領域の整数が小さい順にソートする。そして、第２ソート部８０は、ソートしたレコードのうち最も小さい整数“０”、“０”、“０”、“１”の各々がキー領域に格納された４個のレコードを、送信先である外部のコンピュータ装置やネットワーク等に出力する。
【００４６】
図７に示すように、マージ処理の開始から２サイクル目において、ＭＵＸ４０は、データソート装置１００の制御部や外部のコンピュータ装置等からの指示に基づいて、先頭のレコードの整数が小さい第２レコード列を選択する。そして、ＭＵＸ４０は、整数“２”、“４”、“６”、“８”の各々がキー領域に格納された４個のレコードをＦＩＦＯ２０からマージ部３０に出力させる。ＭＵＸ４０は、受信した４個のレコードを第２ソート部８０に出力する。また、ＦＩＦＯ２０は、出力した４個のレコードのうち、最も大きい整数“４”、“６”、“８”がキー領域に格納された３個のレコードを、レジスタ６０にも出力する。
【００４７】
第１ソート部７０は、レジスタ５０に保持され整数“３”、“５”、“７”がキー領域に格納された３個のレコードと、レジスタ６０に保持され整数“０”、“０”、“０”がキー領域に格納された３個のレコードとを、キー領域の整数が大きい順にソートする。そして、第１ソート部７０は、ソートしたレコードのうち最も大きい整数“３”、“５”、“７”がキー領域に格納された３個のレコードを第２ソート部８０に出力する。
【００４８】
第２ソート部８０は、ＭＵＸ４０から受信した整数“２”、“４”、“６”、“８”の各々がキー領域に格納された４個のレコードと、第１ソート部７０から受信した整数“３”、“５”、“７”の各々がキー領域に格納された３個のレコードとを、キー領域の整数が小さい順にソートする。そして、第２ソート部８０は、ソートしたレコードのうち最も小さい整数“２”、“３”、“４”、“５”がキー領域に格納された４個のレコードを、外部のコンピュータ装置やネットワーク等に出力する。
【００４９】
図８に示すように、ソート処理の開始から３サイクル目において、ＭＵＸ４０は、データソート装置１００の制御部や外部のコンピュータ装置等からの指示に基づいて、先頭のレコードの整数が小さい第１レコード列を選択する。そして、ＭＵＸ４０は、整数“９”、“１１”、“１３”、“１５”の各々がキー領域に格納された４個のレコードをＦＩＦＯ１０からマージ部３０に出力させる。ＭＵＸ４０は、受信した４個のレコードを第２ソート部８０に出力する。また、ＦＩＦＯ１０は、出力した４個のレコードのうち、最も大きい整数“１１”、“１３”、“１５”がキー領域に格納された３個のレコードを、レジスタ５０にも出力する。
【００５０】
第１ソート部７０は、レジスタ５０に保持され整数“３”、“５”、“７”がキー領域に格納された３個のレコードと、レジスタ６０に保持され整数“４”、“６”、“８”がキー領域に格納された３個のレコードとを、キー領域の整数が大きい順にソートする。そして、第１ソート部７０は、ソートしたレコードのうち最も大きい整数“６”、“７”、“８”がキー領域に格納された３個のレコードを第２ソート部８０に出力する。
【００５１】
第２ソート部８０は、ＭＵＸ４０から受信した整数“９”、“１１”、“１３”、“１５”の各々がキー領域に格納された４個のレコードと、第１ソート部７０から受信した整数“６”、“７”、“８”の各々がキー領域に格納された３個のレコードとを、キー領域の整数が小さい順にソートする。そして、第２ソート部８０は、ソートしたレコードのうち最も小さい整数“６”、“７”、“８”、“９”がキー領域に格納された４個のレコードを、外部のコンピュータ装置やネットワーク等に出力する。
【００５２】
そして、データソート装置１００は、第１レコード列および第２レコード列が入力される度に、図６から図８に示したソート処理を繰り返し実行する。
【００５３】
以上、図１から図８に示した実施形態では、レコード数Ｅのレコードは、第２ソート部８０に出力されるとともに、レコード数Ｅのレコードのうち最も大きな整数がキー領域に格納されたレコード数（Ｅ−１）のレコードがレジスタ５０またはレジスタ６０に出力される。第１ソート部７０は、レジスタ５０に保持されたレコード数（Ｅ−１）のレコードと、レジスタ６０に保持されたレコード数（Ｅ−１）のレコードとを、キー領域の整数が大きい順にソートする。そして、第１ソート部７０は、ソートしたレコードのうち最も大きい整数がキー領域に格納されたレコード数（Ｅ−１）のレコードを第２ソート部８０に出力する。これにより、データソート装置１００は、従来のフィードバックの処理を省略でき、従来と比べて高い動作周波数でレコードをマージできる。
【００５４】
また、データソート装置１００は、レコード数Ｅを増加させる場合、第１ソート部７０および第２ソート部８０において直列に接続される一対のロジック回路７１、７２の数を増加させるだけでよい。これにより、データソート装置１００は、マージ部３０の回路を複雑にすることなく、クリティカルパスにおける各レコードのゲート段数を一定にでき、動作周波数の低下を回避できる。
【００５５】
図９は、データソート装置の別の実施形態を示す。図１で説明した要素と同一または同様の機能を有する要素については、同一または同様の符号を付し、これらについては、詳細な説明を省略する。
【００５６】
図９に示したデータソート装置１００Ａは、例えば、ＦＩＦＯ１０、２０およびマージ部３０ａを有するＦＰＧＡやＡＳＩＣ等である。
【００５７】
マージ部３０ａは、例えば、ＭＵＸ４０、レジスタ５０、５５（１）−５５（２）、６０、第１ソート部７０ａおよび第２ソート部８０ａを有する。
【００５８】
ＭＵＸ４０は、データソート装置１００Ａに含まれるプロセッサ等の制御部による制御指示の信号や、外部のコンピュータ装置等からの指示の信号に基づいて、ＦＩＦＯ１０またはＦＩＦＯ２０に対して、第１レコード列または第２レコード列のうち先頭から４個（レコード数Ｅ）のレコードをマージ部３０ａに出力させる。そして、ＭＵＸ４０は、受信した４個のレコードをレジスタ５５（１）に出力する。
【００５９】
レジスタ５５（５５（１）−５５（２））は、ＭＵＸ４０により出力された４個のレコードを順次に保持し、４個のレコードが第２ソート部８０ａに出力されるタイミングと、第１ソート部７０ａの３個（レコード数（Ｅ−１））のレコードが第２ソート部８０ａに出力されるタイミングとを一致させる。すなわち、レジスタ５５は、パイプラインレジスタとして動作する。レジスタ５５は、第３レジスタの一例である。
【００６０】
第１ソート部７０ａは、図１に示した第１ソート部７０と同様に、レコードのキー領域に格納された整数に基づいて、レジスタ５０に保持された３個のレコードと、レジスタ６０に保持された３個のレコードとを、キー領域の整数が最も大きい順にソートする。そして、第１ソート部７０ａは、ソートしたレコードのうち最も大きい整数がキー領域に格納された３個のレコードを第２ソート部８０ａに出力する。第１ソート部７０ａの動作については、図１０で説明する。
【００６１】
第２ソート部８０ａは、図１に示した第２ソート部８０と同様に、レコードのキー領域に格納された整数に基づいて、レジスタ５５（２）から受信した４個のレコードと、第１ソート部７０ａから受信した３個のレコードとを、キー領域の整数が最も小さい順にソートする。そして、第２ソート部８０ａは、ソートしたレコードのうち最も小さい整数がキー領域に格納された４個のレコードを、送信先である外部のコンピュータ装置やネットワーク等に出力する。第２ソート部８０ａの動作については、図１１で説明する。
【００６２】
図１０は、図９に示した第１ソート部７０ａの一例を示す。図２で説明した要素と同一または同様の機能を有する要素については、同一または同様の符号を付し、これらについては、詳細な説明を省略する。なお、図１０は、入力されるレコード数（Ｅ−１）が３個の場合を示すが、第１ソート部７０ａは、３以外のレコード数（Ｅ−１）の場合でも同様に動作する。
【００６３】
図１０に示すように、第１ソート部７０ａは、図２に示した第１ソート部７０と同様に、６組のロジック回路７１とロジック回路７２とを有する。また、第１ソート部７０ａは、４個のレコードを保持するレジスタ７４、７５を有し、パイプラインレジスタとして動作する。そして、レジスタ７４、７５が配置されることにより、第１ソート部７０ａにおけるクリティカルパスを短くすることができ、データソート装置１００Ａにおける動作周波数を高くすることができる。レジスタ７４、７５は、第４レジスタの一例である。
【００６４】
なお、図１０では、第１ソート部７０ａは、２つのレジスタ７４、７５を有するが、レジスタ５０およびレジスタ６０から入力されるレコードのレコード数（Ｅ−１）に応じて、２以外の少なくとも１つのレジスタを有してもよい。また、レジスタ５５の数は、第１ソート部７０に設けられるレジスタ７４、７５の数と同じになるように調整されることが好ましい。これにより、レジスタ５５が４個のレコードを第２ソート部８０ａに出力するタイミングと、第１ソート部７０ａが３個のレコードを第２ソート部８０ａに出力するタイミングとを一致させることができる。
【００６５】
図１１は、図９に示した第２ソート部８０ａの一例を示す。図１１に示すように、第２ソート部８０ａは、図３に示した第２ソート部８０と同様に、７組のロジック回路７１とロジック回路７２とを有する。また、第２ソート部８０ａは、４個のレコードを保持するレジスタ８１、８２を有し、パイプラインレジスタとして動作する。そして、レジスタ８１、８２が配置されることにより、第２ソート部８０ａにおけるクリティカルパスを短くすることができ、データソート装置１００Ａにおける動作周波数を高くすることができる。レジスタ８１、８２は、第５レジスタの一例である。
【００６６】
なお、図１１では、第２ソート部８０ａは、２つのレジスタ８１、８２を有するが、ＭＵＸ４０および第１ソート部７０ａからのレコードのレコード数に応じて、２以外の少なくとも１つのレジスタを有してもよい。
【００６７】
なお、データソート装置１００Ａにおけるマージ処理は、レジスタ５５、７４、７５、８１、８２が設けられることによりクリティカルパスが短くできる、すなわち動作周波数を高くできる点を除き、図５から図８に示したデータソート装置１００におけるソート処理と同様であり、詳細な説明は省略する。
【００６８】
以上、図９から図１１に示した実施形態では、レコード数Ｅのレコードは、第２ソート部８０ａに出力されるとともに、レコード数Ｅのレコードのうち最も大きな整数がキー領域に格納されたレコード数（Ｅ−１）のレコードがレジスタ５０またはレジスタ６０に出力される。第１ソート部７０ａは、レジスタ５０に保持されたレコード数（Ｅ−１）のレコードと、レジスタ６０に保持されたレコード数（Ｅ−１）のレコードとを、キー領域の整数が大きい順にソートする。そして、第１ソート部７０ａは、ソートしたレコードのうち最も大きい整数がキー領域に格納されたレコード数（Ｅ−１）のレコードを第２ソート部８０ａに出力する。これにより、データソート装置１００Ａは、従来のフィードバックの処理を省略でき、従来と比べて高い動作周波数でレコードをマージできる。
【００６９】
また、データソート装置１００Ａは、レコード数Ｅを増加させる場合、第１ソート部７０ａおよび第２ソート部８０ａにおいて直列に接続される一対のロジック回路７１、７２の数を増加させるだけでよい。これにより、データソート装置１００Ａは、マージ部３０ａの回路を複雑にすることなく、クリティカルパスにおける各レコードのゲート段数を一定にでき、動作周波数の低下を回避できる。
【００７０】
また、データソート装置１００Ａは、レジスタ５５、７４、７５、８１、８２が設けられることにより、第１ソート部７０ａおよび第２ソート部８０ａにおけるクリティカルパスが短くでき、ソート処理の動作周波数を高くできる。
【００７１】
図１２は、図１および図９に示したデータソート装置１００、１００Ａの評価結果の一例を示す。図１２は、入力されるレコード数Ｅが３２の場合におけるデータソート装置１００、１１０Ａの動作周波数を示す。図１２の縦軸は、動作周波数を示し、横軸はデータソート装置１００、１００Ａを示す。また、図１２では、従来技術として、W. Song, D. Koch, M. Luj'an, and J. Garside, "Parallel hardware marge sorter", in FCCM, 2016のParallel Mage-Tree（ＰＭＴ）の結果も示す。
【００７２】
図１２に示すように、図１に示したデータソート装置１００は、フィードバックの処理が省略されることにより、ＰＭＴと比べて２．６倍の動作周波数でマージ処理を実行できる。また、図９に示したデータソート装置１００Ａは、フィードバックの処理の省略およびパイプライン化により、ＰＭＴと比べて３．５倍の動作周波数でマージ処理を実行できる。
【００７３】
以上の詳細な説明により、実施形態の特徴点および利点は明らかになるであろう。これは、特許請求の範囲が、その精神および権利範囲を逸脱しない範囲で前述のような実施形態の特徴点および利点にまで及ぶことを意図する。また、当該技術分野において通常の知識を有する者であれば、あらゆる改良および変更に容易に想到できるはずであり、発明性を有する実施形態の範囲を前述したものに限定する意図はなく、実施形態に開示された範囲に含まれる適当な改良物および均等物によることも可能である。
【符号の説明】
【００７４】
１０，２０…ＦＩＦＯ；３０，３０ａ…マージ部；４０，９１，９３…ＭＵＸ；５０，５５（１）−５５（２），６０，７４，７５，８１，８２…レジスタ；７０，７０ａ…第１ソート部；７１（１）−７１（１４），７２（１）−７２（１４）…ロジック回路；８０，８０ａ…第２ソート部；１００，１００Ａ…データソート装置
【図１】
2018194994.tif 000003
【図２】
2018194994.tif 000004
【図３】
2018194994.tif 000005
【図４】
2018194994.tif 000006
【図５】
2018194994.tif 000007
【図６】
2018194994.tif 000008
【図７】
2018194994.tif 000009
【図８】
2018194994.tif 000010
【図９】
2018194994.tif 000011
【図１０】
2018194994.tif 000012
【図１１】
2018194994.tif 000013
【図１２】
2018194994.tif 000014