"入力されたNビットN≧2の検索キーを用いて、Nビット以下の有効ビット長を有する所定の複数の検索対象データに対して検索を行ない、検索結果を出力するための半導体装置であって、複数のメモリ空間を有する記憶部を備え、前記複数のメモリ空間は、同一の有効ビット長の検索対象データごとに構成された複数のグループにそれぞれ対応し、各メモリ空間は、対応のグループに属する検索対象データの有効ビット長に等しいビット長のアドレスによって特定され、前記複数のメモリ空間の各々において、対応するグループに属する各検索対象データの有効ビット部分をアドレスとしたときに特定される領域には、各検索対象データに対応した所定のコードが予め格納され、さらに、前記複数のメモリ空間の各々を特定するアドレスの長さに等しいビット数分のデータを前記検索キーの最上位ビット側から抽出することによって複数のサブ検索キーを生成し、生成した前記複数のサブ検索キーを前記複数のメモリ空間の読出アドレスとして前記記憶部に出力するサブ検索キー生成部と、前記複数のサブ検索キーを読出アドレスとして前記複数のメモリ空間から読み出された各読出データについて、前記複数の検索対象データのいずれかに対応した所定のコードを含む有効な読出データであるか否かを判定する判定回路と、前記判定回路によって有効と判定された読出データのうち、最も空間サイズの大きいメモリ空間から読み出された読出データを選択し、選択した読出データに含まれる所定のコードを出力する選択回路とを備えた半導体装置。前記複数のメモリ空間の各々において、各アドレスによって特定される領域ごとに、前記複数の検索対象データのいずれかに対応した所定のコードが格納されている有効な領域であるか否かを示すバリッドビットがさらに格納され、前記複数のサブ検索キーを読出アドレスとして前記複数のメモリ空間から読み出された各読出データには、バリッドビットの情報が含まれ、前記判定回路は、前記各読出データに含まれるバリッドビットが有効か否かによって、前記各読出データが有効であるか否かを判定する、請求項1に記載の半導体装置。前記記憶部と前記判定回路との間に設けられ、前記複数のメモリ空間から読み出された各読出データを並行して伝送する複数本のデータバスをさらに備える、請求項1または2に記載の半導体装置。前記記憶部は、1~Nビットの各ビット長のアドレスによってそれぞれ特定されるN個のメモリ空間を有し、前記サブ検索キー生成部は、1~Nビットの各ビット長をそれぞれ有するN個のサブ検索キーを生成する、請求項1~3のいずれか1項に記載の半導体装置。前記半導体装置は、パケット交換方式のネットワーク用のルータに設けられ、前記検索キーは、前記ルータに入力されたパケットのヘッダに含まれる宛先アドレスであり、前記複数の検索対象データは、パケットの転送先の候補となる隣接ルータのアドレスに関係する情報であり、前記複数の検索対象データにそれぞれ対応する所定のコードは、前記ルータに入力されたパケットを送信する出力ポートに関係する情報である、請求項1~4のいずれか1項に記載の半導体装置。TCAMを用いた検索方法では検索キーと検索テーブルとを比較する回数は少なくなるが、TCAMデバイスを用いているために消費電力が大きくなるという欠点がある。一方、TCAMを用いない検索方法では、検索キーと検索テーブルとの比較は極めて少ない消費電力で実行できるが、検索回数が増加するためにフォワーディングに時間を要するという欠点がある。たとえば、検索テーブル内のデータを1つずつ読み出して検索キーとの比較を行なうリニア検索では、検索テーブル内のデータと検索キーとが最初に一致する場合と、最後まで一致しない場合とがあるので、平均的に検索テーブルの半分のデータに対して、データ読出しと、読出したデータと検索キーとの比較を行なう必要がある。したがって、この発明の目的は、消費電力が少なくかつ高速な検索動作が可能な半導体装置を提供することである。この発明の一実施の形態による半導体装置は、汎用メモリセル構造を用いて検索システムを構築する。汎用メモリセルにおいて、検索対象データの有効ビット長ごとにそれぞれ異なるメモリ空間を対応付ける。また、各メモリ空間専用のデータバスを介して、各メモリ空間から並行かつ独立してデータを読み出す。上記の実施の形態によれば、TCAMでなく汎用のメモリセル構造を用いて半導体装置を構成できるので、低消費電力化が実現できる。さらに、複数のメモリ空間に並行してアクセスできるので、検索動作の高速化が可能になる。以下、この発明の実施の形態について図面を参照して詳しく説明する。以下の説明では、ルータにおいてネットワークアドレスを検索する場合を例に挙げて説明するが、この発明の用途はルータに限られるものではない。なお、以下の説明において、同一または相当する部分には同一の参照符号を付して、その説明を繰返さない場合がある。[ルータの構成]図1は、この発明の実施の一形態による検索LSI5が実装されたルータ1の構成を示すブロック図である。検索LSILargeScaleIntegration5は、1または複数の半導体基板上に集積化された半導体装置として構成される。図1を参照して、ルータ1は、インターネットなど、パケット交換方式が適用されたネットワークに設けられ、たとえば、TCP/IPに従った通信が行なわれる。ルータ1は、パケット処理部2と、バッファメモリ3と、検索エンジン部4とを含む。ルータ1には、さらに、パケットが入出力されるポートP1~P4が設けられる。ルータの基本処理は、任意のポートから受信したパケットを、そのパケットのヘッダに含まれる宛先アドレスに対応したポートから出力することである。各ポートから受信したパケット図1の場合、ポートP1から受信されたパケット8Aは、一旦バッファメモリ3内に格納される。宛先アドレス情報を含むヘッダ部分は、別途、検索エンジン部4に送られる。検索エンジン部4は、検索LSI5と、検索制御部6と、対応ポートテーブル7とを含む。まず、検索LSI5は、受信パケットに含まれる宛先アドレス情報を検索キーとして、検索LSI5内に格納している隣接ルータのアドレス情報に対して最長一致検索を行なう。これによって、宛先アドレスに到達するためには、次にどの隣接ルータ次ホップのルータにパケットを転送すればよいかが判明する。検索制御部6は、検索LSI5の検索結果を受けて、対応ポートテーブル7を参照することによって、転送先の隣接ルータのアドレスに対応する出力ポートを決定する。検索エンジン部4による出力ポートの決定後、バッファメモリ3内から、先に格納されたパケットが読み出され、読み出されたパケットが、決定した出力ポートから出力される図1の場合、ポートP4からパケット8Bが出力される。パケット処理部2は、パケットの受信から送出に至る一連の動作をコントロールする。[検索LSIをTCAMで構成した場合比較例]以下、この実施の形態の比較例として、図1の検索LSI5をTCAMで構成した場合について説明する。以下の例では、説明を簡単にするために、宛先アドレスに対応する検索キーが4ビットの場合が示されているが、検索キーのビット数Nは、当然ながら4ビットには限られない。たとえば、IPv4InternetProtocolVersion4用のIPアドレスの検索に用いる場合には検索キーのビット数Nは32ビットである。インターネットと直接接続されていない、閉じたLANLocalAreaNetwork内で用いられるIPアドレスを検索する場合には、LANの規模に応じたビット数たとえば16ビットなどがIPアドレスのビット数として用いられる。図2は、この実施の形態の比較例としての検索LSI100の構成を模式的に示すブロック図である。検索LSI100は、TCAM101とプライオリティエンコーダ102とを含む。図2では、検索テーブルとなるTCAM101のメモリ空間に、6つの検索対象データが格納された状態が例示されている。ここで、は、Dontcareビットを表わし、を除くビットbitの数が有効ビット長となる。具体的に、データ[0101],[1010]の有効ビット長は4であり、データ[010],[101]の有効ビット長は3であり、データ[10]の有効ビット長は2であり、データ[0]の有効ビット長は1である。Dontcareビットがあることにより、1つの検索キーに対して複数のデータが一致する場合があるので、最長一致検索longestprefixmatchsearchが用いられる。最長一致検索は、より有効ビット長の長いデータを、検索キーに最も一致したデータとして判断する検索方法である。検索動作は、検索キー[0101]の入力により開始される。TCAM101は、検索テーブルであるメモリ空間全てを一括でチェックし、検索キー[0101]に一致した全ての検索対象データに対応するアドレス情報をプライオリティエンコーダ102に通知する。図2の場合、[0101],[010],[0]の3つのデータが、検索キー[0101]に一致したと判断され、それぞれに対応するアドレス情報[0011],[0110],[1101]がプライオリティエンコーダ102に通知される。プライオリティエンコーダ102は、優先順位が最も高い、すなわち、有効ビット長が最も長いデータ[0101]に対応するアドレス[0011]を出力する。ただし、実際上は、プライオリティエンコーダ102は、上記のように、検索キーに一致したデータのアドレス情報を入手することはできるが、各アドレス情報に対応するデータの有効ビット長を知る術がない。そこで、予めTCAM101に検索対象データを格納する際に有効ビット長が長いデータほどアドレスが若くなるようにしておく。プライオリティエンコーダ102は、より若いアドレスを優先的に出力する。図2の場合、検索LSI100は、検索結果としてアドレス[0011]を出力して、検索動作を終了する。以上により、検索キー[0101]に対して紐付けされた所定の処理を表すコード[0011]が得られたことになる。このように、TCAMは、特殊なメモリセルを使用することで、検索時に、全検索テーブル空間を一括して活性化させ、検索キーに一致するデータを探す方式である。このため、検索速度は高速であるが、極めて消費電力が大きくなる問題がある。さらに、最長一致検索を実行するためには、検索テーブルの作成時に有効ビット長の長いデータほど若いアドレスに格納する必要があり、アドレスの割当て制御が複雑になる。[検索LSIの構成本発明]図3は、図1の検索LSI5の構成を模式的に示すブロック図である。図3では、図2の比較例の場合と同様に、6つの検索対象データ[0101],[010],[0],[1010],[101],[10]に対して、入力された検索キー[0101]を用いた検索が行なわれる例が示される。そして、検索キー[0101]に一致するデータ[0101],[010],[0]のうち、最も有効ビット長の長い[0101]に対応するコード[0011]が出力される例が示される。図2の場合と同様に検索キーのビット数Nを4としているが、実際にはより多ビットの検索キーおよび検索対象データが用いられる。検索動作は、検索キー[0101]の入力によって開始される。図3を参照して、検索LSI半導体装置5は、記憶部11と、サブ検索キー生成部12と、判定回路13と、選択回路14とを含む。以下、各構成要素の構成および動作について説明する。1.記憶部記憶部11は、互いに空間サイズの異なる複数のメモリ空間を含む。通常、検索キーのビット数NN≧2に応じて、互いに空間サイズの異なる1~Nビットの各アドレス長のN個のメモリ空間が設けられる。図3では、N=4として、1~4ビット長のアドレスによってそれぞれ特定可能なメモリ空間M1~M4が設けられる。検索テーブルは、この複数のメモリ空間を用いて構築される。検索テーブルを構築するために、まず、検索対象データが有効ビット長を基準にして複数のグループに分類される。図3に示す例の場合には、有効ビット長が1のデータ[0]によって第1グループが構成され、有効ビット長が2のデータ[10]によって第2グループが構成され、有効ビット長が3のデータ[010],[101]によって第3グループが構成され、有効ビット長が4のデータ[0101],[1010]によって第4グループが構成される。記憶部11には、これらの複数のグループにそれぞれ対応する複数のメモリ空間が設けられる。各グループに属する検索対象データの有効ビット長は、対応するメモリ空間を特定するアドレスの長さに等しい。図3の場合には、上記の第1~第4のグループが、1~4ビットの各ビット長のアドレスによって特定されるメモリ空間M1~M4にそれぞれ対応する。各メモリ空間において、各検索対象データの有効ビット部分Dontcareビットを除く部分をアドレスとしたときに特定される領域には、各検索対象データに対応する所定のコードが格納される。ここで、所定のコードとは、図1のルータ1の出力ポートに関係付けられた情報であり、図2の場合にはTCAMのアドレスに相当する。具体的に説明すると、図2の検索対象データ[0101],[1010]にそれぞれ対応するアドレス[0011],[0100]が、図3では、メモリ空間M4内のアドレス[0101],[1010]によって特定される領域にそれぞれ格納される。図2の検索対象データ[010],[101]にそれぞれ対応するアドレス[0110],[1000]が、図3では、メモリ空間M3内のアドレス[010],[101]によって特定される領域にそれぞれ格納される。図2の検索対象データ[10]に対応するアドレス[1011]が、図3では、メモリ空間M2内のアドレス[10]によって特定される領域に格納される。図2の検索対象データ[0]に対応するアドレス[1101]が、図3では、メモリ空間M1内のアドレス[0]によって特定される領域に格納される。つまり、図2ではTCAM内に格納されていた隣接ルータのアドレス情報の有効ビット部分Dontcareビットを除く部分が、図3ではアドレスとして用いられ、図2ではTCAMのアドレスであったものが、図3ではメモリ空間に格納される所定のコードとして用いられることになる。なお、図3に示すように、各メモリ空間において、各アドレスによって特定される領域ごとに、所定のコードのいずれかが格納された有効な領域であるか、所定のコードがいずれも格納されていない無効な領域であるかを示すバリッドビットValidbitをさらに格納しておくのが好ましい。具体的に図3の場合、アドレス[0101],[010],[0]によって特定される領域には、それぞれデータ[0011],[0110],[1101]が格納されるとともに、バリッドビット1有効を表わすが格納される。同様に、アドレス[1010],[101],[10]によって特定される領域には、それぞれデータ[0100],[1000],[1011]が格納されるとともに、バリッドビット1が格納される。その他の領域には、バリッドビット0無効を表わすが格納される。2.サブ検索キー生成部サブ検索キー生成部12は、N個のメモリ空間の各々を特定するアドレスの長さに等しいビット数分のデータを検索キーの最上位ビット側から抽出することによって、N個のサブ検索キーを生成する。N個のサブ検索キーは、1~Nビットの各ビット長をそれぞれ有する。サブ検索キー生成部12は、生成したN個のサブ検索キーをN個のメモリ空間の読出アドレスとして記憶部11に出力する。具体的に図3の場合には、サブ検索キー生成部12は、検索キー[0101]の上位4ビット[0101]をメモリ空間M4の読出アドレスとして記憶部11に出力し、検索キーの上位3ビット[010]をメモリ空間M3の読出アドレスとして記憶部11に出力する。サブ検索キー生成部12は、さらに、検索キーの上位2ビット[01]をメモリ空間M2の読出アドレスとして記憶部11に出力し、検索キーの上位1ビット[0]をメモリ空間M1の読出アドレスとして記憶部11に出力する。メモリ空間M1~M4から読み出された読出データは、それぞれデータバスB1~B4を通って判定回路13に送信される。データバスB1~B4をそれぞれメモリ空間M1~M4専用に設けることによって、各メモリ空間からのデータの読出しを並行して独立に行なうことができる。3.判定回路判定回路13は、N個のサブ検索キーを読出アドレスとしてN個のメモリ空間からそれぞれ読み出されたN個の読出データの各々が、所定のコードを含む有効な読出データであるか否かを判定する。具体的には、判定回路13は、各読出データに含まれるバリッドビットが有効1であるか否かによって、各読出データが有効であるか否かを判定する。具体的に図3の場合、メモリ空間M1~M4からは、それぞれデータ[1/1101],[0/-],[1/0110],1/0011が読み出される。ここで、読出データはバリッドビット/所定のコード]の順に並んでいるとする。判定回路13は、メモリ空間M2から読み出されたデータに含まれるバリッドビットは0であるので、この読出データは無効であると判定する。そして、判定回路13は、有効と判定したデータ[1/1101],[1/0110],1/0011のみを選択回路14に出力する。4.選択回路選択回路14は、判定回路13によって有効と判定された読出データのうち、最も優先順位が高い、すなわち最も空間サイズの大きいメモリ空間から読み出された読出データを選択し、選択した読出データに含まれる所定のコードを出力する。図3の場合、メモリ空間M4から読み出されたデータ1/0011に含まれるコード[0011]が、検索LSI5による検索結果として出力される。以上によって、図2の場合と同様に、検索キー[0101]に対して紐付けされた所定の処理を表すコード[0011]検索結果を得ることができる。[まとめ]上記のように、この実施の形態によれば、TCAMという特殊なメモリセル構造を使用することなく、汎用メモリセル構造のみで検索システムを構築することができる。この場合、検索キーから、各メモリ空間の読出アドレスサブ検索キーが一意に定まるので、記憶部11で動作しているのは、読出アドレスによってアクセスされている領域のみである。したがって、全検索テーブル空間をチェックして、検索キーに一致する検索対象データを探すTCAMに比べて低消費電力化が実現できる。さらに、各メモリ空間専用のデータバスを介して、各メモリ空間から並行かつ独立してデータを読み出すことによって、高速検索が可能になる。検索対象データ隣接ルータのアドレス情報の有効ビット長に応じて異なるメモリ空間を対応付けることによって、各メモリ空間のサイズを有効ビット長に応じて異ならせることができる。この結果、システムの小型化が可能になる。最長一致検索の実装において、従来のTCAMを用いた検索やリニア検索の場合には、若いアドレスに格納されるデータほど有効ビット長が長くなるように検索テーブルを作成する必要があり、アドレスの割当て制御が複雑であった。これに対して、この実施の形態の場合には、検索対象データの有効ビット長に応じて異なるメモリ空間に割当てるだけでよいので、アドレスの割当て制御が簡単になる。なお、上記の実施の形態では、各メモリ空間から読出データが並行して独立に読み出される場合について説明したが、各メモリ空間からパイプライン方式で順次データが読み出されるようにしてもよい。今回開示された実施の形態はすべての点で例示であって制限的なものでないと考えられるべきである。この発明の範囲は上記した説明ではなくて請求の範囲によって示され、請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。"