JP3938124B2 - データ検索装置 - Google Patents

Description

本発明は、高速で低消費電力のデータ検索装置に関するものである。

インターネットの発展に伴って、パケットの高速経路探索やセキュリティ確保のためにあらかじめ決められたルールデータとパケットデータとの高速な検索比較が要求されている。このような要求から、高速データ検索が可能な連想メモリ（ＣＡＭ：Content Addressable Memory）が必須のデバイスとなってきている（たとえば、特許文献１参照）。

上記特許文献１には、「０」と「１」のみのデータをもつバイナリ(Binary)ＣＡＭや、これに加えて「Ｘ(Don't care)」のデータをもつターナリ(Ternary)ＣＡＭの種類、あるいはビット長の違いに応じて、格納すべきデータを異にする複数の物理バンクを有する連想メモリが開示されている。

ところで、現在主流のＣＡＭは３値ＣＡＭ（ターナリＣＡＭ）と称され、１つのデータは複数のビットデータで構成され、その各ビットは「０」と「１」と「＊（ドントケア）」の３種類を格納することができる。この格納されたデータ（ルールデータ）と外部から入力される検索データ（パケットデータ）とをビットごとに比較する。格納データのビットが「０（または１）」で、検索データの対応ビットが「０（または１）」のときはビット比較結果が一致し、検索データが「１（または０）」のときは不一致ということになる。また、「＊（ドントケア）」は、検索データが「０」であっても「１」であっても一致するということになる。この比較がデータを構成するすべてのビットに対して行われ、そのすべてが一致したとき、はじめて格納データと検索データが一致したことになる。

また、ＣＡＭに格納されるデータと外部からの検索データが複数個一致する場合が存在するので、その際に格納アドレスの小さい（あるいは大きい）順に出力するためのプライオリティ回路が存在する。通常は、この一致したデータのアドレスの一番小さいもののみが出力される構成になっている。したがって、ルールデータを作成する場合は、アドレスの小さい順に重要なルールデータを格納してゆくことになる。この一例を示したものが、図２である。

図２では簡単のために、格納ルールデータ１００は大きく４ビットデータの３つの領域（Ａ，Ｂ，Ｃ）に分かれており、そのルールデータのプライオリティ順（図中では、理解のために順番のプライオリティタグ１０２をつけているが、実際にはこのようなものは存在しない）にしたがって格納アドレス１０１の位置にそれぞれのルールデータが格納される。また、この格納ルールデータ１００の中の「＊（図中はこの記号１つで４ビットを表現している）」はその値がなんでもよいことを示している。さらに、たとえば「２−４」というのは、そのデータが「２」から「４」の領域を表現することを表している。実際には、このような範囲の指定には、格納ルールデータ１００の各ビットの値を適当な値にし、かつ複数の格納ルールデータ１００で１つのルールを表現する場合もあるが、今回簡単のために１つの格納ルールデータ１００で１つのルールが表現できるとしている。

しかしながら、従来の連想メモリは自らに格納された格納データ１つ１つに対応して比較回路を持ち、外部からの検索データとすべての格納データを一度に比較する構造を有する。そのため、きわめて高速な検索が可能となるが、すべての比較回路が同時に動くために、極めて大きな消費電力を必要とする。当然このデバイスを用いたデータ転送装置も高速なデータ転送が可能となるが、大きな消費電力が問題となっている。このような比較回路については上記特許文献１には言及されていないが、言及されていない以上、一般的な構成をとると考えられることから、同じ問題を抱えている。

たとえば、図２に示すＣＡＭはルールデータを効率的に格納し、また、外部からのデータとの検索が極めて高速に行うことができるが、その消費電力が極めて大きい。これは、すべての格納ルールデータと一度に検索データを比較するからである。また、ＣＡＭのプライオリティ回路の特性上、重要なルールほど、アドレスの小さい（または大きい）位置に格納する必要があり、外部からの検索データと一致するルールが存在するエリアをあらかじめ特定することが困難なためである。そのために、すべてのルールデータに対して一致比較を行う必要があったことから、その一致比較の実行に大きな電力を消費している。
特開２００１−２３６７９０号公報

解決しようとする問題点は、外部からの検索データとすべての格納データとを比較するため、消費電力が大きく、そのことが高速で大規模なデータ検索装置の実現を阻害していたことである。

本発明に係るデータ検索装置は、あらかじめ第１の処理重要度の順序に配列された複数のルールデータを含む第１のデータ群を新たに第２の処理重要度の順序に再配列する再配列手段と、この再配列手段により前記第２の処理重要度の順序に並べ替えられた新たな第２のデータ群を前記第２の処理重要度の順序の小さい方または大きい方から順次、複数のメモリブロックに割り当てる割り当て手段と、を有し、前記割り当て手段により割り当てられたデータを前記メモリブロックに格納する際に、その前記メモリブロックの各々に割り当てられたデータに関して、前記再配列手段により前記第１の処理重要度の順序に再々配列して格納することを特徴とする。

本発明では、好適に、前記割り当て手段により割り当てられたデータに関して、すくなくとも１つの前記メモリブロックのデータが、前記第２の処理重要度の順序においてどの範囲にあるかを示す格納データ範囲表示レジスタを有することを特徴とする。
この場合、さらに好適に、前記格納データ範囲表示レジスタと入力検索データとを比較し、比較結果にもとづいて、当該入力検索データと比較すべきデータが格納されているメモリブロックを含むメモリ領域を指定する比較指定部と、前記比較指定部の指定結果にもとづいて、前記複数のメモリブロックから、前記比較すべきデータが格納されたメモリブロックを検索時にアクティブにするブロック制御部と、を有することを特徴とする。

あるいは、上記格納データ範囲表示レジスタを有する場合、好適に、前記複数のメモリブロックの何れか１つまたは複数のメモリブロックの組み合わせを参照番号に対応させて保持しているブロック指定レジスタと、前記ブロック指定レジスタに格納された値に応じて前記メモリブロックをアクティブにするブロック制御部と、を有することを特徴とする。

本発明のデータ検索装置において、第１の処理重要度が決められた複数のルールデータを含む第１のデータ群が入力されると、前記再配列手段により、その第１のデータ群が、新たに第２の処理重要度の順序に再配列される。割り当て手段は、第２の処理重要度に並べ替えられた第２のデータ群を、第２の処理重要度の順序の小さい方（または大きい方）から順次、複数のメモリブロックに割り当てる。そして、第２のデータ群は、メモリごとに割り当てられたデータ単位で、再度、第１の処理重要度の順序に再配列され、それぞれのメモリブロックに格納される。
このような構成のデータ検索装置では、入力される検索データに応じて、どのメモリブロック内を検索すればよいかがわかる。つまり、第２の処理重要度とメモリブロックとの対応関係が格納データ範囲表示レジスタに保持されている場合、その保持内容と入力検索データを比較指定部が比較することにより、あるいは、ブロック指定レジスタの保持内容を、参照番号をもとに調べることにより、ブロック制御部がアクティブにすべきメモリブロックが特定できる。したがって、検索データと同じ内容のデータが含まれる可能性があるメモリブロックを含む１つまたは複数のメモリブロックのみを、検索時にアクティブにする制御が可能となる。そのとき、他のメモリブロックはアクティブにされない。

本発明の構成をもつデータ検索装置を構成することで、従来ＣＡＭの大きな問題点であった大きな消費電力の発生を抑えることが可能になる。これにより、ＣＡＭ本来の格納データの構成が自由に変えられ、かつ高速検索を可能とする高速・低消費電力ＣＡＭが実現できる。

［第１の実施の形態］
第１の実施の形態はデータ検索装置に関する。
本発明の実施の形態におけるデータ検索装置は、半導体メモリ集積回路、当該集積回路を搭載したモジュール、基板、あるいは、これらが筐体に収容された電子機器等で実現される。以下、本発明のデータ検索装置の要部である連想メモリ（ＣＡＭ）を中心に、実施の形態を説明する。

図１は、ＣＡＭの概略構成を示すブロック図である。同図に示すＣＡＭ１０は、複数のメモリブロック１−１，１−２，１−３，…からなるＣＡＭ部１、メモリブロックの何れかをアクティブにするブロック選択制御部２、および、検索制御部３を有する。
ブロック選択制御部２は、本発明の「比較指定部」と「ブロック制御部」との機能を有する。検索制御部３は、データ検索に必要な制御を行うメモリ周辺回路であり、とくに図示しないが、ＣＡＭセルに接続されたビット線、ビット補線、マッチ線等の各種信号線を選択し駆動する回路、書き込みや読み出し時のデータバッファ回路、電源回路等を含む。また、必要に応じて、検索データ（ＳＫ）の一部のビットを比較対象から除くためのマスク機能も検索制御部３に含まれる。さらに、検索制御部３は、第１の処理重要度の順序にしたがって入力されてきた格納ルールデータ（第１のデータ群）を、第２の処理重要度の順序（たとえば、データ値の大小の順序）にしたがって並べ替える「再配列手段」の機能を有する。検索制御部３は、この第２の処理重要度で配列されたデータ群（第２のデータ群）を、その第２の処理重要度の順位で順次、複数のメモリブロック１−１，１−２，１−３，…に割り当てる「割り当て手段」の機能も有する。なお、この「再配列手段」と「割り当て手段」を１つまたはそれぞれ独立の機能ブロックに実現してもよいし、また、「割り当て手段」の機能をブロック選択制御部２に持たせてもよい。

詳細は後述するが、ここで、ルールデータのメモリ格納時の制御を簡単に述べる。
上記「再配列手段」が第１のデータ群を並べ替えて第２のデータ群とし、上記「割り当て手段」により、第２のデータ群に対し、第２の処理重要度の順序にしたがって順次それぞれのメモリグロックに格納するデータ範囲が決められる。後述するように、そのデータ範囲とメモリブロックとの関係を示す情報は、たとえばブロック選択制御部２内の「格納データ範囲表示レジスタ」に保持される。その後、「再配列手段」は、第２のデータ群を実際のメモリブロックに書き込む際に、第２の処理重要度の順位で割り当てられたメモリブロックごとのデータ単位で、もう一度、本来の順位である第１の処理重要度に再配置し直す。そのため、検索制御部３により各メモリブロックに格納されたデータは、大きくメモリブロック間で見ると第２の処理重要度の範囲で区分けされているが、個々のメモリブロック内では第１の処理重要度で順次配列されて格納されている。

以下、このデータ配列と格納、ならびに、データ検索時の制御を詳細に説明する。最初に、第１の処理重要度にしたがって行っていた従来のデータ格納構造を説明し、その後、これとの比較で本発明の実施の形態を説明する。
図２に、従来のデータ格納構造を示す。本例では、格納ルールデータは１１個存在し、そのルールデータは各４ビットずつの３つの領域Ａ，Ｂ，Ｃに分かれている。
最もプライオリティが高いルールデータ１００（同図に示されるプライオリティタグ１０２がＰ１のもの）は、１番目のアドレスに格納されており、Ａが１１，Ｂが２−４，Ｃが３となっている。２番目のプライオリティのルールデータ１００（同図に示されるプライオリティタグ１０２がＰ２のもの）は２番目のアドレスに格納されており、Ａが０，Ｂが６，Ｃが３−５となっている。また、一番プライオリティが低いルールデータ１００（同図に示されるプライオリティタグ１０２がＰ１１のもの）は、１１番目のアドレスに配置されており、Ａが８，Ｂが２，Ｃが１０となっている。

この例でもわかるように、Ａ，Ｂ，Ｃを一連のデータとみなすと、最もプライオリティが高いルールデータ１００はその大きさが１１０２０３から１１０４０３までの範囲を表し、２番目のプライオリティのルールデータ１００は０００６０３から０００６０５の範囲を表し、１１番目のプライオリティのルールデータ１００は０８０２１０を表す。一方、この格納ルールデータと外部からの検索データを比較するわけであるが、その際、従来のＣＡＭはすべての格納ルールデータの比較回路がすべて動くことになるわけである。

このようにすべての格納ルールデータ１００に対して比較しなければならないのは、格納ルールデータ１００がある一般的な秩序（データの大小等）をもって配置されておらず、検索データＳＫと格納ルールデータ１００の関係が全くわからないためである。

そこで、本発明では、あらたに、その格納ルールデータ１００と検索データＳＫにある関係を見いだせるようにＣＡＭデータを構成し、アクセスする部分を限定することで、低消費電力化をはかるものである。

さて、一般的な秩序の代表的なものとして、データの大小がある。そこで、前述した「再配置手段」によって、これをまず大小の順番にならべ、それを４つずつのメモリブロック（以下、単に「BLOCK」と表記する）にアサインしなおしたものが、図３である。大きさの順で並べた場合、本来のルールデータ１００のプライオリティの順番は保たれていない。しかし、各BLOCKに格納されるルールデータ１００の範囲は明確になる。たとえば、
BLOCK１のデータ範囲は、「０００２０１（プライオリティタグＰ４のルールデータ）」から「０１１５３１（プライオリティタグＰ７のルールデータ）」、
BLOCK２のデータ範囲は、「０１１５０２（プライオリティタグＰ９のルールデータ）」から「０７０４３１（プライオリティタグＰ１０のルールデータ）」、
BLOCK３のデータ範囲は、「０８０２１０（プライオリティタグＰ１１のルールデータ）」から「１２０４０５（プライオリティタグＰ５のルールデータ）」、
となる。

しかし、ここでBLOCK１とBLOCK２の境界に問題が発生する。つまり、プライオリティタグＰ７のルールデータは自ら範囲をもち、「０１０８００」から「０１１５３１」までのデータを表現している。一方、プライオリティタグＰ９のルールデータは「０１１５０２」を表している。つまり、プライオリティタグＰ７のルールデータはプライオリティタグＰ９のルールデータよりも小さい場合もあるし、また大きい場合もあるわけである。

このような場合に、このルールデータをどのBLOCKのデータとして扱うべきか、ということについて大きく２つの表現方法が考えられ、そのときの各BLOCKのデータ範囲は以下のようになる。

１）分割する方法
BLOCK１にはこのプライオリティタグＰ７のルールデータの「０１１５０１」までを、BLOCK２には「０１１５０２」から「０１１５３１」までのルールデータを分解して格納した場合、BLOCK１のデータ範囲は「０００２０１」から「０１１５０１（プライオリティタグＰ７のルールデータの一部）」まで、BLOCK２のデータ範囲は「０１１５０２（プライオリティタグＰ７のルールデータの一部）」から「０７０４３１」まで、BLOCK３のデータ範囲は「０８０２１０」から「１２０４０５」までとなる。

２）分割なしの方法
BLOCK１にはこのプライオリティタグＰ７のルールデータの「０１０８００」から「０１１５３１」のすべてを格納し、BLOCK２にはプライオリティタグＰ９のルールデータの「０１１５０２」以降のルールデータを格納した場合、BLOCK１のデータ範囲は「０００２０１」から「０１１５３１」まで、BLOCK２のデータ範囲は「０１１５０２」から「０７０４３１」まで、BLOCK３のデータ範囲は「０８０２１０」から「１２０４０５」までとなる。
このときはBLOCK１とBLOCK２の間でデータの範囲が重複していることに注意をする必要がある。

まずは、上記１）に示す分割する方法の場合のルールデータ格納状態を示したものが図４である。BLOCK１に表現されているプライオリティタグＰ７のルールデータは、「０１０８００」から「０１１５０１」の範囲を表す（同図Ｐ７ＡとＰ７Ｂ）。また、BLOCK２に表現されているプライオリティタグＰ７のルールデータは、「０１１５０２」から「０１１５３１」までを表す（同図Ｐ７Ｃ）。各BLOCKのなかでは、一応本来のルールデータの本来のプライオリティにもとづいたデータ配置にしてある。

さてこの状態で、外部からの検索データとどのように一致検索されるかを説明する。図４では、本発明の「格納データ範囲表示レジスタ」の一実施態様を構成するポインタ２２Ａを有している。まず、この例ではメモリブロック（BLOCK１からBLOCK３）のデータの範囲を表すものとして、ポインタ２２ＡにおけるBLOCK２のデータトップポインタＴＰ２にはBLOCK２の最小データ「０１１５０２」、ポインタ２２ＡにおけるBLOCK３のデータトップポインタＴＰ３にはBLOCK３の最小データ「０７０２００」があらかじめ入力されている。

外部から入力される検索データ（ＳＫ）２０１の値を「０１１５０３」とする。このデータが、レンジコンパレータ(Range Comparator)２１に入力され、データトップポインタＴＰ２，ＴＰ３と比較され、その範囲が格納ルールデータのBLOCK２の範囲であることが判別される。なお、レンジコンパレータ２１は、本発明の「比較指定部」の一実施態様を構成する。

この判別結果により、ブロック制御部(BLOCK CONTROLER)２３がBLOCK２のみをアクティブにする。すると検索データ（ＳＫ）２０１を用いて、アクティブにされたメモリブロックに対し検索が開始される。このようにして従来不可能であったアクティブ化する検索領域を限定し、ＣＡＭによる高速・低消費電力検索を可能とする。

また、格納ルールデータ領域の各BLOCKへのデータのアサインの方法として、データ範囲が重なっている上記２）に示す場合に関しては、図５を参照すると、同図ではBLOCKの格納データ範囲を表示するレジスタ２２内に、BLOCKごとに２つのポインタ値、すなわちトップポインタ(Top Pointer)値ＴＰとエンドポインタ(End Pointer) 値ＥＰをもっている。BLOCK１に関しては各々ＴＰ１（０，２，１）とＥＰ１（１，１５，３１）、BLOCK２に関してはＴＰ２（１，１５，２）とＥＰ２（７，４，３１）、BLOCK３に関してはＴＰ３（８，２，１０）とＥＰ３（１２，４，５）が、それぞれトップポインタ値ＴＰとエンドポインタ値ＥＰの組み合わせとなる。

上記１）の場合と同様に、まず検索データ（ＳＫ）２０１はレンジコンパレータ２１で各BLOCKのトップポインタとエンドポインタの各値と比較される。いま、仮に検索データを「０１１５０３」とすると、検索対象領域はBLOCK１とBLOCK２ということになり、検索時にアクティブになる領域としてBLOCK１とBLOCK２が制御される。このとき一致すべきプライオリティタグＰ７のルールデータはBLOCK１に格納されているため、BLOCK１で一致が発生する。

このように、プライオリティタグＰ７のルールデータの範囲が「０１０８００」から「０１１５３１」であるため、プライオリティタグＰ９のルールデータに比べて小さい領域と大きい領域がある場合に、アドレスの小さいものを出力するような単純なＣＡＭのプライオリティエンコーダ（図示せず）を使用するためには本来のルール上プライオリティの高いものを上位（アドレスの小さい）BLOCKに配置することが重要である。また、もちろん、プライオリティエンコーダ回路を特殊なプライオリティを判断制御するように設計することも可能ではある。

上記説明ではとくに言及しなかったが、一般にはＣＡＭを半導体集積回路で構成するが、そのＩＣの内部に入れる構成は、最低でも複数のBLOCKからなるＣＡＭ部１のみでよく、必要に応じて、すなわち制御のしやすさなどの観点からメモリ周辺回路に入れるべき構成としては、たとえばブロック制御部２３をＩＣに搭載することが望ましい。いずれにしても、本実施の形態によれば、ＣＡＭ部１を構成する複数のBLOCKのうち必要なBLOCKのみがアクティブにされるので、ＣＡＭ ＩＣの消費電力を低減することが可能となる。

［第２の実施の形態］
上記第１の実施の形態では、比較指定部としてのポインタが保持しているデータの格納場所に関する情報がデータの大きさの範囲であった。
第２の実施の形態では、このデータの格納場所に関する情報として、データの大きさの範囲以外でもよい場合を例示する。

図６は、第２の実施の形態に係るデータ検索装置のブロック図である。なお、図１の全体構成図は本実施の形態でも共通する。
このデータ検索装置は、ＣＡＭ３０内に、第１の実施の形態と同様に、複数のメモリブロック(BLOCK)１−１〜１−４を有するＣＡＭ部１と、ブロック制御部、たとえばブロックコントローラ２３とを有する。ＣＡＭ部１内の各BLOCKの構成、BLOCKにデータを格納する方法、データが複数のBLOCKに含まれる場合のBLOCKの分割の仕方などは、第１の実施の形態と共通するため、ここでの説明は省略する。

本実施の形態では、ＣＡＭ３０内に、データの格納場所に関する情報の一例として、テーブル番号とブロック番号の対応関係を定義するブロック指定ブロック指定レジスタ３１を有する。このテーブル番号とブロック番号が、本発明の「参照番号」に該当する。また変換回路３２は、外部から入力されるテーブル番号をこのレジスタ内容と比較し、そのテーブル番号に対応したBLOCKの識別情報に変換する。ついで前記ブロックコントローラ２３は、このBLOCKの識別情報が示す１つまたは複数のブロックのみアクティブにする。

図７はブロック指定レジスタ３１の格納データ例として、テーブル番号とBLOCKとの対応関係を示す図表である。
同図中、「テーブル１」ではBLOCK１と２のブロック番号値が１で他は０である。これは、BLOCK１とBLOCK２のみがこのテーブル１に属することを表している。各BLOCKは基本的に１つのテーブルに属するが、図示のように、重複して複数のテーブルに属することも可能である。また、各テーブルの構成およびBLOCK数に関しても特に制限はない。

ＣＡＭ３０の外部には、入力された検索データ（ＳＫ）２０１にもとづいて、選択すべきテーブルを指定するテーブル選択制御部４を有する。テーブル選択制御部４は、テーブルポインタ(Table pointer)４０と、テーブルコンパレータ(Table comparator)４１と、テーブル制御部４２とを含む。

テーブルポインタ４０は、複数の、ここでは４つのポインタ値ＴＡ．Ｐ１〜ＴＡ．Ｐ４を保持しており、テーブルコンパレータ４１の要求に応じてこれらのポインタ保持内容をテーブルコンパレータ４１に出力する。テーブルコンパレータ４１は、入力される検索データと、読み出したポインタ保持内容とを比較し、検索データと比較すべきＣＡＭ部内の格納データが格納されているテーブル番号を指定する。テーブル制御部４２は、このテーブル番号を出力バス４４に適合した形式に変換して出力させる。

この出力バス４４から送られてきたテーブル番号は前記変換回路３２に入力される。変換回路３２は、テーブル番号とBLOCKとの定義内容を保持したブロック指定レジスタ３１を参照しながら、入力されたテーブル番号から、アクティブにすべきBLOCKを特定する。変換回路３２からのBLOCKの識別情報がブロックコントローラ２３に入力されると、このブロックコントローラ２３の制御によって、検索データと比較すべき格納データを少なくとも含む１つまたは複数のBLOCKがアクティブにされる。その後は、第１の実施の形態と同様に、データ検索が行われ、その検索結果が当該ＣＡＭ３０から出力される。

第２の実施の形態では、データ格納領域の指定をＣＡＭ外部で行うことによりＣＡＭ自体の消費電力を低減できる利点がある。また、第１の実施の形態とは観点を異にしたデータ格納領域の指定方法が可能である。

なお、本実施の形態では、第１の実施の形態と組み合わせることができる。
図８に、この変形例のブロック図を示す。
このデータ検索装置は、そのＣＡＭ３０内に、第１の実施の形態と共通する構成として、データの大きさの範囲を示す情報を保持する「格納データ範囲表示レジスタ」としてのポインタ２２（または２２Ａ）と、「比較指定部」としてのレンジコンパレータ２１とを有する。これらの機能は第１の実施の形態と共通することから、ここでの説明は省略する。この変形例では、検索データと比較すべき格納データのデータ格納領域をテーブルとレンジ（大きさの範囲）の双方から調べるため、その精度が向上し、また、テーブルで大まかなデータ格納領域を絞って、その後、レンジによりデータ格納領域を特定するなど、この制御の効率を上げることができる。

上述した第１から第２の実施の形態では、以下に述べる利点が得られる。
ＣＡＭは、例えばＳＲＡＭベースのセル構成とすることができるため高速なデータ検索が可能である。
従来のＣＡＭは、データがプライオリティ順（第１の処理重要度の順序）に格納されているのみで、データ自身から判別できる固有の順位（第２の処理重要度の順序）にもとづいて配置されていないことから、検索データと格納データの関係が全く分からない。そのため、従来のＣＡＭでは、検索データが入力されるごとにすべてのＣＡＭセルを短時間で一斉に駆動して、メモリの全領域に対し検索を行っていた。
本実施の形態では、メモリを複数のメモリブロックに分け、原則的には１つのメモリブロックのみを、あるいは、１ブロックが数キロバイトのデータを保持する通常のメモリブロックの規模から言うと確率的に少ないが、場合によっては２つのメモリブロックを駆動する。そのため、メモリ容量が大きく、ブロック数が多いほど、消費電力の低減効果が大きい。
ところで、例えばサーバー側や中継用のルータでは、極めて短い時間に非常に大量のパケットを処理するため消費電力が増大する。ＣＡＭチップの消費電力の増大は、チップの発熱により誤動作を引き起こし、高速性能を阻害する。これが、ＣＡＭの集積化を進めるうえでのボトルネックになっていた。本実施の形態では、ＣＡＭの消費電力を数分の１から１桁以上大幅に低減できるため、このような大規模なルータ等の性能を飛躍的に向上させることが可能となる。

なお、上述した実施の形態では、とくにブロック選択制御手段、データの再配列手段および割り当て手段の各処理が、専用あるいは既存のＣＰＵなどにおいてプログラムにより実行させる、アルゴリズムベースの実施の形態も可能である。この場合、より高速な処理が可能となる。

この消費電力データ検索装置およびそれを用いたデータ転送装置の実現は、インターネットが進歩している現代では大きな社会課題になっており、今後この傾向は全世界におよぶものであり、その工業的価値はきわめて大きいものである。

本発明は、大規模なメモリ容量のＣＡＭ、および、それを内蔵したルータなどの各種データ検索装置およびデータ転送装置の用途に広く適用できる。

第１の実施の形態のＣＡＭの概略構成を示すブロック図 第１の実施の形態のデータ格納方法の比較例として、一般的なデータ格納方法を示す図 第１の実施の形態のデータ格納方法を示す図 第１の実施の形態におけるブロック選択制御部の構成とデータ格納の例を示す図 第１の実施の形態におけるブロック選択制御部の他の構成とデータ格納の例を示す図 本発明の第２の実施のデータ検索装置のブロック図 第２の実施の形態におけるテーブル番号とブロックとの対応関係の一例を示す図表 第２の実施の形態のデータ検索装置の変形例のブロック図

符号の説明

１…データ格納部、１−１等…メモリブロック、２…ブロック選択制御部、３…検索制御部、１０…内容アドレスメモリ部（ＣＡＭ）、１１…サーチキー抽出部、１２…出力制御部、２０…データ転送装置、２１…レンジコンパレータ、２２…ポインタレジスタ、２３…ブロック制御部、１００…格納ルールデータ、２０１…検索データ（ＳＫ）

Claims (20)

1. あらかじめ第１の処理重要度の順序に配列された複数のルールデータを含む第１のデータ群を新たに第２の処理重要度の順序に再配列する再配列手段と、この再配列手段により前記第２の処理重要度の順序に並べ替えられた新たな第２のデータ群を前記第２の処理重要度の順序の小さい方または大きい方から順次、複数のメモリブロックに割り当てる割り当て手段と、を有し、
   前記割り当て手段により割り当てられたデータを前記メモリブロックに格納する際に、その前記メモリブロックの各々に割り当てられたデータに関して、前記再配列手段により前記第１の処理重要度の順序に再々配列して格納することを特徴とするデータ検索装置。
2. 前記割り当て手段により割り当てられたデータに関して、すくなくとも１つの前記メモリブロックのデータが、前記第２の処理重要度の順序においてどの範囲にあるかを示す格納データ範囲表示レジスタを有することを特徴とする請求項１に記載のデータ検索装置。
3. 前記格納データ範囲表示レジスタと入力検索データとを比較し、比較結果にもとづいて、当該入力検索データと比較すべきデータが格納されているメモリブロックを含むメモリ領域を指定する比較指定部と、
   前記比較指定部の指定結果にもとづいて、前記複数のメモリブロックから、前記比較すべきデータが格納されたメモリブロックを検索時にアクティブにするブロック制御部と、を有することを特徴とする請求項２に記載のデータ検索装置。
4. 前記複数のメモリブロックの何れか１つまたは複数のメモリブロックの組み合わせを参照番号に対応させて保持しているブロック指定レジスタと、
   前記ブロック指定レジスタに格納された値に応じて前記メモリブロックをアクティブにするブロック制御部と、を有することを特徴とする請求項２に記載のデータ検索装置。
5. 前記参照番号に対応して前記格納データ範囲表示レジスタを有することを特徴とする請求項４に記載のデータ検索装置。
6. 前記第２の処理重要度が、数の大きさに応じた処理重要度を有することを特徴とする請求項１に記載のデータ検索装置。
7. 前記第２の処理重要度が、数の大きさに応じた処理重要度を有することを特徴とする請求項２に記載のデータ検索装置。
8. 前記第２の処理重要度が、数の大きさに応じた処理重要度を有することを特徴とする請求項３に記載のデータ検索装置。
9. 前記第２の処理重要度が、数の大きさに応じた処理重要度を有することを特徴とする請求項４に記載のデータ検索装置。
10. 前記第２の処理重要度が、数の大きさに応じた処理重要度を有することを特徴とする請求項５に記載のデータ検索装置。
11. 前記複数のメモリブロックが連想メモリ素子で構成され、
    格納されたデータの前記第２の処理重要度の範囲に応じて決められる１つ又は複数のメモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項１に記載のデータ検索装置。
12. 前記複数のメモリブロックが連想メモリ素子で構成され、
    格納されたデータの前記第２の処理重要度の範囲に応じて決められる１つ又は複数のメモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項２に記載のデータ検索装置。
13. 前記複数のメモリブロックが連想メモリ素子で構成され、
    アクティブにした前記メモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項３に記載のデータ検索装置。
14. 前記複数のメモリブロックが連想メモリ素子で構成され、
    アクティブにした前記メモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項４に記載のデータ検索装置。
15. 前記複数のメモリブロックが連想メモリ素子で構成され、
    アクティブにした前記メモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項５に記載のデータ検索装置。
16. 前記複数のメモリブロックが連想メモリ素子で構成され、
    格納されたデータの前記第２の処理重要度の範囲に応じて決められる１つ又は複数のメモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項６に記載のデータ検索装置。
17. 前記複数のメモリブロックが連想メモリ素子で構成され、
    格納されたデータの前記第２の処理重要度の範囲に応じて決められる１つ又は複数のメモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項７に記載のデータ検索装置。
18. 前記複数のメモリブロックが連想メモリ素子で構成され、
    アクティブにした前記メモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項８に記載のデータ検索装置。
19. 前記複数のメモリブロックが連想メモリ素子で構成され、
    アクティブにした前記メモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項９に記載のデータ検索装置。
20. 前記複数のメモリブロックが連想メモリ素子で構成され、
    アクティブにした前記メモリブロックに対し、入力された前記検索データにもとづいて内容アドレス検索を実行させ、当該内容アドレス検索でヒットした前記メモリブロックのアドレスを出力する検索制御部を有する請求項１０に記載のデータ検索装置。

Images