(57)【要約】  【課題】  単一コンパレータでプル・スケジューリングのソータを提供すること。  【解決手段】  複数段のバッファ・キューをもち、下段から1/N(Nは好適には2mで、mは2以上の整数)ずつ減らしながら上段に伝播することによりデータを処理する装置であって、隣接する段のバッファ・キューの間に配置され、バッファ・キューの対のエントリを比較して、比較結果に基づき上段のバッファに値を上げる、単一のコンパレータを有し、各コンパレータが比較すべきバッファ・キューの対のエントリの位置の指定を上段から受け取り、下段へ指定を行う装置が提供される。この構成の典型的な応用例は、ソータである。さらに、各コンパレータが比較すべきバッファ・キューの対のエントリの位置の指定を、上段から受け取って格納する、複数段のインデックス・キューが設けられる。【選択図】  図４
2014126931.tif 000002
【特許請求の範囲】
【請求項１】
複数段のバッファ・キューをもち、下段から1/N(Nは2以上の整数)ずつ減らしながら上段に伝播することによりデータを処理する装置であって、
隣接する段のバッファ・キューの間に配置され、バッファ・キューの対のエントリを比較して、比較結果に基づき上段のバッファに値を上げる、単一のコンパレータを有し、
各コンパレータが比較すべきバッファ・キューの対のエントリの位置の指定を上段から受け取り、下段へ指定を行う、
装置。
【請求項２】
各コンパレータが比較すべきバッファ・キューの対のエントリの位置の指定を、上段から受け取って格納する、複数段のインデックス・キューをさらに有する、請求項１に記載の装置。
【請求項３】
前記対のエントリがどちらも空でなく、下位段のインデックス・キューが満杯でないことに応答して、前記コンパレータを動作させて前記対のエントリの一方の内容を上位段に送出するとともに、該一方の内容を除去し、該一方のエントリのインデックスに対するリクエストを下段に送る手段をさらに有し、
当該段のインデックス・キューの最初の要素をポップする手段をさらに有する、請求項２に記載の装置。
【請求項４】
前記対のエントリがどちらかが空であることに応答して、空のエントリのインデックスに対するリクエストを下段に送る手段をさらに有する、請求項１に記載の装置。
【請求項５】
前記バッファ・キューのサイズと、その直下の前記インデックス・キューのサイズが等しい、請求項２に記載の装置。
【請求項６】
上位段からのリクエストを受け取ることのレイテンシをサイクル数でLとしたとき、バッファ・キューが決して空にならないように、バッファ・キューのサイズは、L+1以上とされる、請求項５に記載の装置。
【請求項７】
前記Nが、2または4である、請求項１に記載の装置。
【請求項８】
前記装置が、ソータである、請求項１に記載の装置。
【請求項９】
前記装置が、ハードウェアにより実装されている、請求項１に記載の装置。
【請求項１０】
前記装置が、FPGAにより実装される、請求項９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数段のバッファ・キューをもち、下段からから上段にデータを送りながら処理するデータ処理用論理回路装置に関する。その１つの具体例は、FPGAなどによって実装される、ソータである。
【背景技術】
【０００２】
複数段のバッファ・キューをもつソータにおいては、下段からから上段にデータを送り込む際に、データを比較するためのコンパレータ(比較器)を使用する。このようなソータは、複数のコンパレータにより一気にデータを比較する構成をとるが、複数のコンパレータを備えると、ハードウェア・サイズが大きくなるという問題がある。
【０００３】
そこで、ハードウェア・サイズを節約した、下段と上段の間に単一のコンパレータ構成のソータが例えば、Kerming Fleming et al., "High-throughput Pinelined Mergesort", MIT - CSAIL, 2008などによって提案された。しかし、コンパレータが単一だと、どのような順序でコンパレータを適用するかという、スケジューリングが必要になる。
【０００４】
スケジューリングには、下段から上段にデータを送り込むプッシュ・スケジューリングと、上段が下段にデータを要求して引き上げるプル・スケジューリングがある。
【０００５】
しかし、プッシュ・スケジューリングを実現するためには、依然として、比較的大規模のハードウェアが必要になり、レイテンシも大きいという問題があった。
【０００６】
このとき、プッシュ・スケジューリングを、プル・スケジューリングにすることで、ハードウェア・サイズをさらに節約することができる。これによる既知のアルゴリズムは、入力が揃っていて、出力バッファが満杯でないとき、処理を行いデータを移動するというものである。
【０００７】
従来技術として、特開平５−１５１１６６号公報は、受信バッファに記憶された先頭データの、データメモリのインデックスレジスタが指示するメモリデータに対するソート順位の適否を比較部にて比較判断させ、ソート順位「適」の場合には、制御部により上記受信バッファの先頭データを上記インデックスレジスタが指示するメモリデータの前に挿入登録し、ソート順位「否」の場合には、制御部によりインデックスレジスタが指示するメモリデータを次のデータ位置まで更新させ、上記ソート順位適否の比較判断処理が常に最新ソート位置以降のメモリデータを対象にして実施されるよう構成するソータを開示する。
【０００８】
特開平７−１６０４７５号公報は、マージソート処理のマージ対象リスト群生成処理時に，書き出しブロック毎にそのブロックの識別子とそのブロックの代表キー値からなる補助情報を取得して補助情報リストを作成し、次に，補助情報リストを代表キー値に従ってソートし，そのソートされた補助情報リストをサブ補助情報リストに分割し，それぞれを各処理装置に割り当て、各処理装置は自分に割り当てられたサブ補助情報リストに従って並列にマージ処理を行いソート処理を完了する構成を開示する。
【０００９】
特開平１０−３３６２１６号公報は、それぞれソートキーを含むデータ要素をソートするために、記憶手段が、それぞれ要素を含むことが可能であり、０からｎ−１まで番号を付けられたｎ個の連続したステージに分配されていて、ステージｑはノード２ｑから２ｑ＋１−１を有する、２n−１個のノードを有するバイナリツリーにしたがって構成され、要素は、ノードｉに含まれている各要素が、ノード２ｉおよび２ｉ＋１に含まれている要素のソートキーよりも小さいソートキーを有するように、ツリーの中で分散され、それぞれステージ２０qあるいは連続したステージ間にｎ−１個のインタフェース・レジスタ２６qを有するツリー（２≦ｍ≦ｎ）の数個の連続したステージと組み合わされたｍ個の連続したコントローラ２１qによってツリーが管理されるソータを開示する。
【００１０】
しかし、これらの従来技術は、ハードウェア・サイズを節約できる、単一コンパレータでプルスケジューリングのソータの構成を示唆するものではない。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開平５−１５１１６６号公報
【特許文献２】特開平７−１６０４７５号公報
【特許文献３】特開平１０−３３６２１６号公報
【非特許文献】
【００１２】
【非特許文献１】Kerming Fleming et al., "High-throughput Pinelined Mergesort", MIT - CSAIL, 2008
【発明の概要】
【発明が解決しようとする課題】
【００１３】
この発明の目的は、単一コンパレータでプル・スケジューリングのソータを提供することにある。
【００１４】
この発明の他の目的は、単一コンパレータでプル・スケジューリングのソータにおいて、動作時に出力バッファが常に一杯にならないことを保証することによって、デッドロックを回避する技法を提供することにある。
【課題を解決するための手段】
【００１５】
この発明によれば、複数段のバッファ・キューをもち、下段から1/N(Nは好適には2mで、mは1以上の整数)ずつ減らしながら上段に伝播することによりデータを処理する装置であって、隣接する段のバッファ・キューの間に配置され、バッファ・キューの対のエントリを比較して、比較結果に基づき上段のバッファに値を上げる、単一のコンパレータを有し、各コンパレータが比較すべきバッファ・キューの対のエントリの位置の指定を上段から受け取り、下段へ指定を行う装置が提供される。この構成の典型的な応用例は、ソータである。
【００１６】
この発明の1つの側面によれば、各コンパレータが比較すべきバッファ・キューの対のエントリの位置の指定を、上段から受け取って格納する、複数段のインデックス・キューが設けられる。
【００１７】
この発明の別の側面によれば、前記対のエントリがどちらも空でなく、下位段のインデックス・キューが満杯でないことに応答して、前記コンパレータを動作させて前記対のエントリの一方の内容を上位段に送出するとともに、該一方の内容を除去し、該一方のエントリのインデックスに対するリクエストを下段に送る処理と、当該段のインデックス・キューの最初の要素をポップする処理を実行する論理回路が設けられる。
【００１８】
この発明のさらに別の側面によれば、論理回路は、前記対のエントリがどちらかが空であることに応答して、空のエントリのインデックスに対するリクエストを下段に送る機能を実行する。
【００１９】
この発明のさらに別の側面によれば、デッドロック回避のために、バッファ・キューがフル状態の時に更に要素を追加しようとしてオーバーフローすることがないようになされる。さらに、高性能を達成するために、スタートアップ終了時に、バッファ・キューがフルになるように設計される。このため、バッファ・キューのサイズと、インデックス・キューのサイズが等しくなるようになされる。
【００２０】
この発明のさらに別の側面によれば、高性能の達成のため、上位段からのリクエストを受け取ることのレイテンシをサイクル数でLとしたとき、定常状態でバッファ・キューが決して空にならないように、バッファ・キューのサイズは、L+1以上とされる。
【発明の効果】
【００２１】
以上のように、この発明によれば、単一コンパレータでプル・スケジューリングの構成によって、ハードウェア実装した際に、少ないハードウェア消費量で効率的に動作するソータを実現できるという効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】本発明の装置のハードウェア構成のブロック図である。
【図２】本発明の装置のハードウェア構成のブロック図である。
【図３】本発明の装置のハードウェア構成の機能を説明するための図である。
【図４】本発明の装置の機能構成のブロック図である。
【図５】本発明の装置の処理のフローチャートを示す図である。
【図６】本発明の装置のスタートアップ・サイクルの動作を示す図である。
【図７】本発明の装置のスタートアップ・サイクルの動作を示す図である。
【図８】本発明の装置のスタートアップ・サイクルの動作を示す図である。
【図９】本発明の装置のスタートアップ・サイクルの動作を示す図である。
【図１０】本発明の装置のスタートアップ・サイクルの動作を示す図である。
【図１１】本発明の装置のスタートアップ・サイクルの動作を示す図である。
【図１２】本発明の装置のスタートアップ・サイクルの動作を示す図である。
【図１３】本発明の装置のスタートアップ・サイクルの動作を示す図である。
【図１４】本発明の装置の定常サイクルの動作を示す図である。
【図１５】本発明の装置の定常サイクルの動作を示す図である。
【図１６】本発明の装置の定常サイクルの動作を示す図である。
【図１７】本発明の装置の定常サイクルの動作を示す図である。
【図１８】本発明の装置の定常サイクルの動作を示す図である。
【図１９】本発明の装置の定常サイクルの動作を示す図である。
【発明を実施するための形態】
【００２３】
以下、図面に従って、本発明の実施例を説明する。これらの実施例は、本発明の好適な態様を説明するためのものであり、発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断わらない限り、同一符号は、同一の対象を指すものとする。
【００２４】
図１は、本発明の一実施例に係るソータのハードウェア構成のブロック図である。この構成は、FPGA(Field Programmable Gate Array)によって作製されたものである。
【００２５】
このソータの典型的な用途は、ETL(Extract/Transformation/Load)・データベース系の製品で、ETL/データベースエンジンからデータベース・レコードの列を受け取り、特定のキーでソートしてまたETL/データベースエンジンにソート済みレコード列を返す、という使用法である。しかし、これには限定されず、任意のソータとして用いることができる。
【００２６】
また、この実施例では４段のバッファーキュー・アレイとして実装されているが、この段数及び個々のバッファーキュー・アレイにおけるバッファキューの数は使用目的に応じて適宜設定され、但し、上段に進むに従って、下段から1/N(Nは好適には2mで、mは1以上の整数)ずつ減らしていくように設定される。この実施例では、m=1である。
【００２７】
図１の構成は、バッファキュー・アレイ１０２、１０４、１０６及び１０８をもつ。例えばメモリ・バスに接続されたデータ入力論理回路１１０から、バッファキュー・アレイ１０２、１０４、１０６及び１０８の順にソートしながらデータを送り込み、例えばメモリ・バスに接続されたデータ出力論理回路１１２にソートされたデータを出力する動作を行う。
【００２８】
一番下の段であるバッファキュー・アレイ１０２は、８つのバッファキュー１０２ａ、１０２ｂ、１０２ｃ、１０２ｄ、１０２ｅ、１０２ｆ、１０２ｇ及び１０２ｈをもち、その上段のバッファキュー・アレイ１０４は、４つのバッファキュー１０４ａ、１０４ｂ、１０４ｃ及び１０４ｄをもち、その上段のバッファキュー・アレイ１０６は、２つのバッファキュー１０４ａ及び１０４ｂをもち、最上段のバッファキュー・アレイ１０８は、単一の１０８ａをもつ。
【００２９】
バッファキュー・アレイ１０２とバッファキュー・アレイ１０４の間には、バッファキュー・アレイ１０２の２つのバッファキューの値を比較して、バッファキュー・アレイ１０４に送り込むための単一のコンパレータ１１４と、スケジューラ１２０からのリクエストを受け取り、コンパレータ１１４が比較動作を行うバッファキューの位置を指定するスケジューラ１１６が配置されている。
【００３０】
バッファキュー・アレイ１０４とバッファキュー・アレイ１０６の間には、バッファキュー・アレイ１０４の２つのバッファキューの値を比較して、バッファキュー・アレイ１０６に送り込むための単一のコンパレータ１１８と、スケジューラ１２４からのリクエストを受け取り、コンパレータ１１８が比較動作を行うバッファキューの位置を指定するスケジューラ１２０が配置されている。
【００３１】
バッファキュー・アレイ１０６とバッファキュー・アレイ１０８の間には、バッファキュー・アレイ１０６の２つのバッファキューの値を比較して、バッファキュー・アレイ１０８に送り込むための単一のコンパレータ１２２と、データ出力論理回路１１２からのリクエストを受け取り、コンパレータ１２２が比較動作を行うバッファキューの位置を指定するスケジューラ１２４が配置されている。
【００３２】
スケジューラ１１６、１２０、及び１２４はそれぞれ、図４に示すように、上段のバッファキュー・アレイからのインデックスを格納するためのインデックス・キューをもつ。以下、スケジューラ１１６のインデックス・キューは１１６ａ、スケジューラ１２０のインデックス・キューは１２０ａのような符号で示す。データ入力論理回路１１０も、メモリ・バスからバッファキュー・アレイ１０２にデータを送り込む位置を指定するためのスケジューラ機能をもつ。
【００３３】
図２は、論理的に図１の構成と等価な構成の一部を示す。すなわち、図１の構成では、コンパレータとスケジューラが、別の構成要素として示されていたが、図２では、コンパレータ１２２が、図１に示すスケジューラ１２４の機能も含むものとして示されている。これは単に、機能要素の呼び方だけの問題で本質的ではないと理解されたい。
【００３４】
図３は、コンパレータとスケジューラの機能を図式的に示す図である。すなわち、図３に示されているように、上位の段（ステージともいう）のスケジューラ１２０が、すぐ下の段のスケジューラ１１６に２ビットのインデックスとしてリクエストを送る。
【００３５】
スケジューラ１１６は、このリクエストを処理して、以下の4箇所に制御信号を送る。
(1) バッファキュー・アレイ１０４の書込み位置指示の信号。図４あるいは図６などで示されているように、各バッファキュー・アレイは、書込みインデックスをもつ。すなわち、０番目から数えて、ｉ番目のバッファ・キューに書き込む、というように指示がなされる。
(2) バッファキュー・アレイ１０４の下位のバッファキュー・アレイ１０２の読取り位置指示。図４あるいは図６などに示されているように、各バッファキュー・アレイは、読取りインデックスをもつ。すなわち、読取りインデックスを以って、i*2番目とi*2+1番目のバッファ・キューからデータを読み取って、コンパレータ１１４で比較する、というように指示がなされる。
(3) コンパレータ１１４に対する制御信号。すなわち、コンパレータ１１４の処理を開始させる。また、コンパレータ１１４から処理完了の制御信号を受け取る。
(4) 下位のスケジューラに対するリクエスト。下位のバッファーキュー・アレイが最下段であるなら、データ入力論理回路１１０が、スケジューラの役割を果たす。
このような機能は、スケジューラ１２０及び１２４にも共通である。
【００３６】
次に、図４を参照して、図１に示したソータの論理的機能を説明する。まず、図１に示すように、各バッファキュー・アレイは、１つ以上のバッファキューをもつが、各バッファキューは、図４のように、複数のエントリ(要素)をもつ。やはり図４あるいは図６などで示されているように、インデックス・キューもまた、複数のエントリをもつ。本発明の１つの側面によれば、デッドロックを回避するために、バッファキューのエントリのサイズと、インデックス・キューのサイズが、所定の制約の下に選ばれる。この制約については後述する。
【００３７】
さらに、図４には、コンパレータ１１４が、バッファキュー・アレイ１０２の偶数番と奇数番のバッファ・キューの対を比較することが示されている。図４に示されているように、このようなバッファ・キューの対毎に0,1,2,3と、読取りインデックスとして番号が振られ、インデックス・キュー１１６ａのエントリが、この読取りインデックスを指し示す。
【００３８】
次に、図５のフローチャートを参照して、図１のソータの機能、特にスケジューラの処理について説明する。図５は、各段のスケジューラの処理をあらわす。従って、個々のスケジューラが図５に示す処理を実行する。
【００３９】
ステップ５０２において、スケジューラは、自分のインデックス・キューが空かどうか判断し、もしそうなら、ステップ５２４で何もしないで、ステップ５２６で、上のステージ（段）からのリクエストがあればインデックス・キューの末尾に追加して、処理を終了する。
【００４０】
もしステップ５０２においてスケジューラが、自分のインデックス・キューが空でないと判断したなら、ステップ５０４でインデックス・キューの先頭要素をｉという変数に格納し、ステップ５０６で、下のステージのインデックス・キューが一杯かどうか判断し、もしそうなら、ステップ５２４で何もしないで、ステップ５２６で、上のステージ（段）からのリクエストがあればインデックス・キューの末尾に追加して、処理を終了する。
【００４１】
下のステージのインデックス・キューが一杯でないなら、スケジューラは、ステップ５０８で、下のステージのバッファキューi*2が空かどうか判断する。そして、もしそうなら、スケジューラは、ステップ５１０で、リクエスト(i*2)を下のステージに送り、ステップ５２６で、上のステージからのリクエストがあればインデックス・キューの末尾に追加して、処理を終了する。
【００４２】
もし下のステージのバッファキューi*2が空でないなら、スケジューラは、ステップ５１２で、下のステージのバッファキューi*2+1が空かどうか判断する。そして、もしそうなら、スケジューラは、ステップ５１４で、リクエスト(i*2+1)を下のステージに送り、ステップ５２６で、上のステージ（段）からのリクエストがあればインデックス・キューの末尾に追加して、処理を終了する。
【００４３】
入力側のバッファキューi*2も下のステージのバッファキューi*2+1も空でないと判断すると、スケジューラは、ステップ５１６で、a := 下のステージのバッファキューi*2の先頭の値、b: = 下のステージのバッファキューi*2+1の先頭の値と格納する。
【００４４】
ステップ５１８では、コンパレータがaとbの値を比較し、a > bならステップ５２０でbを出力側、すなわち上段のバッファキュー・アレイのバッファキューiの末尾に追加し、リクエスト(i*2+1)を下のステージに送り、入力バッファキューi*2+1の先頭の値を削除し、インデックス・キューの先頭の値(i)を削除し、ステップ５２６で、上のステージ（段）からのリクエストがあればインデックス・キューの末尾に追加して、処理を終了する。
【００４５】
ステップ５１８でコンパレータが、a > bでないと判断したなら、ステップ５２２でaを出力側、すなわち上段のバッファキュー・アレイのバッファキューiの末尾に追加し、リクエスト(i*2)を下のステージに送り、入力バッファキューi*2の先頭の値を削除し、インデックス・キューの先頭の値(i)を削除し、ステップ５２６で、上のステージ（段）からのリクエストがあればインデックス・キューの末尾に追加して、処理を終了する。
【００４６】
尚、上記の処理で、ステップ５１０、５１４、５２２及び５２４で、リクエストを下のステージに送る処理が行われるが、この構成では、このときリクエストを投げる時点で、次のような条件設定で、出力側のバッファキューが一杯ならないように保証する。
【００４７】
すなわちまず、スタートアップ時に、バッファキューがフルとなり、また決してオーバーフローしないようにするために、バッファ・キューのサイズと、インデックスキューのサイズが等しくなるようになされる。ここでのインデックスキューのサイズとは、当該バッファキューの直下にあるインデックスキューのサイズのことである。
【００４８】
さらに、上位段からのリクエストを受け取ることのレイテンシをサイクル数でLとしたとき、定常状態でバッファキューが決して空にならないように、バッファキューのサイズは、L+1以上とされる。レイテンシをより詳細に説明すると、当該バッファキューの直上のステージからのリクエストが発行されてから、リクエストされたデータが当該バッファキューに対して書き込まれるまでのレイテンシのことである。
【００４９】
このように設定しておくことにより、図５のフローチャートで示す処理が、特に出力バッファキューの空きの有無をチェックすることなく、デッドロックを回避することが可能となる。
【００５０】
次に、図６から図１９までを参照して、図１の構成の動作の一例を説明する。この実施例では、最下段のバッファキュー・アレイ１０２のバッファキューのサイズが３であるが、その上の２つのバッファキュー・アレイ１０４及び１０６のバッファキューのサイズは２である。このように、バッファキュー・アレイ毎にバッファキューのサイズは同一にする必要はなく、異なるサイズに設定してもよい。但し、上述の制約により、バッファキューのサイズと、その直下にあるインデックスキューのサイズは同一になるようになされる。図６の例では、バッファキュー・アレイ１０４の直下にあるのは、インデックスキュー１１６ａである。
【００５１】
さて、ソータの動作は、スタートアップ・サイクルと定常サイクルからなる。図６は、スタートアップ・サイクル１を示す図である。図６において、バッファキュー・アレイ１０４のバッファキュー１０４ａとバッファキュー１０４ｂの先頭のエントリが空なので、スケジューラ１２０は、インデックス=0のリクエストを、下段のバッファキュー・アレイ１０2のスケジューラ１１６に送る。
【００５２】
図７に示す次のスタートアップ・サイクル２では、バッファキュー・アレイ１０４のバッファキュー１０４ａとバッファキュー１０４ｂの先頭のエントリが依然として空なので、スケジューラ１２０は、インデックス＝０のリクエストを、下段のバッファキュー・アレイ１０２のスケジューラ１１６に再び送る。こうして、スケジューラ１１６がリクエストを受け取るが、バッファキュー・アレイ１０２のバッファキュー１０２ａとバッファキュー１０２ｂの先頭のエントリが空なので、スケジューラ１１６は、下段の入力論理回路１１０にリクエストを送る。
【００５３】
図８に示す次のスタートアップ・サイクル３では、バッファキュー・アレイ１０４のバッファキュー１０４ａとバッファキュー１０４ｂの先頭のエントリが依然として空であるが、下位段のインデックス・キュー１１６ａが一杯なので、スケジューラ１２０は何もしない。一方、スケジューラ１１６は、バッファキュー・アレイ１０２のバッファキュー１０２ａとバッファキュー１０２ｂの先頭のエントリが空なので、スケジューラ１１６は、下段の入力論理回路１１０にリクエストを送る。
【００５４】
図９に示す次のスタートアップ・サイクル４では、バッファキュー・アレイ１０４のバッファキュー１０４ａとバッファキュー１０４ｂの先頭のエントリが依然として空であるが、下位段のインデックス・キュー１１６ａが一杯なので、スケジューラ１２０は何もしない。一方、スケジューラ１１６は、バッファキュー・アレイ１０２のバッファキュー１０２ａとバッファキュー１０２ｂの両方の先頭にエントリが格納されるのを待つ。
【００５５】
図１０は、スタートアップ・サイクル７を示す図である。この段階でも、バッファキュー・アレイ１０４のバッファキュー１０４ａとバッファキュー１０４ｂの先頭のエントリが依然として空であるが、下位段のインデックス・キュー１１６ａが一杯なので、スケジューラ１２０は何もしない。一方、スケジューラ１１６は、バッファキュー・アレイ１０２のバッファキュー１０２ａにエントリが格納されたが、バッファキュー１０２ｂのエントリがまだ空なので、その両方の先頭にエントリが格納されるのを待つ。
【００５６】
図１１は、スタートアップ・サイクル８を示す図である。バッファキュー・アレイ１０４のバッファキュー１０４ａとバッファキュー１０４ｂの先頭のエントリが依然として空であるが、下位段のインデックス・キュー１１６ａが一杯なので、スケジューラ１２０は何もしない。一方、スケジューラ１１６は、バッファキュー・アレイ１０２のバッファキュー１０２ａとバッファキュー１０２ｂの両方の先頭に値が格納されたので作動し始め、これにより、バッファキュー１０２ａの先頭のエントリが、バッファキュー・アレイ１０４のバッファキュー１０４ａにポップされる。
【００５７】
図１２のスタートアップ・サイクル９では、バッファキュー１０４ａが最早空ではなく、一方バッファキュー１０４ｂが依然として空なので、インデックス=1というリクエストをスケジューラ１２０が送る。一方、インデックス・キュー１１６ａのエントリに応答して、バッファキュー・アレイ１０２のバッファキュー１０２ａとバッファキュー１０２ｂがコンパレータ１１４によって比較され、結果がバッファキュー・アレイ１０４のバッファキュー１０４ａにポップされる。
【００５８】
図１３のスタートアップ・サイクル１０では、インデックス・キューの2つのエントリに対応して、バッファキュー・アレイ１０４のバッファキュー１０４ａに2つのエントリがプッシュされた状態となる。
【００５９】
図１４から図１９までは、定常サイクルの動作を示す。図１４から図１９において、インデックス・キュー１１６ａ、１２０ａ、１２４ａは便宜上単一要素として示されているけれども、実際は２要素である。図１４の定常サイクル１では、スケジューラ１２４のインデックス・キュー１２４ａがバッファキュー・アレイ１０６の読取りインデックス=0を指し示し、この結果、バッファキュー１０６ａとバッファキュー１０６ｂの先頭のエントリがコンパレータ１２２により比較されて、バッファキュー１０４ａの先頭のエントリが上段に移動対象となる。また、移動対象になったバッファキュー１０４ａの書込みインデックスは、次のサイクルで使用される。
【００６０】
さらに図１４において、インデックス・キュー１２０ａがバッファキュー・アレイ１０４の読取りインデックス=1を指し示し、この結果、バッファキュー１０４ｃとバッファキュー１０４ｄの先頭のエントリがコンパレータ１１８により比較されて、バッファキュー１０４ｃの先頭のエントリが上段に移動対象となる。また、移動対象になったバッファキュー１０４ｃの書込みインデックスは、次のサイクルで使用される。
【００６１】
さらに図１４において、インデックス・キュー１１６ａがバッファキュー・アレイ１０２の読取りインデックス１を指し示し、この結果、バッファキュー１０２ｃとバッファキュー１０２ｄの先頭のエントリがコンパレータ１１４により比較されて、バッファキュー１０４ｃの先頭のエントリが上段に移動対象となる。
【００６２】
図１５は、定常サイクル１の続きを示す。すなわち、図１５において、バッファキュー・アレイ１０６のバッファキュー１０６ａの先頭のエントリがデータ出力論理回路１１２に送られ、バッファキュー・アレイ１０４のバッファキュー１０４ｃの先頭のエントリがバッファキュー・アレイ１０６のバッファキュー１０６ｂに送られ、バッファキュー・アレイ１０２のバッファキュー１０２ｄの先頭のエントリがバッファキュー・アレイ１０４のバッファキュー１０４ｂに送られる。
【００６３】
図１６の定常サイクル２では、スケジューラ１２４のインデックス・キュー１２４ａがバッファキュー・アレイ１０６の読取りインデックス=0を指し示し、この結果、バッファキュー１０６ａとバッファキュー１０６ｂの先頭のエントリがコンパレータ１２２により比較されて、バッファキュー１０４ａの先頭のエントリが上段に移動対象となる。また、移動対象になったバッファキュー１０４ａの書込みインデックスは、次のサイクルで使用される。
【００６４】
さらに図１６において、インデックス・キュー１２０ａがバッファキュー・アレイ１０４の読取りインデックス=0を指し示し、この結果、バッファキュー１０４ａとバッファキュー１０４ｂの先頭のエントリがコンパレータ１１８により比較されて、バッファキュー１０４ａの先頭のエントリが上段に移動対象となる。また、移動対象になったバッファキュー１０４ａの書込みインデックスは、次のサイクルで使用される。
【００６５】
さらに図１６において、インデックス・キュー１１６ａがバッファキュー・アレイ１０２の読取りインデックス=2を指し示し、この結果、バッファキュー１０２ｅとバッファキュー１０２ｆの先頭のエントリがコンパレータ１１４により比較されて、バッファキュー１０４ｆの先頭のエントリが上段に移動対象となる。
【００６６】
図１７は、定常サイクル２の続きを示す。すなわち、図１７において、バッファキュー・アレイ１０６のバッファキュー１０６ａの先頭のエントリがデータ出力論理回路１１２に送られ、バッファキュー・アレイ１０４のバッファキュー１０４ａの先頭のエントリがバッファキュー・アレイ１０６のバッファキュー１０６ａに送られ、バッファキュー・アレイ１０２のバッファキュー１０２ｆの先頭のエントリがバッファキュー・アレイ１０４のバッファキュー１０４ｃに送られる。
【００６７】
図１８の定常サイクル３では、スケジューラ１２４のインデックス・キュー１２４ａがバッファキュー・アレイ１０６の読取りインデックス=0を指し示し、この結果、バッファキュー１０６ａとバッファキュー１０６ｂの先頭のエントリがコンパレータ１２２により比較されて、バッファキュー１０４ｂの先頭のエントリが上段に移動対象となる。また、移動対象になったバッファキュー１０４ｂの書込みインデックスは、次のサイクルで使用される。
【００６８】
さらに図１８において、インデックス・キュー１２０ａがバッファキュー・アレイ１０４の読取りインデックス=0を指し示し、この結果、バッファキュー１０４ａとバッファキュー１０４ｂの先頭のエントリがコンパレータ１１８により比較されて、バッファキュー１０４ｂの先頭のエントリが上段に移動対象となる。また、移動対象になったバッファキュー１０４ｂの書込みインデックスは、次のサイクルで使用される。
【００６９】
さらに図１８において、インデックス・キュー１１６ａがバッファキュー・アレイ１０２の読取りインデックス=0を指し示し、この結果、バッファキュー１０２ａとバッファキュー１０２ｂの先頭のエントリがコンパレータ１１４により比較されて、バッファキュー１０４ａの先頭のエントリが上段に移動対象となる。
【００７０】
図１９は、定常サイクル２の続きを示す。すなわち、図１９において、バッファキュー・アレイ１０６のバッファキュー１０６ａの先頭のエントリがデータ出力論理回路１１２に送られ、バッファキュー・アレイ１０４のバッファキュー１０４ｂの先頭のエントリがバッファキュー・アレイ１０６のバッファキュー１０６ａに送られ、バッファキュー・アレイ１０２のバッファキュー１０２ａの先頭のエントリがバッファキュー・アレイ１０４のバッファキュー１０４ａに送られる。
【００７１】
以上のように、特定の数のバッファキュー・アレイの段数と、バッファキューのサイズと、インデックス・キューのサイズ(要素数)における実施例を説明してきたが、上記制約条件に従う限り、適用するアプリケーションに従い、任意の数のバッファキュー・アレイの段数、バッファキューのサイズ及びインデックス・キューの数を使用することができる。
【００７２】
また、この発明の構成の好適な実装は、FPGA(Field Programmable Gate Array)またはCPLD(Complex Programmable Logic Device)などの書き換え可能な論理素子を用いたハードウェアによる実装であるが、通常のフォトリソグラフ技術によりシリコン・ウェーハ上に作りこんだ論理回路でもよいし、ソフトウェアにより実装してもよい。ソフトウェアによる実装の場合は、一般的にハードウェアによる実装よりは動作速度は低下するが、それでも、本発明の機能をコード化した場合、機能の簡易化によるコード記述の合理化を計ることができる。
【符号の説明】
【００７３】
１０２、１０４、１０６        ・・・  バッファキュー・アレイ
１１４、１１８、１２２        ・・・  コンパレータ
１１６、１２０、１２４        ・・・  スケジューラ
１１６ａ、１２０ａ、１２４ａ  ・・・  インデックス・キュー
【図１】
2014126931.tif 000003
【図２】
2014126931.tif 000004
【図３】
2014126931.tif 000005
【図４】
2014126931.tif 000006
【図５】
2014126931.tif 000007
【図６】
2014126931.tif 000008
【図７】
2014126931.tif 000009
【図８】
2014126931.tif 000010
【図９】
2014126931.tif 000011
【図１０】
2014126931.tif 000012
【図１１】
2014126931.tif 000013
【図１２】
2014126931.tif 000014
【図１３】
2014126931.tif 000015
【図１４】
2014126931.tif 000016
【図１５】
2014126931.tif 000017
【図１６】
2014126931.tif 000018
【図１７】
2014126931.tif 000019
【図１８】
2014126931.tif 000020
【図１９】
2014126931.tif 000021