(57)【要約】【課題】複数のデータがヒットした場合であっても、高スループットで検索結果を出力することができる連想メモリ装置を提供する。【解決手段】各々のワードの内部は、検索対象となるデータが記憶されるデータフィールドと、このデータフィールドに記憶された検索対象となるデータの重み付けを行うための重みデータがバイナリエンコードされた状態で記憶される重みフィールドとに分けられている。検索時には、検索対象となるデータを検索するための検索キーデータとデータフィールドに記憶された検索対象となるデータとの一致検索、および重みデータを検索するための重みキーデータと重みフィールドに記憶された重みデータとの一致検索が全てのワードで同時に行われ、検索キーデータと一致する検索対象のデータが記憶されたワードの中から、検索対象のデータの重みに従って検索結果が出力される。【選択図】図１
2004342230.tif 000002
【特許請求の範囲】
【請求項１】
複数のワードを有するＣＡＭコア部を備える連想メモリ装置であって、
各々の前記ワードの内部は、検索対象のデータが記憶されるデータフィールドと、このデータフィールドに記憶された検索対象のデータの重み付けを行うための重みデータがバイナリエンコードされた状態で記憶される重みフィールドとに分けられ、
検索時には、前記検索対象のデータを検索するための検索キーデータと前記データフィールドに記憶された検索対象のデータとの一致検索、および前記重みデータを検索するための重みキーデータと前記重みフィールドに記憶された重みデータとの一致検索が前記ワードで同時に行われ、前記検索キーデータと一致する検索対象のデータが記憶されたワードの中から、前記検索対象のデータの重みに従って検索結果が出力されることを特徴とする連想メモリ装置。
【請求項２】
前記重みフィールドのビット幅に従って、前記重みキーデータおよびこの重みキーデータを１ビット毎にマスクするマスクデータを生成する重みフィールドデータ／マスク生成回路と、重み付き検索制御回路とを備え、
前記重みフィールドデータ／マスク生成回路において、１回目の検索時に使用される前記重みキーデータは全て同じ値とされ、ｉ（１≦ｉ≦前記重みフィールドのビット幅に相当する数）回目の検索の結果、次回の検索時に使用される前記重みキーデータの上位からｉ番目のビットは、前記検索結果として、ヒットが得られた場合にはその値が保持され、ミスヒットが得られた場合にはその値が反転され、前記マスクデータは、ｉ回目の検索時には、上位からｉ個のビットがマスクなしの状態とされ、
前記重み付き検索制御回路は、前記重みフィールドデータ／マスク生成回路によって生成される重みキーデータおよびマスクデータを用い、前記重みフィールドのビット幅に相当する回数繰り返し検索処理を行うように前記ＣＡＭコア部を制御して、重みが最も重いまたは最も軽い重みデータと同じ値を持つ、最終回の検索時に使用される重みキーデータを得、この最終回の検索時に使用される重みキーデータおよび全てのビットがマスクなしの状態のマスクデータを用いて、最終回の検索処理を行うように前記ＣＡＭコア部を制御し、
前記検索結果として、前記検索キーデータと一致する検索対象のデータが記憶されたワードの中から、前記検索対象のデータの重みが最も重いものまたは最も軽いものが出力される請求項１に記載の連想メモリ装置。
【請求項３】
前記重みフィールドのビット幅を設定するための重みフィールド幅設定レジスタを備え、この重みフィールド幅設定レジスタに設定された前記重みフィールドのビット幅に従って前記重みフィールドのビット幅が可変である請求項１または２に記載の連想メモリ装置。
【請求項４】
複数の連想メモリ装置をカスケード接続して使用する場合の制御を行うカスケード信号入力回路およびカスケード信号出力回路を備え、
前記カスケード信号出力回路は、複数の連想メモリ装置がカスケード接続されて使用される場合に、自分よりも上位および下位の全ての連想メモリ装置の前記カスケード信号入力回路に供給するための、カスケード用の検索結果を出力し、
前記カスケード信号入力回路には、複数の連想メモリ装置がカスケード接続されて使用される場合に、自分よりも上位および下位の全ての連想メモリ装置の前記カスケード信号出力回路から出力されるカスケード用の検索結果が入力され、前記カスケード信号入力回路から出力される検索結果は前記重み付き検索制御回路に入力され、
前記重み付き検索制御回路は、前記検索結果として、複数の連想メモリ装置でヒットが得られた場合に、前記検索対象のデータの重みに従って検索結果が出力されるように制御する請求項１〜３のいずれかに記載の連想メモリ装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、検索キーデータと一致する検索対象のデータが記憶されたワードの中から、検索対象のデータの重みに従って検索結果を出力する連想メモリ（以下、ＣＡＭという）装置に関するものである。
【０００２】
【従来の技術】
データとして、‘０’、‘１’および‘Ｘ’（ドントケア）のいずれかの値を記憶できる３値（ターナリ）のＣＡＭセルを用いたＣＡＭでは、ワード内の任意のビットを‘Ｘ’に設定してマスクできるため、データを検索するための検索キーデータに対して、複数のデータがヒット（一致）することが多くなる。複数のデータがヒットした場合、ヒットしたデータが記憶されている複数のワードの中から、あらかじめ決定されているプライオリティ（優先順位）に従って、例えば最もアドレスの小さいものが検索結果として出力される。
【０００３】
データとして‘Ｘ’が設定されるために、複数のデータがヒットする検索としてよく知られているものの１つに、ＩＰ（インターネット・プロトコル）アドレス検索におけるロンゲスト・プレフィックス・マッチ（Ｌｏｎｇｅｓｔ  Ｐｒｅｆｉｘ  Ｍａｔｃｈ）（以下、ＬＰＭという）がある。ＬＰＭでは、データの最上位ビット側から、検索キーデータと最長一致するネットワークアドレスを持つデータが検索される。
【０００４】
ＩＰアドレスは３２ビットのデータであり、例えば１９２．１６８．０．０／１６（１０進数表現）のように、８ビットのデータ毎にピリオドで区切られて表現される。また、ＩＰアドレスは、上位ビット側のネットワークアドレスと、下位ビット側のホストアドレスとに分けられている。両者の区切り位置を表すのが‘／’の後の数値‘１６’であり、この例の場合、最上位ビットからのネットワークアドレスの長さ（プレフィックス長）は１６ビットとなる。
【０００５】
ＣＡＭを用いてＬＰＭを実現する場合、ＣＡＭの各々のワードには、例えば検索対象となるＩＰアドレスの３２ビットのデータのうち、ネットワークアドレスに対応するデータが記憶され、ホストアドレスに対応するデータは‘Ｘ’とされる。ＬＰＭでは、プレフィックス長の長いものの方がプライオリティが高いため、通常プレフィックス長の長い順にデータをソートしてアドレスの小さい順にＣＡＭ内に記憶しておき、検索が行われる。そして、ヒットした複数のワードの中から、最もアドレスの小さいものが検索結果として出力される。
【０００６】
これにより、検索結果として、検索キーデータと最長一致し、最もアドレスの小さいもの、すなわち最もプライオリティの高いものを１回の検索で出力することができる。
【０００７】
しかし、この方式では、新規なデータを登録したり、不要なデータを削除するたびにデータのソートをし直す必要があるため、検索のスループットが低下するという問題があった。
【０００８】
なお、本出願人は、特許文献１により、上記のようなデータのソートの必要ない最長一致検索装置を既に提案している。
【０００９】
特許文献１の最長一致検索装置は、ＣＡＭの複数のメモリ領域のそれぞれに、各エントリのアドレスを表すアドレスデータと各エントリのプレフィックス長を表すプレフィックスデータのペアを格納しておき、最上位ビット側から最長一致するアドレスデータが複数格納されていた場合に、これら複数のアドレスデータのうち、最長のプレフィックス長を表すプレフィックスデータとペアのアドレスデータが格納されたメモリ領域を検索するものである。
【００１０】
【特許文献１】
特開平１１−２８４６５８号公報
【００１１】
【発明が解決しようとする課題】
本発明の目的は、前記従来技術に基づく問題点を解消し、複数のデータがヒットした場合であっても、高スループットで検索結果を出力することができる連想メモリ装置を提供することにある。
【００１２】
【課題を解決するための手段】
上記目的を達成するために、本発明は、複数のワードを有するＣＡＭコア部を備える連想メモリ装置であって、
各々の前記ワードの内部は、検索対象のデータが記憶されるデータフィールドと、このデータフィールドに記憶された検索対象のデータの重み付けを行うための重みデータがバイナリエンコードされた状態で記憶される重みフィールドとに分けられ、
検索時には、前記検索対象のデータを検索するための検索キーデータと前記データフィールドに記憶された検索対象のデータとの一致検索、および前記重みデータを検索するための重みキーデータと前記重みフィールドに記憶された重みデータとの一致検索が前記ワードで同時に行われ、前記検索キーデータと一致する検索対象のデータが記憶されたワードの中から、前記検索対象のデータの重みに従って検索結果が出力されることを特徴とする連想メモリ装置を提供するものである。
【００１３】
ここで、前記ワードは３値のデータを記憶するターナリＣＡＭセルを用いて構成されるのが望ましく、特にデータフィールドを構成するセルはターナリＣＡＭセルを用いて構成されるのが望ましい。
【００１４】
更に、前記重みフィールドのビット幅に従って、前記重みキーデータおよびこの重みキーデータを１ビット毎にマスクするマスクデータを生成する重みフィールドデータ／マスク生成回路と、重み付き検索制御回路とを備え、
前記重みフィールドデータ／マスク生成回路において、１回目の検索時に使用される前記重みキーデータは全て同じ値とされ、ｉ（１≦ｉ≦前記重みフィールドのビット幅に相当する数）回目の検索の結果、次回の検索時に使用される前記重みキーデータの上位からｉ番目のビットは、前記検索結果として、ヒットが得られた場合にはその値が保持され、ミスヒットが得られた場合にはその値が反転され、前記マスクデータは、ｉ回目の検索時には、上位からｉ個のビットがマスクなしの状態とされ、
前記重み付き検索制御回路は、前記重みフィールドデータ／マスク生成回路によって生成される重みキーデータおよびマスクデータを用い、前記重みフィールドのビット幅に相当する回数繰り返し検索処理を行うように前記ＣＡＭコア部を制御して、重みが最も重いまたは最も軽い重みデータと同じ値を持つ、最終回の検索時に使用される重みキーデータを得、この最終回の検索時に使用される重みキーデータおよび全てのビットがマスクなしの状態のマスクデータを用いて、最終回の検索処理を行うように前記ＣＡＭコア部を制御し、
前記検索結果として、前記検索キーデータと一致する検索対象のデータが記憶されたワードの中から、前記検索対象のデータの重みが最も重いものまたは最も軽いものが出力されるのが好ましい。
【００１５】
また、前記重みフィールドのビット幅を設定するための重みフィールド幅設定レジスタを備え、この重みフィールド幅設定レジスタに設定された前記重みフィールドのビット幅に従って前記重みフィールドのビット幅が可変であるのが好ましい。
【００１６】
また、複数の連想メモリ装置をカスケード接続して使用する場合の制御を行うカスケード信号入力回路およびカスケード信号出力回路を備え、
前記カスケード信号出力回路は、複数の連想メモリ装置がカスケード接続されて使用される場合に、自分よりも上位および下位の全ての連想メモリ装置の前記カスケード信号入力回路に供給するための、カスケード用の検索結果を出力し、
前記カスケード信号入力回路には、複数の連想メモリ装置がカスケード接続されて使用される場合に、自分よりも上位および下位の全ての連想メモリ装置の前記カスケード信号出力回路から出力されるカスケード用の検索結果が入力され、前記カスケード信号入力回路から出力される検索結果は前記重み付き検索制御回路に入力され、
前記重み付き検索制御回路は、前記検索結果として、複数の連想メモリ装置でヒットが得られた場合に、前記検索対象のデータの重みに従って検索結果が出力されるように制御するのが好ましい。
【００１７】
【発明の実施の形態】
以下に、添付の図面に示す好適実施形態に基づいて、本発明の連想メモリ装置を詳細に説明する。
【００１８】
図１は、本発明の連想メモリ装置の一実施形態の構成概略図である。同図に示す連想メモリ（以下、ＣＡＭという）装置１０は、検索対象となる各々のデータに対して重み付けを行い、複数のデータがヒットした場合に、データの重みに従って検索結果を出力する。また、ＣＡＭ装置１０は、複数の当該ＣＡＭ装置（以下、単にデバイスともいう）がカスケード接続されて使用される場合も同様に、複数のデバイスでヒットした場合に、データの重みに従って検索結果を出力する。
【００１９】
デバイス１０は、図１に示すように、データ／コマンド入力回路１２と、ＣＡＭコア部１４と、検索結果出力回路１６と、重みフィールド幅設定レジスタ１８と、重みフィールドデータ／マスク生成回路２０と、重み付き検索制御回路２２と、カスケード信号入力回路２４と、カスケード信号出力回路２６とを備えている。
【００２０】
ＣＡＭコア部１４に記憶されるデータや検索キーデータ等のデータ、書き込みコマンドや検索コマンド等のコマンドは、データ／コマンド入力回路１２を介してデバイス１０内部へ入力される。
【００２１】
ＣＡＭコア部１４は、３値（‘０’、‘１’、‘Ｘ’）のデータを記憶できるターナリＣＡＭセルを用いて構成された複数のワード（図示省略）を備えている。更に、ＣＡＭコア部１４には通常のＣＡＭが備えるアドレスデコーダ、ビット線ドライバ等を備えている。
【００２２】
１ワードの内部は、検索対象のデータが記憶されるデータフィールドと、データフィールドに記憶されるデータの重み付けを行うための重みデータを記憶する重みフィールドとに分けられている。重みデータは、バイナリエンコードされた状態で記憶される。重みフィールドのビット幅は可変であり、重みフィールド幅設定レジスタ１８によって設定される。また、重みフィールドのビット幅に応じてデータフィールドのビット幅も可変となる。
【００２３】
図２は、１ワードが６４ビット幅の場合のワード構成を示す概略図である。図２（ａ）に示すように、重みフィールドのビット幅が８ビットに設定された場合、データフィールドは５６ビット幅となり、データフィールドのデータに対して２５６段階の重み付けを行うことができる。また、同図（ｂ）に示すように、重みフィールドのビット幅が２ビットに設定された場合、データフィールドは６２ビット幅となり、データフィールドのデータに対して４段階の重み付けを行うことができる。
【００２４】
ＣＡＭコア部１４では、データ／コマンド入力回路１２に検索コマンドおよび検索キーデータが与えられると、重み付き検索制御回路２２の制御により、検索キーデータとデータフィールドに記憶されているデータとの一致検索、および重みキーデータと重みフィールドに記憶されている重みデータとの一致検索が全てのワードで同時に行われ、検索キーデータと一致するデータが記憶されたワードの中から、データの重みに従って検索結果が出力される
【００２５】
ＣＡＭコア部１４から出力される検索結果は、検索結果出力回路１６を介してデバイス１０の外部へ出力される。また、ＣＡＭコア部１４から出力される検索結果は、重み付き検索制御回路２２にフィードバックされると共に、カスケード信号出力回路２６にも入力される。
【００２６】
前述のように、重みフィールド幅設定レジスタ１８には、重みフィールドのビット幅が設定される。この重みフィールド幅設定レジスタ１８から出力される重みフィールドのビット幅の情報は重みフィールドデータ／マスク生成回路２０に入力される。
【００２７】
重みフィールドデータ／マスク生成回路２０は、重みフィールド幅設定レジスタ１８に設定される重みフィールドのビット幅の情報に基づいて、重みデータを検索するための重みキーデータ、およびこの重みキーデータを１ビット毎にマスクするマスクデータを自動生成する。重みフィールドデータ／マスク生成回路２０で生成される重みキーデータおよびマスクデータは重み付き検索制御回路２２に入力される。
【００２８】
重み付き検索制御回路２２は、重みフィールドデータ／マスク生成回路２０によって生成される重みキーデータおよびマスクデータを使用して、本実施形態の場合、重みの最も重いデータを検索するための検索処理を行うようにＣＡＭコア部１４を制御する。
【００２９】
ここで、図３の概念図を参照して、重み付き検索を行う場合の動作を説明する。なお、ＣＡＭコア部１４の各々のワードのデータフィールドには検索対象のデータが記憶され、その重みフィールドには、データフィールドに記憶されているデータに対応する重みデータが記憶されている。また、重みフィールド幅設定レジスタ１８には、重みフィールドのビット幅として８ビットが設定されているものとする。
【００３０】
図３に示すように、まず、１回目の検索時には、重みフィールドデータ／マスク生成回路２０により、重みキーデータ＝‘１１１１１１１１’、マスクデータ＝‘０１１１１１１１’が生成される。ここで、マスクデータの‘０’はマスクなし、‘１’はマスクありを意味する。そして、重み付き検索制御回路２２の制御により、検索キーデータ、重みキーデータおよびマスクデータを用いてＣＡＭコア部１４で１回目の検索が行われる。
【００３１】
すなわち、ＣＡＭコア部１４では、検索キーデータと各々のワードのデータフィールドに記憶されているデータとの一致検索が全てのワードで同時に行われる。また、マスクデータ＝‘０１１１１１１１’によってマスクされた重みキーデータ＝‘１ＸＸＸＸＸＸＸ’、と各々のワードの重みフィールドに記憶されている重みデータとの一致検索が全てのワードで同時に行われる。すなわち、重みデータの最上位ビットのみが一致検索の対象となる。
【００３２】
その結果、検索キーデータと一致するデータが記憶されているワードの中で、重みデータの最上位ビットが‘１’であるワードが存在する場合には、検索結果としてヒット（Ｈｉｔ）が得られる。この場合、重みフィールドデータ／マスク生成回路２０により、次の検索（２回目の検索）の時に使用される重みキーデータとして、最上位ビットが‘１’のままの状態とされた重みキーデータ＝‘１１１１１１１１’が生成される。
【００３３】
これに対し、重みデータの最上位ビットが‘１’であるワードが存在しない場合には、検索結果としてミスヒット（Ｍｉｓｓ  Ｈｉｔ）が得られる。この場合、重みフィールドデータ／マスク生成回路２０により、次の検索（２回目の検索）の時に使用される重みキーデータとして、最上位ビットが‘０’の重みキーデータ＝‘０１１１１１１１’が生成される。本実施形態では、１回目の検索でヒットが得られたものとする。
【００３４】
続いて、２回目の検索時には、重みキーデータ＝‘１１１１１１１１’、マスクデータ＝‘００１１１１１１’が生成される。すなわち、重みデータの上位２ビットのみが一致検索の対象となる。
【００３５】
２回目の検索の結果、検索キーデータと一致するデータが記憶されているワードの中で、重みデータの上位から２番目のビットが‘１’であるワードが存在する場合には、検索結果としてヒット（Ｈｉｔ）が得られる。これに対し、重みデータの上位から２番目のビットが‘１’であるワードが存在しない場合には、検索結果としてミスヒット（Ｍｉｓｓ  Ｈｉｔ）が得られる。本実施形態では、２回目の検索でミスヒットが得られたものとする。
【００３６】
なお、１回目の検索時にヒットが得られたワードでは、２回目の検索時にも、データおよび重みデータの最上位ビットで常に一致が検出される。また、３回目以降の検索時も同様である。
【００３７】
以下同様にして、ｉ（１≦ｉ≦８）回目の検索の結果、次の検索時の重みキーデータの上位からｉ番目のビットは、ヒットが得られた場合には‘１’、ミスヒットが得られた場合には‘０’とされる。また、マスクデータは、ｉ回目の検索時には、上位からｉ個のビットが‘０’、残りの（８−ｉ）個のビットが‘１’とされる。すなわち、マスクデータは、最上位ビット側から‘０’が順次シフト入力される。
【００３８】
図３に示すように、本実施形態の場合、重みフィールドのビット幅に相当する８回の検索が行われ、その検索結果が得られた時点で、重みが最も重い重みデータと同じ値を持つ重みキーデータ＝‘１０１１００００’が得られる。
【００３９】
従って、検索キーデータ、８回目の検索の結果得られた重みキーデータ＝‘１０１１００００’、および全てのビットでマスクなしの状態のマスクデータ＝‘００００００００’を用いて、最終回（本実施形態の場合、９回目）の検索を行うことにより、検索キーデータに一致するデータが記憶されているワードの中で、重みの最も重いデータが記憶されているワードを検出することができる。
【００４０】
デバイス１０では、検索対象となる各々のデータに重み付けを行うため、複数のデータがヒットした場合であっても、データの重みに従って検索結果を出力することができる。この場合、検索の手順に従って、重みが最も重いものや最も軽いもの、所定の重みのものを検出することが可能である。また、新規なデータを登録したり、不要なデータを削除した場合であっても、従来のＣＡＭのようにデータのソートを行う必要はないため、高スループットで検索処理を行うことができる。
【００４１】
また、８回目の検索の結果、ヒットが得られた場合、８回目の重みキーデータの最下位ビットも最終回の重みキーデータの最下位ビットも共に‘１’となるため、８回目の検索結果と最終回の検索結果は同じになる。従って、８回目の検索結果に応じて、最終回の検索を行うか行わないかの判断をしてもよいが、そのためにはその判断のための追加回路が必要となるため、無条件に最終回の検索を行うようにしても全く問題はない。
【００４２】
また、検索キーデータと一致するデータが記憶されているワードが存在しない場合には、検索結果として最終的にミスヒットが検出される。
【００４３】
ＩＰアドレスのＬＰＭを行う場合、データフィールドには、ネットワークアドレスに対応するデータが記憶され、ホストアドレスに対応するデータの部分は‘Ｘ’とされる。また、重みフィールドには、重みデータとして、プレフィックス長に対応するデータがバイナリエンコードされた状態で記憶される。これにより、検索キーデータに一致するデータが記憶されているワードの中から、プレフィックス長が最も長いものを検出することができる。
【００４４】
ＩＰアドレスのＬＰＭの場合、データが３２ビットであり、重みデータは５ビットでよいため、１ワードは合計で３７ビットあればよい。従って、１ワードが６４ビットの場合、残りの２７ビットは、自由に使用することができる。例えば、プレフィックス長に対応する重みデータの他に、別の重みデータを記憶してもよい。別の重みデータを記憶すれば、同じネットワークアドレス、同じプレフィックス長のものに対してさらに別の重み付けを行うことができる。
【００４５】
また、本実施形態では、１ワードを構成するＣＡＭセルは全てターナリセルであるとしているが、これに限るわけではなく、‘０’と‘１’の２値データを記憶するバイナリＣＡＭセルを用いてもよいし、ターナリセルとバイナリセルを混合して１ワードを構成することができる。特に、データフィールド部はターナリセルで構成し、重みフィールド部はバイナリセルで構成するのが好ましい。
【００４６】
続いて、図１に示すＣＡＭ１０において、カスケード信号入力回路２４およびカスケード信号出力回路２６は、複数のデバイスをカスケード接続して使用する場合の制御を行う。
【００４７】
カスケード信号出力回路２６からは、複数のデバイスがカスケード接続されて使用される場合に、自分よりも上位および下位の全てのデバイスのカスケード信号入力回路２４に供給するための、カスケード用の検索結果が出力される。このカスケード信号出力回路２６から出力されるカスケード用の検索結果は、検索結果出力回路１６から出力される検索結果とは物理的に違う端子から出力されるが、両者は同じ値を持つ。
【００４８】
また、カスケード信号入力回路２４には、複数のデバイスがカスケード接続されて使用される場合に、自分よりも上位および下位の全てのデバイスのカスケード信号出力回路２６から出力される、カスケード用の検索結果が入力される。カスケード信号入力回路２４から出力される検索結果は重み付き検索制御回路２２に入力される。検索制御回路２２は、カスケード信号入力回路２４から検索結果が入力されると、複数のデバイスをカスケード接続して使用する場合に、その検索処理の制御を行う。
【００４９】
以下、複数のデバイスをカスケード接続して使用する場合を説明する。
【００５０】
図４は、３個のデバイス０，１，２がカスケード接続された状態を表したものである。図中中央のデバイス１を中心として、上側のデバイス０が上位側のデバイスであり、下側のデバイス２が下位側のデバイスである。
【００５１】
ここで、ＣＯ０〜ＣＯ３は、図１に示すＣＡＭ１０において、カスケード信号出力回路２６から出力される検索結果が出力される端子である。また、ＣＩＵ０，ＣＩＵ１は、自分よりも下位のデバイスから出力される検索結果が入力される端子、ＣＩＤ０，ＣＩＤ１は、自分よりも上位のデバイスから出力される検索結果が入力される端子であり、これらの端子から入力された信号は全てカスケード信号入力回路２４に入力される。
【００５２】
ここで、検索結果の‘１’はヒットなしの状態、‘０’はヒットありの状態を表す。デバイス０は最上位のデバイスなので、すなわちデバイス０よりも上位のデバイスは存在しないので、その端子ＣＩＤ０，ＣＩＤ１は‘１’に固定されている。また、デバイス０の端子ＣＩＵ０，ＣＩＵ１には、デバイス０よりも下位のデバイス１の端子ＣＯ０から出力される検索結果、およびデバイス２の端子ＣＯ１から出力される検索結果が入力されている。
【００５３】
デバイス１の上位にはデバイス０が存在し、デバイス１の下位にはデバイス２が存在する。このため、デバイス１の端子ＣＩＤ０には、その上位のデバイス０の端子ＣＯ２から出力される検索結果が入力され、端子ＣＩＵ０には、その下位のデバイス２の端子ＣＯ０から出力される検索結果が入力されている。また、デバイス１の上位および下位にデバイス０，２以外のデバイスは存在しないので、端子ＣＩＤ１，ＣＩＵ１は‘１’に固定されている。
【００５４】
デバイス２は最下位のデバイスなので、すなわちデバイス２よりも下位のデバイスは存在しないので、その端子ＣＩＵ０，ＣＩＵ１は‘１’に固定されている。また、デバイス２の端子ＣＩＤ０，ＣＩＤ１には、デバイス２よりも上位のデバイス１の端子ＣＯ２から出力される検索結果、およびデバイス０の端子ＣＯ３から出力される検索結果が入力されている。
【００５５】
すなわち、各々のデバイスには、自分よりも上位の全てのデバイスから出力される検索結果、および自分よりも下位の全てのデバイスから出力される検索結果が入力される。端子ＣＯ０〜ＣＯ３は入れ替えて使用することが可能である。例えば、デバイス１の端子ＣＯ０をデバイス０の端子ＣＩＵ１に接続し、デバイス２の端子ＣＯ１をデバイス０のＣＩＵ０に接続してもよい。また、端子ＣＩＵ０，ＣＩＵ１、端子ＣＩＤ０，ＣＩＤ１についても同様である。
【００５６】
なお、カスケード接続して使用可能なデバイスの最大個数は何ら制限されず、例えば端子ＣＯ，ＣＩＵ，ＣＩＤの数を増減することによって適宜変更することができる。
【００５７】
次に、図５に示す概念図を参照して、複数のデバイスをカスケード接続して使用する場合の検索動作を説明する。
【００５８】
図５は、勝ち負け決定シーケンサである。複数のデバイスをカスケード接続して使用する場合、最終的に検索結果を出力するデバイス、すなわち重みの最も重いデータが記憶されているデバイスを決定する必要がある。図５は、検索の結果、自分自身のデバイスと、自分よりも上位の全てのデバイスと、自分よりも下位の全てのデバイスとの間で勝ち負けを決定し、最終的に勝ちのデバイスから検索結果を出力するシーケンスを表している。
【００５９】
図５に示すように、まず、現在どのステートにいたとしても、リセット直後はステートＳ１となる。
【００６０】
ステートＳ１において、検索結果が‘０００’または‘１１１’である場合は再度ステートＳ１に戻り、次の検索でも、全てのデバイスの検索結果が勝負の対象となる。ここで、‘０００’および‘１１１’の左端のビットは自分自身のデバイスの検索結果、中央のビットは自分よりも上位の全てのデバイスの検索結果、右端は自分よりも下位の全てのデバイスの検索結果を表す。また、‘０’はヒットなし、‘１’はヒットありの状態を表す。
【００６１】
すなわち、ステートＳ１において、検索結果が‘０００’または‘１１１’の場合とは、全てのデバイスでヒットがない状態、または全てのデバイスでヒットが得られた状態である。この場合、全てのデバイスで条件は同じであるから、次回の検索でも全てのデバイスの検索結果が勝負の対象となる。下位側のビットに向かって検索処理が繰り返し行われ、最終回の検索結果までずっと検索結果が同じであれば、引き分けということになり、プライオリティの高いもの、例えば最上位のデバイスの最終回の検索結果が全体の検索結果として出力される。
【００６２】
ステートＳ１において、検索結果が‘１００’の場合、すなわち自分自身のデバイスでのみヒットが得られ、上位および下位の全てのデバイスでヒットが得られなかった場合はステートＳ５に遷移する。ステートＳ５では、自分自身のデバイスの勝ちが決定しているため、重みフィールドのビット幅に従い、順次下位側のビットに向かって検索処理が繰り返し行われ、自分自身のデバイスの最終回の検索結果が全体の検索結果として出力される。
【００６３】
また、ステートＳ１において、検索結果が‘１０１’の場合、すなわち自分自身のデバイスと、自分よりも下位のデバイスでヒットが得られた場合はステートＳ２に遷移する。ステートＳ２では、自分自身のデバイスと自分よりも下位のデバイスとの間で次回以降の勝負が行われる。その検索結果が‘１Ｘ０’、すなわち自分自身のデバイスでのみヒットが得られた場合にはステートＳ５に遷移する。ステートＳ５における動作は既に説明した通りである。
【００６４】
また、ステートＳ２において、検索結果が‘０Ｘ１’、すなわち自分よりも下位のデバイスでのみヒットが得られた場合にはステートＳ４に遷移する。ステートＳ４では、自分自身のデバイスの負けが決定しているため、たとえ以降の検索でヒットが得られたとしても、自分自身のデバイスの最終回の検索結果は全体の検索結果として出力されない。
【００６５】
また、ステートＳ２において、検索結果が‘０Ｘ０’または‘１Ｘ１’、すなわち自分自身のデバイスおよび自分よりも下位のデバイスの両方でヒットが得られない場合、または両方でヒットが得られた場合は、順次下位側のビットに向かって検索処理が繰り返し行われる。そして、最終回の検索結果までずっと検索結果が同じであれば、両者引き分けということになり、両者のうちのプライオリティの高い方、例えば上位のデバイスの最終回の検索結果が全体の検索結果として出力される。
【００６６】
また、ステートＳ１において、検索結果が‘１１０’の場合、すなわち自分自身のデバイスと、自分よりも上位のデバイスでヒットが得られた場合、ステートＳ３に遷移する。この場合の動作は、ステートＳ２に遷移した場合の動作と同様である。
【００６７】
また、ステートＳ１において、検索結果が‘００１’、‘０１０’または‘０１１’の場合、すなわち自分自身のデバイスではヒットせず、自分よりも上位および下位のデバイスの少なくとも一方でヒットが得られた場合、ステートＳ４に遷移する。ステートＳ４における動作は既に説明した通りである。
【００６８】
以上のように、複数のデバイスをカスケード接続して使用する場合においても、検索の結果、複数のデバイスでヒットした場合には、データの重みに従って検索結果が出力される。
【００６９】
ところで、本出願人は、特願２０００−４４５３５号において、ＣＡＭを使用してデータの最長一致検索を行う方法を提案している。
【００７０】
この最長一致検索方法は、複数の被検索データを格納しておき、検索データにビット単位でマスクをかけて、検索データの、マスクをかけた無効ビット領域を除く有効ビット領域のビットパターンと一致するビットパターンを、有効ビット領域と同一のビット領域に有する被検索データを検索する連想メモリを用いた最長一致検索方法において、有効ビット数が可変な被検索データとともに、被検索データの各ビットに対応して各ビットが有効なビットであるか無効なビットであるかを識別するフラグ列を記憶しておき、検索にあたっては、記憶されている被検索データの中から最長に一致する被検索データを検索するための検索データと有効ビット領域を表すフラグパターンとを用いて二分検索法により検索を行うものである。
【００７１】
しかし、特願２０００−４４５３５号の最長一致検索方法では、フラグ列が展開された形で記憶されているので、ＮビットでＮ通りの重みしか表すことができず非効率である。また、１ワード中に占めることのできるデータ領域が半分しかなく、メモリ容量を有効に活用することができない。例えば、１ワードが６４ビットである場合、データが３２ビット、フラグ列が３２ビットとなる。また、フラグ列の部分が固定長であるため、検索回数は常に一定となる。また、複数のデバイスをカスケード接続して使用することは何ら言及されていない。
【００７２】
これに対し、ＣＡＭ装置１０では、重みデータがバイナリエンコードされた状態で記憶されるため、Ｎビットで（２＾Ｎ）通りの重みを表すことができ、ビットを有効に活用することができる。また、重みフィールドのビット幅が可変なので、必要に応じてデータフィールドおよび重みフィールドのビット幅を調整することができ、メモリ容量を有効利用できる。また、重みフィールドのビット幅Ｍに応じて、検索回数を（Ｍ＋１）回に削減することができる。また、複数のデバイスをカスケード接続して使用することも可能である。
【００７３】
本発明は、基本的に以上のようなものである。
以上、本発明の連想メモリ装置について詳細に説明したが、本発明は上記実施形態に限定されず、本発明の主旨を逸脱しない範囲において、種々の改良や変更をしてもよいのはもちろんである。
【００７４】
【発明の効果】
以上詳細に説明した様に、本発明の連想メモリ装置によれば、検索対象となる各々のデータに重み付けを行うため、複数のデータがヒットした場合であっても、データの重みに従って検索結果を出力することができる。また、従来のＣＡＭのようにデータのソートを行う必要はないため、高スループットで検索処理を行うことができる。
また、本発明の連想メモリ装置によれば、重みデータがバイナリエンコードされた状態で記憶されるため、ビットを有効に活用することができる。また、重みフィールドのビット幅が可変なので、必要に応じてデータフィールドおよび重みフィールドのビット幅を調整することができ、メモリ容量を有効利用できる。また、重みフィールドのビット幅に応じて検索回数を削減することができ、複数のデバイスをカスケード接続して使用することも可能である。
【図面の簡単な説明】
【図１】本発明の連想メモリ装置の一実施形態の構成概略図である。
【図２】（ａ）および（ｂ）は、ワードの構成を表す一実施形態の概略図である。
【図３】重み付き検索の各工程を表す一実施形態の概念図である。
【図４】本発明の連想メモリ装置がカスケード接続された状態を表す一実施形態の概略図である。
【図５】本発明の連想メモリ装置がカスケード接続された場合の重み付き検索の各ステートを表す一実施形態の概念図である。
【符号の説明】
１０  連想メモリ装置
１２  データ／コマンド入力回路
１４  ＣＡＭコア部
１６  検索結果出力回路
１８  重みフィールド幅設定レジスタ
２０  重みフィールドデータ／マスク生成回路
２２  重み付き検索制御回路
２４  カスケード信号入力回路
２６  カスケード信号出力回路
【図１】
2004342230.tif 000003
【図２】
2004342230.tif 000004
【図３】
2004342230.tif 000005
【図４】
2004342230.tif 000006
【図５】
2004342230.tif 000007