(57)【要約】【課題】検索テーブルのエントリ方向およびビット方向への拡張性を備えることである。【解決手段】半導体装置は、エントリ方向とビット方向で構成される検索テーブルをエントリ方向およびビット方向に分割した複数のブロックテーブルごとに検索するブロック検索回路と、ビット方向の複数のブロック検索回路の検索結果を結合する回路と、検索キーと前記複数の結合回路の出力とを入力し、ヒット情報を出力する制御回路と、を備える。【選択図】図２
2017174478.tif 000002
【特許請求の範囲】
【請求項１】
半導体装置は、
エントリ方向とビット方向で構成される検索テーブルをエントリ方向およびビット方向に分割した複数のブロックテーブルに対応する複数のブロック検索回路と、
ビット方向の複数のブロック検索回路の検索結果を結合する複数の結合回路と、
検索キーと前記複数の結合回路の出力とを入力し、ヒット情報を出力する制御回路と、
を備える。
【請求項２】
請求項１の半導体装置において、
前記ブロック検索回路は、
前記検索キーを分割したブロック検索キーのハッシュ値を計算するハッシュ計算回路と、
前記ブロック検索キーと前記ハッシュ値によって格納されているデータを検索し、参照アドレスを出力する検索デバイスと、
前記参照アドレスをマップアドレスに変換する参照テーブルと、
前記マップアドレスによってアクセスされ、前記検索結果を出力するマップテーブルと、
を備える。
【請求項３】
請求項２の半導体装置において、
前記検索デバイスは、
検索対象データと該検索対象データの有効／無効を示す情報とを格納するメモリと、
前記ハッシュ値で前記メモリから読み出した検索対象データとブロック検索キーとを比較する比較器と、
前記ハッシュ値に基づいて前記参照アドレスを生成するアドレス生成器と、
を備える。
【請求項４】
請求項３の半導体装置において
前記メモリはＲＡＭで構成される。
【請求項５】
請求項２の半導体装置において、
前記マップテーブルは、前記ブロック検索回路のエントリ数の２乗の格納場所を有するメモリを備え、複数のマッチ情報が格納可能となっている。
【請求項６】
請求項２の半導体装置において、
前記マップテーブルは、マッチ情報をエンコードして格納するメモリと、読み出したマッチ情報をデコードするデコーダと、を備える。
【請求項７】
請求項６の半導体装置において、
２を底とするブロック検索回路のエントリ数の対数より小さい値にマルチマッチ数の上限を設定する。
【請求項８】
請求項１の半導体装置において、
前記ブロック検索回路は、
前記検索キーを分割したブロック検索キーのハッシュ値を計算するハッシュ計算回路と、
前記ブロック検索キーと前記ハッシュ値によって格納されているデータを検索し、検索結果と参照アドレスを出力する検索デバイスと、
前記参照アドレスをマップアドレスに変換する参照テーブルと、
を備える。
【請求項９】
請求項８の半導体装置において、
前記結合回路は、ビット方向の前記複数のブロック検索回路のそれぞれ前記マップアドレスによってアクセスされるマップテーブルを備え、前記マップテーブルから読み出された検索結果を論理積または論理和して結合する。
【請求項１０】
請求項１の半導体装置において、
前記結合回路はビット方向の複数のブロック検索回路の検索結果を論理積または論理和して結合する。
【請求項１１】
検索システムは、
エントリ方向とビット方向で構成される検索テーブルをエントリ方向およびビット方向に分割した複数のブロックテーブルに対応する複数のブロック検索回路と、
ビット方向の複数のブロック検索回路の検索結果を結合する複数の結合回路と、
前記結合された検索結果を入力する制御回路と、
前記制御回路に検索キーを入力し、前記制御回路からヒット情報を入力するＣＰＵと、
を備える。
【請求項１２】
請求項１１の検索システムにおいて、
前記ブロック検索回路は、
前記検索キーを分割したブロック検索キーのハッシュ値を計算するハッシュ計算回路と、
前記ブロック検索キーと前記ハッシュ値によって格納されているデータを検索し、参照アドレスを出力する検索デバイスと、
前記参照アドレスをマップアドレスに変換する参照テーブルと、
前記マップアドレスによってアクセスされ、前記検索結果を出力するマップテーブルと、
を備える。
【請求項１３】
請求項１２の検索システムにおいて、
前記検索テーブルは、
検索対象データと該検索対象データの有効／無効を示す情報とを格納するメモリと、
前記ハッシュ値で前記メモリから読み出した検索対象データとブロック検索キーとを比較する比較器と、
前記ハッシュ値に基づいて前記参照アドレスを生成するアドレス生成器と、
を備える。
【請求項１４】
請求項１２の検索システムにおいて、
前記結合回路はビット方向の複数のブロック検索回路の検索結果を論理積または論理和して結合する。
【請求項１５】
検索方法は、
検索キーを複数のブロック検索キーに分割し、
エントリ方向とビット方向で構成される検索テーブルをエントリ方向およびビット方向に分割した複数のブロックテーブルに対応する複数のブロック検索回路のそれぞれを前記ブロック検索キーで検索し、
ビット方向の複数のブロック検索回路の検索結果を結合する。
【請求項１６】
請求項１５の検索方法において、
前記ブロック検索キーのハッシュ値を計算し、
前記ブロック検索キーと前記ハッシュ値によって格納されているデータを検索し、参照アドレスを出力し、
前記参照アドレスをマップアドレスに変換し、
前記マップアドレスによってアクセスし、前記検索結果を出力する。
【請求項１７】
請求項１６の検索方法において、
検索対象データと該検索対象データの有効／無効を示す情報とを格納し、
前記ハッシュ値で読み出した検索対象データとブロック検索キーとを比較し、
前記ハッシュ値に基づいて前記参照アドレスを生成する。
【請求項１８】
請求項１６の検索方法において、
ビット方向の複数のブロック検索回路の検索結果を論理積または論理和して結合する。
【発明の詳細な説明】
【技術分野】
【０００１】
半開示は半導体装置に関し、例えば検索回路を備える半導体装置に適用可能である。
【背景技術】
【０００２】
特開２０１３−３７７５０号公報（特許文献１）には、「本発明の一実施形態の内容参照メモリは、複数のバンクを含み、検索対象のＩＰアドレスを格納するメモリアレイを備え、メモリアレイは、可変数のバンクからなる複数のブロックを含み、同一のブロックのバンクにはプリフィックスが同一のＩＰアドレスが格納される。内容参照メモリは、ＩＰアドレスを検索データとして受けて、検索データと同一のＩＰアドレスがいずれのブロックに格納されているかをプリサーチするプリ検索部と、プリサーチによって特定されたブロックから読み出されたＩＰアドレスと検索データとを比較する検索判定部とをさらに備える。」ことが開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１３−３７７５０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１では、テーブルを構築するとき、まずプレフィックスごとにテーブルブロックを構成し各テーブルブロックには同一の長さの検索キーが格納される。各テーブルブロックはエントリ方向への拡張性があるが、ビット方向への拡張が望めないためフレキシブル性が乏しい。
その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【０００５】
本開示のうち、代表的なものの概要を簡単に説明すれば、下記のとおりである。
すなわち、半導体装置は、エントリ方向とビット方向で構成される検索テーブルをビット方向に分割した複数のブロックテーブルごとに検索するブロック検索回路と、ビット方向の複数のブロック検索回路の検索結果を結合する回路と、を備える。
【発明の効果】
【０００６】
上記半導体装置によれば、ビット方向への拡張が可能である。
【図面の簡単な説明】
【０００７】
【図１】実施例に係る検索テーブルの構成を示す図
【図２】実施例に係るＡＳＥの構成を示すブロック図
【図３】ビット方向に並ぶＡＳＥブロックの検索処理の例を示す図
【図４】図２のマージ回路の構成を示すブロック図
【図５】図２のＡＳＥブロックの構成を示すブロック図
【図６】図５の検索デバイスの構成を示すブロック図
【図７】アドレス参照テーブルとマップテーブルを用いたマルチマッチ情報の関係を示す図
【図８Ａ】実施例に係るマップテーブルの構成を示すブロック図
【図８Ｂ】変形例１に係るマップテーブルの構成を示すブロック図
【図８Ｃ】変形例２に係るマップテーブルの構成を示すブロック図
【図８Ｄ】変形例３に係るマップテーブルの構成を示すブロック図
【図９Ａ】実施例に係るＡＳＥのＡＳＥブロック間の接続を示すブロック図
【図９Ｂ】変形例４に係るマップテーブルの構成を示すブロック図
【図１０】変形例５に係るＡＳＥ−ｄの構成を示す図
【図１１】図１０のＡＳＥブロックの構成を示す図
【図１２】図１０の検索デバイスの構成を示す図
【図１３】図１０の参照テーブルの構成を示す図
【図１４】図１０のマップテーブルの構成を示す図
【図１５】変形例５に係るＡＳＥ−ｃの構成を示す図
【図１６】実施形態に係る半導体装置の構成を示すブロック図
【図１７】実施例に係るシステムの構成を示すブロック図
【図１８】図１６のＡＳＥに対するコマンドを説明するための図
【発明を実施するための形態】
【０００８】
以下、実施形態、実施例および変形例について、図面を用いて説明する。ただし、以下の説明において、同一構成要素には同一符号を付し繰り返しの説明を省略することがある。
【０００９】
図１６は実施形態に係る半導体装置の構成を示すブロック図である。実施形態に係る半導体装置１０は、エントリ方向とビット方向で構成される検索テーブルをビット方向に分割した複数のブロックテーブルごとに検索するブロック検索回路（ASE Block）１１と、ビット方向の複数のブロック検索回路の検索結果を結合する回路（Merge Circuit）１２と、を備える。
【００１０】
実施形態によれば、ブロック検索回路で複数のヒットが発生する状態に対応可能であり、ビット方向がフレキシブルに拡張または縮小可能である。これにより、可変長な検索キーにも対応可能である。
【実施例】
【００１１】
実施例に係るシステムについて図１７、１８を用いて説明する。図１７は実施例に係るシステムの構成を示すブロック図である。図１８は図１７のＡＳＥに対するコマンドを説明するための図である。システム１は検索回路であるＡＳＥ（Algorism Search Engine）１０とＡＳＥ１０を制御するＣＰＵ２０とを備える。ＡＳＥ１０はメモリ（Memory）と制御回路（Control Circuit）とで構成される。メモリはＣＡＭ（内部参照メモリ）セルではなく、ＤＲＡＭやＳＲＡＭの標準メモリ（以下、ＲＡＭという。）のメモリセルで構成される。半導体装置であるＡＳＥ１０は１つの半導体チップで構成してもよいし、メモリと制御回路をそれぞれ別の半導体チップで構成してもよい。
【００１２】
ＡＳＥ１０のＣＰＵ２０からの入力インターフェースとしてコマンド、アドレス、ワードをもち、ＣＰＵ２０への出力インターフェースはアドレス、ワードをもつ。図１８に示すように、コマンドはRead、Write、Delete、Searchの４種類がある。Readコマンドはアドレスを入力しメモリのそのアドレスに格納しているデータを読み出す。Writeコマンドはアドレス、データを入力しメモリのそのアドレスにデータを書き込む。Deleteコマンドはアドレスを入力しメモリのそのアドレスに格納しているデータを削除する。Searchコマンドは入力ワードを検索キーとして検索を実行しアドレスを返す。
【００１３】
ＡＳＥに対してＲＡＭを記憶媒体として検索デバイスに割りあてる。検索デバイスを構成する記憶媒体としてＲＡＭを用いることでＴＣＡＭを用いるよりも省電力化が可能になる。
【００１４】
検索テーブルについて図１を用いて説明する。図１は検索テーブルをＡＳＥに格納する例を示す図である。検索テーブル（Search Table）はエントリ（entry）がＥ個、１エントリはＳビット長で構成される。ＡＳＥ１０では、検索テーブルはビット方向とエントリ方向に分割され、それに対応するＡＳＥブロック（ASE Block）１１へ格納される。ＡＳＥブロック１１はエントリがＥｂ個、１エントリはＳｂビット長で構成される。ＡＳＥ１０はエントリ方向およびビット方向がフレキシブルに拡張または縮小可能である。本検索テーブルのアーキテクチャでは、ＩＰアドレスのプレフィックス長ごとに対応したＡＳＥブロック１１を持つことが可能である。
【００１５】
ＡＳＥ１０の構成と検索動作について図２を用いて説明する。図２はＡＳＥの構成を示すブロック図である。ＡＳＥ１０は、エントリ方向にｍ個、ビット方向にｎ個の合計ｍ×ｎ個のＡＳＥブロック１１（１１＿１１、・・・、１１＿１ｎ、１１＿２１、・・・、１１＿２ｎ、１１＿ｍ１、・・・、１１＿ｍｎ）と、ｍ個のマージ回路（Merge Circuit）１２（１２＿１、１２＿２、・・・、１２＿ｍ）と、コントローラ（Controller）１３と、を備える。
【００１６】
（１）コントローラ１３はSearchコマンドとＳビット長の検索キー（Search Key[S]）を受け取り、検索キーをブロック数分に等分割し、Ｓｂビット長に分割されたブロック検索キー（Block Search Key）を各ＡＳＥブロック１１へ送る。
【００１７】
（２）各ＡＳＥブロック１１は入力されたブロック検索キーと格納されている分割された検索テーブル（サブテーブル）と一致比較演算を行い、その結果を出力する。テーブル検索では、１つの検索キーに対して複数のエントリがヒットすることがある。これをマルチマッチと定義する。よって、各ＡＳＥブロック１１はそれぞれ自身のＡＳＥブロックに対するマルチマッチの結果を出力する。マルチマッチのビット方向の処理に関しては下記（３）で、エントリ方向の処理に関しては下記（４）で行われる。
【００１８】
（３）マージ回路１２はエントリごとに各ＡＳＥブロック１１から出力された結果をビット方向に関して結合する。詳細は後述する。
【００１９】
（４）コントローラ１３は図示しないエンコーダによってマージ回路１２の出力をエントリ方向に対して結合する。このとき、出力結果となる検索テーブルのアドレスがマルチマッチによって複数結果が存在する場合、エンコーダは優先度に従い１つの結果を選択する。コントローラ１３はＡビット長のアドレス（Address[A]）およびヒット情報（Hit/Miss）を出力する。
【００２０】
コントローラ１３は全体のタイミング制御、入出力制御を行う。入力時には、外部から入力されたコマンドに従い入力データを適切に処理する。検索時には、マージ処理およびエンコーダ処理を実行する。
【００２１】
各ＡＳＥブロック１１はＲＡＭを実装し、ＡＳＥブロック単体での検索処理を可能とする。
【００２２】
ＡＳＥブロック１１の検索処理について図３を用いて説明する。図３はビット方向に並ぶＡＳＥブロックの検索処理の例を示す図である。上述したように、各ＡＳＥブロック１１の検索結果は、分割された検索キー（ブロック検索キー）ごとにマルチマッチする可能性がある。ＡＳＥブロック（ASE Block）＃１ではブロックエントリの３番目（ＢＥ＃３）と７番目（ＢＥ＃７）の２つのエントリでマッチし、ＡＳＥブロック＃２ではブロックエントリの３番目（ＢＥ＃３）と４番目（ＢＥ＃４）の２つのエントリでマッチする。ＡＳＥブロック＃３ではブロックエントリの１番目（ＢＥ＃１）と３番目（ＢＥ＃３）と７番目（ＢＥ＃７）の３つのエントリでマッチし、ＡＳＥブロック＃４ではブロックエントリの３番目（ＢＥ＃３）と４番目（ＢＥ＃４）と５番目（ＢＥ＃５）の３つのエントリでマッチする。ＡＳＥブロック＃１〜＃４の全てでマッチするエントリに格納されるアドレスはヒットアドレス（Hit Address）である。そのため、マッチした場合の検索結果を“Ｈｉｇｈ”とすると、ビット方向に並ぶＡＳＥブロック１１の検索結果はマージ回路１２で“ＡＮＤ”をとることで、１つの検索結果を取得することができる。また、ＡＳＥブロック１１の出力結果（検索結果）は、データが“Ｈｉｇｈ”となっている位置がマッチしたブロック検索テーブルのアドレスを示す。
【００２３】
なお、エントリ方向に並ぶＡＳＥブロック１１の検索結果は、上述したようにエンコーダで結合される。エンコーダは、優先度を持ったプライオリティ・エンコーダとして機能し、マルチマッチした場合に優先度に従い１つの検索結果を出力する。
【００２４】
次に、マージ回路（結合回路）について図４を用いて説明する。図４はマージ回路の構成を示すブロック図である。マージ回路１２はマルチプレクサ（multiplexer）１２１、ＡＮＤ回路１２２とレジスタ（ＦＦ）１２３で構成される。
【００２５】
まず、ＡＳＥブロック＃１のＥｂビットの検索結果をマルチプレクサ１２１で選択して、ＡＮＤ回路１２２でレジスタ１２３と論理積をとる。このときレジスタ１２３は初期化されていてＥｂビットのすべてが“Ｈｉｇｈ”になっている。ＡＮＤ回路１２２の出力（ＡＳＥブロック＃１の検索結果）がレジスタ１２３に入力される。
【００２６】
次に、ＡＳＥブロック＃２のＥｂビットの検索結果をマルチプレクサ１２１で選択して、ＡＮＤ回路１２２でレジスタ１２３と論理積をとる。このときレジスタ１２３はＡＳＥブロック＃１の検索結果になっている。ＡＮＤ回路１２２の出力（ＡＳＥブロック＃１の検索結果とＡＳＥブロック＃２の検索結果の論理積）がレジスタ１２３に入力される。
【００２７】
その後、ＡＳＥブロック＃３の検索結果、ＡＳＥブロック＃４の検索結果を入力することにより、レジスタ１２３には、ＡＳＥブロック＃１の検索結果とＡＳＥブロック＃２の検索結果とＡＳＥブロック＃３の検索結果とＡＳＥブロック＃４の検索結果との論理積が格納される。
【００２８】
これにより、ＡＳＥブロックの検索結果は、マージ回路１２でビット方向に結合される。マージ回路１２はそれぞれの機能を用いることで、各ＡＳＥブロック動作を時系列にアクティブにすることにより消費電力を抑えることができる。
【００２９】
次に、ＡＳＥブロック１１に備えている各機能の検索動作について図５を用いて説明する。図５はＡＳＥブロックの構成を示すブロック図である。ＡＳＥブロック１１はハッシュ計算回路（Hash）１１１と検索デバイス（ASE core）１１２と参照テーブル（Reference Table）１１３とマップテーブル（Map Table）１１４とを備える。
【００３０】
ハッシュ計算回路１１１は入力データであるブロック検索キー（Block Search Key[Sb]）からハッシュ関数によってハッシュ値（ｈ）を算出する。このハッシュ値（ｈ）によって、後段の検索デバイス１１２を構成するメモリアレイ１１２１から読み出すワード線の決定を行う。すなわち、ハッシュ値（ｈ）はメモリアレイ１１２１の行アドレスになる。ハッシュ計算回路１１１を備えることで、検索デバイス１１２に格納するデータのばらつきを抑制する。
【００３１】
検索デバイス１１２は、入力データ（ブロック検索キー）とメモリアレイ１１２１から一斉に読み出したテーブル（分割された検索テーブル）の値の一致比較を行い、検索結果（result、reference address）を出力する。詳細は後述する。
【００３２】
参照テーブル１１３は、マップテーブル１１４で参照するアドレス番地（map address）をデータとして持つテーブルとなっている。
【００３３】
マップテーブル１１４は、ＡＳＥブロック１１内に格納されるサブテーブルのマルチマッチ情報を保持するためのテーブルである。
【００３４】
次に、検索デバイス１１２について図６を用いて説明する。図６は検索デバイスの構成を示すブロック図である。検索デバイス１１２はＲＡＭで構成されるメモリアレイ１１２１と比較器１１２２とアドレス生成回路（Address Generator）１１２３とを備える。検索デバイス１１２では、入力したブロック検索キーと格納されている分割された検索テーブルの一致比較を行う。検索デバイス１１２に対する入力は、読み出すワード線を選択するため前段のハッシュ計算回路１１１から得られたアドレス情報となる。ワード線を決定した後、ワード線の全てのメモリセルを読み出し読み出したデータと検索するデータを一致比較する。検索デバイス１１２は、読み出された各ビットと一致比較するためにメモリアレイ１１２１のビット方向のビット数と等しい比較器１１２２とアドレス生成回路１１２３で構成する。ＡＳＥブロック１１のメモリアレイ１１２１に格納する値は、検索キー（各ＡＳＥブロック１１の入力となる元の検索キーを等分割した）とメモリから値を読み出す制御に用いるＶａｌｉｄの１ビットである。検索デバイス１１２へ格納する際は、検索キーのハッシュ値を計算し、そのハッシュ値をメモリアレイ１１２１のアドレスとして用いることで格納する。
【００３５】
複数のエントリを格納する場合、複数の検索キーから計算されるハッシュ値が同一の値になることがある。これをハッシュ衝突といい、ハッシュ衝突が起こった場合はワード線上のメモリアレイ１１２１に値が追加される。１つのワード線上のＲＡＭ１１２１へ格納できる検索キーの数は、図６では６個であるが、ビット方向のビット数に依存する。ハッシュ計算回路１１１は、メモリアレイ１１２１を効率よく使用するためにハッシュ衝突の偏りを平均化するためにハッシュ関数を最適化する。
【００３６】
また、図３で説明したように、ＡＳＥブロック１１に格納される検索キーは、元の検索データを分割した値であるため、元の検索データが異なる値を保持していたエントリであっても、ＡＳＥブロックの単位で見た場合には同一の値として一致する場合（マルチマッチ）がある。マルチマッチしたとき、検索デバイス１１２のメモリアレイ１１２１に追加されずに、マップテーブル１１４にマルチマッチの情報として追加される。
【００３７】
次に、マルチマッチ情報の出力について図７を用いて説明する。図７はアドレス参照テーブルとマップテーブルを用いたマルチマッチ情報の関係を示す図である。ここでは、ブロック検索キーは１６ビット長（Ｓｂ＝１６）で、エントリは５１２個（Ｅｂ＝５１２）の場合について説明する。ハッシュ計算回路１１１は８ビットのハッシュ値を出力する。検索デバイス１１２の出力は検索に関するヒット結果（result）と参照アドレス（Reference Address）がある。参照アドレスは、検索デバイス１１２のアドレス選択に用いたハッシュ値（８ビット）と検索デバイス１１２のカラム番号を示す値（２ビット）であり、１０ビット長のアドレスである。
【００３８】
参照テーブル１１３は、マップテーブル１１４で参照するアドレス情報（マップテーブルアドレス（９ビット））を格納したテーブルである。参照テーブル１１３はＲＡＭ（メモリ）で構成される。マップテーブル１１４は、ＡＳＥブロック１１内におけるマルチマッチの結果を格納している。マップテーブル１１４はＲＡＭで構成されるメモリアレイ１１４１と行デコーダ（ＲＤ）１１４２とセンスアンプ（Ｓ／Ａ）１１４３とを備える。マップテーブル１１４はエントリ上で“１（Ｈｉｇｈ）”が格納されているビットがマッチしたことを示し、“Ｈｉｇｈ”が複数ある場合マルチマッチしていることを示し、“Ｈｉｇｈ”が格納されているビットの位置がマルチマッチのアドレス（エントリ）を示す。例えば、マップテーブル１１４の一番上の行では、左から５番目と７番目が“Ｈｉｇｈ”であり、５番目のエントリと７番目のエントリがマルチマッチしている。マップテーブル１１４から行単位で読み出されるので、全エントリのマッチ情報が一度に読み出される。
【００３９】
マージ回路１２を搭載することで、ＡＳＥブロック１１で複数のヒットが発生する状態（マルチマッチ）に対応可能となる。その結果、ビット長の拡張に対応することができ、可変長な検索キーをフレキシブルに扱うことができる。これによって、ネットワーク上に流れるパケットのＬ７層までの監視を目的とするＤＰＩ（Deep Packet Inspection）へ応用範囲を広げることが可能となる。
【００４０】
＜変形例１＞
変形例１は、実施例で搭載するマップテーブル１１４の改良である。変形例１に係るマップテーブルについて図８Ａ、８Ｂを用いて説明する。図８Ａは実施例に係るマップテーブルの構成を示すブロック図である。図８Ｂは変形例１に係るマップテーブルの構成を示すブロック図である。
【００４１】
図８Ａに示すように、実施例において、マップテーブル１１４を用いてマルチマッチ情報を表現するために必要なメモリ容量は、マップテーブル１１４で対応するＡＳＥブロック１１のエントリ数（エントリ方向）ｘＡＳＥブロック１１のエントリ数（ビット方向）、要するにＡＳＥブロック１１のエントリ数の２乗のメモリ容量が必要となる。図７のマップテーブルでは５１２ｘ５１２＝２６２，１４４ビット必要になる。
【００４２】
例えば、ＡＳＥブロック１１に格納するデータが全エントリで同一のデータであった場合、マップテーブル１１４の状態は、１つのエントリのみにマルチマッチの結果が集中し、その１エントリには全ビットに“Ｈｉｇｈ”が格納され、ビット数はＡＳＥブロックのエントリ数と同じものとなる。この場合、エントリ方向の容量は全て無駄となる。
【００４３】
また、反対にマルチマッチが起こらない場合には、エントリごとに１ビットに“Ｈｉｇｈ”が格納され、そのとき、全てのエントリで同一のビットへ“Ｈｉｇｈ”が格納されることは無い。
【００４４】
ゆえに、マップテーブル１１４においてマッチを“Ｈｉｇｈ”、ミスマッチを“Ｌｏｗ”としたときに、“Ｈｉｇｈ”の数は、マップテーブル全体のエントリ数分のみとなるため、エントリ数（エントリ方向）ｘエントリ数（ビット方向）のメモリ容量は無駄が多いといえる。
【００４５】
変形例１のマップテーブル１１４Ａでは、メモリ容量の無駄を減らすために、メモリ容量の圧縮方法として、マルチマッチ情報をエンコードデータとして格納する。実施例では、マルチマッチ情報を表現するためにエントリ数分のビット数を用意してマッチしているエントリに対して“Ｈｉｇｈ”を格納する方法をとっている。変形例１では、マッチしているエントリ情報をエンコードするので、図８Ｂに示すように、「ｌｏｇ２（エントリ数）ｘマルチマッチ数＜エントリ数」の関係を満たすときメモリ容量を圧縮することができる。
【００４６】
例えば、エントリ数が“１０２４”のとき、エントリ数“１０２４”／ｌｏｇ２（エントリ数“１０２４”）＝１０２．４となるためマルチマッチ数を１００以下に設定することでメモリ容量を抑えることができる。また、エントリ数を先ほど同一の１０２４に設定し、マルチマッチ数を６４に設定した場合、メモリ容量を約半分（正確には６４ｘ１０／１０２４＝０．６２５）に抑えることができる。ただし、マルチマッチ数分のデコーダが必要になる。仮に、実施例においてマルチマッチ数を制限する方法をとった場合でも、ビット方向を圧縮することができない。
【００４７】
＜変形例２＞
変形例２に係るマップテーブルについて図８Ｃを用いて説明する。図８Ｃは変形例２に係るマップテーブルの構成を示すブロック図である。変形例２のマップテーブル１１４Ｂでは、マルチマッチの数へ制限を設定する場合に、変形例１のような上限ではなく下限に対して設定することにより、エントリ方向に対して圧縮をすることができる。上述したように、実施例において、サブテーブルの全エントリでマッチする（マルチマッチ数＝エントリ数）場合は、マップテーブル１１４の１行のみが使用される。サブテーブルの１つのエントリでしかマッチしない（マルチマッチ数＝１）場合は、マップテーブル１１４のすべての行が使用される。すなわち、マルチマッチ数の下限を増やすことによってマップテーブルのエントリ方向を減らすことができる。
【００４８】
例えば、マップテーブル１１４Ｂに格納するマルチマッチ数の下限を“４”と設定した場合、エントリ方向を１／４に圧縮することが可能となる。また、マルチマッチ数の下限を“２”と設定しただけであっても、エントリ方向を１／２に圧縮することが可能となる。このように、実現可能な制約においても圧縮が可能な提案手法は非常に有効であるといえる。
【００４９】
実施例のように全ての状況に対応することのより無駄が多くなっていた状況を、変形例１、２のようにいくつかの制約（実利用に対応した制限）を設定することによりメモリ容量の圧縮が可能となる。
【００５０】
＜変形例３＞
変形例３に係るマップテーブルについて図８Ｄを用いて説明する。図８Ｄは変形例３に係るマップテーブルの構成を示すブロック図である。変形例３のマップテーブル１１４Ｃはアドレスの充填率に応じて、アドレスの管理方法を変更する。
【００５１】
マルチマッチ数が４以下の場合は、変形例１と同様に各アドレスをエンコードしてマップテーブル１１４Ｃへ格納する。５個以上の場合は、実施例と同様にマップテーブル１１４Ｃの指定の場所に“Ｈｉｇｈ”を格納する。
【００５２】
エントリ方向に関しての動作は実施例と同様である。ビット方向に関しての動作は、実施例とは異なる。
【００５３】
まず、マップテーブル１１４Ｃへの格納方法は、エンコード情報を格納する。エントリ数を“１０２４”に設定した場合、１０ビットごとにエンコード情報を格納する。次に、検索動作を行う際は、エントリに格納されたデータを全て読み出し、デコーダ１１４４Ｃを用いてエンコード情報をデコードする、さらに、デコードした全データをＯＲ回路１１４５Ｃで“ＯＲ”（論理和）することでマルチマッチ情報を１つにまとめる。そのために、マルチマッチ数分のデコーダが必要となる。これは変形例１にも適用される。
【００５４】
＜変形例４＞
変形例４は、変形例１とは異なる方法でマップテーブルの改良である。変形例４に係るマップテーブルについて図９Ａ、９Ｂを用いて説明する。図９Ａは実施例に係るＡＳＥのＡＳＥブロック間の接続を示すブロック図である。図９Ｂは変形例４に係るマップテーブルの構成を示すブロック図である。
【００５５】
実施例で説明したように、各ＡＳＥブロック１１で検索処理をした後、マージ回路１２でマルチマッチ情報をまとめる必要が発生する。各ＡＳＥブロック１１がそれぞれマルチマッチ情報をマージ回路１２のマルチプレクサ１２１に入力するのでは、配線が多くなってしまう。そこで、例えば、マージ回路のマルチプレクサを分割して各ＡＳＥブロックに配置し、左隣りのＡＳＥブロックからマルチマッチ情報を入力し、自身のマルチマッチ情報とマルチプレクスして右隣りのＡＳＥブロックに渡すことにする。これにより、図９Ａに示すように、各ＡＳＥブロック１１は、マルチマッチ情報としてエントリ数分の配線を隣接するＡＳＥブロックに入出力として接続することで情報を伝達する。しかし、例えばエントリ数を“１０２４”とした場合、１０２４ビットの配線を伝播することになり、実装を考慮した場合は困難が予想される。
【００５６】
そこで、変形例４では、各ＡＳＥブロックがエントリ数分の配線を入出力として接続する必要が無いように、マップテーブルを共有メモリとして扱い、マップテーブルとマージ回路とを纏めてマージ回路１２Ｄを構成する。よって、マージ回路１２Ｄはマップテーブル１１４ＤとＡＮＤ回路１２２Ｄとレジスタ１２３Ｄとを備える。
【００５７】
変形例４に係るＡＳＥブロック１１Ｄはハッシュ計算回路１１１と検索デバイス１１２と参照テーブル１１３とを備える。変形例４では、実施例にて各ＡＳＥブロックで搭載していた参照テーブルとマップテーブルの接続関係を分離して、各ＡＳＥブロック１１Ｄでの検索処理は参照テーブル１１３までとして、参照テーブル１１３の出力データを各ＡＳＥブロック１１Ｄの検索結果とし、マージ回路１２Ｄのマップテーブル１１４Ｄへ転送する。このとき、マップテーブル１１４Ｄへは、各ＡＳＥブロック１１Ｄからｌｏｇ２（エントリ数）の配線が接続される。これにより、接続される配線を削減することが可能となる。
【００５８】
変形例４での動作は、各ＡＳＥブロック１１Ｄが共有メモリであるマップテーブル１１４Ｄへ同時にアクセスしないようにコントロールする必要がある。例えば、左側のＡＳＥブロック１１Ｄから順番にマップテーブル１１４Ｄへアクセスするようにし、左隣のＡＳＥブロックからアクセスが終了したことを知らせる信号を受け取った後、マップテーブル１１４Ｄへアクセスするようにする。
【００５９】
（１）ＡＳＥブロック＃１へ検索キーを与える。そのとき、ＡＳＥブロック１１Ｄは検索処理を行い、参照テーブル１１３の出力結果をマップテーブル１１４Ｄの領域＃１へ転送する。マップテーブル１１４Ｄでは、入力された値（アドレス）に応じてマルチマッチ情報を出力し、レジスタ１２３Ｄへ格納する。
【００６０】
（２）ＡＳＥブロック＃２へ検索キーを与える。そのとき、ＡＳＥブロック１１Ｄは検索処理を行い、参照テーブル１１３の出力結果をマップテーブル１１４Ｄの領域＃２へ転送する。マップテーブル１１４Ｄでは、入力された値（アドレス）に応じてマルチマッチ情報を出力する。同時に、レジスタ１２３Ｄから値を読み出し、マルチマッチ情報とレジスタの値をＡＮＤ回路１２２Ｄで論理積（“ＡＮＤ”）をする。その結果をレジスタ１２３Ｄへ格納する。
【００６１】
（３）ＡＳＥブロック＃ｎまで上記（２）と同様に処理を行う。
【００６２】
アドレスに関するメモリを共有化し、ビット幅の広い（＃エントリ）配線を１つにすることで実装面積を削減することができる。実装面積を削減することで、低消費電力化へもつながる。
【００６３】
＜変形例５＞
ＡＳＥをＦＰＧＡ（Field Programmable Gate Array）等にＩＰとして提供する場合、利用できるメモリ容量は有限だが利用場面は、ユーザーによって様々である。さらに、ＡＳＥをＦＰＧＡに実装する場合、リソースの有限性によりエントリ方向やビット方向への制限が発生する。
【００６４】
そこで、変形例５では、同一のＡＳＥブロックをフレキシブルにエントリ方向の拡充、またはビット方向の拡充の用途に応じて使い分ける。変形例５に係るＡＳＥはエントリ方向に拡張しているＡＳＥ−ｄと、ビット方向に拡張しているＡＳＥ−ｃと、に使い分ける。
【００６５】
変形例５に係るＡＳＥ−ｄについて図１０〜１４を用いて説明する。図１０は変形例５に係るＡＳＥ−ｄの構成を示す図である。図１１は図１０のＡＳＥブロックの構成を示す図である。図１２は図１０の検索デバイスの構成を示す図である。図１３は図１０の参照テーブルの構成を示す図である。図１４は図１０のマップテーブルの構成を示す図である。
【００６６】
（１）図１０に示すように、ＡＳＥ−ｄ１０Ｅは、６４ビットｘ１０２４エントリとしてエントリ方向に展開した形の構成をとる。ＡＳＥ−ｄ１０Ｅは、ＡＳＥブロック１１Ｅを４つ搭載してアドレスaddr[15:14]の２ビットを用いて制御する。展開は、エントリ方向へ向けてコントロールする。
【００６７】
（２）図１１に示すように、ＡＳＥブロック１１Ｄは、addr[17:16]の２ビットを用いて検索デバイス（ASE core）１１２Ｅ／参照テーブル（ＲＥＦ）１１３Ｅ／マップテーブル（ＭＡＰ）１１４Ｅのいずれかを選択する。各検索デバイス１１２Ｅで１６ビット検索を行い、ＡＳＥブロック１１Ｅで１６ビットｘ４＝６４ビット検索を行うため、addr[13:12]の２ビットを用いてコントロールし、検索デバイス１１２Ｅそれぞれに参照テーブル１１３Ｅとマップテーブル１１４Ｅを設置する。
【００６８】
（３）図１２に示すように、検索デバイス１１２Ｅは、addr[1:0]を用いてハッシュ衝突に対応して深さを確保する。エントリ方向では、addr[9:2]によって２５６エントリを確保している。検索デバイス１１２Ｅには３６ビットのデータが格納され、 [17]にＶａｌｉｄビット（Ｖ）、[15:0]に検索対象データであるブロック検索キー（Entry）が格納される。[35:18]、[16]はリザーブ（Reserved、Ｒ）である。検索デバイス１１２Ｅにデータを書き込んだときＶａｌｉｄビットは“１”にされ、データを消去したときＶａｌｉｄビットは“０”にされる。
【００６９】
（４）図１３に示すように、参照テーブル１１３Ｅは、検索デバイス１１２Ｅのアドレス（addr[9:2][1:0]の１０ビット）に対応して１０２４個のアドレスを管理する。参照テーブル１１３Ｅには７２ビットのデータが格納され、[7:0]にマップテーブル１１４Ｅをアクセスするためのアドレス（Address）が格納される。[71:8]はリザーブ（Reserved）である。
【００７０】
（５）図１４に示すように、マップテーブル１１４Ｅは、マルチマッチ数の上限を８個に設定しaddr[2:0]を用いて管理する。さらに、エントリ方向は、addr[11:4]を用いて２５６エントリを管理する。マップテーブル１１４Ｅには３６ビットのデータが格納され、[31:0]にエンコードされたマルチマッチ情報（Original Address MAP）が格納される。[35:32]はリザーブ（Reserved、Rsv）である。
【００７１】
次に、変形例５に係るＡＳＥ−ｃについて図１５を用いて説明する。図１５は変形例５に係るＡＳＥ−ｃの構成を示す図である。
【００７２】
図１５に示すように、ＡＳＥ−ｃ１１Ｆは、１２８ビットｘ５１２エントリとしてビット方向に展開した形の構成をとる。ＡＳＥ−ｃ１１Ｆは、ＡＳＥブロック１１Ｅを４つ搭載してアドレスaddr[15:14]の２ビットを用いて制御する。展開は、ビット方向へ向けてコントロールする。なお、ＡＳＥ−ｃ１１ＦのＡＳＥブロック１１ＥはＡＳＥ−ｄ１０Ｅと同じであり、ＡＳＥ−ｄ１０Ｅの上記（２）〜（５）の構成および制御は、ＡＳＥ−ｃ１１Ｆにも適用される。
【００７３】
ＦＰＧＡ等にＩＰとして提供する場合、利用できるメモリ容量は有限だが利用場面は、ユーザーによって様々である。この手法によって、利用場面に応じてフレキシブルに対応が可能となる。
【００７４】
実施例、変形例１〜５のＡＳＥは、例えばネットワーク検索エンジンに適用可能であり、また検索エンジンが利用される検索システムに応用可能である。
【００７５】
以上、本発明者によってなされた発明を実施形態、実施例および変形例に基づき具体的に説明したが、本発明は、上記実施形態、実施例および変形例に限定されるものではなく、種々変更可能であることはいうまでもない。
【００７６】
実施例では、マッチ情報を“Ｈｉｇｈ”としマージ回路でＡＮＤ回路を用いて結合するように説明したが、マッチ情報を“Ｌｏｗ”としマージ回路でＯＲ回路を用いて結合するようにしてもよい。
【符号の説明】
【００７７】
１・・・システム
１０・・・ＡＳＥ（検索装置）
１１・・・メモリ
１１１・・・ハッシュ計算回路
１１２・・・検索デバイス
１１２１・・・メモリアレイ
１１２２・・・比較器
１１２３・・・アドレス生成回路
１１３・・・参照テーブル
１１４・・・マップテーブル
１２・・・マージ回路
１２１・・・マルチプレクサ
１２２・・・ＡＮＤ回路
１２３・・・レジスタ
１３・・・コントローラ
２０・・・ＣＰＵ
【図１】
2017174478.tif 000003
【図２】
2017174478.tif 000004
【図３】
2017174478.tif 000005
【図４】
2017174478.tif 000006
【図５】
2017174478.tif 000007
【図６】
2017174478.tif 000008
【図７】
2017174478.tif 000009
【図８Ａ】
2017174478.tif 000010
【図８Ｂ】
2017174478.tif 000011
【図８Ｃ】
2017174478.tif 000012
【図８Ｄ】
2017174478.tif 000013
【図９Ａ】
2017174478.tif 000014
【図９Ｂ】
2017174478.tif 000015
【図１０】
2017174478.tif 000016
【図１１】
2017174478.tif 000017
【図１２】
2017174478.tif 000018
【図１３】
2017174478.tif 000019
【図１４】
2017174478.tif 000020
【図１５】
2017174478.tif 000021
【図１６】
2017174478.tif 000022
【図１７】
2017174478.tif 000023
【図１８】
2017174478.tif 000024