(57)【特許請求の範囲】
【請求項１】
検索データと１つ以上の登録データとを比較して検索データに一致する登録データがある場合に、その登録データに対応したデータを出力する連想記憶装置において、
数値範囲を指定する検索データおよび数値範囲を指定する登録データを入力して、前記検索データによって指定される数値範囲と前記登録データによって指定される数値範囲との間に重複範囲がある場合に重複信号を出力する複数のエントリと、
前記重複信号を出力したエントリに割り当てられているアドレスを示すアドレスデータを出力するエンコーダとを備え、
前記検索データは、数値範囲の先頭を示す検索データ範囲先頭値と数値範囲の末尾を示す検索データ範囲末尾値とを含み、前記登録データは、数値範囲の先頭を示す範囲先頭値登録データと数値範囲の末尾を示す範囲末尾値登録データとを含み、
前記エントリは、前記検索データ範囲先頭値と前記範囲末尾値登録データとを比較する第１の比較回路と、前記検索データ範囲末尾値と前記範囲先頭値登録データとを比較する第２の比較回路と、前記第１の比較回路の出力と前記第２の比較回路の出力とにもとづいて重複信号を出力する論理回路とを含み、
前記第１の比較回路は、前記検索データ範囲先頭値の方が前記範囲末尾値登録データよりも大きい場合に有意な信号を出力し、
前記第２の比較回路は、前記検索データ範囲末尾値の方が前記範囲先頭値登録データよりも小さい場合に有意な信号を出力し、
前記論理回路は、前記第１の比較回路および前記第２の比較回路がともに有意な信号を出力しない場合重複信号を出力する
ことを特徴とする連想記憶装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、入力された検索データにもとづいて所定の条件を満たすデータに対応したアドレスデータ等を出力する連想記憶装置に関する。
【０００２】
【従来の技術】
図５は、従来の連想記憶装置の一例を示すブロック図である。連想記憶装置（ＣＡＭ）３０には、検索データ５１が入力されるとともに、プロセッサバス７を介してプロセッサ８から登録データが供給される。ＣＡＭ３０は、検索データ５１に一致する登録データが設定されたエントリを示す一致エントリアドレス５２を出力する。
【０００３】
ＣＡＭ３０には、それぞれが検索データ５１と登録データとを入力するエントリ＃１用ＣＡＭセル３１、エントリ＃２用ＣＡＭセル３２、エントリ＃３用ＣＡＭセル３３、・・・、エントリ＃ｎ用ＣＡＭセル３９と、それぞれのエントリ＃１用ＣＡＭセル３１、エントリ＃２用ＣＡＭセル３２、エントリ＃３用ＣＡＭセル３３、・・・、エントリ＃ｎ用ＣＡＭセル３９から出力されるエントリ＃１一致信号４１、エントリ＃２一致信号４２、エントリ＃３一致信号４３、・・・、エントリ＃ｎ一致信号４９を入力し一致エントリアドレス５２を出力するエンコーダ５が設けられている。以下、エントリ＃１一致信号４１、エントリ＃２一致信号４２、エントリ＃３一致信号４３、・・・、エントリ＃ｎ一致信号４９のそれぞれを、単に、エントリ一致信号と呼ぶことがある。
【０００４】
図６は、エントリ＃１用ＣＡＭセル３１の構成を示すブロック図である。なお、エントリ＃２用ＣＡＭセル３２、エントリ＃３用ＣＡＭセル３３、・・・、エントリ＃ｎ用ＣＡＭセル３９の構成も、エントリ＃１用ＣＡＭセル３１の構成と同じである。
【０００５】
アドレスデコーダ３０７は、プロセッサバス７を監視し、プロセッサバス７に所定のアドレス信号が出力されたことを検知すると、登録データレジスタ３０１に登録データ書込信号３０５を出力し、マスクデータレジスタ３０３にマスクデータ書込信号３０６を出力する。マスク機能付き比較回路３０８は、登録データレジスタ３０１に設定されている登録データ３０２と検索データ５１とを、マスクデータレジスタ３０３に設定されているマスクデータ３０４でマスクした上で比較し、それらが一致していれば、エントリ＃１一致信号４１を出力する。
【０００６】
次に動作について説明する。アドレスデコーダ３０７は、自ＣＡＭセルの登録データレジスタ３０１を指定するアドレス信号がプロセッサバス７に出力されると、登録データレジスタ３０１に対して登録データ書込信号３０５を出力する。このとき、プロセッサ８は、登録データレジスタ３０１に格納されるべき登録データも出力している。登録データレジスタ３０１は、登録データ書込信号３０５に応じてプロセッサバス７から登録データを取り込んで格納する。また、アドレスデコーダ３０７は、自ＣＡＭセルのマスクデータレジスタ３０３を指定するアドレス信号がプロセッサバス７に出力されると、マスクデータレジスタ３０３に対してマスクデータ書込信号３０６を出力する。このとき、プロセッサ８は、マスクデータレジスタ３０３に格納されるべきマスクデータも出力している。マスクデータレジスタ３０３は、マスクデータ書込信号３０６に応じてプロセッサバス７からマスクデータを取り込んで格納する。
【０００７】
マスク機能付き比較回路３０８は、登録データレジスタ３０１から登録データ３０２を入力するとともに、マスクデータレジスタ３０３からマスクデータ３０４を入力する。そして、マスクデータ３０４で指定されるビット以外について、検索データ５１と登録データ３０２とを比較する。それらが一致すれば、エントリ＃１一致信号４１を出力する。
【０００８】
同様に、エントリ＃２用ＣＡＭセル３２、エントリ＃３用ＣＡＭセル３３、・・・、エントリ＃ｎ用ＣＡＭセル３９も、マスクデータで指定されるビット以外について、検索データ５１と登録データとを比較する。それらが一致すれば、エントリ＃２一致信号４２、エントリ＃３一致信号４３、・・・、エントリ＃ｎ一致信号４９を出力する。
【０００９】
エンコーダ５は、エントリ＃１用ＣＡＭセル３１、エントリ＃２用ＣＡＭセル３２、エントリ＃３用ＣＡＭセル３３、・・・、エントリ＃ｎ用ＣＡＭセル３９のうち、エントリ一致信号を出力したＣＡＭセルのエントリアドレスをエンコードして一致エントリアドレスを生成し出力する。
【００１０】
【発明が解決しようとする課題】
以上のように構成された連想記憶装置を、データが数値を示している場合に適用し、検索データが示す数値が所定範囲内に入っているか否か判断するような使い方をしたときには、所定範囲として任意の範囲を指定することができない。例えば、６ビットの検索データが１０進数で０〜１の範囲に入っているか否か判定する場合には、登録データとして”０００００ｘ”（ｘは０または１）を設定し、マスクデータとして”０００００１”（「１」がマスクビット＝非照合のビット）を設定すればよい。
【００１１】
また、６ビットの検索データが１０進数で０〜３の範囲に入っているか否か判定する場合には、登録データとして”００００ｘｘ”（ｘは０または１）を設定し、マスクデータとして”００００１１”（「１」がマスクビット＝非照合のビット）を設定すればよい。
【００１２】
ところが、例えば、検索データが”００００１０”、”００００１１”、”０００１００”および”０００１０１”のいずれかと一致するか否か（１０進数で２〜５の範囲に入っているか否か）を、マスクデータと登録データを用いて検索することは困難である。
【００１３】
この場合、登録データとして、”００００１０”、”００００１１”、”０００１００”および”０００１０１”を設定し、マスクデータとして”００００００”（マスクなし）を設定すれば検索は可能である。しかし、広い範囲を検索する場合には、膨大な数のＣＡＭセルを用いなければならず、現実には実現困難である。従来の連想記憶装置では、連続する数値を登録データとして登録したい場合には全ての数値を登録データとして登録する必要があるので、登録可能なエントリを浪費してしまい、用意されているエントリ数を越える範囲の登録データを登録することはできない。
【００１４】
本発明は、上記のような課題を解決するための発明であって、任意の数値範囲を比較することができる連想記憶装置を提供することを目的とする。
【００１５】
【課題を解決するための手段】
本発明による連想記憶装置は、検索データと１つ以上の登録データとを比較して検索データに一致する登録データがある場合に、その登録データに対応したデータを出力する連想記憶装置において、数値範囲を指定する検索データおよび数値範囲を指定する登録データを入力して、検索データによって指定される数値範囲と登録データによって指定される数値範囲との間に重複範囲がある場合に重複信号を出力する複数のエントリと、重複信号を出力したエントリに割り当てられているアドレスを示すアドレスデータを出力するエンコーダとを備え、エントリは、検索データ範囲先頭値と範囲末尾値登録データとを比較する第１の比較回路と、検索データ範囲末尾値と範囲先頭値登録データとを比較する第２の比較回路と、第１の比較回路の出力と第２の比較回路の出力とにもとづいて重複信号を出力する論理回路とを含み、第１の比較回路が、検索データ範囲先頭値の方が範囲末尾値登録データよりも大きい場合に有意な信号を出力し、第２の比較回路が、検索データ範囲末尾値の方が範囲先頭値登録データよりも小さい場合に有意な信号を出力し、論理回路が、第１の比較回路および第２の比較回路がともに有意な信号を出力しない場合重複信号を出力することを特徴とする。
【００２０】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。図１は、本発明による連想記憶装置の実施の一形態を示すブロック図である。範囲比較機能付き連想記憶装置（以下、ＣＡＭという。）１には、検索データ範囲先頭値および検索データ範囲末尾値が入力されるとともに、プロセッサバス７を介してプロセッサ８から範囲先頭値登録データおよび範囲末尾値登録データが供給される。ＣＡＭ１は、検索データ範囲先頭値から検索データ範囲末尾値までの範囲と、範囲先頭値登録データから範囲末尾値登録データまでの範囲との間に重複範囲があることを検出したエントリを特定しうる重複エントリアドレス６を出力する。
【００２１】
なお、検索データ範囲先頭値は数値範囲のうちの最も小さい値であり、検索データ範囲末尾値は数値範囲のうちの最も大きい値である。また、範囲先頭値登録データが示す値は数値範囲のうちの最も小さい値であり、範囲末尾値登録データが示す値は数値範囲のうちの最も大きい値である。
【００２２】
ＣＡＭ１には、それぞれが検索データ範囲先頭値および検索データ範囲末尾値と範囲先頭値登録データおよび範囲末尾値登録データとを入力する複数のエントリが設けられている。具体的には、それぞれが検索データ範囲先頭値および検索データ範囲末尾値と範囲先頭値登録データおよび範囲末尾値登録データとを入力するエントリとしてのエントリ＃１用範囲比較回路１１、エントリ＃２用範囲比較回路１２、エントリ＃３用範囲比較回路１３、・・・、エントリ＃ｎ用範囲比較回路１９が設けられている。また、それぞれのエントリ＃１用範囲比較回路１１、エントリ＃２用範囲比較回路１２、エントリ＃３用範囲比較回路１３、・・・、エントリ＃ｎ用範囲比較回路１９から出力されるエントリ＃１重複信号２１、エントリ＃２重複信号２２、エントリ＃３重複信号２３、・・・、エントリ＃ｎ重複信号２９を入力し重複エントリアドレス６を出力するエンコーダ５が設けられている。以下、エントリ＃１重複信号２１、エントリ＃２重複信号２２、エントリ＃３重複信号２３、・・・、エントリ＃ｎ重複信号２９のそれぞれを、単に、エントリ重複信号と呼ぶことがある。
【００２３】
図２は、エントリ＃１用範囲比較回路１１の構成例を示すブロック図である。なお、エントリ＃２用範囲比較回路１２、エントリ＃３用範囲比較回路１３、・・・、エントリ＃ｎ用範囲比較回路１９の構成も、エントリ＃１用範囲比較回路１１の構成と同じである。なお、エントリ＃１用範囲比較回路１１、エントリ＃２用範囲比較回路１２、エントリ＃３用範囲比較回路１３、・・・、エントリ＃ｎ用範囲比較回路１９には、それぞれ、アドレス（例えば＃１〜＃ｎ）が割り当てられている。
【００２４】
アドレスデコーダ１０７は、プロセッサバス７を監視し、プロセッサバス７に所定のアドレス信号（範囲先頭値登録レジスタ１０１または範囲末尾値登録レジスタ１０３のアドレスを示す信号）が出力されたことを検知すると、範囲先頭値登録レジスタ１０１または範囲末尾値登録レジスタ１０３に範囲先頭値データ書込信号１０５または範囲末尾値データ書込信号１０６を出力する。
【００２５】
第１の大小比較回路（第１の比較回路）１０９は、Ａ入力としての検索データ範囲先頭値２と範囲末尾値登録レジスタ１０３に保持されている範囲末尾値登録データ１０４（Ｂ入力）とを比較し、検索データ範囲先頭値２の方が範囲末尾値登録データ１０４よりも大きい場合にはＡ＞Ｂ信号１１０を出力する。また、第２の大小比較回路（第２の比較回路）１１１は、Ａ入力としての検索データ範囲末尾値３と範囲先頭値登録レジスタ１０１に保持されている範囲先頭値登録データ１０２（Ｂ入力）とを比較し、検索データ範囲末尾値３の方が範囲先頭値登録データ１０２よりも小さい場合にはＡ＜Ｂ信号１１２を出力する。反転論理和回路（ＮＯＲ回路）１１３は、Ａ＞Ｂ信号１１０とＡ＜Ｂ信号１１２とのＮＯＲをとってエントリ＃１重複信号２１として出力する。
【００２６】
なお、この実施の形態では、エントリ＃１重複信号２１はハイアクティブであり、Ａ＞Ｂ信号１１０およびＡ＜Ｂ信号１１２もハイアクティブである。すなわち、第１の大小比較回路１０９は、検索データ範囲先頭値２の方が範囲末尾値登録データ１０４よりも大きい場合に有意な信号を出力する。また、第２の大小比較回路１１１は、検索データ範囲末尾値３の方が範囲先頭値登録データ１０２よりも小さい場合に有意な信号を出力する。従って、ＮＯＲ回路１１３は、Ａ＞Ｂ信号１１０とＡ＜Ｂ信号１１２との双方が出力されなかったとき（具体的には双方ともローレベルであったとき）に、エントリ＃１重複信号２１を出力する（具体的にはハイレベルにする）。また、この実施の形態では、ＮＯＲ回路１１３が用いられているが、他の論理回路を用いてもよい。例えば、Ａ＞Ｂ信号１１０およびＡ＜Ｂ信号１１２がローアクティブであれば、論理積（ＡＮＤ）回路が用いられる。
【００２７】
次に動作について説明する。アドレスデコーダ１０７は、自ＣＡＭセルの範囲先頭値登録レジスタ１０１を指定するアドレス信号がプロセッサバス７に出力されると、範囲先頭値登録レジスタ１０１に対して範囲先頭値データ書込信号１０５を出力する。このとき、プロセッサ８は、範囲先頭値登録レジスタ１０１に格納されるべき範囲先頭値登録データも出力している。範囲先頭値登録レジスタ１０１は、範囲先頭値データ書込信号１０５に応じてプロセッサバス７から範囲先頭値登録データを取り込んで格納する。
【００２８】
また、アドレスデコーダ１０７は、自ＣＡＭセルの範囲末尾値登録レジスタ１０３を指定するアドレス信号がプロセッサバス７に出力されると、範囲末尾値登録レジスタ１０３に対して範囲末尾値データ書込信号１０６を出力する。このとき、プロセッサ８は、範囲末尾値登録レジスタ１０３に格納されるべき範囲末尾値登録データも出力している。範囲末尾値登録レジスタ１０３は、範囲末尾値データ書込信号１０６に応じてプロセッサバス７から範囲末尾値登録データを取り込んで格納する。
【００２９】
第１の大小比較回路１０９には、検索データ範囲先頭値２がＡ入力として入力され、範囲末尾値登録レジスタ１０３に保持されている範囲末尾値登録データ１０４がＢ入力として入力される。また、第２の大小比較回路１１１には、検索データ範囲末尾値３がＡ入力として入力され、範囲先頭値登録レジスタ１０１に保持されている範囲先頭値登録データ１０２がＢ入力として入力される。
【００３０】
第１の大小比較回路１０９は、Ａ入力とＢ入力とを比較し、Ａ入力の方がＢ入力よりも大きい場合にはＡ＞Ｂ信号１１０を出力する。また、第２の大小比較回路１１１は、Ａ入力とＢ入力とを比較し、Ａ入力の方がＢ入力よりも小さい場合にはＡ＜Ｂ信号１１２を出力する。ＮＯＲ回路１１３は、Ａ＞Ｂ信号１１０とＡ＜Ｂ信号１１２とのＮＯＲをとってエントリ＃１重複信号２１として出力する。
【００３１】
従って、第１の大小比較回路１０９は、検索データ範囲先頭値２の方が範囲末尾値登録データ１０４よりも大きい場合にはＡ＞Ｂ信号１１０を出力する。また、第２の大小比較回路１１１は、検索データ範囲末尾値３の方が範囲先頭値登録データ１０２よりも小さい場合にＡ＜Ｂ信号１１２を出力する。
【００３２】
図３の（Ａ）に示すように、検索データ範囲先頭値２の方が範囲末尾値登録データ１０４よりも大きい場合にはＡ＞Ｂ信号１１０が出力される（ハイレベルになる）ので、エントリ＃１重複信号は出力されない（ハイレベルにならない）。また、図３の（Ｂ）に示すように、検索データ範囲末尾値３の方が範囲先頭値登録データ１０２よりも小さい場合にはＡ＜Ｂ信号１１２が出力される（ハイレベルになる）ので、エントリ＃１重複信号は出力されない（ハイレベルにならない）。
【００３３】
図３の（Ｃ）〜（Ｆ）のそれぞれに例示するように重複範囲が存在する場合には、Ａ＞Ｂ信号１１０もＡ＜Ｂ信号１１２も出力されない（ハイレベルにならない）ので、ＮＯＲ回路１１３からエントリ＃１重複信号が出力される（ハイレベルになる）。なお、エントリ＃１重複信号は、エントリ＃１（具体的にはエントリ＃１用範囲比較回路１１）で、登録データで指定される範囲において検索データで指定される範囲と重複する範囲があることを示す信号である。
【００３４】
同様に、エントリ＃２用範囲比較回路１２、エントリ＃３用範囲比較回路１３、・・・、エントリ＃ｎ用範囲比較回路１９も、検索データ範囲先頭値と範囲末尾値登録データとを比較するとともに、検索データ範囲末尾値と範囲先頭値登録データとを比較する。そして重複している範囲があれば、重複範囲があることを示すエントリ＃２重複信号２２、エントリ＃３重複信号２３、・・・、エントリ＃ｎ重複信号２９を出力する。
【００３５】
そして、エンコーダ５は、エントリ＃１用範囲比較回路１１、エントリ＃２用範囲比較回路１２、エントリ＃３用範囲比較回路１３、・・・、エントリ＃ｎ用範囲比較回路１９のうち、エントリ重複信号を発生しているエントリを示す情報をエンコードし、エンコード結果を重複エントリアドレス６を出力する。なお、重複エントリアドレス６は、後述するように、例えば、ＣＡＭ１の後段に設置されているＲＡＭのアドレスを示すデータとなる。
【００３６】
以上のように、この実施の形態では、連想記憶装置は範囲比較機能付きＣＡＭを備え、検索データおよび登録データとしてそれぞれ範囲を指定するデータ（検索データ範囲先頭値と検索データ範囲末尾値、および範囲先頭値登録データと範囲末尾値登録データ）を用い、それぞれのデータで指定される双方の範囲を照合して、検索データで指定される範囲と重複する範囲のあるエントリのアドレスに対応したデータをエントリ重複信号によって出力するように構成されている。従って、マスクデータを用いる場合とは異なり、任意の数値範囲を取り扱うことができるようになる。また、連続する数値を登録データとして登録したい場合に各数値を複数のエントリに分けて登録するという必要もなくなる。
【００３７】
次に、本発明による連想記憶装置の具体的適用例を説明する。図４は、ルータ装置におけるＩＰフィルタ機能を実現するパケット廃棄判別回路の一構成例を示すブロック図である。この例では、プロセッサ８は、登録データとして、パケットを廃棄するＴＣＰ／ＵＤＰポート番号の範囲、およびパケットの通過を許可するＴＣＰ／ＵＤＰポート番号の範囲を、それぞれ１つまたは複数個指定する。すなわち、エントリ＃１用範囲比較回路１１、エントリ＃２用範囲比較回路１２、エントリ＃３用範囲比較回路１３、・・・、エントリ＃ｎ用範囲比較回路１９のうち１つまたは複数のエントリ用範囲比較回路に、パケットを廃棄するＴＣＰ／ＵＤＰポート番号の範囲に対応した範囲先頭値登録データと範囲末尾値登録データとを設定するとともに、他の１つまたは複数のエントリ用範囲比較回路に、パケットの通過を許可するＴＣＰ／ＵＤＰポート番号の範囲に対応した範囲先頭値登録データと範囲末尾値登録データとを設定する。
【００３８】
また、エンコーダ５の出力によってアドレス指定されるＲＡＭ９における、パケットを廃棄するＴＣＰ／ＵＤＰポート番号の範囲を登録データで設定したエントリに対応したアドレスに「廃棄する」を示すフラグをセットする。また、パケットの通過を許可するＴＣＰ／ＵＤＰポート番号の範囲を登録データで設定したエントリに対応したアドレスに「廃棄しない」を示すフラグをセットする。
【００３９】
そして、入力パケットのＴＣＰ／ＵＤＰヘッダ内のポート番号を検索データとしてＣＡＭ１に与える。この例では、検索データ範囲先頭値と検索データ範囲末尾値とにポート番号を与える。すなわち、範囲は「１」である。例えば、入力パケットのＴＣＰ／ＵＤＰヘッダ内のポート番号が、パケットを廃棄するＴＣＰ／ＵＤＰポート番号の範囲に含まれているのであれば、パケットを廃棄するＴＣＰ／ＵＤＰポート番号の範囲に対応した範囲先頭値登録データと範囲末尾値登録データとが設定されたエントリ用範囲比較回路からエントリ重複信号が出力される。エンコーダ５は、そのエントリ重複信号をエンコードする。すなわち、「廃棄する」を示すフラグがセットされているＲＡＭ９のアドレスを重複エントリアドレス６として出力する。その結果、ＲＡＭ９から、「廃棄する」を示すフラグが出力される。
【００４０】
ＲＡＭ９の出力は、例えばパケットの通過を制御するゲート回路に入力され、ＲＡＭ９の出力結果に応じてパケットが制御される。「廃棄する」を示すフラグが出力された場合にはパケットの通過が阻止される。なお、この例では、検索データで指定される範囲は「１」であったが、もちろん「１」を越える範囲の検索データを使用することもできる。
【００４１】
【発明の効果】
本発明によれば、連想記憶装置を、検索データとして範囲を指定するデータを取り扱い、登録データとして範囲を指定するデータを取り扱うように構成したので、任意の数値範囲を比較することができる連想記憶装置を提供することができる効果がある。
【図面の簡単な説明】
【図１】  本発明による連想記憶装置の実施の一形態を示すブロック図である。
【図２】  エントリ＃１用範囲比較回路の構成例を示すブロック図である。
【図３】  検索データと登録データの範囲例を示す説明図である。
【図４】  ルータ装置におけるＩＰフィルタ機能を実現するパケット廃棄判別回路の一構成例を示すブロック図である。
【図５】  従来の連想記憶装置の一例を示すブロック図である。
【図６】  エントリ＃１用ＣＡＭセルの構成を示すブロック図である。
【符号の説明】
１      範囲比較機能付きＣＡＭ
５      エンコーダ
８      プロセッサ
９      ＲＡＭ
１１〜１９  エントリ＃１用範囲比較回路〜エントリ＃ｎ用範囲比較回路
１０１  範囲先頭値登録レジスタ
１０３  範囲末尾値登録レジスタ
１０７  アドレスデコーダ
１０９  第１の大小比較回路
１１１  第２の大小比較回路
１１３  ＮＯＲ回路
【図１】
0003808333.tif 000002
【図２】
0003808333.tif 000003
【図３】
0003808333.tif 000004
【図４】
0003808333.tif 000005
【図５】
0003808333.tif 000006
【図６】
0003808333.tif 000007