(57)【要約】      （修正有）【課題】キーデータの書込処理時に全衝突が発生した場合の効率的な解決手段を提供する。【解決手段】書込対象のキーデータを複数の分割データに分割し，複数の分割データのそれぞれを分割メモリに割り当てて，各分割データをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間に，分割データに対応するエントリアドレスを書き込む。このとき，ある分割データに対応するエントリアドレスを書き込むべきメモリ空間に，既に他の分割データに対応するエントリアドレスが書き込まれている場合には，メモリ空間に，エントリアドレスの衝突を表す衝突情報を登録する。さらに，あるキーデータから分割された複数の分割データの全てについて衝突が生じている場合には，その全衝突が生じているキーデータとこれに対応するエントリアドレスとを，バックアップメモリに書き込む。【選択図】図３
2016219073.tif 000002
【特許請求の範囲】
【請求項１】
メモリアドレスによって特定されるメモリ空間に，キーデータに対応するエントリアドレスが書き込まれる検索メモリマット（１００）と，
前記検索メモリマットに接続された制御回路（２００）と，
前記制御回路に接続されたバックアップメモリ（３００）と，を備え，
前記検索メモリマット（１００）は，
前記メモリ空間が，前記メモリアドレスを保持したまま，複数の分割メモリ（１１０ａ，１１０ｂ…）に区分されたものであり，
前記制御回路（２００）は，
前記キーデータが入力される入力部（２１０）と，
前記入力部に入力された前記キーデータを複数の分割データに分割する分割部（２２０）と，
複数の前記分割データのそれぞれを，複数の前記分割メモリに割り当てて，各分割データをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間に，当該分割データに対応するエントリアドレスを書き込む書込部（２３０）と，を有し，
前記書込部（２３０）は，
ある分割データに対応するエントリアドレスを書き込むべきメモリ空間に，既に他の分割データに対応するエントリアドレスが書き込まれている場合には，当該メモリ空間に，エントリアドレスの衝突を表す衝突情報を書き込み，
あるキーデータから分割された複数の分割データの全てについて前記衝突が生じている場合には，その全衝突が生じているキーデータとこれに対応するエントリアドレスとを，前記バックアップメモリ（３００）に書き込む
半導体装置。
【請求項２】
請求項１に記載の半導体装置であって，
前記エントリアドレスに対応づけて前記キーデータを記憶する確認用メモリ（４００）を，さらに備える
半導体装置。
【請求項３】
請求項１に記載の半導体装置であって，
マスクレジスタ（５００）を，さらに備え，
前記マスクレジスタ（５００）は，所望のマスクパターンが登録されており，当該マスクパターンに応じて，前記キーデータにマスクを付与するものであり，
前記マスクが付与されたキーデータが，前記制御回路（２００）の前記入力部（２１０）に入力される
半導体装置。
【請求項４】
請求項１に記載の半導体装置であって，
前記制御回路（２００）は，
前記入力部（２１０）に，検索対象データとしてのキーデータが入力され，前記分割部（２２０）が，当該検索対象データとしてのキーデータを複数の分割データに分割した場合において，
前記分割データのそれぞれをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間にアクセスし，アクセスしたメモリ空間から，当該分割データに対応するエントリアドレスを読み出す読出部（２４０）を，さらに有し，
前記読出部（２４０）は，
前記メモリ空間にアクセスしたときに，当該メモリ空間に前記衝突情報が書き込まれている場合には，分割データに対応するエントリアドレスを読み出さずに，ドントケアとして処理し，
ある検索対象データとしてのキーデータから分割された複数の分割データの全てがドントケアとして処理される場合，又は，読み出したエントリアドレスに不一致が生じている場合に，前記バックアップメモリ（３００）から，当該検索対象データとしてのキーデータに基づいて，これに対応するエントリアドレスを検索する
半導体装置。
【請求項５】
請求項３に記載の半導体装置（１０）を複数有する情報処理システムであって，
複数の前記半導体装置（１０）は，前記マスクレジスタ（５００）に登録されている前記マスクパターンが異なる
情報処理システム。
【請求項６】
請求項５に記載の情報処理システムであって，
複数の前記半導体装置（１０）に接続されたマスクコントローラ（２０）を，さらに備え，
前記マスクコントローラ（２０）は，
マスク部位を有する複数のキーデータが含まれるテーブルデータが入力されるテーブルデータ入力部（２１）と，
前記テーブルデータに含まれる複数のキーデータのマスク部位のパターンを解析して，複数種類のマスクパターンを生成するマスクパターン生成部（２２）と，
前記マスクパターン生成部（２２）が生成した複数種類のマスクパターンを，それぞれ，異なる前記半導体装置（１０）の前記マスクレジスタ（５００）に登録するマスクパターン登録部（２３）と，を有する
情報処理システム。
【請求項７】
メモリアドレスによって特定されるメモリ空間に，キーデータに対応するエントリアドレスが書き込まれる検索メモリマット（１００）と，
前記検索メモリマットに接続された制御回路（２００）と，
前記制御回路に接続されたバックアップメモリ（３００）と，を備える半導体装置（１０）に対し，
前記エントリアドレスを書き込む情報書込方法であって，
前記検索メモリマット（１００）は，
前記メモリ空間が，前記メモリアドレスを保持したまま，複数の分割メモリ（１１０ａ，１１０ｂ…）に区分されたものであり，
前記書込方法は，
前記制御回路にキーデータが入力される工程と，
前記制御回路が，前記キーデータを複数の分割データに分割する工程と，
前記制御回路が，複数の前記分割データのそれぞれを，複数の前記分割メモリに割り当てて，各分割データをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間に，当該分割データに対応するエントリアドレスを書き込む工程と，を含み，
前記エントリアドレスを書き込む工程において，前記制御回路は，
ある分割データに対応するエントリアドレスを書き込むべきメモリ空間に，既に他の分割データに対応するエントリアドレスが書き込まれている場合には，当該メモリ空間に，エントリアドレスの衝突を表す衝突情報を登録し，
あるキーデータから分割された複数の分割データの全てについて前記衝突が生じている場合には，その全衝突が生じているキーデータとこれに対応するエントリアドレスとを，前記バックアップメモリ（３００）に書き込む
情報書込方法。
【請求項８】
請求項７に記載の情報書込方法によって，前記半導体装置（１０）に対して書き込まれた前記エントリアドレスを読み出す情報読出方法であって，
前記制御回路に検索対象データとしてのキーデータが入力される工程と，
前記制御回路が，前記検索対象データとしてのキーデータを複数の分割データに分割する工程と，
前記制御回路が，前記分割データのそれぞれをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間にアクセスし，アクセスしたメモリ空間から，当該分割データに対応するエントリアドレスを読み出す工程と，を含み，
前記エントリアドレスを読み出す工程において，前記制御回路は，
前記メモリ空間にアクセスしたときに，当該メモリ空間に前記衝突情報が登録されている場合には，分割データに対応するエントリアドレスを読み出さずに，ドントケアとして処理し，
ある検索対象データとしてのキーデータから分割された複数の分割データの全てがドントケアとして処理される場合又は，読み出したエントリアドレスに不一致が生じている場合に，前記バックアップメモリ（３００）から，当該検索対象データとしてのキーデータに基づいて，これに対応するエントリアドレスを検索する
情報読出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，半導体装置，複数の半導体装置を備える情報処理システム，及び半導体装置に対するエントリアドレスの書込／読出方法に関する。具体的に説明すると，本発明の半導体装置は，データの書込時及び検索時における消費電力を低減させることを図った連想メモリ（ＣＡＭ：Content Addressable Memory）などに関するものである。
【背景技術】
【０００２】
近年，クラウドコンピューティングの時代となり，インターネットスイッチやルータの高性能化や消費電力の低減が緊急の課題であるとされている。また，インターネットの検索エンジンとしては，より高速かつ低消費電力で確実な検索操作を行うことができるものが求められている。このような要求に応えるために，近年，インターネットスイッチや検索エンジンでは，ＣＡＭを使用することが多くなってきている。
【０００３】
ここで，一般的なＣＡＭは，ＣＡＭ内に記憶されているデータ検索を行う際に，キーデータと呼ばれる検索データが入力される。そして，ＣＡＭは，キーデータと同じデータがメモリに記憶されている場合に，そのキーデータが記憶されているメモリのアドレス（番地）を出力する。このときのアドレスは，エントリアドレスとも呼ばれる。一般的に，このような検索機能を実現するためには，ＣＡＭ内の全メモリ空間へのアクセスが必要となり，回路構成が複雑になるだけではなく，消費電力が大きくなるという問題があった。特に，この消費電力が大きくなるという問題は，ＣＡＭの規模に伴って大きくなるものであるため，現在では非常に深刻な問題であるとされている。
【０００４】
このような問題に対し，例えば特許文献１では，ＣＡＭの高速検索性を活かしつつ，低消費電力化を図ることを目的としたデータ検索装置が提案されている。特許文献１のデータ検索装置は，プライオリティが決められた複数のルールデータを，その大小の順序に応じて新たに順序付けし，その順序に応じて複数のメモリブロックに割り当てる。また，この検索装置は，データの検索を行う際には，検索すべき一つのメモリブロックを指定して検索処理を実行する。このように，特許文献１のデータ検索装置は，検索処理を行う際に，指定された一つのブロックのみをアクティブにし，他のブロックをアクティブにする必要がないことから，その分，通常のＣＡＭと比較して検索時の消費電力を低減することができるとされている。
【０００５】
しかしながら，上記特許文献１に開示されたデータ検索装置は，通常のメモリと比較して検索時の消費電力を低減することが可能であるものの，検索処理を実行するためには，一度にブロック内の全メモリ空間にアクセスする必要がある。このため，従来のデータ検索装置は，回路構成が複雑であるとともに，検索時における消費電力が大きいという問題を有していた。このように，上記特許文献１の技術は，現在の問題に対する根本的な解決策を提示するものではなかった。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−１８５７９２号公報
【特許文献２】特許第５５７５９９７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで，高速かつ低消費電力でのデータ検索を実現するために，本発明者らによって，新規な半導体装置（ＣＡＭ）が検討されている（特許文献２）。この新規なＣＡＭは，メモリアドレスによって特定されるメモリ空間にキーデータに対応するエントリアドレスが書き込まれる検索メモリマットと，この検索メモリマットに接続された制御回路とを備える。検索メモリマットは，メモリ空間が，メモリアドレスを保持したまま，複数の分割メモリに区分されている。ＣＡＭに対して，検索メモリマットに書き込むためのキーデータが入力されると，制御回路は，このキーデータを複数の分割データに分割する。そして，制御回路は，複数の分割データのそれぞれを，複数の分割メモリに割り当てて，各分割データをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間に，当該分割データに対応するエントリアドレスを書き込んでいく。このようにして，検索メモリマットに，複数のキーデータに対応するエントリアドレスが書き込まれていく。
【０００８】
また，検索メモリマットに書き込まれたキーデータを検索する処理は，書込処理と同様のステップで行われる。つまり，ＣＡＭに対して，検索対象データとしてのキーデータが入力されると，制御回路は，この検索対象データとしてのキーデータを複数の分割データに分割していく。そして，制御回路は，分割データのそれぞれをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間にアクセスし，アクセスしたメモリ空間から，当該分割データに対応するエントリアドレスを読み出す。
【０００９】
このようにして，本発明者により開発された新規なＣＡＭでは，キーデータが複数に分割され，この分割されたキーデータのそれぞれに対応するエントリアドレスが，分割メモリに記憶される。このため，このエントリアドレスを検索する際には，検索メモリマット全体を一度にアクティブに（活性化）させる必要はなく，検索メモリマットを分割メモリごとに部分的にアクティブにさせて検索することが可能となる。従って，このＣＡＭによれば，従来のＣＡＭと同様の高速性でデータ検索を実現しつつ，従来のＣＡＭよりも極めて低い消費電力でデータ検索を実行することができる。
【００１０】
ただし，ＣＡＭのメモリ空間に対して，複数のキーデータに対応するエントリアドレスを書き込もうとする場合，そのメモリ空間に，他のキーデータに対応するエントリアドレスが既に書き込まれている事態が想定される。このように，メモリ空間にエントリアドレスの衝突が生じている場合には，そのメモリ空間に，エントリアドレスの衝突を表す衝突情報（ドントケア値）を登録することで対処する。これにより，エントリアドレスの書込処理／読出処理を高速化できる。
【００１１】
しかしながら，半導体装置に書き込もうとするキーデータの値に偏りが生じており，キーデータの値がほぼ同じ値となっている場合など，キーデータを書き込もうとする際に，すべてのメモリ空間に衝突（全衝突）が生じている場合もある。このような全衝突が生じている場合，分割されたメモリ空間には，キーデータに対応するエントリアドレスが書き込まれることなく，衝突情報（ドントケア値）のみが登録されることとなる。そうすると，全衝突が生じているキーデータを検索メモリマットから検索しようとする際には，衝突情報（ドントケア値）しか読み出すことができない。この場合，例えば，衝突しているエントリアドレスから，検索対象のキーデータに対応するエントリアドレスの複数の候補を読み出し，これらの複数の候補の中から，検索対象のキーデータに対応するかどうかを一つ一つ照合する処理（いわゆる総ざらい処理）を行う必要ある。このような総ざらい処理が発生すると，データ検索処理を遅延を招いたり，データ検索の精度が低下するという問題があると考えられていた。
【００１２】
このように，本発明者らによっても，新規なＣＡＭの構造において，キーデータの書込処理時に全衝突が発生した場合の対策については検討の余地があるとされていた。
【００１３】
また，ＣＡＭは，ワイルドカード検索機能を実装していることが求められる。例えば，ＩＰｖ４に準拠した３２ビットのＩＰアドレスは，上位２４ビット（又は２８ビット）がネットワークアドレスとなり，下位８ビット（又は４ビット）がホストアドレスとなるように規定されている。例えば，２４ビットのネットワークアドレスは「／２４」のように表記され，２８ビットのネットワークアドレスは「／２８」のように表記される。このような。このとき，例えば，ＣＡＭに記憶されたＩＰアドレスのうち，上位２４ビットのネットワークアドレスが一致するものが検索対象とされ，下位８ビットのホストアドレスが無視（ドントケア）して検索が行われることも多い。このような，部分一致の検索機能は，ワイルドカード検索機能とも呼ばれる。
【００１４】
一般的なＣＡＭには，このようなワイルドカード検索機能が実装されていることが求められている。本発明者らに検討されている新規なＣＡＭの構造においても，このワイルドカード検索機能を実現するためのアーキテクチャについては検討の余地があるとされていた。
【００１５】
そこで，本発明の第１は，キーデータの書込処理時に全衝突が発生した場合の効率的な解決手段を提供することを第１の目的とする。
【００１６】
また，本発明は，ワイルドカード検索機能を実現するための効率的なアーキテクチャを提供することを第２の目的とする。
【００１７】
本発明は，第１の目的と第２の目的の少なくともいずれか一方を達成するものである。
【課題を解決するための手段】
【００１８】
本発明の第１の側面は，半導体装置に関する。
本発明の半導体装置は，検索メモリマット１００と，制御回路２００と，バックアップメモリ３００と，を備える。
検索メモリマット１００は，メモリアドレス（ＭＡ）によって特定されるメモリ空間に，キーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）が書き込まれる。制御回路２００は，検索メモリマット１００に接続されている。バックアップメモリ３００は，制御回路２００に接続されている。
検索メモリマット１００は，メモリ空間が，メモリアドレス（ＭＡ）を保持したまま，複数の分割メモリ１１０ａ，１１０ｂ…に区分されたものある。つまり，検索メモリマット１００は，共通するメモリアドレス（ＭＡ）を有する複数の分割メモリ１１０ａ，１１０ｂ…によって構成されている。
制御回路２００は，入力部２１０と，分割部２２０と，書込部２３０と，を有する。
入力部２１０には，検索メモリマット１００に書き込むためのキーデータ（ＫＤ）が入力される。分割部２２０は，入力部２１０に入力されたキーデータ（ＫＤ）を複数の分割データに分割する。そして，書込部２３０は，複数の分割データのそれぞれを，複数の分割メモリ１１０ａ，１１０ｂ…に割り当てて，各分割データをアドレスとして，各分割メモリ１１０ａ，１１０ｂ…のメモリアドレス（ＭＡ）によって特定されるメモリ空間に，当該分割データに対応するエントリアドレス（ＥＡ）を書き込む（図４参照）。
ここで，書込部２３０は，ある分割データに対応するエントリアドレス（ＥＡ）を書き込むべきメモリ空間に，既に他の分割データに対応するエントリアドレス（ＥＡ）が書き込まれている場合には，当該メモリ空間に，エントリアドレス（ＥＡ）の衝突を表す衝突情報（ドントケア値）を登録する（図５参照）。
さらに，書込部２３０は，あるキーデータから分割された複数の分割データの全てについて，エントリアドレス（ＥＡ）の衝突が生じている場合には，その全衝突が生じているキーデータ（ＫＤ）とこれに対応するエントリアドレス（ＥＡ）とを対応付けて，バックアップメモリ３００に書き込む（図６参照）。
【００１９】
上記構成のように，本発明の半導体装置は，全衝突対策として，バックアップメモリ３００を備えている。つまり，本発明の半導体装置では，（ｉ）キーデータを複数の分割データに分割し，（ｉｉ）各分割データを分割メモリ１１０ａ，１１０ｂ…に割り当てて，（ｉｉｉ）各分割データをアドレスとして，各分割メモリ１１０ａ，１１０ｂ…のメモリアドレスによって特定されるメモリ空間にアクセスし，（ｉｖ）アクセスしたメモリ空間に，キーデータに対応するエントリアドレスを書き込む処理を行う（図４参照）。このとき，ある分割データに対応するエントリアドレス（ＥＡ）を書き込むべきメモリ空間に，既に他の分割データに対応するエントリアドレス（ＥＡ）が書き込まれている場合には，当該メモリ空間に，エントリアドレス（ＥＡ）の衝突を表す衝突情報（ドントケア値）を登録する（図５参照）。しかしながら，このような衝突情報は，あるキーデータから分割された複数の分割データの全てについて書き込まれる可能性もある。そこで，本発明の半導体装置は，全衝突が生じている場合には，その全衝突が生じているキーデータとこれに対応するエントリアドレスとを対応付けて，検索メモリマット１００とは別に設けられたバックアップメモリ３００に書き込む（図６参照）。このように，本発明の半導体装置は，バックアップメモリ３００を設けておくことで，全衝突が生じるキーデータとそのエントリアドレスとを，回避させて記憶しておくことができる。全衝突が生じたキーデータは，読出処理（検索処理）が非常に煩雑なものであったが，バックアップメモリ３００に記憶しておくことで，読出処理（検索処理）を迅速かつ効率的に行うことができる。これにより，上述した本発明の第１の目的が達成される。
【００２０】
本発明の半導体装置は，エントリアドレス（ＥＡ）に対応づけてキーデータ（ＫＤ）が記憶される確認用メモリ４００を，さらに備えることが好ましい。特に，この確認用メモリ４００には，上述したバックアップメモリ３００に書き込まれていないエントリアドレス（ＥＡ）とキーデータ（ＫＤ）のみが記憶されることが好ましい。
【００２１】
上記構成のように，半導体装置は，検索メモリマット１００及びバックアップメモリ３００とは別の用途として，確認用メモリ４００を備えていることが好ましい。例えば，半導体装置は，新規なキーデータが入力されてきたときに，その新規なキーデータにエントリアドレスを割り当てて，その新規なキーデータとエントリアドレスの対応関係を，確認用メモリ４００に記憶しておくことができる。このようにすることで，キーデータの読出処理によってエントリアドレスを読み出すときに，適宜，確認用メモリ４００を参照するようにすれば，その読み出したエントリアドレスが，検索対象データに対応するものであるかどうかを確認することができる。特に，検索メモリマット１００においてにエントリアドレスの衝突が発生しており，読み出し処理時にドントケア処理が行われる場合には，確認用メモリ４００を利用して，読み出したエントリアドレスが適切なものであるかを確認することは有効である。このようにして，本発明によれば，エントリアドレスの衝突が生じている場合であっても，正確にデータ検索を行うことが可能となる。また，バックアップメモリ３００に書き込まれるエントリアドレスとキーデータについては，確認用メモリ４００に記憶する必要はない。これにより，バックアップメモリ３００と確認用メモリ４００という別々のメモリに，重複したデータが書き込まれることを防止できる。
【００２２】
本発明の半導体装置は，さらに，マスクレジスタ５００を備えることが好ましい。
マスクレジスタ５００は，所望のマスクパターンが登録されており，当該マスクパターンに応じて，入力されたキーデータにマスクを付与する処理を行う。そして，マスクレジスタ５００によってマスクが付与されたキーデータが，制御回路２００の入力部２１０に入力される。
【００２３】
上記構成のように，マスクレジスタ５００を設け，書込対象又は検索対象のキーデータに対してマスクを付与することにより，本発明の半導体装置にワイルドカード検索機能を実装することができる。つまり，マスクが付与された後のキーデータを，入力部２１０を介して，分割部２２０及び書込部２３０へと入力して処理することにより，マスクが付与されたキーデータを検索メモリマット１００に記憶しておくことができる。これにより，検索メモリマット１００からキーデータに対応するエントリアドレスを読み出す際にも，マスクが付与されたビットを無視する（ドントケアとする）ことが可能となる。これにより，上述した本発明の第２の目的が達成される。
【００２４】
本発明の半導体装置において，制御回路２００は，さらに，読出部２４０を有することが好ましい。まず，入力部２１０に，検索対象データとしてのキーデータが入力されると，分割部２２０が，当該検索対象データとしてのキーデータを複数の分割データに分割する。その後，読出部２４０は，分割データのそれぞれをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間にアクセスし，アクセスしたメモリ空間から，当該分割データに対応するエントリアドレスを読み出す（図７参照）。
このとき，読出部２４０は，メモリ空間にアクセスしたときに，当該メモリ空間に前記衝突情報が登録されている場合には，分割データに対応するエントリアドレスを読み出さずに，ドントケアとして処理する（図７参照）。
他方，読出部２４０は，ある検索対象データとしてのキーデータから分割された複数の分割データの全てがドントケアとして処理される場合，又は，読み出したエントリアドレスに不一致が生じている場合に，バックアップメモリ３００から，当該検索対象データとしてのキーデータに基づいて，これに対応するエントリアドレスを検索する（図８参照）。
【００２５】
上記構成のように，検索対象データとしてのキーデータに対応するエントリアドレスを読み出そうとした場合，分割データの全てがドントケアとして処理される場合（全衝突）が想定される。例えば，全衝突が発生している場合，メモリ空間に書き込まれているエントリアドレスの候補を全て読み出して，検索対象データとしてのキーデータと一致しているかどうかを総ざらい的に検証することも可能である。しかし，上述した総ざらい処理を行うと，キーデータの検索処理に著しい遅延が発生する。そこで，このように全衝突が発生している場合や，エントリアドレスの不一致が生じている場合に，バックアップメモリ３００を参照して，検索対象データとしてのキーデータに一致するキーデータを検索することとしている。これにより，総ざらい処理による処理遅延を回避し，迅速かつ効率的に検索結果を出力することが可能となる。このような処理は，上述した本発明の第１の目的に関連する。
【００２６】
本発明の第２の側面は，情報処理システムに関する。第２の側面に係る情報処理システムは，上述した第１の側面に係る半導体装置１０を複数有するシステムである。
本発明の情報処理システムにおいて，複数の半導体装置１０は，それぞれ，マスクレジスタ５００に登録されているマスクパターンが異なることが好ましい。
【００２７】
上記構成のように，半導体装置１０を複数用意し，各半導体装置１０のマスクレジスタ５００に異なるマスクパターンを登録しておく。そして，書込対象又は検索対象のキーデータがシステムに入力されたときには，マスクパターンの異なる複数の半導体装置１０のそれぞれに，同じキーデータを入力する。このようにして，予め複数のマスクパターンを登録しておくことで，ワイルドカード検索機能を利用するユーザに対して，ユーザの希望に則した検索結果を提供することができる。
【００２８】
本発明の情報処理システムは，さらに，マスクコントローラ２０を備えていることが好ましい。
マスクコントローラ２０は，複数の半導体装置１０のそれぞれに接続されている。
マスクコントローラ２０は，テーブルデータ入力部２１と，マスクパターン生成部２２と，マスクパターン登録部２３と，を有する。
テーブルデータ入力部２１には，マスク部位を有する複数のキーデータが含まれるテーブルデータが入力される。すなわち，テーブルデータには，複数のキーデータが含まれており，この複数のキーデータの中にはマスク部位を有するものが含まれる。キーデータのマスク部位には，複数のパターンが存在していることが好ましい（図１１参照）。
マスクパターン生成部２２は，テーブルデータに含まれる複数のキーデータのマスク部位のパターンを解析して，複数種類のマスクパターンを生成する（図１１参照）。
マスクパターン登録部２３は，マスクパターン生成部２２が生成した複数種類のマスクパターンを，それぞれ，異なる前記半導体装置１０のマスクレジスタ５００に登録する（図１２，図１参照）。
【００２９】
上記構成のように，マスクコントローラ２０を備えることで，マスク部位の異なる複数のキーデータから構成されるテーブルデータを，一括して，半導体装置１０の検索メモリマット１００に書き込むことができる。テーブルデータを書き込む際に，マスクコントローラ２０が，キーデータのマスク部位を自動的に解析して，このマスク部位をパターン化し，このマスク部位のパターンに対応するマスクパターンを，半導体装置１０のマスクレジスタ５００に登録していく。このため，テーブルデータ内に含まれるキーデータを検索する際には，ワイルドカード検索機能を利用することが可能となる。このような処理は，上述した本発明の第２の目的に関連する。
【００３０】
本発明の第３の側面は，情報書込方法に関する。第３の側面に係る情報書込方法は，上述した第１の側面に係る半導体装置により実行される。
情報書込方法は，
制御回路にキーデータが入力される工程と；
制御回路が，キーデータを複数の分割データに分割する工程と；
制御回路が，複数の前記分割データのそれぞれを，複数の分割メモリに割り当てて，各分割データをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間に，当該分割データに対応するエントリアドレスを書き込む工程と，を含む。
エントリアドレスを書き込む工程において，制御回路は，ある分割データに対応するエントリアドレスを書き込むべきメモリ空間に，既に他の分割データに対応するエントリアドレスが書き込まれている場合には，当該メモリ空間に，エントリアドレスの衝突を表す衝突情報を登録する。ただし，制御回路は，あるキーデータから分割された複数の分割データの全てについて衝突が生じている場合には，その全衝突が生じているキーデータとこれに対応するエントリアドレスとを対応付けて，バックアップメモリ３００に書き込む。
【００３１】
本発明の第４の側面は，情報読出方法に関する。第４の側面に係る情報読出方法は，上述した第３の側面に係る情報書込方法によって，半導体装置に書き込まれた情報を読み出す方法である。
情報読出方法は，
制御回路に検索対象データとしてのキーデータが入力される工程と；
制御回路が，検索対象データとしてのキーデータを複数の分割データに分割する工程と；
制御回路が，分割データのそれぞれをアドレスとして，各分割メモリのメモリアドレスによって特定されるメモリ空間にアクセスし，アクセスしたメモリ空間から，当該分割データに対応するエントリアドレスを読み出す工程と，を含む。
エントリアドレスを読み出す工程において，制御回路は，メモリ空間にアクセスしたときに，当該メモリ空間に前記衝突情報が登録されている場合には，分割データに対応するエントリアドレスを読み出さずに，ドントケアとして処理する。ただし，制御回路は，ある検索対象データとしてのキーデータから分割された複数の分割データの全てがドントケアとして処理される場合，又は，読み出したエントリアドレスに不一致が生じている場合に，バックアップメモリ３００から，当該検索対象データとしてのキーデータに基づいて，これに対応するエントリアドレスを検索する。
【発明の効果】
【００３２】
本発明によれば，キーデータの書込処理時に全衝突が発生した場合の効率的な解決手段を提供することができる（第１の目的）。また，本発明によれば，ワイルドカード検索機能を実現するための効率的なアーキテクチャを提供することができる（第２の目的）。
【図面の簡単な説明】
【００３３】
【図１】図１は，本発明に係る情報処理システムの機能ブロックを示している。
【図２】図２は，本発明に係る半導体装置の機能ブロックを示している。
【図３】図３は，本発明に係る半導体装置による書込処理／読出処理のフローを示している。
【図４】図４は，基本的な書込処理の例を示している。
【図５】図５は，衝突が生じた場合の書込処理の例を示している。
【図６】図６は，全衝突が生じた場合の書込処理の例を示している。
【図７】図７は，基本的な読出処理の例を示している。
【図８】図８は，不一致が発生した場合の読出処理の例を示している。
【図９】図９は，全衝突が発生した場合の読出処理の例を示している。
【図１０】図１０は，マスクコントローラの構成例を示している。
【図１１】図１１は，マスクレジスタを含む情報処理システムの構成例を示している。
【図１２】図１２は，マスク処理を含む書込処理の例を示している。
【図１３】図１３は，マスク処理を含む読出処理の例を示している。
【図１４】図１４は，符号化処理の一例を示している。
【図１５】図１５は，符号化処理の他の例を示している。
【図１６】図１６は，ワイルドカード検索の方式例を示している。
【図１７】図１７は，ワイルドカード検索の方式例を示している。
【図１８】図１８は，ワイルドカード検索の方式例を示している。
【図１９】図１９は，ワイルドカード検索の方式例を示している。
【図２０】図２０は，ワイルドカード検索の方式例を示している。
【図２１】図２１は，ワイルドカード検索の方式例を示している。
【図２２】図２２は，ワイルドカード検索の方式例を示している。
【図２３】図２３は，ワイルドカード検索の方式例を示している。
【図２４】図２４は，ワイルドカード検索の方式例を示している。
【発明を実施するための形態】
【００３４】
以下，図面を用いて本発明を実施するための形態について説明する。本発明は，以下に説明する形態に限定されるものではなく，以下の形態から当業者が自明な範囲で適宜修正したものも含む。
【００３５】
図１は，情報処理システム１の概要を示したブロック図である。図１に示されるように，情報処理システム１は，複数の半導体装置１０と，各半導体装置１０の入力側に接続されたマスクコントローラ２０と，各半導体装置１０の出力側に接続されたプライオリタイザ３０と，を含む。本願明細書では，まず，半導体装置１０の構成について詳しく説明する。その後，複数の半導体装置１０を含んで構成された情報処理システム１の構成について説明を行う。
【００３６】
図１は，半導体装置１０の内部構成の概要を示している。また，図２は，半導体装置１０の主たる機能構成を示した機能ブロック図である。また，図３は，半導体装置１０による処理の流れを示したフロー図である。さらに，図４〜図６は，半導体装置１０によるエントリアドレスの書込処理の例を示しており，図７〜図９は，半導体装置１０によるエントリアドレスの読出処理（検索処理）の例を示している。
【００３７】
図１及び図２に示されるように，半導体装置１０は，基本的に，検索メモリマット１００と制御回路２００とを備える。また半導体装置１０は，さらに，バックアップメモリ３００，確認用メモリ４００，マスクレジスタ５００，及び符号化回路６００を備えることが好ましい。制御回路２００は，検索メモリマット１００，バックアップメモリ３００，及び確認用メモリ４００に接続されており，各メモリ１００，３００，４００に対して所定のデータ（情報）を書き込んだり読み出したりする情報処理を総合的に制御する機能を担っている。特に，制御回路２００は，検索メモリマット１００に対するデータの書込処理及び読出処理が主たる機能となる。また，制御回路２００には，マスクレジスタ５００及び符号化回路６００を介してデータが入力される。このため，制御回路２００は，マスクレジスタ５００及び符号化回路６００を経由したデータに基づいて，各メモリ１００，３００，４００に対して，データの書込処理及び読出処理を行う。
【００３８】
検索メモリマット１００は，メモリアドレス（ＭＡ）によって特定されるメモリ空間（Ｄ）に，キーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）が書き込まれる記憶装置（メモリ）である。検索メモリマット１００は，エントリアドレス（ＥＡ）を書き込むためのメモリ空間（Ｄ）が，メモリアドレス（ＭＡ）を保持したまま，複数の分割メモリ１１０ａ，１１０ｂ…に区分された構成となっている。例えば，検索メモリマット１００及び複数の分割メモリ１１０ａ，１１０ｂ…の例は，図４などに示されている。
【００３９】
まず，図４を参照して，簡単に，検索メモリマット１００と，それに記憶されるエントリアドレス（ＥＡ）及びキーデータ（ＫＤ）の関係について説明する。図４に示されるように，検索メモリマット１００は，ｙ軸方向に沿って複数のメモリアドレス（ＭＡ）が順番に割り当てられており，このメモリアドレス（ＭＡ）によってメモリ空間（Ｄ）のアドレス（番地）が特定されている。メモリ空間（Ｄ）は，ｘ軸方向に沿ってデータを記憶する領域を有している。この検索メモリマット１００は，複数の分割メモリ１１０ａ，１１０ｂ…に区分されている。複数の分割メモリ１１０ａ，１１ｂ…は，メモリアドレス（ＭＡ）と，それによって特定されるメモリ空間（Ｄ）を保持している。また，複数の分割メモリ１１０ａ，１１０ｂ…のメモリアドレス（ＭＡ）は，それぞれ共通している。つまり，分割メモリ１１０ａ，１１０ｂ…のそれぞれは，メモリアドレス（ＭＡ）とそれによって特定されるメモリ空間（Ｄ）とが一対一で対応付けられた構成となっている。このように，検索メモリマット１００は，複数の分割メモリ１１０ａ，１１０ｂ…に区分されたものと考えることができる。言い換えると，複数の分割メモリ１１０ａ，１１０ｂ…の集合によって，検索メモリマット１００が構築されている。
【００４０】
本発明の半導体装置１０は，ＣＡＭ（連想メモリ）として利用することができる。つまり，半導体装置１０は，検索メモリマット１００に，キーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）を書き込む。その後又はこれと同時に，半導体装置１０は，エントリアドレス（ＥＡ）と対応付けてキーデータ（ＫＤ）を確認用メモリ４００又はバックアップメモリ３００に書き込む。他方，半導体装置１０に対して，検索対象としてのキーデータ（ＫＤ）を入力すると，半導体装置１０は，このキーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）を読み出して出力する。つまり，「キーデータ」とは，半導体装置１０に記憶される所望のデータを意味する。また，「エントリアドレス」とは，キーデータ（ＫＤ）が記憶されているメモリ（具体的には確認用メモリ４００又はバックアップメモリ３００）の場所（アドレス）を示すメタデータを意味している。
【００４１】
図４に示された例において，エントリアドレス（ＥＡ）は，１６進法２桁で表される８ｂｉｔのデータとして定義されている。８ｂｉｔのエントリアドレス（ＥＡ）は，００〜ＦＦの値をとる。半導体装置１０は，１つのエントリアドレス（ＥＡ）に対応付けて，１つのキーデータ（ＫＤ）を記憶するものである。つまり，１つのキーデータ（ＫＤ）に対し，１つのエントリアドレス（ＥＡ）が割り当てられる。このため，エントリアドレス（ＥＡ）が８ｂｉｔの情報である場合，半導体装置１０には２５６のキーデータ（ＫＤ）を記憶することが可能となる。従って，エントリアドレスが８ｂｉｔに設定されている半導体装置は，総エントリ数が２５６となる。なお，本発明において，エントリアドレス（ＥＡ）は，２ｂｉｔ以上のデータであれば問題ない。例えば，エントリアドレス（ＥＡ）は，３ｂｉｔ，４ｂｉｔ，６ｂｉｔ，又は８ｂｉｔ以上とすることもできる。また，エントリアドレス（ＥＡ）のｂｉｔ数は，検索メモリマット１００のメモリアドレス（ＭＡ）のｂｉｔ数と一致していることが好ましい。図４に示した例では，エントリアドレス（ＥＡ）とメモリアドレス（ＭＡ）は，共に，８ｂｉｔに設定されている。
【００４２】
また，図４に示された例において，半導体装置１０に入力されたキーデータ（ＫＤ）は，１４４ｂｉｔのデータに設定されている。１４４ｂｉｔのキーデータ（ＫＤ）を，エントリアドレス（ＥＡ）のｂｉｔ数に対応するように８ｂｉｔごとに分割すると，１８個のデータ（分割データ）に分割できる（つまり，１４４ｂｉｔ÷８ｂｉｔ＝１８）。ここで，本発明の半導体装置１０において，検索メモリマット１００を構成する分割メモリ１１０ａ，１１０ｂ…の数は，少なくともキーデータの分割数（１８）以上必要とされる。なお，キーデータ（ＫＤ）のｂｉｔ数は，１４４ｂｉｔに限定されるものではなく，必要に応じて適宜調整可能である。また，キーデータ（ＫＤ）を複数の分割データに分割するにあたり，キーデータ（ＫＤ）のｂｉｔ数を割る数は，エントリアドレス（ＥＡ）のｂｉｔ数であることが好ましい。つまり，（分割メモリの数）≧（ＫＤのｂｉｔ数）÷（ＥＡのｂｉｔ数）となることが好ましい。
【００４３】
また，図４に示された例において，各分割メモリ１１０ａ，１１０ｂ…のメモリアドレス（ＭＡ）は，それぞれ，８ｂｉｔで定義されたデータ（情報）である。つまり，図４に示された例では，キーデータ（ＫＤ）から分割された分割データと，メモリアドレス（ＭＡ）とは，それぞれ８ｂｉｔに設定されている点で共通している。このように，分割データとメモリアドレス（ＭＡ）のｂｉｔ数は一致していることが好ましい。なお，上述のとおり，メモリアドレス（ＭＡ）のｂｉｔ数は，エントリアドレス（ＥＡ）のｂｉｔ数とも一致する。
【００４４】
このように，本発明の半導体装置１０において，検索メモリマット１００は，エントリアドレス（ＥＡ）を書き込むためのメモリ空間（Ｄ）が，メモリアドレス（ＭＡ）を保持したまま，複数の分割メモリ１１０ａ，１１０ｂ…に区分された構成となっている。各分割メモリは，例えば，ＳＲＡＭ（Static Random Access Memory）などの記憶装置を用いて構成することができる。この意味において，本発明は，複数のＳＲＡＭを利用して実現したＣＡＭであるということができる。本発明のように，複数のＳＲＡＭを用いて実現したＣＡＭを，ＳＲＡＭ−ＣＡＭと称することもできる。
【００４５】
また，図４に示された例のように，半導体装置１０に記憶可能なキーデータ（ＫＤ）の数（総エントリ数）を２５６エントリと定めた場合，この２５６エントリを識別するために必要なエントリアドレス（ＥＡ）のｂｉｔサイズは，８ｂｉｔになる。また，半導体装置１０に入力されるキーデータのｂｉｔサイズが１４４ｂｉｔであるとした場合，これをエントリアドレス（ＥＡ）のｂｉｔ数８で割ると１８となる。このような条件を想定すると，分割メモリ１１０ａ，１１０ｂ…の数は，少なくとも１８以上必要となる。
【００４６】
本発明の半導体装置１０において，最低限必要となる分割メモリ１１０ａ，１１０ｂ…の数Ｎ（検索メモリマット１００の分割数Ｎ）は，以下の式により求めることができる。
（式）Ｎ＝Ｌ／ｌｏｇ２・Ｍ
Ｌ：キーデータ長（ｂｉｔ数）
Ｍ：総エントリ数
Ｎ：分割メモリの最小個数（検索メモリマットの分割数）
【００４７】
続いて，図２〜図９を参照して，半導体装置１０による書込処理及び読出処理について説明する。なお，図２及び図３に示されたマスクレジスタ５００によるマスク処理と，符号化回路６００による符号化処理については，後ほど詳しく後述する。まずは，マスク処理と符号化処理を除き，半導体装置１０による基本的な書込処理について説明を行う。
【００４８】
図２に示されるように，制御回路２００は，基本的に，入力部２１０，分割部２２０，書込部２３０，読出部２４０，確認部２５０，及び出力部２６０を有している。これらの要素２１０〜２６０は，制御回路２００の機能を概念的に分類して示したものである。すなわち，制御回路２００は，これらの機能的要素２１０〜２６０を利用して，検索メモリマット１００に対しエントリアドレス（ＥＡ）を書き込んだり，検索メモリマット１００に記憶されているエントリアドレス（ＥＡ）を読み出したりする処理を行う。また，図３には，制御回路２００による情報処理のフローが示されている。
【００４９】
まず，制御回路２００により行われるエントリアドレス（ＥＡ）の書込処理を説明する。基本的な書込処理の具体例は，図４〜図６に示されている。ここでの書込処理とは，新しいキーデータ（ＫＤ）を記憶するにあたり，その新しいキーデータ（ＫＤ）に対応したエントリアドレス（ＥＡ）を検索メモリマット１００に書き込む処理である。
【００５０】
図２に示されるように，書込処理においては，まず，書込対象となるキーデータが，半導体装置１０に入力される。ここで，書込対象のキーデータは，図２に示されるように，制御回路２００の入力部２１０に直接入力されることとしてもよい。また，書込対象となるキーデータは，マスクレジスタ５００と符号化回路６００とを経由して，制御回路２００の入力部２１０に入力されてもよい。マスクレジスタ５００と符号化回路６００による処理については，詳しくは後述する。
【００５１】
書込対象のキーデータが制御回路２００の入力部２１０に入力されると，この入力部２１０は，キーデータを分割部２２０へと送出する。つまり，入力部２１０は，制御回路２００における入力インターフェースとして機能する。
【００５２】
続いて，分割部２２０は，書込対象のキーデータを，複数の分割データへと分割する。例えば，分割部２２０は，検索メモリマット１００を構築する分割メモリ１１０ａ，１１０ｂ…の数と等しい数にキーデータを分割することが好ましい。つまり，分割部２２０がキーデータを分割する分割数ｎは，検索メモリマット１００を構築する分割メモリ１１０ａ，１１０ｂ…の数Ｎと等しいことが好ましい。これにより，分割部２２０によって複数に分割したキーデータ（分割データ）の全てを，それぞれ順番に，複数の分割メモリ１１０ａ，１１０ｂ…に対して割り当てていくことができる。例えば，図３に示した例において，半導体装置１０には，１４４ｂｉｔのキーデータが入力されることが想定されている。また，各キーデータに割り当てられるエントリアドレスのｂｉｔ数は，８ｂｉｔであり，分割メモリの数は１８となっている。このような条件において，分割部２２０は，１４４ｂｉｔのキーデータを，８ｂｉｔ毎に１８個の分割データへと分割することが好ましい。分割部２２０によって，１４４ｂｉｔのキーデータは，８ｂｉｔずつ，１８個の分割データに変換される。なお，分割部２２０による分割条件は，分割メモリの数や，エントリアドレスのｂｉｔ数，キーデータのｂｉｔ数などに応じて，適宜変更することが可能である。分割部２２０によって生成された複数の分割データは，書込部２３０へと送出される。
【００５３】
さらに詳しく説明すると，分割部２２０により分割された分割データのビット数（α）は，検索メモリマット１００のメモリアドレス（ＭＡ）のビット数（β）と等しいことが好ましい（α＝β）。例えば，図４などに示されるように，検索メモリマット１００のメモリアドレス（ＭＡ）が８ｂｉｔで表される場合には，分割部２２０は，キーデータ（ＫＤ）を８ｂｉｔの分割データに分割することが好ましい。また例えば，検索メモリマット１００のメモリアドレス（ＭＡ）が，２ｂｉｔで表される場合には，分割部２２０は，キーデータ（ＫＤ）を２ｂｉｔの分割データに分割することが好ましい。これにより，後の処理において，分割部２２０が分割した分割データのそれぞれを，当該分割データをアドレスとして，検索メモリマット１００を構築する分割メモリに適切に割り当てることができる。
【００５４】
書込部２３０は，検索メモリマット１００を構築する複数の分割メモリ１１０ａ，１１０ｂ…や，確認用メモリ４００，バックアップメモリ３００に対して，所定のデータを書き込む機能を有する。
【００５５】
図２及び図３に示されるように，半導体装置１０に対して書込対象のキーデータ（ＫＤ）が入力されると，まず，書込部２３０は，このキーデータ（ＫＤ）に対して固有のエントリアドレス（ＥＡ）を割り当てる。このエントリアドレス（ＥＡ）は，一つのキーデータ（ＫＤ）について一つ割り当てられるものである。
【００５６】
また，書込部２３０は，キーデータ（ＫＤ）に対して固有のエントリアドレス（ＥＡ）を割り当てた後，又は割り当てると同時に，検索メモリマット１００を構成する複数の分割メモリ１１０ａ，１１０ｂ…に対して，キーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）を書き込んでいく。図３に示されるように，書込部２３０は，複数の分割データをアドレスとして，これらの分割データのそれぞれに対応するエントリアドレス（ＥＡ）を，分割メモリ１１０ａ，１１０ｂ…に対して書き込む。
【００５７】
具体的に説明すると，図３に示されるように，キーデータ（ＫＤ）の分割数と検索メモリマット１００の区分数は等しくなっている。図３に示した例では，キーデータ（ＫＤ）は，１８個の分割データに分割されており，検索メモリマット１００は，１８個の分割メモリに区分されている。まず，書込部２３０は，複数の分割データを，それぞれ１つずつ，分割メモリに割り当てる。つまり，１番目の分割データは１番目の分割メモリに割り当てられ，２番目の分割データは２番目の分割メモリに割り当てられ，同じようにして，ｋ番目の分割データはｋ番目の分割メモリに割り当てられる。ここで，各分割メモリは，メモリアドレス（ＭＡ）が付与されており，このメモリアドレス（ＭＡ）によってメモリ空間が特定されている。書込部２３０は，分割データを分割メモリに割り当てた後，この分割データと分割メモリのメモリアドレス（ＭＡ）とを照合して，この分割データと一致するメモリアドレス（ＭＡ）を指定する。例えば，分割データが“００”という値である場合，書込部２３０は，分割メモリの中から，“００”という値を有するメモリアドレス（ＭＡ）を指定する。そして，書込部２３０は，分割データに一致するメモリアドレス（ＭＡ）によって特定されるメモリ空間にアクセスし，このメモリ空間に分割データに対応するエントリアドレス（ＥＡ）を書き込んでいく。例えば，分割データ“００”に対応するエントリアドレスが“０１”である場合，メモリアドレス“００”によって特定されるメモリ空間に，エントリアドレス“０１”を書き込む。このように，書込部２３０は，分割データをアドレスとして，メモリアドレス（ＭＡ）によって特定されるメモリ空間にアクセスし，アクセスしたメモリ空間に，分割データに対応するエントリアドレス（ＥＡ）を書き込む。書込部２３０は，このようなエントリアドレス（ＥＡ）の書込処理を，分割データが割り当てられた全ての分割メモリに対して行っていく。このような処理が，基本的な書込処理となる。
【００５８】
また，書込部２３０は，入力部２１０に入力されたキーデータ（ＫＤ）（分割前の状態のキーデータ）と，これに割り当てたエントリアドレス（ＥＡ）とを対応付けて，確認用メモリ４００に書き込む処理を行う。すなわち，新しい書込対象のキーデータが半導体装置１０に入力された際，書込部２３０は，この新しいキーデータに対して一つのエントリアドレスを割り当てて，新しいキーデータとエントリアドレスの対応関係を，確認用メモリ４００に記憶しておく。これにより，確認用メモリ４００には，エントリアドレス（ＥＡ）とキーデータ（ＫＤ）とが一対一で対応して記憶される。このように，確認用メモリ４００は，キーデータとエントリアドレスの対応関係を記憶しておくためのデータベースとしても機能する。また，確認用メモリ４００は，後述するように，読出処理を行う際に，制御回路が読み出したエントリアドレスが正しいものであるか否かの最終確認を行う際にも利用される。なお，確認用メモリ４００は，ＳＲＡＭ等の公知の記憶装置によって構成すればよい。
【００５９】
また，例えば図３や図４に示されるように，確認用メモリ４００は，予めエントリアドレス（ＥＡ）がすべて登録されている構成であってもよい。つまり，確認用メモリ４００は，予め登録されているエントリアドレス（ＥＡ）によって空のメモリ空間が特定されており，この空のメモリ空間に対してキーデータ（ＫＤ）を書き込むことができるようになっている。例えば，書込部２３０は，キーデータ（ＫＤ）に対して割り当てられたエントリアドレス（ＥＡ）を参照して，確認用メモリ４００にアクセスする。そして，確認用メモリ４００内のエントリアドレス（ＥＡ）によって特定されるメモリ空間に，キーデータ（ＫＤ）を書き込む。このような処理によっても，結果的には，一つのエントリアドレス（ＥＡ）と一つのキーデータ（ＫＤ）とが対応付けて確認用メモリ４００に記憶されることとなる。
【００６０】
次に，図４〜図６を参照して，書込部２３０による書込処理について，具体例を挙げて説明する。
【００６１】
まず，図４は，基本的な書込処理の例を示している。図４に示した例では，“００＿０１＿０２＿０３＿０４＿０５＿０６＿０７＿０８＿０９＿０Ａ＿０Ｂ＿０Ｃ＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿１１”という値のキーデータ（ＫＤ）が，半導体装置１０に入力される。なお，アンダーラインは便宜的に付されたものであり，本来的には存在しない。キーデータ（ＫＤ）は，１６進法で表された１４４ｂｉｔの値である。書込部２３０は，まずこのキーデータ（ＫＤ）に対して，“００”の値を持つエントリアドレス（ＥＡ）を割り当てる。エントリアドレス（ＥＡ）は，１６進法２桁で表された８ｂｉｔの値である。
【００６２】
またキーデータ（ＫＤ）が半導体装置１０に入力されると，分割部２２０が，このキーデータ（ＫＤ）を複数の分割データに分割する。図４に示された例において，検索メモリマット１００のメモリアドレス（ＭＡ）及びエントリアドレス（ＥＡ）は８ｂｉｔの値である。また，検索メモリマット１００は，１８個の分割メモリ１１０ａ，１１０ｂ，…１１０ｍに区分されている。そこで，分割部２２０は，１４４ｂｉｔのキーデータ（ＫＤ）を，８ｂｉｔずつ，１８個の分割データへと分割する。このため，各分割データは，８ｂｉｔの値となる。図４に示した例において，キーデータ（ＫＤ）は，“００”“０１”“０２”“０３”“０４”“０５”“０６”“０７”“０８”“０９”“０Ａ”“０Ｂ”“０Ｃ”“０Ｄ”“０Ｅ”“０Ｆ”“１０”“１１”という１８個の分割データに分割される。
【００６３】
その後，書込部２３０は，分割部２２０によって生成された分割データを，分割メモリ１１０ａ〜１１０ｍに割り当てて，エントリアドレス（ＥＡ）を書き込んでいく。図４に示されるように，まず，書込部２３０は，１番目の分割データ“００”を１番目の分割メモリ１１０ａに割り当てる。１番目の分割メモリ１１０ａは，“００”〜“ＦＦ”の値を持つ８ｂｉｔのメモリアドレス（ＭＡ）を有している。ここで，書込部２３０は，１番目の分割データ“００”を参照して１番目の分割メモリ１１０ａのメモリアドレス（ＭＡ）“００”を指定し，このメモリアドレス“００”によって特定されるメモリ空間（Ｄ）にアクセスする。そして，書込部２３０は，メモリアドレス“００”によって特定されるメモリ空間（Ｄ）に対し，１番目の分割データ“００”に対応するエントリアドレス（ＥＡ）“００”を書き込む。このような書込処理を，書込部２３０は，２番目〜１８番目の分割データについても同様にして行う。例えば，書込部２３０は，２番目の分割データ“０１”を２番目の分割メモリ１１０ｂに割り当てて，２番目の分割データ“０１”を参照して２番目の分割メモリ１１０ｂのメモリアドレス（ＭＡ）“０１”を指定し，このメモリアドレス“０１”によって特定されるメモリ空間（Ｄ）に対し，２番目の分割データ“０１”に対応するエントリアドレス（ＥＡ）“００”を書き込む。また，例えば，書込部２３０は，１８番目の分割データ“１１”を１８番目の分割メモリ１１０ｍに割り当てて，１８番目の分割データ“１１”を参照して１８番目の分割メモリ１１０ｍのメモリアドレス（ＭＡ）“１１”を指定し，このメモリアドレス“１１”によって特定されるメモリ空間（Ｄ）に対し，１８番目の分割データ“１１”に対応するエントリアドレス（ＥＡ）“００”を書き込む。このようにして，書込部２３０は，キーデータ（ＫＤ）を複数の分割データに分割した上で，検索メモリマット１００を構成する複数の分割メモリ１１０ａ，１１０ｂ…に対して，キーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）を書き込んでいく。
【００６４】
また，図４に示されるように，書込部２３０は，検索メモリマット１００に対する書込処理を終えると，書込対象としてのキーデータ（ＫＤ）（分割前の状態のキーデータ）と固有のエントリアドレス（ＥＡ）とを対応付けて，これらの値を確認用メモリ４００に書き込む。これにより，確認用メモリ４００には，エントリアドレス（ＥＡ）とキーデータ（ＫＤ）とが一対一で対応付けられて記憶されることとなる。
【００６５】
続いて，図５を参照して，書込処理において，エントリアドレス（ＥＡ）の「衝突」が生じる場合の例を説明する。本発明の半導体装置では，書込部２３０が，分割データをアドレスとして，その分割データに対応するエントリアドレス（ＥＡ）を，分割メモリ１１０ａ…に書き込む。このため，同じ分割メモリの同じメモリ空間に複数のエントリアドレス（ＥＡ）が書き込まれる可能性がある。このように，同じメモリ空間に複数のエントリアドレスが書き込まれる現象を，本願明細書では「衝突」と表現している。ここで，本発明の半導体装置は，エントリアドレス（ＥＡ）の書込処理を行うにあたり「衝突」が生じた場合に，「衝突」が発生したメモリ空間に，衝突情報（ドントケア値）を登録し，そのまま書込処理を続行する。これにより，エントリアドレスの書込処理を高速化できる。つまり，本発明は，エントリアドレス（ＥＡ）の衝突を避けるのではなく，エントリアドレスの衝突を気にせずに書込処理を行う。これにより，本発明は，書込処理／読出処理におけるアルゴリズムを簡素化し，さらには，データ検索の高速性と低消費電力性の両立を実現している。
【００６６】
図５は，衝突が発生する場合の書込処理の例を示している。図５に示した例では，図４に示したキーデータ（ＫＤ）に続いて，“００＿０２＿０２＿０３＿０４＿０５＿０６＿０７＿０８＿０９＿０Ａ＿０Ｂ＿０Ｃ＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿ＦＦ”という値のキーデータ（ＫＤ）が，半導体装置１０に入力される。書込部２３０は，まずこのキーデータ（ＫＤ）に対して，“０１”の値を持つエントリアドレス（ＥＡ）を割り当てる。
【００６７】
また，キーデータ（ＫＤ）が半導体装置１０に入力されると，分割部２２０が，このキーデータ（ＫＤ）を複数の分割データに分割する。分割部２２０は，１４４ｂｉｔのキーデータ（ＫＤ）を，８ｂｉｔずつ，１８個の分割データへと分割する。図５に示した例において，キーデータ（ＫＤ）は，“００”“０２”“０２”“０３”“０４”“０５”“０６”“０７”“０８”“０９”“０Ａ”“０Ｂ”“０Ｃ”“０Ｄ”“０Ｅ”“０Ｆ”“１０”“ＦＦ”という１８個の分割データに分割される。
【００６８】
その後，書込部２３０は，分割部２２０によって生成された分割データを，分割メモリ１１０ａ〜１１０ｍに割り当てて，エントリアドレス（ＥＡ）を書き込んでいく。図５に示されるように，まず，書込部２３０は，１番目の分割データ“００”を１番目の分割メモリ１１０ａに割り当てて，１番目の分割データ“００”を参照して１番目の分割メモリ１１０ａのメモリアドレス（ＭＡ）“００”を指定し，このメモリアドレス“００”によって特定されるメモリ空間（Ｄ）にアクセスする。そして，書込部２３０は，このメモリ空間（Ｄ）に，１番目の分割データ“００”に対応するエントリアドレス（ＥＡ）“０１”を書き込もうとする。しかしながら，このメモリアドレス“００”によって特定されるメモリ空間（Ｄ）には，すでに，他のエントリアドレス（ＥＡ）“００”が書き込まれている（図４参照）。このため，書込部２３０は，このメモリ空間（Ｄ）に，新しいエントリアドレス（ＥＡ）“０１”を書き込むことができない。このように，一つのメモリ空間に複数のエントリアドレス（ＥＡ）が書き込まれる現象が，「衝突」である。このような「衝突」が生じている場合，書込部２３０は，衝突が生じているメモリ空間（Ｄ）に，エントリアドレスの衝突を表す衝突情報（ドントケア値）を登録する。このように，書込部２３０は，１番目の分割データ“００”については，対応するメモリ空間に衝突情報を登録して，その書込処理を終える。
【００６９】
このような書込処理を，書込部２３０は，２番目〜１８番目の分割データについても同様にして行う。例えば，書込部２３０は，２番目の分割データ“０２”を２番目の分割メモリ１１０ｂに割り当てて，２番目の分割データ“０２”を参照して２番目の分割メモリ１１０ｂのメモリアドレス（ＭＡ）“０２”を指定し，このメモリアドレス“０２”によって特定されるメモリ空間（Ｄ）に対し，２番目の分割データ“０２”に対応するエントリアドレス（ＥＡ）“０１”を書き込む。２番目の分割データ“０２”に関しては，衝突が生じていないため，分割メモリに書き込むことができる。他方，例えば，書込部２３０は，３番目の分割データ“０２”を３番目の分割メモリ１１０ｃに割り当てて，３番目の分割データ“０２”を参照して３番目の分割メモリ１１０ｃのメモリアドレス（ＭＡ）“０２”を指定し，このメモリアドレス“０２”によって特定されるメモリ空間（Ｄ）に対し，３番目の分割データ“０２”に対応するエントリアドレス（ＥＡ）“０１”を書き込もうとする。しかしながら，メモリアドレス“０２”によって特定されるメモリ空間（Ｄ）には，すでに，他のエントリアドレス“００”が書き込まれている。そこで，書込部２３０は，このメモリ空間に，衝突情報（ドントケア値）を登録して，３番目の分割データ“０２”に関する書込処理を終える。このように，書込部２３０は，衝突が生じる部分については衝突情報を登録して，分割データのすべてについて書込処理を行う。このように，衝突が発生したメモリ空間については衝突情報を登録してそのまま書込処理を続行することで，エントリアドレスの書込処理を高速化することができる。
【００７０】
その後，書込部２３０は，図５に示されるように，書込対象としてのキーデータ（ＫＤ）（分割前の状態のキーデータ）と固有のエントリアドレス（ＥＡ）とを対応付けて，これらの値を確認用メモリ４００に書き込む。これにより，確認用メモリ４００には，エントリアドレス（ＥＡ）とキーデータ（ＫＤ）とが一対一で対応付けられて記憶されることとなる。
【００７１】
続いて，図６を参照して，書込処理において，エントリアドレス（ＥＡ）の「全衝突」が生じる場合の例を説明する。本発明の半導体装置１０は，上記のように，エントリアドレスが衝突したメモリ空間には，衝突情報を登録していく。しかし，一つのキーデータ（ＫＤ）から生成された複数の分割データの全てについて，衝突が生じる可能性も存在する。このような全衝突が生じる可能性は極めて低いものであるが，理論的には発生し得る。そこで，図６では，全衝突が発生した場合の対策を示している。
【００７２】
図６は，全衝突が発生する場合の書込処理の例を示している。図６に示した例では，図４及び図５に示したキーデータ（ＫＤ）に続いて，“００＿０１＿０２＿０３＿０４＿０５＿０６＿０７＿０８＿０９＿０Ａ＿０Ｂ＿０Ｃ＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿ＦＦ”という値のキーデータ（ＫＤ）が，半導体装置１０に入力される。書込部２３０は，まずこのキーデータ（ＫＤ）に対して，“０２”の値を持つエントリアドレス（ＥＡ）を割り当てる。
【００７３】
また，キーデータ（ＫＤ）が半導体装置１０に入力されると，分割部２２０が，このキーデータ（ＫＤ）を複数の分割データに分割する。分割部２２０は，１４４ｂｉｔのキーデータ（ＫＤ）を，８ｂｉｔずつ，１８個の分割データへと分割する。図６に示した例において，キーデータ（ＫＤ）は，“００”“０１”“０２”“０３”“０４”“０５”“０６”“０７”“０８”“０９”“０Ａ”“０Ｂ”“０Ｃ”“０Ｄ”“０Ｅ”“０Ｆ”“１０”“ＦＦ”という１８個の分割データに分割される。
【００７４】
その後，書込部２３０は，分割部２２０によって生成された分割データを，分割メモリ１１０ａ〜１１０ｍに割り当てて，エントリアドレス（ＥＡ）を書き込んでいく。図６に示されるように，まず，書込部２３０は，１番目の分割データ“００”を１番目の分割メモリ１１０ａに割り当てて，１番目の分割データ“００”を参照して１番目の分割メモリ１１０ａのメモリアドレス（ＭＡ）“００”を指定し，このメモリアドレス“００”によって特定されるメモリ空間（Ｄ）にアクセスして，１番目の分割データ“００”に対応するエントリアドレス（ＥＡ）“０２”を書き込もうとする。しかしながら，このメモリアドレス“００”によって特定されるメモリ空間（Ｄ）には，すでに別のエントリアドレスが書き込まれており，衝突が発生している。同様に，書込部２３０は，２番目〜１８番目の分割データについても，これらの分割データをアドレスとして，２番目〜１８番目の分割メモリ１１０ｂ〜１１０ｍのメモリ空間にアクセスする。しかし，２番目〜１８番目の分割メモリ１１０ｂ〜１１０ｍにおいても，衝突が発生している。その結果，１番目〜１８番目の分割メモリ１１０ａ〜１１０ｍの全てについて，衝突が発生していることとなる。
【００７５】
図６に示されるように，このような全衝突が生じた場合，書込部２３０は，全衝突が生じたキーデータ（ＫＤ）を，固有のエントリアドレス（ＥＡ）と対応付けて，バックアップメモリ３００に書き込む。バックアップメモリ３００は，例えば図３に示されるように，キーデータ（ＫＤ）とエントリアドレス（ＥＡ）と一対一で対応付けて記憶することのできるメモリである。バックアップメモリ３００は，例えばＳＲＡＭなどの公知のメモリによって構成することができる。このように，書込部２３０は，検索メモリマット１００に書き込むと全衝突が生じるキーデータ（ＫＤ）については，この全衝突を回避するために，検索メモリマット１００には書き込まずに，バックアップメモリ３００に書き込んでおくことが好ましい。このように，検索メモリマット１００とは別に，バックアップメモリ３００を設けておくことで，全衝突が生じたキーデータ（ＫＤ）の書込処理が簡易になるととともに，全衝突が生じたキーデータ（ＫＤ）の検索処理（読出処理）を効率的に行うことができるようになる。なお，図６に示されるように，バックアップメモリ３００に書き込まれるキーデータ（ＫＤ）は，分割部２２０によって分割される前の状態のものであることが好ましい。
【００７６】
図４及び図５を参照して説明したとおり，通常であれば，書込部２３０は，検索メモリマット１００に対する書込処理の後，キーデータ（ＫＤ）とエントリアドレス（ＥＡ）を対応付けて確認用メモリ４００に書き込む処理を行う。ただし，図６に示されるように，全衝突が生じているキーデータ（ＫＤ）は，バックアップメモリ３００に書き込まれる。この場合，バックアップメモリ３００に書き込まれたキーデータ（ＫＤ）を，改めて確認用メモリ４００に書き込む必要はない。このように，バックアップメモリ３００と確認用メモリ４００のいずれか一方にのみキーデータ（ＫＤ）が書き込まれるようにすることで，そのキーデータ（ＫＤ）を読み出す際には，そのキーデータ（ＫＤ）が書き込まれている方のメモリのみを参照すれば済むため，検索処理を高速化させることができる。
【００７７】
また，図６に示されるように，全衝突が生じた場合，確認用メモリ４００にはキーデータ（ＫＤ）が書き込まれず，本来であればキーデータ（ＫＤ）が書き込まれるべきであったメモリ空間は空（ブランク）のまま保持される。例えば，確認用メモリ４００には，エントリアドレス（ＥＡ）“０２”が登録されているものの，このエントリアドレス（ＥＡ）“０２”によって特定されるメモリ空間は，空（ブランク）の状態となっている。このため，確認用メモリ４００にアクセスして，空（ブランク）のメモリ空間を参照すれば，どのエントリアドレス（ＥＡ）に対応するキーデータ（ＫＤ）に全衝突が生じて，バックアップメモリ３００に記憶されているのかを把握することができる。つまり，確認用メモリ４００を見れば，エントリアドレス（ＥＡ）“０２”に対応するキーデータ（ＫＤ）に全衝突が生じていることを容易に把握できる。
【００７８】
続いて，図２，図３，及び図７〜図９を参照して，半導体装置１０による基本的な読出処理（検索処理）について説明を行う。ここでの読出処理とは，検索対象となるキーデータ（ＫＤ）が半導体装置１０に入力されたときに，この半導体装置１０が，検索メモリマット１００を検索して，検索対象となるキーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）を読み出す処理である。なお，マスク処理と符号化処理を含む読出処理については後ほど説明することとし，ここでは，マスク処理と符号化処理を除いた読出処理について説明を行う。
【００７９】
図２に示されるように，書込処理においては，まず，書込対象となるキーデータが，半導体装置１０に入力される。ここで，書込対象のキーデータは，図２に示されるように，制御回路２００の入力部２１０に直接入力されることとしてもよい。また，書込対象となるキーデータは，マスクレジスタ５００と符号化回路６００とを経由して，制御回路２００の入力部２１０に入力されてもよい。マスクレジスタ５００と符号化回路６００により処理については，詳しくは後述する。
【００８０】
図２及び図３に示されるように，検索対象のキーデータ（ＫＤ）が制御回路２００の入力部２１０に入力されると，この入力部２１０は，キーデータ（ＫＤ）を分割部２２０へと送出する。続いて，分割部２２０は，検索対象のキーデータ（ＫＤ）を，複数の分割データへと分割する。ここで，分割部２２０が検索対象のキーデータ（ＫＤ）を分割するときの条件（アルゴリズム）は，上述した書込対象のキーデータ（ＫＤ）を分割するときの条件（アルゴリズム）と同じである。分割部２２０によって得られた複数の分割データは，読出部２４０へと送出される。
【００８１】
読出部２４０は，複数の分割データそれぞれについて，この分割データをアドレスとして検索メモリマット１００の各分割メモリ１１０ａ，１１０ｂ…にアクセスし，分割メモリ１１０ａ，１１０ｂ…に記憶されているエントリアドレス（ＥＡ）を読み出す。ここで，読出部２４０が，分割データをアドレスとして分割メモリにアクセスする方法（アルゴリズム）は，上述した書込部２３０が分割データをアドレスとして分割メモリにアクセスする方法と同じである。つまり，まず，読出部２４０は，複数の分割データを，それぞれ１つずつ，分割メモリに割り当てる。つまり，１番目の分割データは１番目の分割メモリに割り当てられ，２番目の分割データは２番目の分割メモリに割り当てられ，同じようにして，ｋ番目の分割データはｋ番目の分割メモリに割り当てられる。ここで，各分割メモリは，メモリアドレス（ＭＡ）が付与されており，このメモリアドレス（ＭＡ）によってメモリ空間が特定されている。読出部２４０は，分割データを分割メモリに割り当てた後，この分割データと分割メモリのメモリアドレス（ＭＡ）とを照合して，この分割データと一致するメモリアドレス（ＭＡ）を指定する。例えば，分割データが“００”という値である場合，読出部２４０は，分割メモリの中から，“００”という値を有するメモリアドレス（ＭＡ）を指定する。また，読出部２４０は，分割データに一致するメモリアドレス（ＭＡ）によって特定されるメモリ空間にアクセスする。そして，読出部２４０は，アクセスしたメモリ空間に記憶されているエントリアドレス（ＥＡ）を読み出していく。このように，読出部２４０は，分割データをアドレスとして，メモリアドレス（ＭＡ）によって特定されるメモリ空間にアクセスし，アクセスしたメモリ空間に記憶されているエントリアドレス（ＥＡ）を読みだす。このように，読出部２４０は，基本的に書込部２３０と同じ手順でメモリ空間にアクセスして，そこに記憶されているエントリアドレス（ＥＡ）を読み出すものである。
【００８２】
次に，図７〜図９を参照して，読出部２４０による読出処理について，具体例を挙げて説明する。
【００８３】
まず，図７は，基本的な読出処理の例を示している。図７に示した例では，“００＿０２＿０２＿０３＿０４＿０５＿０６＿０７＿０８＿０９＿０Ａ＿０Ｂ＿０Ｃ＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿ＦＦ”という値のキーデータ（ＫＤ）が，検索対象として，半導体装置１０に入力される。検索対象のキーデータ（ＫＤ）が半導体装置１０に入力されると，分割部２２０が，このキーデータ（ＫＤ）を複数の分割データに分割する。図７に示された例において，分割部２２０は，１４４ｂｉｔのキーデータ（ＫＤ）を，８ｂｉｔずつ，１８個の分割データへと分割する。このため，各分割データは，８ｂｉｔの値となる。図７に示した例において，キーデータ（ＫＤ）は，“００”“０２”“０２”“０３”“０４”“０５”“０６”“０７”“０８”“０９”“０Ａ”“０Ｂ”“０Ｃ”“０Ｄ”“０Ｅ”“０Ｆ”“１０”“ＦＦ”という１８個の分割データに分割される。
【００８４】
その後，読出部２４０は，分割部２２０によって生成された分割データをアドレスとして分割メモリ１１０ａ〜１１０ｍにアクセスし，エントリアドレス（ＥＡ）を読み出していく。図７に示されるように，まず，読出部２４０は，１番目の分割データ“００”を１番目の分割メモリ１１０ａに割り当てて，１番目の分割データ“００”を参照して１番目の分割メモリ１１０ａのメモリアドレス（ＭＡ）“００”を指定し，このメモリアドレス（ＭＡ）“００”によって特定されるメモリ空間（Ｄ）にアクセスする。しかしながら，１番目の分割メモリ１１０ａにおいて，メモリアドレス（ＭＡ）“００”によって特定されるメモリ空間（Ｄ）には，衝突情報（ドントケア値）が登録されている。このような場合に，読出部２４０は，１番目の分割メモリ１１０ａからはエントリアドレス（ＥＡ）を読み出さずに，ドントケア（配慮しないもの）として処理する。
【００８５】
次に，読出部２４０は，２番目の分割データ“０２”を２番目の分割メモリ１１０ｂに割り当てて，２番目の分割データ“０２”を参照して２番目の分割メモリ１１０ｂのメモリアドレス（ＭＡ）“０２”を指定し，このメモリアドレス（ＭＡ）“０２”によって特定されるメモリ空間（Ｄ）にアクセスする。このアクセスしたメモリ空間（Ｄ）には，衝突情報は登録されておらず，エントリアドレス“０１”のみが記憶されている。そこで，読出部２４０は，このメモリ空間（Ｄ）からエントリアドレス“０１”を読み出す。このような書込処理を，書込部２３０は，３番目〜１８番目の分割データについても同様にして行う。例えば，読出部２４０は，３番目の分割データ“０２”をアドレスとして，３番目の分割メモリ１１０ｃのメモリ空間にアクセスするが，このメモリ空間には衝突情報が登録されているため，ドントケアとして処理する。また，読出部２４０は，１８番目の分割データ“ＦＦ”をアドレスとして，１８番目の分割メモリ１１０ｍのメモリ空間にアクセスすると，このメモリ空間からエントリアドレス“０１”を読み出すことができる。
【００８６】
読出部２４０は，１つのキーデータ（ＫＤ）から分割された複数の分割データのそれぞれについて，上記した読出処理を行う。ここで，１つキーデータ（ＫＤ）に基づいて読み出されたエントリアドレス（ＥＡ）の値が一致する場合，読出部２４０は，その読み出したエントリアドレス（ＥＡ）を有効なものと判断する。他方，１つキーデータ（ＫＤ）に基づいて読み出されたエントリアドレス（ＥＡ）の値に不一致がある場合，読出部２４０は，その読み出したエントリアドレス（ＥＡ）を無効なものと判断する。つまり，読出部２４０は，１つのキーデータ（ＫＤ）に関する読出処理において，１種類のエントリアドレス（ＥＡ）のみが読み出された場合を有効とし，２種類以上のエントリアドレス（ＥＡ）が読み出された場合を無効とする。図７に示された例においては，検索対象のキーデータ（ＫＤ）を分割して読出処理を行ったところ，ドンドケアとして処理されたものを除き，各分割メモリから“０１”という共通の値のエントリアドレス（ＥＡ）が読み出されている。このように，読み出されたエントリアドレス（ＥＡ）の値は同じ“０１”であり，すべて一致している。このため，図７の例において，読出部２４０は，エントリアドレス（ＥＡ）“０１”を有効な値であると判断することができる。
【００８７】
また，読出部２４０が有効な値としてのエントリアドレス（ＥＡ）を読み出した場合，そのエントリアドレス（ＥＡ）は，確認部２５０へと送出される（図２参照）。例えば，図７の例において，エントリアドレス（ＥＡ）“０１”を有効な値であると判断できるため，このエントリアドレス（ＥＡ）“０１”が，確認部２５０へと送出される。確認部２５０は，読出部２４０によって有効と判断されたエントリアドレス（ＥＡ）に基づいて，確認用メモリ４００にアクセスする。確認用メモリ４００には，上述したとおり，エントリアドレス（ＥＡ）に対応づけてキーデータ（ＫＤ）が記憶されている。ここで，確認部２５０は，エントリアドレス（ＥＡ）と対応付けられているキーデータ（ＫＤ）を確認用メモリ４００から読み出す。図７に示された例において，確認用メモリ４００からは，エントリアドレス（ＥＡ）“０１”に対応付けられた“００＿０２＿０２＿０３＿０４＿０５＿０６＿０７＿０８＿０９＿０Ａ＿０Ｂ＿０Ｃ＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿ＦＦ”という値のキーデータ（ＫＤ）が読み出される。ここで，確認部２５０は，確認用メモリ４００から読み出されたキーデータ（ＫＤ）と半導体装置１０に入力されたキーデータ（ＫＤ）とを比較する。そして，確認部２５０は，その比較結果を出力する。比較結果に関する情報としては，例えば，比較対象とされた２つのキーデータ（ＫＤ）が一致又は不一致であるという情報となる。図７に示された例において，確認部２５０（比較器）において比較されたキーデータ（ＫＤ）は，互いに同じ値である。従って，確認部２５０は，キーデータ（ＫＤ）が一致する旨の情報（一致情報）を出力することができる。
【００８８】
図２及び図３に示されるように，読出部２４０によって有効であると判断されたエントリアドレス（ＥＡ）と，確認部２５０による確認情報（一致又は不一致の情報）は，出力部２６０へと送出される（図２参照）。出力部２６０は，外部回路に接続されている。このため，出力部２６０を介して，エントリアドレス（ＥＡ）と確認情報が外部回路へと出力される。このように，出力部２６０は，半導体装置１０の出力インターフェースとして機能する。
【００８９】
次に，図８は，読出部２４０によって読み出されたエントリアドレス（ＥＡ）の値が不一致であった場合の例を示している。図８に示した例において，読出部２４０は，２番目の分割データ“０１”をアドレスとして，２番目の分割メモリ１１０ｂのメモリ空間にアクセスしたところ，このメモリ空間からエントリアドレス“００”を読み出すことができた。他方，読出部２４０は，１８番目の分割データ“ＦＦ”をアドレスとして，１８番目の分割メモリ１１０ｍのメモリ空間にアクセスしたところ，このメモリ空間からエントリアドレス“０１”を読み出すことができた。しかしながら，読出部２４０が２番目の分割メモリ１１０ｂから読み出したエントリアドレス“００”と，１８番目の分割メモリ１１０ｍから読み出したエントリアドレス“０１”の値との間には，不一致が発生している。このため，読出部２４０は，入力されたキーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）を一意に特定することができない。このように，読み出したエントリアドレス（ＥＡ）に不一致が発生している場合，検索メモリマット１００には，入力されたキーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）が書き込まれていないものと判断できる。従って，読出部２４０は，これらの読み出したエントリアドレス（ＥＡ）を無効と判断する。
【００９０】
一方，図６を参照して説明したとおり，本発明の半導体装置１０では，キーデータ（ＫＤ）の書込処理時において，エントリアドレス（ＥＡ）の全衝突が生じている場合には，検索メモリマット１００には書き込まずに，キーデータ（ＫＤ）をバックアップメモリ３００に書き込むこととしている。このため，図８に示されるように，読出部２４０によって読み出されたエントリアドレス（ＥＡ）に不一致が生じており，エントリアドレス（ＥＡ）が検索メモリマット１００に書き込まれていないと判断できる場合であっても，キーデータ（ＫＤ）がバックアップメモリ３００に記憶されている可能性がある。そこで，図８に示されるように，読出部２４０は，検索対象として入力されたキーデータ（ＫＤ）に基づいて，バックアップメモリ３００に記憶されている情報を検索する。バックアップメモリ３００には，上述したとおり，キーデータ（ＫＤ）とエントリアドレス（ＥＡ）が対応付けて記憶されている。このため，読出部２４０は，バックアップメモリ３００内を検索して，検索対象のキーデータ（ＫＤ）と同じキーデータ（ＫＤ）を発見したときには，そのキーデータ（ＫＤ）に対応付けられているエントリアドレス（ＥＡ）を読み出して出力する。他方，読出部２４０は，バックアップメモリ３００内を検索しても，検索対象のキーデータ（ＫＤ）と同じキーデータ（ＫＤ）を発見できなかったときには，例えば“検索情報なし（一致情報なし）”との情報を出力して，検索処理を終了する。図８に示した例では，検索対象のキーデータ（ＫＤ）に基づいてバックアップメモリ３００を検索したところ，一致するキーデータ（ＫＤ）が記憶されていたため，これに対応するエントリアドレス（ＥＡ）“０２”が出力されている。
【００９１】
続いて，図９は，読出部２４０による読出処理がすべてドントケアとして処理された場合の例を示している。図９に示されるように，半導体装置１０に検索対象としてのキーデータ（ＫＤ）が入力されると，分割部２２０は，このキーデータ（ＫＤ）を複数の分割データへと分割する。また，読出部２４０は，各分割データをアドレスとして，各分割メモリ１１０ａ…１１０ｍにアクセスし，各分割メモリのメモリ空間からエントリアドレス（ＥＡ）を読み出そうとする。しかし，図９に示した例では，読出部２４０がアクセスしたメモリ空間の全てに衝突情報が登録されている。このため，読出部２４０は，すべての分割データについて，ドントケアとして処理している。その結果，読出部２４０は，検索メモリマット１００から全くエントリアドレス（ＥＡ）を読み出すことができず，検索結果を得ることができない。
【００９２】
このような場合に，例えば，衝突している複数のエントリアドレス（ＥＡ）を候補として，これらの複数の候補の中から，検索対象のキーデータに対応するかどうかを一つ一つ照合する処理（いわゆる総ざらい処理）を行うことも考えられる。しかし，このような総ざらい処理が発生すると，データ検索処理の遅延を招いたり，データ検索の精度が低下するという問題があると考えられていた。
【００９３】
このため，本発明の半導体装置１０では，図６を参照して説明したとおり，エントリアドレス（ＥＡ）の全衝突が生じる場合には，キーデータ（ＫＤ）をバックアップメモリ３００に退避させて書き込むこととしている。このため，図９に示されるように，読出部２４０は，アクセスしたメモリ空間の全てに衝突情報が登録されている場合には，バックアップメモリ３００を検索する処理を行う。つまり，読出部２４０は，全衝突によりエントリアドレス（ＥＡ）を検索できない場合には，検索対象として入力されたキーデータ（ＫＤ）に基づいて，バックアップメモリ３００に記憶されている情報を検索する。読出部２４０は，バックアップメモリ３００内を検索して，検索対象のキーデータ（ＫＤ）と同じキーデータ（ＫＤ）を発見したときには，そのキーデータ（ＫＤ）に対応付けられているエントリアドレス（ＥＡ）を読み出して出力する。他方，読出部２４０は，バックアップメモリ３００内を検索しても，検索対象のキーデータ（ＫＤ）と同じキーデータ（ＫＤ）を発見できなかったときには，例えば“検索情報なし（一致情報なし）”との情報を出力して，検索処理を終了する。図９に示した例では，検索対象のキーデータ（ＫＤ）に基づいてバックアップメモリ３００を検索したところ，一致するキーデータ（ＫＤ）が記憶されていたため，これに対応するエントリアドレス（ＥＡ）“０２”が出力されている。
【００９４】
このように，本発明の半導体装置は，全衝突対策として，バックアップメモリ３００を備えている。本発明の半導体装置は，バックアップメモリ３００を設けておくことで，全衝突が生じるキーデータとそのエントリアドレスとを，回避させて記憶しておくことができる。全衝突が生じたキーデータを読み出すための処理は非常に煩雑なものであったが，バックアップメモリ３００に記憶しておくことで，読出処理（検索処理）を迅速かつ効率的に行うことができる。
【００９５】
次に，図１〜３及び図１０〜図１３を参照して，半導体装置にワイルドカード機能を実装するためのマスク処理について説明する。
【００９６】
図１に示されるように，複数の半導体装置１０によって情報処理システム１が構築されている。情報処理システム１は，マスクコントローラ２０と，複数の半導体装置１０と，プライオリタイザ３０とを備えている。また，複数の半導体装置１０は，それぞれ，マスクレジスタ５００を備えている。
【００９７】
マスクコントローラ２０は，各半導体装置１０のマスクレジスタ５００に接続されている。例えば，半導体装置１０には，複数のキーデータ（ＫＤ）から構成されるテーブルデータを入力することができる。テーブルデータを入力することにより，半導体装置１０に対して複数のキーデータ（ＫＤ）を一括して書き込むことが可能となる。このような場合に，マスクコントローラ２０は，複数のキーデータ（ＫＤ）から構成されるテーブルデータを解析し，このテーブルデータから複数のマスクパターンを抽出して，各マスクパターンを半導体装置１０のマスクレジスタ５００に登録する機能を有する。また，マスクレジスタ５００は，登録されているマスクパターンに応じて，書込対象／検索対象となるキーデータ（ＫＤ）に対してマスクを付与する機能を持つ。また，プライオリタイザ３０は，各半導体装置１０の制御回路２００の出力端に接続されている。プライオリタイザ３０は，各制御回路２００から出力されたエントリアドレス（ＥＡ）が入力される。プライオリタイザ３０は，同時に複数の制御回路２００からエントリアドレス（ＥＡ）が入力されたときに，各エントリアドレス（ＥＡ）の優先度（プライオリティ）を決定し，優先度の高い順に一又は複数のエントリアドレス（ＥＡ）を選択して出力する機能を持つ。
【００９８】
まず，半導体装置１０のマスクレジスタ５００にマスクパターンを登録する初期登録処理について説明する。
【００９９】
図１０には，半導体装置１０を含む情報処理システム１に入力可能なテーブルデータの一例が示されている。例えば，本発明の情報処理システム１は，インターネットスイッチやルータを構成するＣＡＭとして利用することができる。図１０に示されるように，テーブルデータは，例えば，スイッチルータ用のＣＡＭに書き込むべき複数のキーデータ（ＫＤ）によって構成されている。例えば，各キーデータ（ＫＤ）は，「Ｓｒｃ−ＩＰ」（送信元のＩＰアドレス），「Ｄｓｔ−ＩＰ」（送信先のＩＰアドレス），「Ｐｒｏｔｏｃｏｌ」（通信に使用されるプロトコル），「Ｓｒｃ−Ｐｏｒｔ」（送信元端末のポート番号），及び「Ｄｓｔ−Ｐｏｒｔ」（送信先端末のポート番号）などに関する情報が含まれる。また，図１０において，「＊」は特定されていない情報（マスク部位）を示している。また，「Ｓｒｃ−ＩＰ」は，ＩＰｖ４に準拠した３２ビットのＩＰアドレスを示すものであるが，「／２４」や「／２８」といった表記は，上位２４ビット（又は２８ビット）がネットワークアドレスとなり，下位８ビット（又は４ビット）がホストアドレスとなることを示している。スイッチルータ用のＣＡＭにおいては，一般的に，ＩＰアドレスのうちのホストアドレスとなる下位ビットを無視（ドントケア）として検索される。このため，例えば「／２８」といったＩＰアドレスにおいては，下位４ビットをマスク部位として扱うことが一般的である。
【０１００】
図１０に示されるように，テーブルデータを構成する複数のキーデータ（ＫＤ）は，異なる部分にマスク部位を有している。ただし，各キーデータ（ＫＤ）のマスク部位は，全てのデータにおいて異なるというわけでなく，共通するマスク部位を有するキーデータ（ＫＤ）も存在している。例えば，図１０に示した例では，テーブルデータは８つのキーデータ（ＫＤ）によって構成されているが，マスク部位の共通性によってグループ分けすると，５つのグループに分類することができる。同じグループに属するキーデータ（ＫＤ）は，共通するマスク部位を有していることとなる。
【０１０１】
そこで，このようなテーブルデータをマスクコントローラ２０に入力すると，マスクコントローラ２０がテーブルデータを解析して，マスクパターンを自動的に生成し，各半導体装置１０のマスクレジスタ５００に登録する。つまり，図１０に示されるように，マスクコントローラ２０は，テーブルデータ入力部２１と，マスクパターン生成部２２と，マスクパターン登録部２３を備えている。これらの要素は，マスクコントローラ２０の機能的ブロックである。
【０１０２】
テーブルデータ入力部２１には，半導体装置１０に書き込むことを希望する所望のテーブルデータが入力される。テーブルデータ入力部２１は，入力インターフェースとして機能する。テーブルデータ入力部２１は，入力されたテーブルデータをマスクパターン生成部２２に送出する。
【０１０３】
マスクパターン生成部２２は，入力されたテーブルデータに含まれるキーデータ（ＫＤ）のマスク部位を解析し，このマスク部位のパターンに基づいて，一又は複数のマスクパターンを生成する。まず，マスクパターン生成部２２は，テーブルデータに含まれる複数のキーデータ（ＫＤ）の中から，共通する部分にマスク部位を有するキーデータ（ＫＤ）を抽出する。このように，マスクパターン生成部２２は，マスク部位の共通性に基づいて，キーデータ（ＫＤ）を複数のグループに分類する。つまり，同じグループに属するキーデータ（ＫＤ）は，共通するマスク部位を有している。その後，各グループのマスク部位の共通性に基づいて，マスクパターンを生成する。例えば，図１０に示した例において，マスクパターンは，“ＦＦＦＦＦＦＦ０００００００００ＦＦＦＦＦＦ００００”のように表される。“Ｆ”は，１６進法における０〜Ｆまでの任意の数値が存在する部位（非マスク部位）であり，“０”は検索において無視される部位（マスク部位）を示している。このようにして，マスクパターン生成部２２は，キーデータ（ＫＤ）が属する各グループについて，マスクパターンを生成する。図１０に示された例にいて，マスクパターン１〜５までの５つのマスクパターンが生成されている。
【０１０４】
マスクパターン登録部２３は，マスクパターン生成部２２によって生成された複数のマスクパターンを，それぞれ，異なる半導体装置１０のマスクレジスタ５００に振り分けて登録する。例えば，マスクパターン生成部２２によって５つのマスクパターンが生成された場合，マスクパターン登録部２３は，５つのマスクパターンをそれぞれ異なるマスクレジスタ５００に登録する。例えば，図１０に示されるように，マスクレジスタ５００は，５つ用意される。第１のマスクレジスタ５００には，パターン１のマスクパターンが登録され，第２のマスクレジスタ５００には，パターン２のマスクパターンが登録され，第３〜第５のマスクレジスタ５００も同様に処理される。このように，複数のマスクレジスタ５００には，それぞれ異なるマスクパターンが登録されることとなる。これにより，複数の半導体装置１０のマスクレジスタ５００に対するマスクパターンの初期登録処理が完了する。
【０１０５】
続いて，マスクパターン登録済みのマスクレジスタ５００を有する半導体装置１０によって，エントリアドレス（ＥＡ）を書き込む処理，及びエントリアドレス（ＥＡ）を検索する処理について説明する。
【０１０６】
図１２は，マスクレジスタ５００を利用した書込処理の一例を示している。図１２は，１つの半導体装置１０による書込処理を示しているが，情報処理システム１に含まれる他の半導体装置１０についても同様の書込処理が行われる（図１１参照）。図１２に示した例では，“００＿０１＿０２＿０３＿０４＿０５＿０６＿０７＿０８＿０９＿０Ａ＿０Ｂ＿０Ｃ＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿１１”という値のキーデータ（ＫＤ）が，書込対象として，半導体装置１０に入力される。書込部２３０は，このキーデータ（ＫＤ）に対して，“００”の値を持つエントリアドレス（ＥＡ）を割り当てる。
【０１０７】
図１２に示されるように，書込対象のキーデータ（ＫＤ）は，所定のマスクパターンが登録されているマスクレジスタ５００に入力される。例えば，図１２に示した例において，マスクレジスタ５００には，“ＦＦ＿ＦＦ＿ＦＦ＿ＦＦ＿００＿００＿００＿００＿ＦＦ＿ＦＦ＿ＦＦ＿ＦＦ＿Ｆ０＿ＦＦ＿ＦＦ＿ＦＦ＿ＦＦ＿Ｆ０”というマスクパターンが登録されている。マスクレジスタ５００は，このマスクパターンに応じて，書込対象のキーデータ（ＫＤ）に対してマスクを付与する。例えば，“Ｆ”は，１６進法における０〜Ｆまでの任意の数値が存在する部位（非マスク部位）である。このため，マスクレジスタ５００は，“Ｆ”の部位については，キーデータ（ＫＤ）の値を変換しない。他方，“０”は検索において無視される部位（マスク部位）である。このため，マスクレジスタ５００は，“０”の部位については，キーデータ（ＫＤ）の値を全て“０”に変換する。このため，マスクレジスタ５００によって，書込対象のキーデータ（ＫＤ）の値は，“００＿０１＿０２＿０３＿０４＿０５＿０６＿０７＿０８＿０９＿０Ａ＿０Ｂ＿０Ｃ＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿１１”から，“００＿０１＿０２＿０３＿００＿００＿００＿００＿０８＿０９＿０Ａ＿０Ｂ＿００＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿１０”に変換される。これにより，書込処理のキーデータ（ＫＤ）にマスクが付与されたこととなる。
【０１０８】
その後，書込部２３０は，通常どおり，マスク付与後のキーデータ（ＫＤ）について，検索メモリマット１００を構成する複数の分割メモリ１１０ａ，１１０ｂ…に対して，エントリアドレス（ＥＡ）の書込処理を行う。書込処理は，図４を参照して説明したものと同じであるため詳しい説明は省略する。このように，例えば，書込対象のキーデータ（ＫＤ）を，マスクレジスタ５００に入力し，マスクレジスタ５００によって所定のマスク部位の値を全て“０”に変換する。そして，書込対象のキーデータ（ＫＤ）について，検索において無視される部位（マスク部位）を全て“０”という値に変換した上で，検索メモリマット１００に対する書込処理を行う。これにより，同じマスクレジスタ５００を通過したキーデータ（ＫＤ）は，全て同じ部位が“０”という値となる。このため，マスクが付与されたキーデータ（ＫＤ）が書き込まれると，マスク部位に対応するメモリ空間には必ず衝突情報が登録されることとなり，その読出処理においてドントケア（検索無視）として処理される。このため，マスク部位については検索対象としない，いわゆるワイルドカード検索機能を実現することができる。
【０１０９】
なお，図１２に示した例において，マスクレジスタ５００は，キーデータ（ＫＤ）のマスク部位を，全て“０”という値に変換している。ただし，マスク部位の値の変換値は“０”に限られない。“０”以外の値であっても，書込処理時に衝突が生じるように，キーデータ（ＫＤ）のマスク部位を共通した値に変換するようにすればよい。
【０１１０】
また，図１２に示されるように，書込部２３０は，マスク付与後のキーデータ（ＫＤ）の値を，エントリアドレス（ＥＡ）と対応付けて，確認用メモリ４００に書き込む。つまり，ここでは，マスクが付与される前のキーデータ（ＫＤ）ではなく，マスク付与後のキーデータ（ＫＤ）の値が，確認用メモリ４００に書き込まれる。
【０１１１】
続いて，図１３は，マスクレジスタ５００を利用した読出処理（検索処理）の一例を示している。図１３は，１つの半導体装置１０による読出処理を示しているが，情報処理システム１に含まれる他の半導体装置１０についても同様の読出処理が行われる（図１１参照）。図１３に示した例では，“００＿０１＿０２＿０３＿ＤＥ＿ＡＤ＿ＢＥ＿ＥＦ＿０８＿０９＿０Ａ＿０Ｂ＿０１＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿１Ｆ”という値のキーデータ（ＫＤ）が，検索対象として，半導体装置１０に入力される。その後，検索対象のキーデータ（ＫＤ）は，所定のマスクパターンが登録されているマスクレジスタ５００に入力される。例えば，図１２に示した例において，マスクレジスタ５００には，“ＦＦ＿ＦＦ＿ＦＦ＿ＦＦ＿００＿００＿００＿００＿ＦＦ＿ＦＦ＿ＦＦ＿ＦＦ＿Ｆ０＿ＦＦ＿ＦＦ＿ＦＦ＿ＦＦ＿Ｆ０”というマスクパターンが登録されている。マスクレジスタ５００は，このマスクパターンに応じて，検索対象のキーデータ（ＫＤ）に対してマスクを付与する。例えば，マスクレジスタ５００は，“Ｆ”の部位については，キーデータ（ＫＤ）の値を変換せず，“０”の部位については，キーデータ（ＫＤ）の値を全て“０”に変換する。このため，マスクレジスタ５００によって，検索対象のキーデータ（ＫＤ）の値は，“００＿０１＿０２＿０３＿ＤＥ＿ＡＤ＿ＢＥ＿ＥＦ＿０８＿０９＿０Ａ＿０Ｂ＿０１＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿１Ｆ”から，“００＿０１＿０２＿０３＿００＿００＿００＿００＿０８＿０９＿０Ａ＿０Ｂ＿００＿０Ｄ＿０Ｅ＿０Ｆ＿１０＿１０”に変換される。これにより，検索処理のキーデータ（ＫＤ）にマスクが付与されたこととなる。
【０１１２】
その後，読出部２４０は，通常どおり，マスク付与後のキーデータ（ＫＤ）について，検索メモリマット１００を構成する複数の分割メモリ１１０ａ，１１０ｂ…にアクセスし，エントリアドレス（ＥＡ）の読出処理を行う。読出処理（検索処理）は，図７を参照して説明したものと同じであるため詳しい説明は省略する。このように，例えば，検索対象のキーデータ（ＫＤ）を，マスクレジスタ５００に入力し，マスクレジスタ５００によって所定のマスク部位の値を全て“０”に変換する。そして，検索対象のキーデータ（ＫＤ）について，検索において無視される部位（マスク部位）を全て“０”という値に変換した上で，検索メモリマット１００に対する検索処理を行う。これにより，マスク部位については検索条件として考慮することなく，検索処理を行うことができる。例えば，図１２に示された書込対象のキーデータ（ＫＤ）（マスク付与前）と，図１３に示された検索対象のキーデータ（ＫＤ）（マスク付与前）は，値が異なっている。しかし，図１２に示されたマスク付与後のキーデータ（ＫＤ）（マスク付与前）と，図１３に示されたマスク付与後のキーデータ（ＫＤ）（マスク付与前）とは，値が同じである。このため，マスクが付与された部分を検索条件として無視することで，図１３に示されたマスク付与後のキーデータ（ＫＤ）に基づいて検索メモリマット１００を検索すれば，図１２に示された書込対象のキーデータ（ＫＤ）に対応するエントリアドレス（ＥＡ）を読みだすことができる。このため，マスク部位については検索対象としない，いわゆるワイルドカード検索機能を実現することができる。
【０１１３】
その後，図１３に示されるように，確認部２５０は，読出部２４０が読み出したエントリアドレス（ＥＡ）に基づいて確認用メモリ４００を参照し，確認用メモリ４００から，エントリアドレス（ＥＡ）に対応づけて記憶されているキーデータ（ＫＤ）を読み出す。そして，確認部２５０は，確認用メモリ４００から読み出したキーデータ（ＫＤ）と，マスク付与後の検索対象のキーデータ（ＫＤ）とを比較し，一致するか否かの情報を出力する。上述したとおり，確認用メモリ４００には，書込処理（図１２参照）において，マスク付与後の書込対象のキーデータ（ＫＤ）が記憶されている。このため，マスク付与後のキーデータ同士を比較することで，確認部２５０は，検索処理が正しく行われたか否かを確認することができる。図１３に示した例では，確認部２５０（比較器）から一致情報が出力されている。
【０１１４】
図１２及び図１３で説明した書込処理／読出処理は，複数の半導体装置１０において同時に行われる。つまり，図１１に示されるように，情報処理システム１では，同じ書込対象又は検索対象のキーデータ（ＫＤ）が，同時に，複数の半導体装置１０に対して入力される。複数の半導体装置１０は，それぞれ異なるマスクパターンが登録されたマスクレジスタ５００を有している。検索対象のキーデータ（ＫＤ）を複数の半導体装置１０に入力した場合，各半導体装置１０から得られる検索結果（エントリアドレス及び確認情報）は異なるものとなる。例えば，１つの半導体装置１０のみから検索結果が出力される場合もあるし，複数の半導体装置１０から検索結果が出力される場合もある。複数の半導体装置１０からの検索結果は，すべてプライオリタイザ３０へと入力される。
【０１１５】
図１１に示されるように，プライオリタイザ３０は，複数の半導体装置１０から検索結果が入力された場合に，その複数の検索結果の優先度を比較して，一又は複数の検索結果を選択して出力する。例えば，図１１に示した例では，第２の半導体装置１０と第４の半導体装置１０からの検索結果が，プライオリタイザ３０に入力されている。この場合，例えば，プライオリタイザ３０は，第２の半導体装置１０からの検索結果を優先して外部へと出力し，第４の半導体装置１０からの検索結果を破棄している。このため，第２の半導体装置１０の検索結果が優先されたものといえる。このように，プライオリタイザ３０は，複数の半導体装置１０に検索結果に優劣をつけるためのアルゴリズムがプログラムされており，このアルゴリズムに従って，検索結果の出力の可否を決定する。優劣のためのアルゴリズムは，任意に設定することができる。
【０１１６】
このように，ワイルドカード検索を行った場合，複数の半導体装置１０から異なる検索結果が得られる事態も想定される。この場合に，半導体装置１０の出力先にプライオリタイザ３０を設定しておくことで，例えば，１つの検索結果のみを選択し，残りの検索結果を破棄することができる。これにより，情報処理システム１から出力される検索結果（エントリアドレス）を１つのみに絞ることができ，その検索結果を受け取る外部回路において誤作動や混乱が生じることを防止できる。
【０１１７】
なお，詳しい図示は省略するが，書込対象のキーデータ（ＫＤ）に対してマスクを付与して検索メモリマット１００に書き込む際に，「全衝突」（図６参照）が生じる可能性もある。この場合，図３に示されるように，マスク付与後のキーデータ（ＫＤ）が，エントリアドレス（ＥＡ）と対応付けて，バックアップメモリ３００に書き込まれる。また，検索対象のキーデータ（ＫＤ）に対してマスクを付与して検索処理を行う際に，検索メモリマット１００から読み出されたエントリアドレス（ＥＡ）に「不一致」（図８参照）が生じたり，「全衝突」（図９参照）が生じる可能性もある。この場合，図３に示されるように，マスク付与後のキーデータ（ＫＤ）に基づいて，バックアップメモリ３００を検索する。これにより，マスク処理とバックアップメモリ３００を利用した全衝突対策処理とを併用することができる。
【０１１８】
次に，図１〜図３，図１４，及び図１５を参照して，キーデータ（ＫＤ）の符号化処理について説明する。
【０１１９】
上述したとおり，本発明の半導体装置１０は，エントリアドレス（ＥＡ）の書込処理において衝突が発生したときには，メモリ空間に衝突情報を登録することとしている。ここで，書込対象のキーデータ（ＫＤ）に偏りがあると，データの衝突頻度が高くなり，検索不能データ列が多くなるという問題が発生する。例えば，ＩＤ番号やＩＰアドレスを降順で連続的に書き込む場合のように，ほとんど同じデータが連続して同じ検索メモリマット１００に書き込まれると，データの偏りが発生する。これにより，検索メモリマット１００内において，エントリアドレスの衝突が発生する確率が高くなる。例えば，“００＿０１＿０２＿０３”というキーデータ（ＫＤ）に続けて，“００＿０１＿０２＿０４”というキーデータ（ＫＤ）が入力されたことを考えると，２つのキーデータ（ＫＤ）の値には最後の１ｂｉｔしか違いがない。このため，後者のキーデータ（ＫＤ）の書込処理を行う際には，ほとんどの値について衝突情報を登録する必要がある。このようなデータの偏りは，防ぐことが好ましい。
【０１２０】
そこで，本発明の半導体装置１０は，キーデータ（ＫＤ）を符号化するための符号化回路６００（図１〜図３等参照）を備える。図１〜図３に示されるように，書込対象／検索対象のキーデータ（ＫＤ）が半導体装置１０の制御回路２００に入力される前に，符号化回路６００によって，キーデータ（ＫＤ）を符号化する。ここにいう符号化には，キーデータの値を所定のアルゴリズムで拡散（分散）させることや，キーデータの値の順番を並び替えるような処理が含まれる。このように，ほとんど同じキーデータが続けて入力された場合であっても，これらのキーデータを符号化することにより，検索メモリマット１００に書き込まれるデータの偏りを解消することが可能となる。データの偏りが解消すれば，検索メモリマット１００内で衝突が発生する可能性を低下させることができる。その結果，正確にデータ検索を行うことのできる可能性が高まる。なお，符号化回路６００は，書込対象のキーデータ（ＫＤ）についても検索対象のキーデータ（ＫＤ）についても全く同じアルゴリズムで符号化する。これにより，書込対象のキーデータ（ＫＤ）と検索対象のキーデータ（ＫＤ）を整合させることができる。
【０１２１】
図１４は，符号化回路６００によって実行される符号化処理の一例を概念的に示している。図１４に示されるように，符号化回路６００は，書込対象／検索対象のキーデータ（１４４ｂｉｔ）を，複数の分割データ（１〜１８）に分割する。このときの分割処理は，上述した分割部２２０による処理と同じようにすればよい。その後，符号化回路６００は，複数の分割データ（１〜１８）の位置を並べ替える。このときの並べ替え処理は，一定のアルゴリズムに基づいて行われる。その後，符号化回路６００は，並べ替えられた複数の分割データの値を拡散（分散）させる。分割データの値の拡散処理は，公知の符号化アルゴリズム（暗号化アルゴリズム）に基づいて行うことができる。例えば，拡散処理を行うことで，最初に入力されたキーデータ（ＫＤ）は，ｂｉｔ数を維持したまま，異なる値に変換されることが好ましい。図１４に示された例において，最初のキーデータ（ＫＤ）と拡散処理後のデータ（拡散化データ）は，共に１４４ｂｉｔのデータであるとされている。
【０１２２】
上記のように，例えば並べ替え処理と拡散処理との組み合わせによって，符号化回路６００はキーデータ（ＫＤ）を符号化することができる。符号化されたキーデータ（拡散化データ）は，上述した制御回路２００に入力される（図１〜図３参照）。その後，図１４に示されるように，制御回路２００は，通常どおり，拡散化データを分割して，複数の分割データを生成し，各分割データをアドレスとして，検索メモリマット１００を構成する分割メモリにアクセスする。そして，制御回路２００は，アクセスした分割メモリに対してエントリアドレス（ＥＡ）を書き込む処理，又はアクセスした分割メモリからエントリアドレス（ＥＡ）を読み出す処理を行う。
【０１２３】
図１５は，符号化回路６００によって実行される符号化処理の他の例を概念的に示している。図１５に示されるように，符号化回路６００は，書込対象／検索対象のキーデータ（１４４ｂｉｔ）を複製する。例えば，図１５に示されているように，分割メモリが１８個存在する場合には，符号化回路６００は，この分割メモリの数に併せて，キーデータ（ＫＤ）を１８個複製する。複製された複数のキーデータ（ＫＤ）は同じ値を持つものである。その後，符号化回路６００は，同じ値を持つ複数のキーデータ（ＫＤ）に対して，それぞれ異なる拡散アルゴリズムに基づいた拡散処理を行う。例えば，キーデータ（ＫＤ）は１８個に複製されているため，拡散アルゴリズムも１８種類用意されている。これにより，異なる値を持つ拡散化データが得られる。このように，符号化回路６００は，１つのキーデータ（ＫＤ）から，複数（分割メモリに対応した数）の拡散化データを生成することとしてもよい。
【０１２４】
上記のように，例えば複製処理と拡散処理との組み合わせによって，符号化回路６００はキーデータ（ＫＤ）を符号化することができる。複数の拡散化データは，上述した制御回路２００に入力される（図１〜図３参照）。その後，図１５に示されるように，制御回路２００は，複数の拡散化データをそれぞれ分割して，各拡散化データから複数の分割データを生成する。また，制御回路２００は，各分割データをアドレスとして，検索メモリマット１００を構成する分割メモリにアクセスする。そして，制御回路２００は，アクセスした分割メモリに対してエントリアドレス（ＥＡ）を書き込む処理，又はアクセスした分割メモリからエントリアドレス（ＥＡ）を読み出す処理を行う。
【０１２５】
このように，符号化回路６００を設けて，キーデータ（ＫＤ）を符号化することにより，検索メモリマット１００に書き込まれるデータの偏りを解消することができる。データの偏りが解消すれば，検索メモリマット１００内で衝突が発生する可能性を低下させることができる。その結果，正確にデータ検索を行うことのできる可能性が高まる。
【０１２６】
なお，図１〜図３に示されるように，マスク処理と符号化処理を併用する場合，マスクレジスタ５００の後段に，符号化回路６００を設けることが好ましい。つまり，符号化回路６００は，マスクレジスタ５００によってマスクが付与されたキーデータ（ＫＤ）を符号化する。また，図１〜図３に示されるように，バックアップメモリ３００，マスクレジスタ５００，及び符号化回路６００を併用することも当然に可能である。
【０１２７】
続いて，図１６〜図２４を参照して，ワイルドカード検索機能を実現するための方式の他の例について説明する。
【０１２８】
図１６（ａ）は，ワイルドカード検索機能の方式例１を概念的に示している。図１６（ａ）に示された方式例１は，図１〜図１５を参照して説明した方式と同じである。図１６（ｂ）は，方式例１とは異なる方式例２を概念的に示したものである。以下では，図１７〜図２４を参照して，この図１６（ｂ）に示された方式例２について説明する。
【０１２９】
図１７（ａ）は，検索メモリに書き込むキーデータの構成の例を示している。例えば，ＴＣＡＭ（半導体装置）に入力するキーデータの構成が，図１７（ａ）のような構成を有している場合について考える。図１７（ａ）に示されるように，キーデータの構成は，以下のように構成されている。
・入力キーデータ長：３２ｂｉｔ
・入力キーデータの中のＷ／Ｃ（ワイルドカード：ｄｏｎ’ｔ  ｃａｒｅ  ｂｉｔ）となる部分：下位４ｂｉｔ（／２８）又は８ｂｉｔ（／２４）
・エントリ数：４ｋ
【０１３０】
Ｗ／Ｃ部分を，／２４又は／２８に限定して考えた場合（／３２は含まれない），少なくとも下位の４ｂｉｔは検索対象外となるため，上位２８ｂｉｔのみが検索の対象となる。ここで，Ｗ／Ｃ影響を受けない部分を「固定部分」と定義し，Ｗ／Ｃになる可能性のある部分を「Ｗ／Ｃ部分」と定義する。この定義に従うと，「Ｗ／Ｃ部分」は４ｂｉｔ，「固定部分」は２４ｂｉｔになる。この例ではエントリ数が４ｋであるため，検索メモリを構成する各分割メモリのワード長（フラグは除く）は，１２ｂｉｔになる。つまり，「固定部分」（２４ｂｉｔ）を分割メモリ（１２ｂｉｔ）に割り当てると，分割メモリ２個分になる。分割メモリの数が２個というのは衝突理論から考えると少なすぎるため，衝突が多発するという問題が発生する。この問題を解決するためには，固定部分のキーデータを拡張する必要がある。このため，固定部分のキーデータを，図１７（ｂ）に示すように拡張して，
分割メモリ６個分に相当するように，少なくても６個（７２ｂｉｔ）程度に拡張する必要がある。
【０１３１】
図１７（ｂ）は，固定部分のキーデータを拡張した例を示している。図１７（ｂ）において，拡張された固定部分（７２ｂｉｔ）は，（１）〜（６）で示されている。また，Ｗ／Ｃ部分（／２８と／２４の差分データ＋マスク情報）は，（７）で示されている。つまり，マスク部分を除いた／２４及び／２８のデータは，下記のようになる。
・／２４のキーデータは固定部分の２４ｂｉｔのみ（Ｗ／Ｃ部分はマスクされる）
・／２８のキーデータは固定部分の２４ｂｉｔ＋４ｂｉｔ（Ｗ／Ｃ部分）
【０１３２】
また，マスクデータは，／２４か／２８かを指定する部分である。（７）で示されたＷ／Ｃ部分のマスク状態を，マスクデータによって下記のように指定する。
・／２４：１１（２ｂｉｔ）
・／２８：０１（２ｂｉｔ）
・登録無し：００（２ｂｉｔ）
なお，「登録なし：００」は，／２８のみの登録時に誤って，／２４と判断することを防止するのに必要とされる。
【０１３３】
図１８（ａ）は，／２４及び／２８対応のＴＣＡＭの構成例を示している。ＴＣＡＭの実現に必要なメモリ構成は，図１８（ａ）に示されるようになり，キーデータを４ｋ×１４４ｂｉｔのブロックに収容可能である。マスク情報は，その前の４ｂｉｔをマスクするかどうかが識別でき，且つ，その前の４ｂｉｔにマスクしたデータが登録されていることが識別できればよい。このため，マスク情報は，２ｂｉｔあれば十分である。
【０１３４】
また，図１８（ｂ）は，／１６及び／１８対応のＴＣＡＭ（２０ｂｉｔ）の構成例を示している。ここで，図１８（ａ）に示した／２４及び／２８（ビット長３２ｂｉｔ）対応ＴＣＡＭの基本動作を説明するには規模が大きすぎるため，基本的な考え方は変えずに，規模を小さくした／１６及び／１８（ビット長２０ｂｉｔ）対応のＴＣＡＭを用いて基本動作と，そのＴＣＡＭの構成方法について説明する。なお，フラグを除くデータビットを２４ｂｉｔから７２ｂｉｔへと拡散する操作以外は，／２４及び／２８対応のものと，／１６及び／１８対応のものとで，同じ操作とすることができる。
【０１３５】
図１９（ａ）は，／１６及び／１８対応のＴＣＡＭ（２０ｂｉｔ）が備える確認用メモリへの登録例を示している。確認用メモリは，検索データの最終検査用のメモリである。基本的に，確認用メモリは，Ｗ／Ｃの仕様とＷ／Ｃの処理後のデータを登録する場所である。確認用メモリでは，Ｗ／Ｃの処理に無関係な部分と，Ｗ／Ｃの処理に関係する部分とに分けられる。Ｗ／Ｃの処理に無関係な部分を，ここでは「固定部分」と呼ぶ。また，Ｗ／Ｃの処理に関係する部分を，「マスク部分」と呼ぶ。／１６及び／１８の場合は，図１９（ａ）示すように，（１）〜（５）が固定部分となり，（５）及び（６）がマスク部分となる。／１６の場合には，（１）〜（４）がＷ／Ｃ処理されない固定部分となり，／１８の場合には，（１）〜（５）がＷ／Ｃ処理されない固定部分となる。（５）を，固定部分に含めるか否かは，（６）のマスクデータ（（５）をマスクするかしないかを定義した情報）で決まる。／１６及び／１８対応ＴＣＡＭにはビット長が２０ｂｉｔであるが，／１６又は／１８の何れの場合であって，下位２ｂｉｔのデータはマスクされることになる。このため，検索に係わるビットは，上位から１６ｂｉｔ又は上位から１８ｂｉｔということになる。なお，（１）〜（４）の固定データ部分については，この例では拡散によるビット数の拡張が不要な場合であるが，ビット数の拡張が必要な場合であっても，ビット数拡張前のデータを確認用メモリに登録することとなる。
【０１３６】
ここで，／１６及び／１８対応ＴＣＡＭが備える検索メモリマットへの登録方法について説明する。固定データ部分のビット数が少ない場合，衝突防止の点から，必要に応じて拡散によるビット拡張操作が必要となる。すなわち，例えば，エントリ数が４ｋであるのに対して固定データ部分のビット数が２４ｂｉｔの場合，ビット拡張を行わずに分割メモリに登録しようとすると，分割メモリの数が２となり，登録データがランダムであっても１／１４．３の確率で衝突が起き，衝突が使用上の大きな問題となる。従って，この問題を解決するには，登録データのランダム化と分割メモリ数の増大による衝突確率の大幅低減を図るために，拡散操作によるビット数の拡張が必須になる。なお，／１６及び／１８対応ＴＣＡＭでは，拡散によるビット拡張は不要としているので，原則的には（１）〜（４）のデータをそのまま検索メモリマットに登録することになる。ただし，マスク部分にＷ／Ｃが含まれるため，（１）〜（４）が必ずしもユニークになるとは限らない。つまり，（１）〜（４）部分において連続的に同じデータが登録される可能性も考えられる。このように，（１）〜（４）部分において同じデータが複数個存在すると，（１）〜（４）に全列衝突が発生し，１サイクルで検索することが出来なくなるという問題も発生する。
【０１３７】
従って，このような全列衝突を防ぐための対策が必要となる。そこで，説明する方式例では，このＷ／Ｃによる全列衝突を防ぐために，最初のデータのみ検索メモリマットに登録し，２回目以降のデータは検索メモリマットに登録しないという概念を導入する。このような概念を，ここでは「グループ登録」と称している。「グループ登録」を行う場合，グループを代表する番号が必要になる。このグループを代表する番号を，ここでは「代表番号」と称する。さらに，この代表番号には，登録した最初のキーデータのエントリアドレスを用いるものとする。このようにすれば，（１）〜（４）の同じデータを１つのグループとし，そのグループを代表番号により区別することができるようになる。
【０１３８】
図１９（ｂ）は，グループ登録の制約事項を説明するための図である。（１）〜（４）における同じ１つのグループには，登録上の制約がある。まず，基本的な制約事項として，ＣＡＭには同じデータは登録できないという制約がある。この制約によると，（１）〜（４）が同じデータの場合，本例では，（５）か（６）の何れかに違いがなければ登録できないことになる。この制約から登録できる範囲を考えると，以下のことがいえる。
・マスク１とマスク３の混在が可能。
・ただし，マスク１は（５）が０の場合のみ，マスク３は（５）が０〜３まで登録可能。
・マスク１とマスク３が混在する場合はマスク１の登録エントリ番号が小さくなければならない。
・（マスク１とマスク３が混在する場合の代表番号は必ずマスク１の番号になる）
この制約事項から，同じグループに属する登録データの数は，マスク１も含めると最大で５ということになる。ただし，マスク３が優先的に検索されるので，マスク３に登録されている（５）のデータは，マスク１の登録があったとしても，マスク1として検索されることはない。
【０１３９】
その他，「グループ登録」の導入により，検索データの中に登録しない領域が生じるため，グループ登録の数が増えるに従って衝突確率が低下するという利点がある。また，「グループ登録」は，登録時の基本的な制約事項の確認を行うため，登録前に必ず読出し確認を行うための特別な制約事項が発生しないという利点もある。なお，基本的な制約事項を確認するには，固定データ部分の検索メモリを確認するだけでよく，確認用メモリによる最終確認までは必要としない。
【０１４０】
続いて，マスクデータ部分の登録について説明する。図２０（ａ）は，マスクデータ部分の構成例を示している。図２０に示されるように，マスクデータ部分は，確認用メモリの（５）と（６）に相当する部分の登録処理を行う部分である。／１６及び／１８対応ＴＣＡＭ（２０ｂｉｔ）の例に示したように，マスクデータ部分は，確認代表番号変換メモリとコード検索メモリ（１６ｗ×２ｂｉｔ  ＳＲＡＭ）の２個からなる。
【０１４１】
代表番号変換メモリとコード変換メモリについて説明する。まず，（５）のビット数は４ｂｉｔであるが，Ｗ／Ｃが存在するため，／１６（マスク１）では（５）全ビットが検索対象外となり，／１８（マスク３）では最下位から２ｂｉｔが検索対象外になる。そこで，両者に共通する最下位からの２ｂｉｔを除いた残りの２ｂｉｔの部分を，（５）のデータとする。このように考えると，（５）の登録データは，／１６ではマスク処理後のデータである０となり，／１８では最下位からの２ｂｉｔを除いた上位２ｂｉｔのデータである０〜３となる。Ｗ／Ｃがある場合，（５）の違いにより。（１）〜（４）の全列衝突が発生する。この全列衝突避けるためには，「グループ登録」を導入する必要がある。また，グループ間の衝突を避けるため，０〜１５のエントリ内に／１８の０〜３の登録範囲に合わせて，登録領域を確保し，各グループに割り付ける。この領域の割り付けを行うためのメモリが，「代表番号変換メモリ」であり，各領域内に（５）の値を登録したメモリが，「コード変換メモリ」である。
【０１４２】
図２０（ｂ）は，代表番号変換メモリの登録方法の例を示している。図２０（ｂ）に示されるように，１６個あるエントリを４で割ると，４個の０〜３を登録できる領域を確保できる。この０〜３を登録できる４個の領域の０のエントリアドレスを，マスク３の代表番号のシフト番号とすると，エントリアドレスの０，４，８，１２が０〜３を登録できる領域を代表するシフト番号になる。このシフト番号を導入することで，どの領域に０〜３を登録するか簡単に定めることができる。例えば，図２０（ｂ）に示されるように，代表番号１にシフト番号４を登録し，シフト番号４で検索メモリのエントリアドレス４〜７に，０〜３を登録する領域に指定する。このように，０〜３を登録する領域の割り付けを行うのが，代表番号変換メモリの役目である。
【０１４３】
図２１（ａ）は，コード検索メモリの登録方法の例を示している。図２１（ａ）の図は，コード３の（５）が，０〜３の何れかの値であることを示している。前述の例（図２０（ｂ）参照）で示したように，代表番号変換メモリの代表番号が１でシフト番号４が指定されたとすると，（５）の０〜３は，図２１（ａ）に示されるように，エントリアドレス４〜７に割り付けられる。例えば，（５）が０であり，このデータのエントリアドレスが５だとすると，図２１（ａ）の切り出し部分に示されるように，４ワードメモリの０番地に，エントリアドレス５が登録される。同様に，（５）が１，２であり，それらのデータのアドレスがそれぞれ４，１２であるとすると，１番地にエントリアドレス４が登録され，２番地にエントリ番号１２が登録される。このように切り出し部分で見ると，分割メモリに登録する基本的手法と全く同じになる。ただし，この切り出し部分は，エントリ数が０〜１５の一部である。このため，エントリ数が０〜１５の中にこの切り出し部分をあてはめる必要がある。このあてはめ操作にシフト番号を用いることになる。この例では，切り出し部分をエントリアドレスの４〜７にあてはめるため，シフト番号の４を（５）の値に加算する。この様な操作を行うことで，コード検索メモリへのデータ登録を行うことができる。
【０１４４】
続いて，このような方式例のＴＣＡＭを用いた検索動作について説明する。図２１（ｂ）は，検索動作における動作１を示している。動作１は，「検索データの前処理」である。つまり，検索データの前処理では，入力された２０ｂｉｔの検索データを１８ｂｉｔ化するとともに，（１）〜（５）の割り付けを行う。検索時に入力される検索データは２０ｂｉｔである。この入力データにはＷ／Ｃが含まれており，検索の対象となるデータは／１６又は／１８である。このため，２０ｂｉｔの入力データのうち，検索の対象となるのは１８ｂｉｔ又は１６ｂｉｔであり，最下位から２ｂｉｔのデータは検索に無関係なデータとなる。このＣＡＭは，エントリが１６ワードである。このため，２０ｂｉｔの入力データを４ｂｉｔ単位で区切り，最上位からこの４ｂｉｔ単位で区切ったデータに，それぞれ（１）〜（５）の番号を割り当てると，（１）〜（４）は４ｂｉｔずつ合計１６ｂｉｔとなり，（５）は下位２ｂｉｔの構成になる。（１）〜（４）は固定部分である。他方，（５）は，／１６のときには，（５）の２ｂｉｔが全ビットマスクされて０になり，／１８のときには，そのまま２ｂｉｔのデータとして取り扱われることとなる。しかし，検索データが入力された段階では，（５）のデータが／１６であるか，それとも／１８であるかは不明である。そこで，２０ｂｉｔの入力データの最下位から２ｂｉｔを除いて，この入力データを（１）〜（５）に割り当てる操作が必要になる。この操作が，「検索データの前処理」である。
【０１４５】
図２２（ａ）は，検索動作における動作２を示している。動作２では，（１）〜（４）の固定データによるグループ（代表番号）の検索を行う。入力データの（１）〜（４）を用いて，固定部分の検索メモリを検索する。ここでの検索動作が，図２２（ａ）に示されている。
【０１４６】
図２２（ｂ）は，検索動作における動作３を示している。動作３では，（５）のマスクデータによる検索を行う。まず，入力データの（５）と読み出した代表番号とを用いて，マスク３のデータが登録されているか否かを検索する。登録データはマスク１かマスク３のどちらかであるため，マスク３であると仮定して検索を行い，マスク３に登録されていなければマスク１のデータであるという前提の検索方法を用いている。この検索方法が成立するためには，マスク１とマスク３が混在する場合には，マスク１をマスク３の前のエントリに登録する必要がある。なお，図２３（ｂ）において，代表番号変換で空白となっているところは，マスク３ではない（つまりマスク１のデータである）ということを示している。また，検索結果で空白となったところもマスク１のデータとなる。
【０１４７】
図２３（ａ）は，検索動作における動作４を示している。動作４では，動作３の検索結果を用いて確認用メモリを検索し検索入力との比較を行う。一致すればマッチ状態となり，不一致ならアンマッチとなる。図２３（ａ）において，検索順序の１と４は，検索入力データで見ると同じになる。また，マスク３（コード３）を優先して検索することから，コード３の登録データを見ると，該当番号が登録されており，検索結果はエントリ番号４と判断される。検索順序の１と４は同じグループに属しており，コード３を優先して検索するため，コード３に登録しているエントリ番号はコード１のデータとしては検索されなくなる（ロンゲストマッチになる）。
【０１４８】
図２３（ｂ）は，コード検索メモリの登録領域拡張法の一例を示している。／１６及び／１８対応ＴＣＡＭの場合，例では，エントリ数１６の中のうち，マスク３（コード３）の登録領域としては４種類しか取れない。これよりも登録領域を増やす必要が生じる場合もある。その場合の対策方法を検討すると，次の対策が考えられる。まず，対策方法１としては，マスク３（コード３）を，別々なＴＣＡＭブロックに登録することが考えられる。また，対策方法２としては，コード３のコード検索メモリの数を増やし，識別番号を付加することが考えられる。代表番号変換メモリの数を増やすことはせずに，未使用のフラグ（３ｂｉｔ）を活用して，増やしたコード検索メモリの識別を行う。例えば，０００は１個目，００１は２個目のようにし，代表番号変換メモリの変換時に，変換データが０で，フラグの００１が読み出されたら，２個目の０〜３の該当番地を検索するようにすればよい。
【０１４９】
図２４は，パイプライン動作の場合における検索動作のフローを示している。図２４は，上記した検索動作をまとめたものである。図２４に示されるように，検索動作は，第１サイクルから第４サイクルによって実行することができる。
【０１５０】
以上，本願明細書では，本発明の内容を表現するために，図面を参照しながら本発明の実施形態の説明を行った。ただし，本発明は，上記実施形態に限定されるものではなく，本願明細書に記載された事項に基づいて当業者が自明な変更形態や改良形態を包含するものである。
【符号の説明】
【０１５１】
１…情報処理システム              １０…半導体装置
２０…マスクコントローラ          ２１…テーブルデータ入力部
２２…マスクパターン生成部        ２３…マスクパターン登録部
３０…プライオリタイザ            １００…検索メモリマット
１１０…分割メモリ                ２００…制御回路
２１０…入力部                    ２２０…分割部
２３０…書込部                    ２４０…読出部
２５０…確認部                    ２６０…出力部
３００…バックアップメモリ        ４００…確認用メモリ
５００…マスクレジスタ            ６００…符号化回路
【図１】
2016219073.tif 000003
【図２】
2016219073.tif 000004
【図３】
2016219073.tif 000005
【図４】
2016219073.tif 000006
【図５】
2016219073.tif 000007
【図６】
2016219073.tif 000008
【図７】
2016219073.tif 000009
【図８】
2016219073.tif 000010
【図９】
2016219073.tif 000011
【図１０】
2016219073.tif 000012
【図１１】
2016219073.tif 000013
【図１２】
2016219073.tif 000014
【図１３】
2016219073.tif 000015
【図１４】
2016219073.tif 000016
【図１５】
2016219073.tif 000017
【図１６】
2016219073.tif 000018
【図１７】
2016219073.tif 000019
【図１８】
2016219073.tif 000020
【図１９】
2016219073.tif 000021
【図２０】
2016219073.tif 000022
【図２１】
2016219073.tif 000023
【図２２】
2016219073.tif 000024
【図２３】
2016219073.tif 000025
【図２４】
2016219073.tif 000026