(57)【要約】      （修正有）【課題】メモリチップの増加を抑制しつつ効率的な検索処理の実行が可能な検索回路を提供する。【解決手段】検索回路は、複数の検索ステージに分割され、複数の検索ステージのうちの第１グループに対応する検索ステージに対応するエントリデータを格納する第１メモリ５０３−１〜５０３−（Ｋ−８）と、複数の検索ステージのうちの第１グループ以外の第２グループに対応するエントリデータ群を格納する第２メモリ５０６と、第１メモリおよび第２メモリに対してバイナリサーチを実行する検索処理部とを備える。第２メモリは、第２グループの検索ステージ数に従って設けられる複数のメモリバンクを含む。第２グループに対応するエントリデータ群は、バイナリサーチの読み出し順序位置に従って複数のサブエントリデータ群に分割される。各サブエントリデータ群のエントリデータは、検索ステージ毎に各メモリバンクにそれぞれ格納される。【選択図】図６
2020187407.tif 000002
【特許請求の範囲】
【請求項１】
複数のエントリデータに対して入力された検索キーが一致するか否かを検索する検索回路であって、
前記複数のエントリデータは、バイナリサーチの読み出し順序位置に従って複数の検索ステージに分割され、
前記複数の検索ステージのうちの第１グループに対応する検索ステージに対応するエントリデータを格納する第１メモリと、
前記複数の検索ステージのうちの前記第１グループ以外の第２グループに対応するエントリデータ群を格納する第２メモリと、
前記第１メモリおよび第２メモリに対してバイナリサーチを実行する検索処理部とを備え、
前記第２メモリは、前記第２グループの検索ステージ数に従って設けられる複数のメモリバンクを含み、
前記第２グループに対応するエントリデータ群は、前記バイナリサーチの読み出し順序位置に従って複数のサブエントリデータ群に分割され、
各前記サブエントリデータ群のエントリデータは、前記検索ステージ毎に各前記メモリバンクにそれぞれ格納される、検索回路。
【請求項２】
各前記サブエントリデータ群のエントリデータは、同じ検索ステージ毎に同一のメモリバンクにそれぞれ格納される、請求項１記載の検索回路。
【請求項３】
各前記メモリバンクは、前記検索ステージにそれぞれ対応付けられ、
各前記サブエントリデータ群のエントリデータは、前記検索ステージ毎に対応するメモリバンクの１つに格納される、請求項１記載の検索回路。
【請求項４】
第１のサブエントリデータ群のエントリデータと第２のサブエントリデータ群のエントリデータとは、前記検索ステージ毎に互いに異なるメモリバンクにそれぞれ格納される、請求項１記載の検索回路。
【請求項５】
前記検索処理部は、前記検索ステージに従って前記複数のメモリバンクに対して順番にアクセスする、請求項１記載の検索回路。
【請求項６】
前記検索処理部は、
前記第１メモリに対してバイナリサーチを実行する第１検索処理部と、
前記第１検索処理部の検索結果に基づいて前記第２メモリに対してバイナリサーチを実行する第２検索処理部とを含む、請求項１記載の検索回路。
【請求項７】
前記第２検索処理部は、
前記第２メモリに対してアクセスするためのインタフェース回路をさらに含む、請求項６記載の検索回路。
【請求項８】
前記インタフェース回路は、
前記複数のメモリバンクにそれぞれ対応して設けられ、検索キーおよび前記複数のメモリバンクのうちの１つのメモリバンクにアクセスするためのアドレス情報をそれぞれ格納することが可能な複数のＦＩＦＯバッファと、
前記複数のＦＩＦＯバッファに格納されている情報を順番に切り替えて前記第２メモリに出力する出力セレクタとを含む、請求項７記載の検索回路。
【請求項９】
前記第２検索処理部は、
前記第２メモリから読み出されたエントリデータと、前記ＦＩＦＯ検索キーとが一致するか否かを判定する判定回路を含み、
前記インタフェース回路は、
前記判定回路の判定結果に基づいて前記複数のＦＩＦＯバッファの１つに前記検索キーおよび前記複数のメモリバンクのうちの次のメモリバンクにアクセスするためのアドレス情報を出力する入力セレクタをさらに含む、請求項８記載の検索回路。
【請求項１０】
前記第２メモリは、ＤＲＡＭである、請求項１記載の検索回路。
【請求項１１】
前記第２メモリに含まれる前記複数のメモリバンクのうちの同一のメモリバンクに対するアクセスは所定期間禁止されている、請求項１０記載の検索回路。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、複数のエントリデータが格納される検索テーブルに対して入力された検索キーが一致するか否かを検索する検索回路に関する。
【背景技術】
【０００２】
ＩＴ技術の進展により大容量のデータベースから対象となる特定のデータが格納されている場所を高速に検索するアプリケーションが必要とされている。例えばインターネットにおいて宛先となるＩＰアドレスから目的となる端末への経路を決定するために、宛先ＩＰアドレスを検索データとし、目的地への経路を検索結果として出力するデータベース検索が実施されている。このようなデータベースの中から特定のデータを検索する場合、目的とするデータが見つかるまで順次データを検索していくリニアサーチ（Linear-Search）と呼ばれる方式がある。Ｎ個の要素をもつ集合Ｙの中から検索データＫｅｙに一致するデータを検索する場合、以下のようなアルゴリズムで検索が実施される。
【０００３】
【表１】
2020187407.tif 000003
【０００４】
上記のように集合の各要素を一個ずつ順番に検索していき、目的のデータが見つかった時点で検索終了となる。
【０００５】
したがって、リニアサーチ（Linear-Search）のワーストケースは目的とするデータが集合の最終要素Ｙ［Ｎ］であった場合であり、Ｎ回の検索動作が必要になる。そのためデータベースの要素数が大きくなるほど検索性能が低下する。
【０００６】
一方、リニアサーチ（Linear-Search）より高速に検索を実施する方法の一つとしてバイナリサーチ（Binary-Search）がある。
【０００７】
特許文献１には、バイナリサーチを高速にする技術として、メモリアクセスの各々でアクセスされるメモリアドレスをあらかじめ規定し、各々を別のメモリインスタンスに分離することでパイプライン化して検索性能を高速化させる方式が提案されている。
【０００８】
ここで、大規模なバイナリサーチ（Binary-Search）の検索テーブルを構築する場合には、検索テーブルのデータはＡＳＩＣやＦＰＧＡの内蔵メモリではなく、専用のＤＲＡＭやＳＲＡＭ等の汎用メモリチップを用いるのが一般的である。
【０００９】
そのため、高速化のために特許文献１に従うパイプライン化を実施する場合、メモリインスタンスの数だけメモリチップが必要となる。
【００１０】
また、各々のメモリチップはパイプライン動作を実現するためプロセッサとの間に独立したメモリバスを必要とする。
【００１１】
このような実装方法ではボードの実装面積の増加やメモリを制御するプロセッサの制御が複雑化する課題が生じる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】米国特許第６５４９５１９号明細書
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本開示は、上記の課題を解決するためになされたものであって、検索テーブルが大規模化した場合であっても、メモリチップの増加を抑制しつつ効率的な検索処理の実行が可能な検索回路を提供する。
【００１４】
その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１５】
ある局面に従う複数のエントリデータに対して入力された検索キーが一致するか否かを検索する検索回路であって、複数のエントリデータは、バイナリサーチの読み出し順序位置に従って複数の検索ステージに分割され、複数の検索ステージのうちの第１グループに対応する検索ステージに対応するエントリデータを格納する第１メモリと、複数の検索ステージのうちの第１グループ以外の第２グループに対応するエントリデータ群を格納する第２メモリと、第１メモリおよび第２メモリに対してバイナリサーチを実行する検索処理部とを備える。第２メモリは、第２グループの検索ステージ数に従って設けられる複数のメモリバンクを含む。第２グループに対応するエントリデータ群は、バイナリサーチの読み出し順序位置に従って複数のサブエントリデータ群に分割され、各サブエントリデータ群のエントリデータは、検索ステージ毎に各メモリバンクにそれぞれ格納される。
【発明の効果】
【００１６】
一実施例によれば、本開示の検索回路は、検索テーブルが大規模化した場合であっても、メモリチップの増加を抑制しつつ効率的な検索処理の実行が可能である。
【図面の簡単な説明】
【００１７】
【図１】実施形態１に基づく通信機器１の構成を説明する図である。
【図２】比較例に従うバイナリサーチのアクセス手順を説明する図である。
【図３】比較例に従うバイナリサーチのパイプライン化を説明する図である。
【図４】一般的なＤＲＡＭのメモリチップについて説明する図である。
【図５】比較例に従うメモリバンクにデータを格納した場合について説明する図である。
【図６】実施形態１に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【図７】実施形態１に従う１Ｍアドレスのエントリデータ群について説明する図である。
【図８】実施形態１に従う第１処理部５０２および内蔵メモリ５０３の動作について説明する図である。
【図９】実施形態１に従う第２処理部５０４、インタフェース回路５０５およびメモリ５０６の動作について説明する図である。
【図１０】実施形態１に従う複数の検索キーＫ０〜Ｋ３の検索動作について説明する図である。
【図１１】実施形態１に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その１）である。
【図１２】実施形態１に従う複数の検索キーＫ０〜Ｋ６の検索動作について説明する図である。
【図１３】実施形態１に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その２）である。
【図１４】実施形態１に従う複数の検索キーＫ０〜Ｋ２４の検索動作について説明する図である。
【図１５】実施形態１に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その３）である。
【図１６】実施形態２に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【図１７】実施形態３に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【図１８】実施形態３に従う第２処理部１１０４、インタフェース回路１１０５およびメモリ１１０６の動作について説明する図である。
【図１９】実施形態３に従う複数の検索キーＫ０〜Ｋ７の検索動作について説明する図である。
【図２０】実施形態３に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その１）である。
【図２１】実施形態３に従う複数の検索キーＫ０〜Ｋ１５の検索動作について説明する図である。
【図２２】実施形態３に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その２）である。
【図２３】実施形態３に従う複数の検索キーＫ０〜Ｋ２３の検索動作について説明する図である。
【図２４】実施形態３に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その３）である。
【図２５】実施形態３の変形例に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【図２６】実施形態３の変形例２に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【発明を実施するための形態】
【００１８】
実施形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付し、その説明は繰り返さない。
【００１９】
（実施形態１）
＜通信機器１の全体構成＞
図１は、実施形態１に基づく通信機器１の構成を説明する図である。
【００２０】
図１に示されるように、通信機器１は、スイッチあるいはルータ等の通信装置である。
通信機器１は、インターネットと接続される。パケットデータの転送処理を実行する。
【００２１】
通信機器１は、ＣＰＵ（Central Processing Unit）２と、転送制御回路４と、汎用メモリ６と、検索回路８とを含む。
【００２２】
ＣＰＵ２は、機器全体を制御する。
ＣＰＵ２は、汎用メモリ６に格納されたプログラムと協働して種々の機能を実現する。たとえば、汎用メモリ６は、ＤＲＡＭ（Dynamic Random Access Memory）で構成することが可能であり、ＣＰＵ２と協働することによりオペレーティングシステム（ＯＳ）を構築する。ＣＰＵ２は、隣接する通信機器等と情報交換し、転送処理に必要な情報を維持管理する。
【００２３】
転送制御回路４は、通信パケットの転送処理を実行する。転送制御回路４は、転送処理に特化したＡＳＩＣ（Application Specific Integrated Circuit）回路あるいはＮＰＵ(Network Processing Unit)といった専用ハードウェアが設けられている。転送制御回路４は、検索回路８にアクセスして、転送処理に必要な情報を取得する。
【００２４】
＜比較例に従うバイナリサーチ（Binary-Search）の検索アルゴリズム＞
バイナリサーチは、あらかじめ検索対象となる集合のデータを小さい順にソートし、以下のようなアルゴリズムで目的となる検索テータと一致するデータが見つかるまで検索動作を繰り返す。
【００２５】
【表２】
2020187407.tif 000004
【００２６】
Ｎ個の要素をもつ、バイナリサーチ（Binary-Search）の検索テーブルの参照回数をＬｏｇ2（Ｎ）＝Ｋと定義した場合、一回のバイナリサーチ（Binary-Search）の検索動作にはバイナリサーチ（Binary-Search）の検索テーブルを格納したメモリへＫ回のアクセスが必要となる。
【００２７】
ここで、Ｎ＝１５と仮定した場合、Ｋ＝Ｌｏｇ2（１５）＝４となるため一回のバイナリサーチ（Binary-Search）に必要なメモリアクセスは最大で４回となる。
【００２８】
図２は、比較例に従うバイナリサーチのアクセス手順を説明する図である。
図２（Ａ）に示されるように、メモリ１０１にソートされた要素Ｙ［１］〜Ｙ［１５］までの１５個の要素を格納した場合、破線で示されたようなアクセス順でバイナリサーチが実行される。
【００２９】
図２（Ｂ）に示されるように、パイプライン化するためには、それぞれのアクセス段数（検索ステージ）毎にメモリに格納する。具体的には、メモリ１０２に要素Ｙ［８］を格納する。メモリ１０３に要素Ｙ［４］，Ｙ［１２］を格納する。メモリ１０４に要素Ｙ［２］，Ｙ［６］，Ｙ［１０］，Ｙ［１４］を格納する。メモリ１０５に要素Ｙ［１］，Ｙ［３］，Ｙ［５］，Ｙ［７］，Ｙ［９］，Ｙ［１１］，Ｙ［１３］，Ｙ［１５］を格納する。
【００３０】
図３は、比較例に従うバイナリサーチのパイプライン化を説明する図である。
図３（Ａ）に示されるように、Ｋ回のメモリアクセスを必要とするバイナリサーチ（Binary-Search）をＤＲＡＭなどのメモリチップを使用してパイプライン化するにはＫ個のメモリ２０２−１〜２０２−Ｋと、各メモリ２０２−１〜２０２−Ｋに対してアクセスするためのプロセッサ２００の処理部２０１−１〜２０１−Ｋを設ける必要がある。
【００３１】
そして、当該メモリ２０２と処理部２０１との間を接続するためのＫ個のメモリバスも必要になる。
【００３２】
しかしながら、上述したように、メモリチップ数が増加し、ボードの実装面積の増加やメモリを制御するプロセッサ２００のピン数の増加により、プロセッサ２００の制御が複雑化する。
【００３３】
したがって、大規模なバイナリサーチ（Binary-Search）を構築する場合、すべてをパイプライン化するのではなく一部をパイプライン化することが考えられる。
【００３４】
図３（Ｂ）は、パイプラインを２段階に分割して、アクセス段数（検索ステージ）が１〜Ｋ／２段までの前段部分をバイナリサーチ（Binary-Search）を実行するプロセッサ２１０の内蔵メモリ２１２に格納する。そして、残りのアクセス段数（検索ステージ）が（（Ｋ／２）＋１）〜Ｋ段までの後段部分をメモリチップ２１３に格納する。
【００３５】
当該構成により、メモリチップ数の増加を抑制することが可能である。
しかし、図３（Ａ）はＫ段のバイナリサーチ（Binary-Search）をパイプライン化しているのでパイプライン化していない場合と比較して検索性能はＫ倍となるが、図３（Ｂ）は、２段階しかパイプライン化していないので検索性能は２倍にしかならない。
【００３６】
また、検索するBinary-Search検索テーブルが大規模である場合、図３（Ｂ）などに使用されるメモリは、ＤＲＡＭやＳＲＡＭなどの汎用メモリを用いるのが一般的である。
【００３７】
図４は、一般的なＤＲＡＭのメモリチップについて説明する図である。
図４（Ａ）は、ＤＲＡＭのメモリチップが複数のメモリバンクに分割されている場合が示されている。一例として、メモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に分割されている場合が示されている。
【００３８】
一般的なＤＲＡＭメモリチップでは、プリチャージ期間等を設ける必要があるため同一のメモリバンクＢａｎｋに対するアクセスには時間的制約が設けられている。
【００３９】
具体的には、同一のメモリバンクＢａｎｋへのアクセスは一定の待機時間ｔＲＣの間、アクセスが禁止される構成となっている。
【００４０】
図４（Ｂ）では、同一のメモリバンクＢａｎｋへのアクセスは６サイクル禁止されている場合が示されている。
【００４１】
本例に示されるように、同一のメモリバンクＢａｎｋへのアクセスが集中するような場合には、待機時間ｔＲＣが頻繁に発生するため検索性能が低下する場合が考えられる。
【００４２】
この場合、サイクルＴ−３〜Ｔ−５の間においては待機時間ｔＲＣにより同一のメモリバンクＢａｎｋへのアクセスができない場合が示されている。
【００４３】
図５は、比較例に従うメモリバンクにデータを格納した場合について説明する図である。
【００４４】
図５に示されるように、図４で説明したメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に対してデータを格納する場合が示されている。
【００４５】
例えば、メモリアドレス０からソート順にＮ個のデータを格納する。メモリアドレス０は、メモリバンクＢａｎｋ［０］の先頭アドレスとする。メモリアドレスの最後は、メモリバンクＢａｎｋ［７］の最終アドレスとする。
【００４６】
当該複数のメモリバンクＢａｎｋを用いたバイナリサーチを実行する際のアクセス順について説明する。
【００４７】
ここで、表２に示すバイナリサーチ（Binary-Search）アルゴリズムであらかじめ規定されたアクセス順でバイナリサーチ（Binary-Search）を実行する。その場合、最初にメモリバンクＢａｎｋ［４］にアクセスし、次に、メモリバンクＢａｎｋ「２」にアクセスし、次にメモリバンクＢａｎｋ［１］にアクセスする。そして、メモリバンクＢａｎｋ［０］にアクセスする。４回目以降のメモリアクセスは、同一のメモリバンクＢａｎｋ［０］にアクセスが集中する。
【００４８】
この場合、上記の如く待機時間ｔＲＣの影響により、検索性能が低下することになる。
＜実施形態１に従うバイナリサーチ（Binary-Search）の検索アルゴリズム＞
図６は、実施形態１に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【００４９】
図６を参照して、実施形態１に従う検索回路は、プロセッサ５０１と、メモリ５０６とを含む。
【００５０】
プロセッサ５０１は、複数の第１処理部５０２−１〜５０２−（Ｋ−８）と、複数の内蔵メモリ５０３−１〜５０３−（Ｋ−８）と、第２処理部５０４と、第２処理部５０４とメモリ５０６との間のデータの授受を実行するインタフェース回路５０５とを含む。
【００５１】
複数の第１処理部５０２−１〜５０２−（Ｋ−８）（総称して第１処理部５０２とも称する）と、複数の内蔵メモリ５０３−１〜５０３−（Ｋ−８）（総称して内蔵メモリ５０３とも称する）はそれぞれ対応付けられており、パイプライン化されている。
【００５２】
具体的には、検索キーＫｅｙの入力に対して第１処理部５０２−１は、内蔵メモリ５０３−１にアクセスして検索キーＫｅｙと内蔵メモリ５０３−１に格納されているデータとが一致するか否かを判断する。第１処理部５０２−１は、検索キーＫｅｙとデータとが一致すると判断した場合には、一致（Ｈｉｔ）と判定する。一方、第１処理部５０２−１は、検索キーＫｅｙとデータとが一致しないと判断した場合には、ミス（Ｍｉｓｓ）と判定する。そして、次段の第１処理部５０２−２に検索キーＫｅｙとともに判定結果を出力する。
【００５３】
当該処理を第１処理部５０２−２から第１処理部５０２−（Ｋ−８）まで順次繰り返す。
【００５４】
そして、第１処理部５０２−（Ｋ−８）の判定結果が第２処理部５０４に出力される。
第２処理部５０４は、第１処理部５０２−（Ｋ−８）の判定結果に基づいてインタフェース回路５０５を介してメモリ５０６にアクセスする。
【００５５】
メモリ５０６は、複数のメモリバンクＢａｎｋを含む。一例として、８個のメモリバンクＢａｎｋが設けられている場合が示されている。
【００５６】
実施形態１に従うエントリデータの割り当て方式について説明する。
実施形態１では、バイナリサーチ（Binary-Search）を実行するＫ回のメモリアクセスを次表に示す仕方で割り当てる。
【００５７】
【表３】
2020187407.tif 000005
【００５８】
本例においては、メモリ５０６が有するメモリバンクＢａｎｋ数と同じ最終８回のメモリアクセス段数（検索ステージ）Ｓｔａｇｅ［Ｋ−７］〜Ｓｔａｇｅ［Ｋ］のエントリデータをそれぞれメモリ５０６の各メモリバンクＢａｎｋに割り当てる。また、残りのメモリアクセス段数（検索ステージ）Ｓｔａｇｅ［１］〜Ｓｔａｇｅ［Ｋ−８］のエントリデータをプロセッサ５０１の内蔵メモリ５０３−１〜５０３−［Ｋ−８］にそれぞれ割り当てる。
【００５９】
この構成ではプロセッサ５０１で実行するバイナリサーチ（Binary-Search）の検索ステージＳｔａｇｅ［１］〜Ｓｔａｇｅ［Ｋ−８］は，パイプライン処理されるので短いレイテンシと１サイクルのスループットでバイナリサーチ（Binary-Search）を順次実行できる。
【００６０】
また、プロセッサ５０１に実装する（Ｋ−８）個の内蔵メモリ５０３の合計の容量はＮ／２５６となる。
【００６１】
したがって、全体で１Ｍアドレスの容量を持つエントリデータの場合には、プロセッサ５０１には、その１／２５６となる４Ｋアドレスの内蔵メモリを実装するだけで実装可能となる。内蔵メモリの容量を小さく設計することが可能である。
【００６２】
そして、検索ステージＳｔａｇｅ［Ｋ−７］以降の８回のメモリアクセスは、メモリ５０６へアクセスすることになる。
【００６３】
この場合、検索ステージＳｔａｇｅ毎のエントリデータが各メモリバンクＢａｎｋに割り当てられている。
【００６４】
したがって、同一のメモリバンクＢａｎｋに対するアクセスが集中することはなく、メモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に順次アクセスすることになる。
【００６５】
それゆえ、同一のメモリバンクＢａｎｋへのアクセス制限による待機時間ｔＲＣにより検索性能が低下することを抑制することが可能である。ワーストケースの検索性能はバイナリサーチ（Binary-Search）一回あたりのメモリアクセス回数８回によって規定される。
【００６６】
図７は、実施形態１に従う１Ｍアドレスのエントリデータ群について説明する図である。
【００６７】
図７に示されるように、１Ｍアドレスのエントリデータ群に対してバイナリサーチを実行する場合には、２０回のメモリアクセスが必要となる。すなわち、検索ステージＳｔａｇｅ数はＫ＝２０である。
【００６８】
ここでは、検索ステージＳｔａｇｅ［１］〜Ｓｔａｇｅ［２０］に分割された１Ｍアドレスのエントリデータ群が示されている。一例として１６進数標記の２０ビットのメモリアドレスが示されている。
【００６９】
そして、本例においては、１Ｍアドレスのエントリデータ群を２つのグループに分割する。
【００７０】
複数の内蔵メモリ５０３に格納する第１グループのエントリデータ群と、メモリ５０６に格納する第２グループのエントリデータ群とに分割する。
【００７１】
第１グループのエントリデータ群を内蔵メモリ５０３に格納する。
具体的には、検索ステージＳｔａｇｅに対応するメモリアドレスのエントリデータを内蔵メモリ５０３に順次格納する。
【００７２】
具体的には、検索ステージＳｔａｇｅ［１］に対応するメモリアドレス［８００００］のエントリデータを内蔵メモリ５０３−１に格納する。また、検索ステージＳｔａｇｅ［２］に対応するメモリアドレス［４００００］，［Ｃ００００］のエントリデータ群を内蔵メモリ５０３−２に格納する。また、検索ステージＳｔａｇｅ［３］に対応するメモリアドレス［２００００］，［６００００］，［Ａ００００］，［Ｅ００００］のエントリデータ群を内蔵メモリ５０３−３に格納する。同様に検索ステージＳｔａｇｅ毎に対応するメモリアドレスのエントリデータ群を内蔵メモリ５０３に順次格納する。
【００７３】
次に、第１グループ以外の残りの第２グループのエントリデータ群をメモリ５０６に格納する。メモリ５０６は、８個のメモリバンクＢａｎｋを有する。
【００７４】
本例においては、残りのエントリデータ群について、８個のメモリバンクＢａｎｋに対応する８個の検索ステージＳｔａｇｅに従ってグループ化される複数のサブエントリデータ群に分割する。本例においては、複数のサブエントリデータ群ＢＬＫ［０］〜ＢＬＫ［４０９５］に分割される。１つのサブエントリデータ群ＢＬＫは、２５６個のエントリデータで構成される。サブエントリデータ群ＢＬＫ［０］は、メモリアドレス［０００００］〜［０００ＦＦ］にそれぞれ対応するエントリデータで構成される。サブエントリデータ群ＢＬＫ［４０９５］は、メモリアドレス［ＦＦＦ００］〜［ＦＦＦＦＦ］にそれぞれ対応するエントリデータで構成される。
【００７５】
そして、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］にそれぞれ対応するメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に順次格納する。
【００７６】
一例として、サブエントリデータ群ＢＬＫ［０］に関して、検索ステージＳｔａｇｅ［１３］に対応するメモリアドレス［０００８０］のエントリデータをメモリバンクＢａｎｋ［０］に格納する。検索ステージＳｔａｇｅ［１４］に対応するメモリアドレス［０００４０］，［０００Ｃ０］のエントリデータ群をメモリバンクＢａｎｋ［１］に格納する。同様に検索ステージＳｔａｇｅ毎に対応するメモリアドレスのエントリデータ群を対応するメモリバンクＢａｎｋに順次格納する。
【００７７】
他のサブエントリデータ群ＢＬＫについても同様である。
当該方式により、各サブエントリデータ群ＢＬＫの検索ステージＳｔａｇｅ［１３］に対応するメモリアドレスのエントリデータはメモリバンク［０］に格納される。各サブエントリデータ群ＢＬＫの検索ステージＳｔａｇｅ［１４］に対応するメモリアドレスのエントリデータはメモリバンク［１］に格納される。各サブエントリデータ群ＢＬＫの検索ステージＳｔａｇｅ［１５］に対応するメモリアドレスのエントリデータはメモリバンク［２］に格納される。各サブエントリデータ群ＢＬＫの検索ステージＳｔａｇｅ［１６］に対応するメモリアドレスのエントリデータはメモリバンク［３］に格納される。各サブエントリデータ群ＢＬＫの検索ステージＳｔａｇｅ［１７］に対応するメモリアドレスのエントリデータはメモリバンク［４］に格納される。各サブエントリデータ群ＢＬＫの検索ステージＳｔａｇｅ［１８］に対応するメモリアドレスのエントリデータはメモリバンク［５］に格納される。各サブエントリデータ群ＢＬＫの検索ステージＳｔａｇｅ［１９］に対応するメモリアドレスのエントリデータはメモリバンク［６］に格納される。各サブエントリデータ群ＢＬＫの検索ステージＳｔａｇｅ［２０］に対応するメモリアドレスのエントリデータはメモリバンク［７］に格納される。
【００７８】
当該方式により、エントリデータ群をメモリに格納することにより、同一のメモリバンクＢａｎｋに対するアクセスが集中することを回避することが可能である。すなわち、検索ステージＳｔａｇｅ［１３］以降、メモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に順次アクセスすることになる。
【００７９】
それゆえ、同一のメモリバンクＢａｎｋへのアクセス制限による待機時間ｔＲＣにより検索性能が低下することを抑制することが可能である。
【００８０】
図８は、実施形態１に従う第１処理部５０２および内蔵メモリ５０３の動作について説明する図である。
【００８１】
図８を参照して、複数の第１処理部５０２は、内蔵メモリ５０３と協働して第１グループのエントリデータ群の検索動作を実行する。
【００８２】
ここでは、ある検索ステージＳｔａｇｅに対応する第１処理部５０２および内蔵メモリ５０３の動作について説明する。
【００８３】
第１処理部５０２は、制御信号ｉ＿ｖａｌｉｄに従って検索動作を実行する。具体的には、第１処理部５０２は、制御信号ｉ＿ｖａｌｉｄ＝「１」に従って内蔵メモリ５０３に格納されたエントリデータに検索キーｉ＿ｋｅｙが一致するか否かの検索動作を実行する。
【００８４】
制御信号ｉ＿ｖａｌｉｄは、内蔵メモリ５０３に対する読出コマンドｒｅａｄとして入力される。
【００８５】
内蔵メモリ５０３は、読出コマンドｒｅａｄ＝「１」の入力およびアドレス信号ａｄｄｒｅｓｓとして入力される検索アドレスｉ＿ａｄｄの入力に従って読出動作を実行する。そして、内蔵メモリ５０３は、指定されたアドレスに格納されているエントリデータｉ＿ｄａｔａを第１処理部５０２に出力する。
【００８６】
第１処理部５０２は、エントリデータｉ＿ｄａｔａと、検索キーｉ＿ｋｅｙとが一致するか否かを判断し、一致すると判断した場合には、一致結果（hit「１」）およびエントリデータｉ＿ｄａｔａに含まれる出力データｏ＿ｄａｔａを出力する。
【００８７】
ここで、出力データｏ＿ｄａｔａは検索キーとエントリデータとが一致した場合に第１処理部５０２から出力されるデータであり、検索テーブルに格納されるエントリデータごとに設定される。
【００８８】
一方、第１処理部５０２は、エントリデータｉ＿ｄａｔａと、検索キーｉ＿ｋｅｙとが一致するか否かを判断し、一致しないと判断した場合には、不一致結果（hit「０」）を出力する。この場合には、第１処理部５０２は、出力データｏ＿ｄａｔａは出力しない。
【００８９】
そして、第１処理部５０２は、次段の第１処理部５０２に対して制御信号ｏ＿ｖａｌｉｄ＝「１」、検索キーｏ＿ｋｅｙおよび検索アドレスｏ＿ａｄｄを出力する。
【００９０】
次段の第１処理部５０２は、上記で説明したように、制御信号i＿ｖａｌｉｄ、検索キーi＿ｋｅｙおよび検索アドレスi＿ａｄｄの入力を受けて上記と同様の処理を繰り返す。
【００９１】
上記の例においては、検索ステージＳｔａｇｅ［１］〜Ｓｔａｇｅ［１２］にそれぞれ対応する第１処理部５０２−１〜５０２−１２および内蔵メモリ５０３−１〜５０３−１２との間で上記処理を実行する。
【００９２】
図９は、実施形態１に従う第２処理部５０４、インタフェース回路５０５およびメモリ５０６の動作について説明する図である。
【００９３】
図９を参照して、第２処理部５０４は、メモリ５０６と協働して第２グループのエントリデータ群の検索動作を実行する。
【００９４】
第２処理部５０４は、第２グループのエントリデータ群に対する検索動作を連続的に実行する検索エンジン６００を含む。
【００９５】
インタフェース回路５０５は、複数のＦＩＦＯバッファ７０２と、選択回路７０１，７０３と、バンク選択回路７０４と、複数のフリップフロップＦＦ７０５とを含む。
【００９６】
第２処理部５０４は、最終の第１処理部５０２の検索結果を受けてＦＩＦＯバッファ７０２に出力する。
【００９７】
複数のＦＩＦＯバッファ７０２は、各々複数の格納領域を有する。
複数のメモリバンクＢａｎｋにそれぞれ対応して複数のＦＩＦＯバッファ７０２がそれぞれ設けられる。具体的には、一例としてメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］にそれぞれ対応して複数のＦＩＦＯバッファ７０２が設けられている。
【００９８】
一例として１つのメモリバンクＢａｎｋに対応して設けられるＦＩＦＯバッファ７０２には、４つの格納領域が設けられている。
【００９９】
各格納領域は、検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとを格納することが可能である。ＦＩＦＯバッファ７０２は、データの入力順に従って出力される。
【０１００】
最初の検索キーＫｅｙは、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２に格納される。
【０１０１】
複数のＦＩＦＯバッファ７０２は、それぞれ選択回路７０３にデータを出力する。
バンク選択回路７０４は、選択回路７０３に出力されている複数のＦＩＦＯバッファ７０２からのデータを選択する信号を出力する。
【０１０２】
選択回路７０３は、バンク選択回路７０４からの選択信号に従って複数のＦＩＦＯバッファ７０２からのデータの１つをメモリ５０６に出力する。なお、メモリ５０６には、ＦＩＦＯバッファ７０２に格納されているデータのうち検索アドレスａｄｄと、指定するバンクアドレスｂｋとを出力する。メモリ５０６は、検索アドレスａｄｄと指定するバンクアドレスｂｋとに基づいて指定されたアドレスに格納されているエントリデータを第２処理部５０４に出力する。
【０１０３】
また、選択回路７０３から出力されたデータは、複数のフリップフロップ（ＦＦ）７０５に格納される。
【０１０４】
具体的には、複数のフリップフロップ（ＦＦ）７０５は、検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとをそれぞれ格納する。
【０１０５】
本例においては３段のフリップフロップ（ＦＦ）７０５が設けられている。当該３段のフリップフロップ（ＦＦ）７０５は、メモリ５０６にアクセスしてデータが読み出されるまでのレイテンシに基づいて設けられたものである。
【０１０６】
メモリ５０６にアクセスして、当該アクセスに基づくエントリデータi＿ｄａｔａが検索エンジン６００に入力されるタイミングと同じタイミングで、アクセスする際に用いたデータが検索エンジン６００に入力されるようにタイミング調整するためのものである。
【０１０７】
当該フリップフロップ（ＦＦ）７０５の段数は任意の個数に調整可能である。
検索エンジン６００は、メモリ５０６に格納されているエントリデータと、検索キーＫｅｙとが一致するか否かの検索動作を実行する。
【０１０８】
検索エンジン６００は、エントリデータｉ＿ｄａｔａと、検索キーｋｅｙとが一致するか否かを判断し、一致すると判断した場合には、一致結果（hit「１」）およびエントリデータｉ＿ｄａｔａに含まれる出力データｏ＿ｄａｔａを出力する。
【０１０９】
一方、検索エンジン６００は、エントリデータｉ＿ｄａｔａと、検索キーｋｅｙとが一致するか否かを判断し、一致しないと判断した場合には、出力データｏ＿ｄａｔａを出力しない。
【０１１０】
そして、検索エンジン６００は、検索動作を再度実行するために検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとを選択回路７０１に出力する。
【０１１１】
選択回路７０１は、複数のＦＩＦＯバッファ７０２のいずれかに出力する。
具体的には、バンクアドレスｂｋに従って次のメモリバンクＢａｎｋに対応するＦＩＦＯバッファ７０２に出力する。例えば、選択回路７０１は、前回の検索動作の際にメモリバンクＢａｎｋ［０］が指定されていた場合には、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ７０２に検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとを出力して格納する。検索キーＫｅｙとエントリデータｉ＿ｄａｔａとが一致しない場合には、当該処理をメモリバンクＢａｎｋ［７］に対応するＦＩＦＯバッファ７０２に格納するまで繰り返す。
【０１１２】
図１０は、実施形態１に従う複数の検索キーＫ０〜Ｋ３の検索動作について説明する図である。
【０１１３】
図１０を参照して、本例においては、検索キーＫ０〜Ｋ３が連続的に入力されて検索動作を実行する場合が示されている。
【０１１４】
検索キーＫ０〜Ｋ３は、まず、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２に順次格納される。
【０１１５】
次に、選択回路７０３は、バンク選択回路７０４からの選択信号に従って複数のＦＩＦＯバッファ７０２からのデータの１つをメモリ５０６に出力する。
【０１１６】
本例においては、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２に格納されているデータを出力する。
【０１１７】
選択回路７０３は、検索キーＫ０および検索キーＫ０とともに入力されたアドレスデータをメモリ５０６に出力する。
【０１１８】
また、フリップフロップ（ＦＦ）７０５に、検索キーＫ０および検索キーＫ０とともに入力されたアドレスデータが格納される。
【０１１９】
図１１は、実施形態１に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その１）である。
【０１２０】
図１１を参照して、サイクルＴ−０において、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２から検索キーＫ０が出力される。これにより、検索キーＫ０に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０１２１】
次のサイクルＴ−１〜Ｔ−７においては、メモリバンクＢａｎｋ［１］〜［７］にそれぞれ対応するＦＩＦＯバッファ７０２にデータが格納されていないためメモリ５０６による検索動作は実行しない。
【０１２２】
次に、サイクルＴ−８においては、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２から検索キーＫ１が出力される。これにより、検索キーＫ１に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０１２３】
次のサイクルＴ−９においては、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ７０２から検索キーＫ０が出力される。これにより、検索キーＫ０に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［１］に対する検索動作を実行する。
【０１２４】
図１２は、実施形態１に従う複数の検索キーＫ０〜Ｋ６の検索動作について説明する図である。
【０１２５】
図１２を参照して、本例においては、検索キーＫ０〜Ｋ６が連続的に入力されて検索動作を実行する場合が示されている。
【０１２６】
検索キーＫ０〜Ｋ６は、上述したようにまず、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２に順次格納される。そして、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２から検索キーが出力される。これにより、検索キーに対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０１２７】
本例においては、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２に検索キーＫ４，Ｋ５，Ｋ６が格納されている場合が示されている。
【０１２８】
また、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ７０２に検索キーＫ１，Ｋ２が格納されている場合が示されている。
【０１２９】
そして、フリップフロップ（ＦＦ）７０５に、検索キーＫ３，Ｋ０および検索キーＫ３，Ｋ０とともに入力されたアドレスデータが格納される。
【０１３０】
図１３は、実施形態１に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その２）である。
【０１３１】
図１３を参照して、サイクルＴ−２０において、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２から検索キーＫ３が出力される。これにより、検索キーＫ３に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０１３２】
また、サイクルＴ−２１において、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ７０２から検索キーＫ０が出力される。これにより、検索キーＫ０に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［１］に対する検索動作を実行する。
【０１３３】
次のサイクルＴ−２２〜Ｔ−２７においては、メモリバンクＢａｎｋ［２］〜［７］にそれぞれ対応するＦＩＦＯバッファ７０２にデータが格納されていないためメモリ５０６による検索動作は実行しない。
【０１３４】
次に、サイクルＴ−２８においては、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２から検索キーＫ４が出力される。これにより、検索キーＫ４に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０１３５】
次のサイクルＴ−２９においては、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ７０２から検索キーＫ１が出力される。これにより、検索キーＫ１に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［１］に対する検索動作を実行する。
【０１３６】
次のサイクルＴ−３０においては、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ７０２から検索キーＫ０が出力される。これにより、検索キーＫ０に対して検索ステージＳｔａｇｅ「１５」のメモリバンクＢａｎｋ［２］に対する検索動作を実行する。
【０１３７】
図１４は、実施形態１に従う複数の検索キーＫ０〜Ｋ２４の検索動作について説明する図である。
【０１３８】
図１４を参照して、本例においては、検索キーＫ０〜Ｋ２４が連続的に入力されて検索動作を実行する場合が示されている。
【０１３９】
検索キーＫ０〜Ｋ２４は、上述したようにまず、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２に順次格納される。そして、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２から検索キーが出力される。これにより、検索キーに対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０１４０】
本例においては、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２に検索キーＫ２２，Ｋ２３，Ｋ２４が格納されている場合が示されている。
【０１４１】
また、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ７０２に検索キーＫ１９，Ｋ２０が格納されている場合が示されている。
【０１４２】
また、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ７０２に検索キーＫ１６，Ｋ１７が格納されている場合が示されている。
【０１４３】
また、メモリバンクＢａｎｋ［３］に対応するＦＩＦＯバッファ７０２に検索キーＫ１３，Ｋ１４が格納されている場合が示されている。
【０１４４】
また、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ７０２に検索キーＫ１０，Ｋ１１が格納されている場合が示されている。
【０１４５】
また、メモリバンクＢａｎｋ［５］に対応するＦＩＦＯバッファ７０２に検索キーＫ７，Ｋ８が格納されている場合が示されている。
【０１４６】
また、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ７０２に検索キーＫ１４，Ｋ５が格納されている場合が示されている。
【０１４７】
また、メモリバンクＢａｎｋ［７］に対応するＦＩＦＯバッファ７０２に検索キーＫ１１，Ｋ２が格納されている場合が示されている。
【０１４８】
そして、フリップフロップ（ＦＦ）７０５に、検索キーＫ６，Ｋ３，Ｋ０および検索キーＫ６，Ｋ３，Ｋ０とともに入力されたアドレスデータが格納される。
【０１４９】
図１５は、実施形態１に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その３）である。
【０１５０】
図１５を参照して、サイクルＴ−４５において、メモリバンクＢａｎｋ［５］に対応するＦＩＦＯバッファ７０２から検索キーＫ６が出力される。これにより、検索キーＫ６に対して検索ステージＳｔａｇｅ「１８」のメモリバンクＢａｎｋ［５］に対する検索動作を実行する。
【０１５１】
サイクルＴ−４６において、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ７０２から検索キーＫ３が出力される。これにより、検索キーＫ３に対して検索ステージＳｔａｇｅ「１９」のメモリバンクＢａｎｋ［６］に対する検索動作を実行する。
【０１５２】
サイクルＴ−４７において、メモリバンクＢａｎｋ［７］に対応するＦＩＦＯバッファ７０２から検索キーＫ０が出力される。これにより、検索キーＫ０に対して検索ステージＳｔａｇｅ「２０」のメモリバンクＢａｎｋ［７］に対する検索動作を実行する。
【０１５３】
サイクルＴ−４８において、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ７０２から検索キーＫ２２が出力される。これにより、検索キーＫ２２に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０１５４】
サイクルＴ−４９において、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ７０２から検索キーＫ１９が出力される。これにより、検索キーＫ１９に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［１］に対する検索動作を実行する。
【０１５５】
サイクルＴ−５０において、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ７０２から検索キー１６が出力される。これにより、検索キーＫ１６に対して検索ステージＳｔａｇｅ「１５」のメモリバンクＢａｎｋ［２］に対する検索動作を実行する。
【０１５６】
サイクルＴ−５１において、メモリバンクＢａｎｋ［３］に対応するＦＩＦＯバッファ７０２から検索キーＫ１３が出力される。これにより、検索キーＫ１３に対して検索ステージＳｔａｇｅ「１６」のメモリバンクＢａｎｋ［３］に対する検索動作を実行する。
【０１５７】
サイクルＴ−５２において、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ７０２から検索キーＫ１０が出力される。これにより、検索キーＫ１０に対して検索ステージＳｔａｇｅ「１７」のメモリバンクＢａｎｋ［４］に対する検索動作を実行する。
【０１５８】
サイクルＴ−５３において、メモリバンクＢａｎｋ［５］に対応するＦＩＦＯバッファ７０２から検索キーＫ７が出力される。これにより、検索キーＫ７に対して検索ステージＳｔａｇｅ「１８」のメモリバンクＢａｎｋ［５］に対する検索動作を実行する。
【０１５９】
サイクルＴ−５４において、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ７０２から検索キーＫ４が出力される。これにより、検索キーＫ４に対して検索ステージＳｔａｇｅ「１９」のメモリバンクＢａｎｋ［６］に対する検索動作を実行する。
【０１６０】
サイクルＴ−５５において、メモリバンクＢａｎｋ［７］に対応するＦＩＦＯバッファ７０２から検索キーＫ１が出力される。これにより、検索キーＫ１に対して検索ステージＳｔａｇｅ「２０」のメモリバンクＢａｎｋ［７］に対する検索動作を実行する。
【０１６１】
当該方式に示されるように、検索動作の際に、メモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に順次アクセスすることにより、ＮＯＰ（No Operation）サイクルを抑制し、複数の検索キーの検索動作の際に効率的な検索動作を実行することが可能である。
【０１６２】
（実施形態２）
上記の実施形態１においては、エントリデータ群を２つのグループに分割し、複数の内蔵メモリ５０３に格納する第１グループのエントリデータ群と、メモリ５０６に格納する第２グループのエントリデータ群とに分割する場合について説明した。そして、第１グループ以外の残りのエントリデータ群について、メモリバンクＢａｎｋの個数に対応する８個の検索ステージＳｔａｇｅに従ってグループ化される複数のサブエントリデータ群に分割する場合について説明した。そして、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅにそれぞれ対応するメモリバンクＢａｎｋに順次格納する場合について説明した。
【０１６３】
この場合、図６に示されるように、前段の検索ステージＳｔａｇｅに対応するメモリバンクＢａｎｋの使用する容量は、後段の検索ステージＳｔａｇｅに対応するメモリバンクＢａｎｋの使用する容量の１／２である。したがって、複数のメモリバンクＢａｎｋが全て同じ容量で設計される場合には、前段の検索ステージＳｔａｇｅに対応するメモリバンクＢａｎｋになるに従って大きい未使用の容量が存在することになる。
【０１６４】
実施形態２においては、効率的にメモリの容量を使用する方式について説明する。
図１６は、実施形態２に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【０１６５】
図１６を参照して、実施形態２に従う検索回路は、プロセッサ６０１と、メモリ６０６とを含む。
【０１６６】
プロセッサ６０１は、複数の第１処理部６０２−１〜６０２−（Ｋ−４）と、複数の内蔵メモリ６０３−１〜６０３−（Ｋ−４）と、第２処理部６０４と、第２処理部６０４とメモリ６０６との間のデータの授受を実行するインタフェース回路６０５とを含む。
【０１６７】
複数の第１処理部６０２−１〜６０２−（Ｋ−４）と、複数の内蔵メモリ６０３−１〜６０３−（Ｋ−４）はそれぞれ対応付けられており、パイプライン化されている。
【０１６８】
具体的には、検索キーＫｅｙの入力に対して第１処理部６０２は、内蔵メモリ６０３にアクセスして検索キーＫｅｙと内蔵メモリ６０３に格納されているデータとが一致するか否かを判断する。第１処理部６０２は、検索キーＫｅｙとデータとが一致すると判断した場合には、一致（Ｈｉｔ）と判定する。そして、当該データに関連付けられている情報を出力する。一方、第１処理部６０２は、検索キーＫｅｙとデータとが一致しないと判断した場合には、ミス（Ｍｉｓｓ）と判定する。そして、次段の第１処理部６０２に判定結果とともに検索キーＫｅｙを出力する。
【０１６９】
当該処理を順次繰り返す。
そして、第１処理部６０２−（Ｋ−４）の判定結果が第２処理部６０４に出力される。
【０１７０】
第２処理部６０４は、第１処理部６０２−（Ｋ−４）の判定結果に基づいてインタフェース回路６０５を介してメモリ６０６にアクセスする。
【０１７１】
メモリ６０６は、複数のメモリバンクＢａｎｋを含む。一例として、８個のメモリバンクＢａｎｋが設けられている場合が示されている。
【０１７２】
本例においては、メモリ６０６が有するメモリバンクＢａｎｋ数と異なるメモリアクセス段数（検索ステージ）Ｓｔａｇｅ［Ｋ−３］〜Ｓｔａｇｅ［Ｋ］のエントリデータをそれぞれメモリ５０６の各メモリバンクＢａｎｋに割り当てる。
【０１７３】
残りのメモリアクセス段数（検索ステージ）Ｓｔａｇｅ［１］〜Ｓｔａｇｅ［Ｋ−４］のエントリデータをプロセッサ６０１の内蔵メモリ６０３−１〜６０３−［Ｋ−４］にそれぞれ割り当てる。
【０１７４】
この構成ではプロセッサ６０１で実行するバイナリサーチ（Binary-Search）の検索ステージＳｔａｇｅ［１］〜Ｓｔａｇｅ［Ｋ−４］は，パイプライン処理されるので短いレイテンシと１サイクルのスループットでバイナリサーチ（Binary-Search）を順次実行することが可能である。
【０１７５】
そして、検索ステージＳｔａｇｅ［Ｋ−３］以降の４回のメモリアクセスは、メモリ６０６へアクセスすることになる。
【０１７６】
具体的には、メモリ６０６で実行する検索ステージ数＝Ｌｏｇ2（メモリバンク数Ｍ）＋１に設定する。
【０１７７】
本例においては、検索ステージＳｔａｇｅ４段分のエントリデータ群をメモリ６０６に格納する。
【０１７８】
具体的には、検索ステージＳｔａｇｅ［Ｋ−３］に対応するエントリデータ群をメモリバンクＢａｎｋ［０］に格納する。次に、検索ステージＳｔａｇｅ［Ｋ−２］に対応するエントリデータ群をメモリバンクＢａｎｋ［１］に格納する。次に、検索ステージＳｔａｇｅ［Ｋ−１］に対応するエントリデータ群をメモリバンクＢａｎｋ［２］，Ｂａｎｋ［３］に格納する。次に、検索ステージＳｔａｇｅ［Ｋ］に対応するエントリデータ群をメモリバンクＢａｎｋ［４］，Ｂａｎｋ［５］，Ｂａｎｋ［６］，Ｂａｎｋ［７］に格納する。
【０１７９】
検索動作については、上記の実施形態１で説明したのと基本的に同様であるのでその詳細な説明については繰り返さない。
【０１８０】
実施形態２においては、効率的にメモリ６０６の容量を有効に活用することが可能である。
【０１８１】
（実施形態３）
実施形態３においては、さらに効率的にメモリの容量を使用する方式について説明する。
【０１８２】
図１７は、実施形態３に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【０１８３】
図１７（Ａ）を参照して、実施形態３に従う検索回路は、プロセッサ１１０１と、メモリ１１０６とを含む。
【０１８４】
プロセッサ１１０１は、複数の第１処理部１１０２−１〜１１０２−（Ｋ−８）と、複数の内蔵メモリ１１０３−１〜１１０３−（Ｋ−８）と、第２処理部１１０４と、第２処理部１１０４とメモリ１１０６との間のデータの授受を実行するインタフェース回路１１０５とを含む。複数の第１処理部１１０２−１〜１１０２−（Ｋ−８）は、実施形態１の複数の第１処理部５０２−１〜５０２−（Ｋ−８）と同一の機能を有するものであり、その説明を省略する。
【０１８５】
そして、第１処理部１１０２−（Ｋ−８）の判定結果が第２処理部１１０４に出力される。
【０１８６】
第２処理部１１０４は、第１処理部１１０２−（Ｋ−８）の判定結果に基づいてインタフェース回路１１０５を介してメモリ１１０６にアクセスする。
【０１８７】
メモリ１１０６は、複数のメモリバンクＢａｎｋを含む。一例として、８個のメモリバンクＢａｎｋが設けられている場合が示されている。
【０１８８】
本例においては、メモリ１１０６が有するメモリバンクＢａｎｋ数と同じメモリアクセス段数（検索ステージ）Ｓｔａｇｅ［Ｋ−７］〜Ｓｔａｇｅ［Ｋ］のエントリデータをそれぞれメモリ１１０６の各メモリバンクＢａｎｋに割り当てる。
【０１８９】
この構成ではプロセッサ１１０１で実行するバイナリサーチ（Binary-Search）の検索ステージＳｔａｇｅ［１］〜Ｓｔａｇｅ［Ｋ−８］は、パイプライン処理されるので短いレイテンシと１サイクルのスループットでバイナリサーチ（Binary-Search）を順次実行できる。
【０１９０】
そして、検索ステージＳｔａｇｅ［Ｋ−７］以降の８回のメモリアクセスは、メモリ１１０６へアクセスする。
【０１９１】
図１７（Ｂ）を参照して、本例においては、１Ｍアドレスのエントリデータ群を２つのグループに分割する。
【０１９２】
複数の内蔵メモリ１１０３に格納する第１グループのエントリデータ群と、メモリ１１０６に格納する第２グループのエントリデータ群とに分割する。
【０１９３】
第１グループのエントリデータ群はメモリ１１０３に格納される。
次に、第１グループ以外の残りの第２グループのエントリデータ群をメモリ１１０６に格納する。メモリ１１０６は、８個のメモリバンクＢａｎｋを有する。
【０１９４】
本例においては、残りのエントリデータ群について、８個のメモリバンクＢａｎｋに対応する８個の検索ステージＳｔａｇｅに従ってグループ化される複数のサブエントリデータ群に分割する。本例においては、複数のサブエントリデータ群ＢＬＫ［０］〜ＢＬＫ［４０９５］に分割される。
【０１９５】
１つのサブエントリデータ群ＢＬＫは、２５６個のエントリデータで構成される。各サブエントリデータ群ＢＬＫのエントリデータは、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］のそれぞれに対応し、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］に対応するエントリデータがメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に順次格納される。
【０１９６】
本実施形態３においては、サブエントリデータ群ＢＬＫ［０］は、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］に対応するエントリデータがメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に順次格納される。サブエントリデータ群ＢＬＫ［１］は、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］に対応するエントリデータがメモリバンクＢａｎｋ［１］〜Ｂａｎｋ［７］およびＢａｎｋ［０］に順次格納される。サブエントリデータ群ＢＬＫ［２］は、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］に対応するエントリデータがメモリバンクＢａｎｋ［２］〜Ｂａｎｋ［７］およびＢａｎｋ［０］，「１」に順次格納される。
【０１９７】
他のサブエントリデータ群ＢＬＫについても同様の方式に従ってメモリバンクＢａｎｋに格納する。すなわち、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］毎に、対応するメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］のいずれかに順次格納される。
【０１９８】
当該方式により、検索ステージＳｔａｇｅが後段に対応するメモリバンクＢａｎｋにエントリデータが集中することを回避することが可能であり、各メモリバンクＢａｎｋの使用容量を平滑化することが可能である。また、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］毎に、対応するメモリバンクＢａｎｋが異なるため同一のメモリバンクＢａｎｋへのアクセス制限による待機時間ｔＲＣにより検索性能が低下することを抑制することも可能である。
【０１９９】
図１８は、実施形態３に従う第２処理部１１０４、インタフェース回路１１０５およびメモリ１１０６の動作について説明する図である。
【０２００】
図１８を参照して、第２処理部１１０４は、メモリ１１０６と協働して第２グループのエントリデータ群の検索動作を実行する。
【０２０１】
第２処理部１１０４は、第２グループのエントリデータ群に対する検索動作を連続的に実行する検索エンジン１３０７と、アドレスエンコーダ１３０８とを含む。
【０２０２】
インタフェース回路１１０５は、複数のＦＩＦＯバッファ１３０２と、選択回路１３０１，１３０３と、バンク選択回路１３０４と、複数のフリップフロップ（ＦＦ）１３０５とを含む。
【０２０３】
アドレスエンコーダ１３０８は、最終の処理部１１０２の検索結果を受けて、次の検索ステージＳｔａｇｅ［１３］に対応するメモリ１１０６のメモリバンクＢａｎｋを指定するアドレスに変換する。例えば、アドレスエンコーダ１３０８は、最終の処理部１１０２の検索結果に基づき、次にアクセスされるサブエントリデータ群ＢＬＫのブロックアドレスをｎＢＬＫ、メモリ１１０６で実施される残りの検索回数をｎＳｔａｇｅ、メモリ１１０６が有するメモリバンク数をｎＢａｎｋとすると、メモリバンクＢａｎｋを指定するアドレスは、（ｎＢＬＫ＋ｎＳｔａｇｅ）％ｎＢａｎｋで求められる。また、アドレスエンコーダ１３０８は、メモリ１１０６のメモリバンク内での検索アドレスも生成する。そして、アドレスエンコーダ１３０８は、選択回路１３０１に対して、これら変換したアドレスと検索キーＫｅｙとを出力する。
【０２０４】
上記したように各サブエントリデータ群ＢＬＫ毎に、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］のそれぞれ対応するメモリバンクＢａｎｋは異なる。
【０２０５】
一例として、サブエントリデータ群ＢＬＫ［０］の検索Ｓｔａｇｅ［１３］に対応するエントリデータを検索する場合には、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１１０２に検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとを格納する。
【０２０６】
また、サブエントリデータ群ＢＬＫ［１］の検索Ｓｔａｇｅ［１３］に対応するエントリデータを検索する場合には、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ１１０２に検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとを格納する。
【０２０７】
他のサブエントリデータ群ＢＬＫのエントリデータを検索する場合についても同様である。
【０２０８】
選択回路１３０１は、複数の調停回路１３０６を含む。
複数の調停回路１３０６は、メモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］にそれぞれ対応して設けられる複数のＦＩＦＯバッファ１３０２にそれぞれ対応している。
【０２０９】
調停回路１３０６は、ＦＩＦＯバッファ１３１０と、セレクタ１３１１とを含む。
セレクタ１３１１は、ＦＩＦＯバッファ１３１０の出力と検索エンジン１３０７からの出力結果を受けて、いずれか一方を出力する。本例においては、検索エンジン１３０７からの出力結果を優先して出力する。
【０２１０】
検索エンジン１３０７からの出力結果を受けた場合には、当該出力結果を対応するＦＩＦＯバッファ１３０２に出力する。一方、検索エンジン１３０７からの出力結果を受けない場合には、ＦＩＦＯバッファ１３１０に格納されている情報をＦＩＦＯバッファ１３０２に出力する。
【０２１１】
複数のＦＩＦＯバッファ１３０２は、各々複数の格納領域を有する。
複数のメモリバンクＢａｎｋにそれぞれ対応して複数のＦＩＦＯバッファ１３０２がそれぞれ設けられる。具体的には、一例としてメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］にそれぞれ対応して複数のＦＩＦＯバッファ１３０２が設けられている。
【０２１２】
一例として１つのメモリバンクＢａｎｋに対応して設けられるＦＩＦＯバッファ１３０２には、４つの格納領域が設けられている。
【０２１３】
各格納領域は、検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとを格納することが可能である。ＦＩＦＯバッファ１３０２は、データの入力順に従って出力される。
【０２１４】
複数のＦＩＦＯバッファ１３０２は、それぞれ選択回路１３０３にデータを出力する。
バンク選択回路１３０４は、選択回路１３０３に出力されている複数のＦＩＦＯバッファ１３０２からのデータを選択する信号を出力する。
【０２１５】
選択回路１３０３は、バンク選択回路１３０４からの選択信号に従って複数のＦＩＦＯバッファ１３０２からのデータの１つをメモリ１１０６に出力する。なお、メモリ１１０６には、ＦＩＦＯバッファ１３０２に格納されているデータのうち検索アドレスａｄｄと、指定するバンクアドレスｂｋとを出力する。メモリ１１０６は、検索アドレスａｄｄと指定するバンクアドレスｂｋとに基づいて指定されたアドレスに格納されているエントリデータを第２処理部１１０４に出力する。
【０２１６】
また、選択回路１３０３から出力されたデータは、複数のフリップフロップ（ＦＦ）１３０５に格納される。
【０２１７】
具体的には、複数のフリップフロップ（ＦＦ）１３０５は、検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとをそれぞれ格納する。
【０２１８】
本例においては３段のフリップフロップ（ＦＦ）１３０５が設けられている。当該３段のフリップフロップ（ＦＦ）１３０５は、メモリ１１０６にアクセスしてデータが読み出されるまでのレイテンシに基づいて設けられたものである。
【０２１９】
メモリ１１０６にアクセスして、当該アクセスに基づくエントリデータi＿ｄａｔａが検索エンジン１３０７に入力されるタイミングと同じタイミングで、アクセスする際に用いたデータが検索エンジン１３０７に入力されるようにタイミング調整するためのものである。
【０２２０】
当該フリップフロップ（ＦＦ）１３０５の段数は任意の個数に調整可能である。
検索エンジン１３０７は、メモリ１１０６に格納されているエントリデータと、検索キーＫｅｙとが一致するか否かの検索動作を実行する。
【０２２１】
検索エンジン１３０７は、エントリデータｉ＿ｄａｔａと、検索キーｋｅｙとが一致するか否かを判断し、一致すると判断した場合には、一致結果（hit「１」）およびエントリデータｉ＿ｄａｔａに含まれる出力データｏ＿ｄａｔａを出力する。
【０２２２】
一方、検索エンジン１３０７は、エントリデータｉ＿ｄａｔａと、検索キーｋｅｙとが一致するか否かを判断し、一致しないと判断した場合には、出力データｏ＿ｄａｔａを出力しない。
【０２２３】
そして、検索エンジン１３０７は、検索動作を再度実行するために検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとを選択回路１３０１に出力する。
【０２２４】
選択回路１３０１は、これら検索キーＫｅｙと、検索アドレスａｄｄと指定するバンクアドレスｂｋとを複数のＦＩＦＯバッファ１３０２のいずれかに出力する。
【０２２５】
具体的には、バンクアドレスｂｋに従って次のメモリバンクＢａｎｋに対応するＦＩＦＯバッファ１３０２に出力する。例えば、選択回路１３０１は、前回の検索動作の際にメモリバンクＢａｎｋ［０］が指定されていた場合には、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ１３０２に検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとを出力して格納する。検索キーＫｅｙとエントリデータｉ＿ｄａｔａとが一致しない場合には、当該処理を最終のメモリバンクＢａｎｋに対応するＦＩＦＯバッファ１３０２に格納するまで繰り返す。
【０２２６】
上述したように、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅ［１３］〜Ｓｔａｇｅ［２０］毎に、対応するメモリバンクＢａｎｋが異なる。したがって、当該方式により、複数のＦＩＦＯバッファ１３０２のいずれかに検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとが出力されて格納される。すなわち、上記の実施形態１の方式では、検索ステージＳｔａｇｅ［１３］に対応するメモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファに検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋが最初に格納されていた。一方、実施形態３に従う方式では、検索キーＫｅｙと、検索アドレスａｄｄと、指定するバンクアドレスｂｋとが複数のＦＩＦＯバッファ１３０２のいずれかに出力されて分散的に格納される。
【０２２７】
したがって、検索ステージごとに異なるメモリバンクにアクセスし、各メモリバンクに割り当てられるエントリ数が平均化でき、結果、メモリを効率的に利用できる。
【０２２８】
図１９は、実施形態３に従う複数の検索キーＫ０〜Ｋ７の検索動作について説明する図である。
【０２２９】
図１９を参照して、本例においては、検索キーＫ０〜Ｋ７が連続的に入力されて検索動作を実行する場合が示されている。ここでは、検索キーＫ０〜Ｋ７がプロセッサ１１０１で検索された結果に基づいてアドレスエンコーダ１３０８が指定したメモリバンクが、すべて偶数バンクである場合について説明する。すなわち、検索ステージＳｔａｇｅ「１３」に対応するエントリデータが偶数バンクに格納されているとする。
【０２３０】
すなわち、検索キーＫ０は、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１は、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ２は、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ３は、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ４は、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ５は、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ６は、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ７は、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２に格納される。すなわち、検索キーＫ（４ｎ＋０）は、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に最初に格納される。検索キーＫ（４ｎ＋１）は、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２に最初に格納される。検索キーＫ（４ｎ＋２）は、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２に最初に格納される。検索キーＫ（４ｎ＋３）は、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２に最初に格納される。
【０２３１】
すなわち、検索キーＫ（４ｎ＋０）は、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に最初に格納される。検索キーＫ（４ｎ＋１）は、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２に最初に格納される。検索キーＫ（４ｎ＋２）は、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２に最初に格納される。検索キーＫ（４ｎ＋３）は、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２に最初に格納されるものとする。
【０２３２】
次に、選択回路１３０３は、バンク選択回路１３０４からの選択信号に従って複数のＦＩＦＯバッファ１３０２からのデータの１つをメモリ１１０６に出力する。
【０２３３】
本例においては、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に格納されているデータを出力する。
【０２３４】
選択回路１３０３は、検索キーＫ０および検索キーＫ０とともに入力されたアドレスデータをメモリ１１０６に出力する。
【０２３５】
また、フリップフロップ（ＦＦ）１３０５に、検索キーＫ０および検索キーＫ０とともに入力されたアドレスデータが格納される。
【０２３６】
図２０は、実施形態３に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その１）である。
【０２３７】
図２０を参照して、サイクルＴ−６０において、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２から検索キーＫ０が出力される。これにより、検索キーＫ０に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０２３８】
次のサイクルＴ−６１においては、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ１３０２にデータが格納されていないためメモリ１１０６による検索動作は実行しない。
【０２３９】
次のサイクルＴ−６２においては、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１が出力される。これにより、検索キーＫ１に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［２］に対する検索動作を実行する。
【０２４０】
次のサイクルＴ−６３においては、メモリバンクＢａｎｋ［３］に対応するＦＩＦＯバッファ１３０２にデータが格納されていないためメモリ１１０６による検索動作は実行しない。
【０２４１】
次のサイクルＴ−６４においては、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２から検索キーＫ２が出力される。これにより、検索キーＫ２に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［４］に対する検索動作を実行する。
【０２４２】
次のサイクルＴ−６５においては、メモリバンクＢａｎｋ［５］に対応するＦＩＦＯバッファ１３０２にデータが格納されていないためメモリ１１０６による検索動作は実行しない。
【０２４３】
次のサイクルＴ−６６においては、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２から検索キーＫ３が出力される。これにより、検索キーＫ３に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［６］に対する検索動作を実行する。
【０２４４】
次のサイクルＴ−６７においては、メモリバンクＢａｎｋ［７］に対応するＦＩＦＯバッファ１３０２にデータが格納されていないためメモリ１１０６による検索動作は実行しない。
【０２４５】
次のサイクルＴ−６８においては、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２から検索キーＫ４が出力される。これにより、検索キーＫ４に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０２４６】
次のサイクルＴ−６９においては、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ１３０２にデータが格納されていないためメモリ１１０６による検索動作は実行しない。
【０２４７】
次のサイクルＴ−７０においては、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２から検索キーＫ５が出力される。これにより、検索キーＫ５に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［２］に対する検索動作を実行する。
【０２４８】
次のサイクルＴ−７１においては、メモリバンクＢａｎｋ［３］に対応するＦＩＦＯバッファ１３０２にデータが格納されていないためメモリ１１０６による検索動作は実行しない。
【０２４９】
次のサイクルＴ−７２においては、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２から検索キーＫ６が出力される。これにより、検索キーＫ６に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［４］に対する検索動作を実行する。
【０２５０】
次のサイクルＴ−７３においては、メモリバンクＢａｎｋ［５］に対応するＦＩＦＯバッファ１３０２にデータが格納されていないためメモリ１１０６による検索動作は実行しない。
【０２５１】
次のサイクルＴ−７４においては、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２から検索キーＫ７が出力される。これにより、検索キーＫ７に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［２］に対する検索動作を実行する。
【０２５２】
次のサイクルＴ−７５においては、メモリバンクＢａｎｋ［７］に対応するＦＩＦＯバッファ１３０２にデータが格納されていないためメモリ１１０６による検索動作は実行しない。
【０２５３】
図２１は、実施形態３に従う複数の検索キーＫ０〜Ｋ１５の検索動作について説明する図である。
【０２５４】
図２１を参照して、本例においては、検索キーＫ０〜Ｋ１５が連続的に入力されて検索動作を実行する場合が示されている。ここで、検索キーＫ０〜Ｋ１５がプロセッサ１１０１によって検索された結果に基づいて、最初にアドレスエンコーダが指定するメモリバンクがすべて偶数バンクである場合について説明する。
【０２５５】
検索キーＫ０〜Ｋ７は、上述したように、まず、メモリバンクＢａｎｋ［０］，Ｂａｎｋ［２］，Ｂａｎｋ［４］，Ｂａｎｋ［６］にそれぞれ対応するＦＩＦＯバッファ１３０２に順次格納される。例えば、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２から検索キーが出力される。検索キーに対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０２５６】
検索ステージＳｔａｇｅ「１３」の検索処理が実行されると、次の検索ステージＳｔａｇｅ「１４」では、検索を開始したメモリバンクの隣のバンクが指定される。図２１では、検索キーＫ０〜Ｋ５については、検索動作に従って検索ステージＳｔａｇｅ「１４」の検索動作として、メモリバンクＢａｎｋ［１］，Ｂａｎｋ［３］，Ｂａｎｋ［５］，Ｂａｎｋ［７］に対応するＦＩＦＯバッファ１３０２が指定される場合が示されている。
【０２５７】
また、新たな検索キーＫ８〜Ｋ１５が連続的に入力されて検索動作を実行する場合が示されている。
【０２５８】
検索キーＫ８は、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ９は、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１０は、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１１は、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１２は、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１３は、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１４は、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１５は、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２に格納される。
【０２５９】
そして、フリップフロップ（ＦＦ）１３０５に、検索キーＫ６，Ｋ７および検索キーＫ６，Ｋ７とともに入力されたアドレスデータが格納される。
【０２６０】
図２２は、実施形態３に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その２）である。
【０２６１】
図２２を参照して、サイクルＴ−８０において、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２から検索キーＫ８が出力される。これにより、検索キーＫ８に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０２６２】
また、サイクルＴ−８１において、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ１３０２から検索キーＫ０が出力される。これにより、検索キーＫ０に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［１］に対する検索動作を実行する。
【０２６３】
サイクルＴ−８２において、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２から検索キーＫ９が出力される。これにより、検索キーＫ９に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［２］に対する検索動作を実行する。
【０２６４】
また、サイクルＴ−８３において、メモリバンクＢａｎｋ［３］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１が出力される。これにより、検索キーＫ１に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［３］に対する検索動作を実行する。
【０２６５】
サイクルＴ−８４において、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１０が出力される。これにより、検索キーＫ１０に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［４］に対する検索動作を実行する。
【０２６６】
また、サイクルＴ−８５において、メモリバンクＢａｎｋ［５］に対応するＦＩＦＯバッファ１３０２から検索キーＫ２が出力される。これにより、検索キーＫ２に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［５］に対する検索動作を実行する。
【０２６７】
サイクルＴ−８６において、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１１が出力される。これにより、検索キーＫ１１に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［６］に対する検索動作を実行する。
【０２６８】
また、サイクルＴ−８７において、メモリバンクＢａｎｋ［７］に対応するＦＩＦＯバッファ１３０２から検索キーＫ３が出力される。これにより、検索キーＫ３に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［７］に対する検索動作を実行する。
【０２６９】
サイクルＴ−８８〜Ｔ９６についても同様の処理が実行される。
図２３は、実施形態３に従う複数の検索キーＫ０〜Ｋ２３の検索動作について説明する図である。
【０２７０】
図２３を参照して、本例においては、検索キーＫ０〜Ｋ２３が連続的に入力されて検索動作を実行する場合が示されている。
【０２７１】
検索キーＫ０〜Ｋ２３は、上述したようにまず、メモリバンクＢａｎｋ［０］，Ｂａｎｋ［２］，Ｂａｎｋ［４］，Ｂａｎｋ［６］にそれぞれ対応するＦＩＦＯバッファ１３０２に順次格納される。
【０２７２】
そして、検索キーＫ０〜Ｋ５については、検索動作に従って検索ステージＳｔａｇｅ「１５」のメモリバンクＢａｎｋ［２］，Ｂａｎｋ［４］，Ｂａｎｋ［６］，Ｂａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に格納されている場合が示されている。
【０２７３】
また、新たな検索キーＫ１６〜Ｋ２３が連続的に入力されて検索動作を実行する場合が示されている。
【０２７４】
検索キーＫ１６は、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１７は、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１８は、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ１９は、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ２０は、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ２１は、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ２２は、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２に格納される。検索キーＫ２３は、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２に格納される。
【０２７５】
そして、フリップフロップ（ＦＦ）１３０５に、検索キーＫ６，Ｋ７および検索キーＫ６，Ｋ７とともに入力されたアドレスデータが格納される。
【０２７６】
図２４は、実施形態３に従う複数の検索キーの検索動作のタイミングチャートについて説明する図（その３）である。
【０２７７】
図２４を参照して、サイクルＴ−１００において、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１６が出力される。これにより、検索キーＫ１６に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０２７８】
また、サイクルＴ−１０１において、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ１３０２から検索キーＫ８が出力される。これにより、検索キーＫ８に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［１］に対する検索動作を実行する。
【０２７９】
サイクルＴ−１０２において、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１７が出力される。これにより、検索キーＫ１７に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［２］に対する検索動作を実行する。
【０２８０】
また、サイクルＴ−１０３において、メモリバンクＢａｎｋ［３］に対応するＦＩＦＯバッファ１３０２から検索キーＫ９が出力される。これにより、検索キーＫ９に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［３］に対する検索動作を実行する。
【０２８１】
サイクルＴ−１０４において、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１８が出力される。これにより、検索キーＫ１８に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［４］に対する検索動作を実行する。
【０２８２】
また、サイクルＴ−１０５において、メモリバンクＢａｎｋ［５］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１０が出力される。これにより、検索キーＫ１０に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［５］に対する検索動作を実行する。
【０２８３】
サイクルＴ−１０６において、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１９が出力される。これにより、検索キーＫ１９に対して検索ステージＳｔａｇｅ「１３」のメモリバンクＢａｎｋ［６］に対する検索動作を実行する。
【０２８４】
また、サイクルＴ−１０７において、メモリバンクＢａｎｋ［７］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１１が出力される。これにより、検索キーＫ１１に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［７］に対する検索動作を実行する。
【０２８５】
サイクルＴ−１０８において、メモリバンクＢａｎｋ［０］に対応するＦＩＦＯバッファ１３０２から検索キーＫ３が出力される。これにより、検索キーＫ３に対して検索ステージＳｔａｇｅ「１５」のメモリバンクＢａｎｋ［０］に対する検索動作を実行する。
【０２８６】
また、サイクルＴ−１０９において、メモリバンクＢａｎｋ［１］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１２が出力される。これにより、検索キーＫ１２に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［１］に対する検索動作を実行する。
【０２８７】
サイクルＴ−１１０において、メモリバンクＢａｎｋ［２］に対応するＦＩＦＯバッファ１３０２から検索キーＫ０が出力される。これにより、検索キーＫ０に対して検索ステージＳｔａｇｅ「１５」のメモリバンクＢａｎｋ［２］に対する検索動作を実行する。
【０２８８】
また、サイクルＴ−１１１において、メモリバンクＢａｎｋ［３］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１３が出力される。これにより、検索キーＫ１３に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［３］に対する検索動作を実行する。
【０２８９】
サイクルＴ−１１２において、メモリバンクＢａｎｋ［４］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１が出力される。これにより、検索キーＫ１に対して検索ステージＳｔａｇｅ「１５」のメモリバンクＢａｎｋ［４］に対する検索動作を実行する。
【０２９０】
また、サイクルＴ−１１３において、メモリバンクＢａｎｋ［５］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１４が出力される。これにより、検索キーＫ１４に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［５］に対する検索動作を実行する。
【０２９１】
サイクルＴ−１１４において、メモリバンクＢａｎｋ［６］に対応するＦＩＦＯバッファ１３０２から検索キーＫ２が出力される。これにより、検索キーＫ２に対して検索ステージＳｔａｇｅ「１５」のメモリバンクＢａｎｋ［６］に対する検索動作を実行する。
【０２９２】
また、サイクルＴ−１１５において、メモリバンクＢａｎｋ［７］に対応するＦＩＦＯバッファ１３０２から検索キーＫ１５が出力される。これにより、検索キーＫ１５に対して検索ステージＳｔａｇｅ「１４」のメモリバンクＢａｎｋ［７］に対する検索動作を実行する。
【０２９３】
当該方式に示されるように、検索動作の際に、メモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に順次アクセスすることにより、ＮＯＰ（No Operation）サイクルを抑制し、複数の検索キーの検索動作の際に効率的な検索動作を実行することが可能である。
【０２９４】
（変形例）
図２５は、実施形態３の変形例に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【０２９５】
図２５（Ａ）を参照して、実施形態３に従う検索回路は、プロセッサ１４０１と、メモリ１４０６とを含む。
【０２９６】
プロセッサ１４０１は、複数の第１処理部１４０２−１〜１４０２−（Ｋ−６）と、複数の内蔵メモリ１４０３−１〜１４０３−（Ｋ−６）と、第２処理部１４０４と、第２処理部１４０４とメモリ１４０６との間のデータの授受を実行するインタフェース回路１４０５とを含む。複数の第１処理部１４０２−１〜１４０２−（Ｋ−６）は、実施形態１の複数の第１処理部５０２−１〜５０２−（Ｋ−８）と同一の機能を有するものであり、その説明を省略する。
【０２９７】
そして、第１処理部１４０２−（Ｋ−６）の判定結果が第２処理部１４０４に出力される。
【０２９８】
第２処理部１４０４は、第１処理部１４０２−（Ｋ−６）の判定結果に基づいてインタフェース回路１４０５を介してメモリ１４０６にアクセスする。
【０２９９】
メモリ１４０６は、複数のメモリバンクＢａｎｋを含む。一例として、８個のメモリバンクＢａｎｋが設けられている場合が示されている。
【０３００】
本例においては、メモリ１４０６が有するメモリバンクＢａｎｋ数よりも少ないメモリアクセス段数（検索ステージ）Ｓｔａｇｅ［Ｋ−５］〜Ｓｔａｇｅ［Ｋ］のエントリデータをそれぞれメモリ１４０６の各メモリバンクＢａｎｋに割り当てる。
【０３０１】
この構成ではプロセッサ１４０１で実行するバイナリサーチ（Binary-Search）の検索ステージＳｔａｇｅ［１］〜Ｓｔａｇｅ［Ｋ−６］は、パイプライン処理されるので短いレイテンシと１サイクルのスループットでバイナリサーチ（Binary-Search）を順次実行できる。
【０３０２】
そして、検索ステージＳｔａｇｅ［Ｋ−５］以降の６回のメモリアクセスは、メモリ１４０６へアクセスする。
【０３０３】
図２５（Ｂ）を参照して、本例においては、１Ｍアドレスのエントリデータ群を２つのグループに分割する。
【０３０４】
複数の内蔵メモリ１４０３に格納する第１グループのエントリデータ群と、メモリ１４０６に格納する第２グループのエントリデータ群とに分割する。
【０３０５】
第１グループのエントリデータ群は、メモリ１４０３に格納される。
次に、第１グループ以外の残りの第２グループのエントリデータ群をメモリ１４０６に格納する。メモリ１４０６は、８個のメモリバンクＢａｎｋを有する。
【０３０６】
本例においては、残りのエントリデータ群について、６個の検索ステージＳｔａｇｅに従ってグループ化される複数のサブエントリデータ群に分割する。本例においては、複数のサブエントリデータ群ＢＬＫ［０］〜ＢＬＫ［１６３８３］に分割される。
【０３０７】
１つのサブエントリデータ群ＢＬＫは、６４個のエントリデータで構成される。各サブエントリデータ群ＢＬＫのエントリデータは、検索ステージＳｔａｇｅ［１５］〜Ｓｔａｇｅ［２０］のそれぞれに対応し、検索ステージＳｔａｇｅ［１５］〜Ｓｔａｇｅ［２０］に対応するエントリデータがメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に順次格納される。
【０３０８】
実施形態３の変形例においては、サブエントリデータ群ＢＬＫ［０］は、検索ステージＳｔａｇｅ［１５］〜Ｓｔａｇｅ［２０］に対応するエントリデータがメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［５］に順次格納される。サブエントリデータ群ＢＬＫ［１］は、検索ステージＳｔａｇｅ［１５］〜Ｓｔａｇｅ［２０］に対応するエントリデータがメモリバンクＢａｎｋ［１］〜Ｂａｎｋ［６］に順次格納される。サブエントリデータ群ＢＬＫ［２］は、検索ステージＳｔａｇｅ［１５］〜Ｓｔａｇｅ［２０］に対応するエントリデータがメモリバンクＢａｎｋ［２］〜Ｂａｎｋ［７］に順次格納される。
【０３０９】
他のサブエントリデータ群ＢＬＫについても同様の方式に従ってメモリバンクＢａｎｋに格納する。すなわち、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅ［１５］〜Ｓｔａｇｅ［２０］毎に、対応するメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］のいずれかに順次格納される。
【０３１０】
当該方式により、検索ステージＳｔａｇｅが後段に対応するメモリバンクＢａｎｋにエントリデータが集中することを回避することが可能であり、各メモリバンクＢａｎｋの使用容量を平滑化することが可能である。また、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅ［１５］〜Ｓｔａｇｅ［２０］毎に、対応するメモリバンクＢａｎｋが異なるため同一のメモリバンクＢａｎｋへのアクセス制限による待機時間ｔＲＣにより検索性能が低下することを抑制することも可能である。
【０３１１】
１回当たりのバイナリサーチ（Binary-Search）におけるメモリ１４０６にアクセスする回数を８回から６回に削減することにより検索性能を向上させることが可能である。
【０３１２】
次表は、プロセッサで実行するバイナリサーチの段数と、メモリで実行するバイナリサーチの段数との関係を説明するものである。
【０３１３】
【表４】
2020187407.tif 000006
【０３１４】
ここで、上記表に示されるように実施形態３においては、メモリに割り当てる検索ステージＳｔａｇｅ数を変更してもバイナリサーチの検索テーブルを格納するために必要なメモリ容量は同じである。そのため、メモリに割り当てる検索ステージＳｔａｇｅ数はプロセッサに内蔵可能なメモリ容量によって決定することが可能である。
【０３１５】
プロセッサで処理する検索ステージＳｔａｇｅ数が増加すれば、メモリへのアクセス回数が減少するため検索性能は向上する。一方で、プロセッサに内蔵しなければならないエントリ数も増加するためプロセッサをＡＳＩＣやＦＰＧＡで実現する場合、その分メモリリソースを消費する。コストや必要な検索性能などからプロセッサに実装するバイナリサーチの検索ステージＳｔａｇｅ数は柔軟に変更可能であることが望ましい。
【０３１６】
実施形態１および２に従う方式では、メモリが有するメモリバンク数によってメモリに割り当てる検索ステージＳｔａｇｅ数が制限される。一方、実施形態３に従う方式では、メモリへ割り当てる検索ステージＳｔａｇｅ数によってメモリの必要容量は影響されず、ほぼ１００％のメモリ容量をバイナリサーチの検索テーブルとして利用することが可能である。そのため、相反するプロセッサの内蔵メモリの搭載量と検索性能について製品仕様に最適な条件になるよう柔軟にメモリへ割り当てる検索ステージＳｔａｇｅ数を選択することが望ましい。
【０３１７】
（変形例２）
図２６は、実施形態３の変形例２に従うバイナリサーチの検索アルゴリズムの概要について説明する図である。
【０３１８】
図２６（Ａ）を参照して、実施形態３の変形例２に従う検索回路は、プロセッサ１５０１と、メモリ１５０６とを含む。
【０３１９】
プロセッサ１５０１は、複数の第１処理部１５０２−１〜１５０２−４と、複数の内蔵メモリ１５０３−１〜１５０３−４と、第２処理部１５０４と、第２処理部１５０４とメモリ１５０６との間のデータの授受を実行するインタフェース回路１５０５とを含む。
【０３２０】
複数の第１処理部１５０２−１〜１５０２−４と、複数の内蔵メモリ１５０３−１〜１５０３−４はそれぞれ対応付けられており、パイプライン化されている。
【０３２１】
具体的には、検索キーＫｅｙの入力に対して第１処理部１５０２は、内蔵メモリ１５０３にアクセスして検索キーＫｅｙと内蔵メモリ１５０３に格納されているデータとが一致するか否かを判断する。第１処理部１５０２は、検索キーＫｅｙとデータとが一致すると判断した場合には、一致（Ｈｉｔ）と判定する。そして、当該データに関連付けられている情報を出力する。一方、第１処理部１５０２は、検索キーＫｅｙとデータとが一致しないと判断した場合には、ミス（Ｍｉｓｓ）と判定する。そして、次段の第１処理部１５０２に判定結果とともに検索キーＫｅｙを出力する。
【０３２２】
当該処理を順次繰り返す。
そして、第１処理部１５０２−４の判定結果が第２処理部１５０４に出力される。
【０３２３】
第２処理部１５０４は、第１処理部１５０２−４の判定結果に基づいてインタフェース回路１５０５を介してメモリ１５０６にアクセスする。
【０３２４】
メモリ１５０６は、複数のメモリバンクＢａｎｋを含む。一例として、８個のメモリバンクＢａｎｋが設けられている場合が示されている。
【０３２５】
メモリ１５０６に割り当てられた１つのエントリアドレスに対応して２つの検索ステージＳｔａｇｅ数に対応するエントリデータを格納する。
【０３２６】
たとえばメモリ１５０６の１つのエントリアドレスのビット幅が９６ビット以上であるとする。
【０３２７】
この場合、３２ビットのエントリデータを３個格納することが可能である。すなわち、１つのエントリアドレスに対応するメモリセル群に２段分のバイナリサーチのエントリデータを格納する。
【０３２８】
本例においては、メモリ１５０６が有するメモリバンクＢａｎｋ数に対応してメモリアクセス段数（検索ステージ）Ｓｔａｇｅ［５］〜Ｓｔａｇｅ［２０］のエントリデータをそれぞれメモリ１５０６の各メモリバンクＢａｎｋに割り当てる。
【０３２９】
残りのメモリアクセス段数（検索ステージ）Ｓｔａｇｅ［１］〜Ｓｔａｇｅ［４］のエントリデータをプロセッサ１５０１の内蔵メモリ１５０３−１〜１５０３−４にそれぞれ割り当てる。
【０３３０】
この構成ではプロセッサ１５０１で実行するバイナリサーチ（Binary-Search）の検索ステージＳｔａｇｅ［１］〜Ｓｔａｇｅ［４］は，パイプライン処理されるので短いレイテンシと１サイクルのスループットでバイナリサーチ（Binary-Search）を順次実行することが可能である。
【０３３１】
そして、検索ステージＳｔａｇｅ［５］以降の８回のメモリアクセスは、メモリ１５０６へアクセスすることになる。
【０３３２】
図２６（Ｂ）を参照して、本例においては、１Ｍアドレスのエントリデータ群を２つのグループに分割する。
【０３３３】
複数の内蔵メモリ１５０３に格納する第１グループのエントリデータ群と、メモリ１５０６に格納する第２グループのエントリデータ群とに分割する。
【０３３４】
第１グループのエントリデータ群をメモリ１５０３に格納する。
次に、第１グループ以外の残りの第２グループのエントリデータ群をメモリ１５０６に格納する。メモリ１５０６は、８個のメモリバンクＢａｎｋを有する。
【０３３５】
本例においては、残りのエントリデータ群について、８個の検索ステージＳｔａｇｅに従ってグループ化される複数のサブエントリデータ群に分割する。本例においては、複数のサブエントリデータ群ＢＬＫ［０］〜ＢＬＫ［１５］に分割される。
【０３３６】
１つのサブエントリデータ群ＢＬＫは、６５５３６個のエントリデータで構成される。
そして、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅ毎に対応するメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］に順次格納する。
【０３３７】
具体的には、サブエントリデータ群ＢＬＫ［０］の検索ステージＳｔａｇｅ［５］，Ｓｔａｇｅ［６］に対応するエントリデータをメモリバンクＢａｎｋ［０］に格納する。サブエントリデータ群ＢＬＫ［０］の検索ステージＳｔａｇｅ［７］，Ｓｔａｇｅ［８］に対応するエントリデータをメモリバンクＢａｎｋ［１］に格納する。サブエントリデータ群ＢＬＫ［０］の検索ステージＳｔａｇｅ［９］，Ｓｔａｇｅ［１０］に対応するエントリデータをメモリバンクＢａｎｋ［２］に格納する。サブエントリデータ群ＢＬＫ［０］の検索ステージＳｔａｇｅ［１１］，Ｓｔａｇｅ［１２］に対応するエントリデータをメモリバンクＢａｎｋ［３］に格納する。サブエントリデータ群ＢＬＫ［０］の検索ステージＳｔａｇｅ［１３］，Ｓｔａｇｅ［１４］に対応するエントリデータをメモリバンクＢａｎｋ［４］に格納する。サブエントリデータ群ＢＬＫ［０］の検索ステージＳｔａｇｅ［１５］，Ｓｔａｇｅ［１６］に対応するエントリデータをメモリバンクＢａｎｋ［５］に格納する。サブエントリデータ群ＢＬＫ［０］の検索ステージＳｔａｇｅ［１７］，Ｓｔａｇｅ［１８］に対応するエントリデータをメモリバンクＢａｎｋ［６］に格納する。サブエントリデータ群ＢＬＫ［０］の検索ステージＳｔａｇｅ［１９］，Ｓｔａｇｅ［２０］に対応するエントリデータをメモリバンクＢａｎｋ［７］に格納する。
【０３３８】
同様にして、サブエントリデータ群ＢＬＫ［１］の検索ステージＳｔａｇｅ［５］〜Ｓｔａｇｅ［１８］に対応するエントリデータをメモリバンクＢａｎｋ［１］〜Ｂａｎｋ［７］に順次格納する。そして、サブエントリデータ群ＢＬＫ［１］の検索ステージＳｔａｇｅ［１９］，［２０］に対応するエントリデータをメモリバンクＢａｎｋ［０］に格納する。
【０３３９】
同様にして、サブエントリデータ群ＢＬＫ［２］の検索ステージＳｔａｇｅ［５］〜Ｓｔａｇｅ［１６］に対応するメモリバンクＢａｎｋ［２］〜Ｂａｎｋ［７］に順次格納する。そして、サブエントリデータ群ＢＬＫ［２］の検索ステージＳｔａｇｅ［１７］，［１８］に対応するエントリデータをメモリバンクＢａｎｋ［０］に格納する。また、サブエントリデータ群ＢＬＫ［２］の検索ステージＳｔａｇｅ［１９］，［２０］に対応するエントリデータをメモリバンクＢａｎｋ［１］に格納する。
【０３４０】
他のサブエントリデータ群ＢＬＫについても同様の方式に従ってメモリバンクＢａｎｋに格納する。すなわち、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅ［５］〜Ｓｔａｇｅ［２０］毎に、対応するメモリバンクＢａｎｋ［０］〜Ｂａｎｋ［７］のいずれかに順次格納する。
【０３４１】
当該方式により、検索ステージＳｔａｇｅが後段に対応するメモリバンクＢａｎｋにエントリデータが集中することを回避することが可能であり、各メモリバンクＢａｎｋの使用容量を平滑化することが可能である。
【０３４２】
また、各サブエントリデータ群ＢＬＫのエントリデータに対して、検索ステージＳｔａｇｅ［５］〜Ｓｔａｇｅ［２０］毎に、対応するメモリバンクＢａｎｋが異なるため同一のメモリバンクＢａｎｋへのアクセス制限による待機時間ｔＲＣにより検索性能が低下することを抑制することも可能である。
【０３４３】
また、プロセッサ１５０１の内蔵メモリを小容量化させるとともに、メモリ１５０６を大容量化させることが可能であり、コストを低減することが可能である。
【０３４４】
また、１つのメモリバンクＢａｎｋに対して２段分のエントリデータが格納されるためメモリアクセス回数を削減することが可能であり、検索性能を向上させることが可能である。
【０３４５】
上記の実施形態においては、検索回路において、上記処理を実行する構成について説明したがＣＰＵ２と、汎用メモリ６との協働関係に基づいて上記処理を実行する構成とすることも可能である。また、特にこれに限られず専用回路を設けることも可能である。
【０３４６】
以上、本開示を実施形態に基づき具体的に説明したが、本開示は、実施形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【符号の説明】
【０３４７】
１  通信機器、２  ＣＰＵ、４  転送制御回路、６  汎用メモリ、８  検索回路。
【図１】
2020187407.tif 000007
【図２】
2020187407.tif 000008
【図３】
2020187407.tif 000009
【図４】
2020187407.tif 000010
【図５】
2020187407.tif 000011
【図６】
2020187407.tif 000012
【図７】
2020187407.tif 000013
【図８】
2020187407.tif 000014
【図９】
2020187407.tif 000015
【図１０】
2020187407.tif 000016
【図１１】
2020187407.tif 000017
【図１２】
2020187407.tif 000018
【図１３】
2020187407.tif 000019
【図１４】
2020187407.tif 000020
【図１５】
2020187407.tif 000021
【図１６】
2020187407.tif 000022
【図１７】
2020187407.tif 000023
【図１８】
2020187407.tif 000024
【図１９】
2020187407.tif 000025
【図２０】
2020187407.tif 000026
【図２１】
2020187407.tif 000027
【図２２】
2020187407.tif 000028
【図２３】
2020187407.tif 000029
【図２４】
2020187407.tif 000030
【図２５】
2020187407.tif 000031
【図２６】
2020187407.tif 000032