(57)【要約】それぞれがサブワード列を含む、異なるサイズの比較ユニットに分割される、可変サイズのワードを検索するためのＣＡＭメモリである。比較ユニットの両端のサブワードの位置は、コマンド信号により選択される。従って、任意のサイズの検索されるデータワードが、メモリワード内に隣接して格納される。これにより、メモリの全てを、格納および検索のために用いることができる。検索サイクルの数と、データワードの位置を見つけるために必要な時間が、顕著に削減される。サブワードからの一致信号は、同じ比較ユニットの先行するサブワードの文字列全体が一致信号をセットし、かつ、次のコマンド信号がセットされた場合にのみ、ワード一致として出力される。【選択図】図３
2004526274.tif 000002
【特許請求の範囲】
【請求項１】
所定の順序で配置された基本メモリユニット（サブワード）に分割され、ランダムな位置で異なるサイズのワードを検索するためのコンテントアドレッサブルメモリであって、
各サブワードが比較器を備え、
各サブワードは１つまたはそれ以上のデータラインに接続され、
各サブワードは、前記サブワードに格納されたデータと前記データライン上のデータとが所定の関係を満たす場合、一致信号を出力するよう設計され、
前記コンテントアドレッサブルメモリは、前記コンテントアドレッサブルメモリを、それぞれが選択可能な数の連続するサブワードを含む比較ユニットに選択的に分割すると共に、前記比較ユニットの最下位のサブワード位置と最上位のサブワード位置とを所定の順序で選択する手段を備え、
各比較ユニットは、前記比較ユニットの全てのサブワードがサブワード一致信号を出力した場合、ワード一致信号を出力するよう設計されていることを特徴とするコンテントアドレッサブルメモリ。
【請求項２】
前記比較ユニットのそれぞれが、前記ワード一致信号を単一のサイクル内で出力するよう設計された、請求項１に記載のコンテントアドレッサブルメモリ。
【請求項３】
前記コンテントアドレッサブルメモリが、当該コンテントアドレッサブルメモリをコールアウトモードで動作可能とする手段をさらに備えた、請求項１または２に記載のコンテントアドレッサブルメモリ。
【請求項４】
前記サブワードがアプリケーションに必要な最小サイズを有する、請求項１ないし３のいずれかに記載のコンテントアドレッサブルメモリ。
【請求項５】
前記コンテントアドレッサブルメモリが、前記データラインを比較のためにマスクすることを可能とする手段をさらに備えた、請求項１ないし４のいずれかに記載のコンテントアドレッサブルメモリ。
【請求項６】
前記メモリを選択的に分割し、前記比較ユニットの最下位および最上位サブワードを定義する手段が、一群のコマンド信号であり、各コマンド信号は、少なくとも１つのサブワードに関連付けられている、請求項１ないし５のいずれかに記載のコンテントアドレッサブルメモリ。
【請求項７】
前記メモリを選択的に分割し、前記比較ユニットの最下位および最上位サブワードを定義する手段が、一群のコマンドラインであり、各コマンドラインが、少なくとも１つのサブワードに関連付けられている、請求項１ないし６のいずれかに記載のコンテントアドレッサブルメモリ。
【請求項８】
前記コマンド信号が、一群のコマンドラインに循環的に接続され、前記一群のコマンドラインがｎラインを含む場合、添え字ｊのサブワードのコマンド信号がラインｒに接続され、
前記ｒは、ｎをｊで割った際の剰余である、請求項７に記載のコンテントアドレッサブルメモリ。
【請求項９】
前記一群のコマンドラインが、コマンドバス内に含まれた、請求項７に記載のコンテントアドレッサブルメモリ。
【請求項１０】
複数のサブワードがどのコマンド信号にも関連づけられておらず、
前記非接続サブワードのそれぞれにおけるワード一致信号が、当該位置における特定の論理回路に応じてそれぞれ発行される、請求項１ないし９のいずれかに記載のコンテントアドレッサブルメモリ。
【請求項１１】
前記論理回路が、固定状態のコマンドラインが前記サブワードに関連づけられている場合と同じ機能を提供することにより、前記コンテントアドレッサブルメモリ内の複数の固定位置において、固定された区切りの定義を提供する、請求項１０に記載のコンテントアドレッサブルメモリ。
【請求項１２】
前記比較ユニットのサイズが互いに等しくかつ固定であり、
前記コンテントアドレッサブルメモリが、前記比較ユニット内で、先頭および最終のサブワードの位置を変更する手段を備えた、請求項１〜１１のいずれかに記載のコンテントアドレッサブルメモリ。
【請求項１３】
コンテントアドレッサブルメモリ内のランダムな位置で異なるサイズのワードを検索する方法であって、
i)検索されるワードデータを前記コンテントアドレッサブルメモリのデータライン上にセットし、
ii)一つの比較ユニットに対する所定の順序で最下位サブワードを定義すると共に、先行する比較ユニットに対する所定の順序で最上位サブワードを定義することで、前記比較ユニットのそれぞれが、検索されるデータワードと等しいサイズのサブワード列を含むように、前記コンテントアドレッサブルメモリを比較ユニットに区切り、
iii)i)サブワードSWiの一致信号が出力され、ii)前記サブワードSWiに対して所定の順序内で先行するサブワードのサブワード一致信号が出力されるか、あるいは、前記サブワードSWiに関連付けられたコマンド信号が前記サブワードSWiに関連付けられた論理回路によってセットされた場合に、前記サブワード列内のサブワードSWiに対してサブワード一致信号を出力する論理関数を実行し、
iv) サブワードSWiのサブワード一致信号と、所定の順序内で次のサブワードに関連づけられたコマンド信号との両方が、前記サブワードに関連づけられた第２の論理回路により出力された場合に、ワード一致信号を出力する論理関数を実行するステップを含むことを特徴とする方法。
【請求項１４】
前記ワード一致信号を出力する論理関数が、単一サイクル内で実行される、請求項１３に記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項１５】
前記コンテントアドレッサブルメモリが、当該コンテントアドレッサブルメモリをコールアウトモードで動作させる手段をさらに備えた、請求項１３または１４に記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項１６】
前記比較ユニットは、一群のコマンド信号により定義され、
各コマンド信号は、少なくとも１つのサブワードに関連づけられ、
比較ユニットのサブワード列内で所定の順序における最下位のサブワードは、前記コマンド信号が関連づけられるサブワードであり、
先行する比較ユニットのそれぞれのサブワード列内で所定の順序における最上位のサブワードは、前記コマンド信号が関連づけられるサブワードに先行するサブワードである、請求項１３ないし１５のいずれかに記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項１７】
前記コマンド信号のいくつかのまたは全てが、複数のコマンドラインによってセットされる、請求項１４ないし１６のいずれかに記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項１８】
それぞれに前記サブワードに関連づけられた前記コマンド信号のいくつかのまたは全てが、それら各々のサブワードおよび／または他のサブワードに格納されたデータの論理結合の結果である、請求項１４ないし１７のいずれかに記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項１９】
前記コマンド信号に関連づけられたサブワードに格納されたデータが空白、ドット、または同様の文字を含む分離記号である場合、コマンド信号がセットされる、請求項１８に記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項２０】
１つまたは複数位置において、特定の論理回路に従って、前記ワード一致信号がセットされる、請求項１３ないし１９のいずれかに記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項２１】
前記コマンド信号が一定の状態を有する、請求項１３ないし２０のいずれかに記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項２２】
データライン上の複数のデータビットが比較のためにマスクされた、請求項１３ないし２１のいずれかに記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項２３】
前記方法が、全てのワード一致出力をプライオリティエンコーダへ入力するステップをさらに含み、
前記プライオリティエンコーダは、所定の優先順位に従い、ワード一致信号がセットされた全てのサブワード列の中から、一つのサブワード列のアドレスを出力する、請求項１３ないし２２のいずれかに記載の、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項２４】
請求項１ないし１２のいずれかに記載のコンテントアクセシブルメモリを用い、ワード文字列の入力ストリーム内で、与えられたワードリスト内の一つまたは複数のワードの存在を検出する方法。
【請求項２５】
実質的に、図面を参照してここで説明したように、コンテントアドレッサブルメモリ内で異なるサイズのワードを検索する方法。
【請求項２６】
実質的に、図面を参照してここで説明したように、異なるサイズのワードを検索するコンテントアドレッサブルメモリ。
【発明の詳細な説明】
【背景技術】
【０００１】
連想メモリシステム（Associative memory system）において実行される検索処理が知られている。この場合、特定のデータワード（検索キー）がメモリに与えられ、連想メモリシステムは、検索キーのデータと同じデータを格納しているメモリの１ワードの位置を返す。この機能は、従来は、比較器をメモリの各ワードに結合させることによって実現されている。比較器が、メモリワードに格納されているデータと検索キーとが一致したことを検出すると、ワード一致信号が発行される。
【０００２】
メモリの複数ワードが一致するデータを有する場合は、予め定められた基準によって単一の一致信号を選択するためにプライオリティ回路が用いられることがある。そして、より高い優先順位の一致信号を発行するメモリワードのアドレスが出力される。
【０００３】
コンテントアドレッサブルメモリ（ＣＡＭ）のような既存のシステムにおいて、検索キーは、所定のサイズでなければならない。このサイズは、検索されるワードの最大サイズによって決定される。これらのメモリは、ＣＡＭのメモリの基本ワードが最大サイズを持つワードとなるように構成される。各比較器が、同じ所定サイズのワードの一対を比較するように設計されているからである。
【０００４】
検索キーが、この最大サイズよりも短いワードである場合は、一般的に用いられている技術は、以下から成り立つ。
ａ）検索キーに任意のビットを加えて所定のサイズに適合させる。
ｂ）これらの任意のビット間での比較を無効とする追加の論理回路を提供することにより、関連するビットの比較のみを有効とする。
【０００５】
このようなシステムの欠点は、メモリの基本ワード内に全体が含まれるワードのみが検索可能であるということにある。このため、例えば、検索ワードの最大サイズが８文字であり、各々の文字が１バイトで表される場合、そのメモリは、比較プロセス用の各８バイトからなる基本ユニットに分割される。メモリへ与えられる８バイトデータは、バイト１−８、バイト９−１６、バイト１７−２４等と同時にかつそれぞれに比較される。このメモリ分割は、比較パーティション（Comparison Partition）と称され、このパーティションによって定義されるメモリの一部は、比較ユニット（Comparison Units）と称される。ＣＡＭの規定の仕様書によれば、比較ユニットのサイズは、検索可能なワードの最大サイズに等しいことは明らかである。このようなメモリにおいて、各ワードが別個の比較ユニットに分離して格納されている構成では、検索動作を実行することを可能とするために、全てのワードはＣＡＭに格納されていることが必要である。当然、この構成によれば、メモリの使用は非効率的なものとなる。なぜなら、多くのワードが、比較ユニットよりも短いサイズを持つことがあるからである。この欠点により、これらの連想メモリは、効率的かつ柔軟に使用することができず、そのため、適用範囲が限定されてしまう。例えばこのように、このタイプのＣＡＭは、テキストファイルを効率的に検索するためには利用できない。その理由は、ファイルデータがＣＡＭに格納される場合はワードの位置を予め決定することができないのに対して、テキストファイルでは、データは長い文字列の形式で格納されるからである。
【０００６】
既存のシステムには、所定のサイズの数による、限られた数の組み合わせを認めるように改良されたものもある。これらのシステムの一つは、いくつかのＣＡＭワードの関数を論理的に結合することによりＣＡＭワードをグループ化できるＣＡＭである。これにより、予め定められた少数のサイズの中から、比較ユニットのサイズを選択することが可能である。しかし、比較ユニットサイズの種類が限定されており、効率的な使用のためには、格納されたワードは、依然として、比較ユニットに適合するサイズでなければならず、一つのワードは一つの比較ユニットに格納される。
【０００７】
米国特許第６，０００，００８号には、異なるサイズのワード列を見つけるために連続した検索サイクルが用いられるメモリシステムが開示されている。このシステムは、検索される文字列を、検索キーと同じサイズの基本ワードに分割しなければならないという点で不利である。また、このシステムは、一度にただ一つの基本ワードの検索しかできず、文字列全体を見つけるためには、その文字列中の基本ワードの数と等しい数の検索サイクルが必要である、という欠点もある。
【０００８】
米国特許第６，０００，００８号のシステムのさらなる欠点は、メモリの追加の「開始ビット」を各基本ワードに追加しなければならない点にある。このため、回路領域をさらに必要とする。また、各検索動作の前に前述の「開始ビット」を適切な値に設定する必要があるので、検索動作がより複雑になる。
【０００９】
従って、文字列全体を検索キーにロードして比較することを可能とする、メモリのランダムな位置に格納されたワード列を発見する手段を提供することが望ましい。さらに、メモリに追加ビットを加えることなく、ワード列を見つけるための検索サイクルの数を大きく削減する手段を提供することが望ましい。
［発明の開示］
本発明は、比較ユニットについて無制限の数の異なるサイズを許容してワードの文字列全体が検索キーにロードされ比較されるようにすることによって、従来のデバイスの欠点を克服する、連想メモリシステム（Associative メモリ システム）および異なるサイズのワードを検索するための方法に関する。本発明において、比較ユニットは、メモリの隣接ワードの一群によって定義される。これらのメモリワードは、アプリケーションに必要とされる最小限の小さいサイズを有し、ここではサブワードと称される。なお、「メモリワード」という言葉は、サブワード列を意味する。各比較ユニットの両端のメモリのサブワードの位置は、各検索動作の前に、コマンド信号によって新しく選択することができる。従って、検索されるデータのワードは、それらのワードのサイズがどのようなサイズであっても、メモリ内に隣接して格納される。本発明のシステムおよび方法のこの利点によれば、格納と検索に用いることのできるメモリセルの数はかなり増加し、メモリ空間のほとんどを含むようになる。与えられたワードのデータの位置を見つけるために必要な検索サイクルの数が大きく削減され、検索時間を短縮できることは、本発明のさらなる利点である。
【００１０】
好適な実施形態においては、ワード列の比較は、単一サイクル内で達成することができる。
【００１１】
このようなメモリシステムおよび方法は、メモリ内のランダムな位置に格納された異なるサイズのデータワードを検索するために好適に用いることができる。後述するさらなる利点によれば、与えられたワードをテキスト内で検索するために必要な時間は、大きく削減される。高速検索およびフィルタリング動作を高速に実行しなければならない通信システムは、本発明の適用が想定される多くの分野の一つである。
［発明を実施するための最良の形態］
本発明は、コンテントアドレッサブルメモリのランダムな位置において異なるサイズのデータワードを検索するための方法およびシステムに関する。
【００１２】
連想メモリシステム内でワードデータの効率的かつ高速な検索を可能とする本発明の利点をより明確にし、この種の処理に発生する問題であって本発明のシステムおよび方法で解決される問題を明らかにするために、従来のシステムについて、図１および図２を参照しながら、ここで詳細に説明する。
【００１３】
図１および図２において、与えられたテキスト内のワードを検索するために一般的なＣＡＭがどのように用いられるかを示す。特に、検索ワードの位置が見つかるまでに、多数の検索サイクルが必要とされることが分かるであろう。
【００１４】
図１に、一般的なコンテントアドレッサブルメモリ（ＣＡＭ）を示す。このＣＡＭは、多数のメモリワードW1〜Wnと、検索されるワードを格納する検索キーレジスタとを有する。データは、システムバスにより、検索キーレジスタへロードされる。各メモリワードは、データラインにより検索キーレジスタに接続され、メモリワードWiに格納されたワードを検索キーレジスタに格納されたワードと比較するための比較器を備えている。検索処理が実行されるとき、この比較器は、メモリワードWiに格納されたワードと検索キーレジスタに格納されたワードとが等しければ、あるいは、これらのワードが所定の関係を満たしていれば、ワード一致信号Miを発行する。いくつかのメモリワードが一致するデータを格納している場合があるので、複数のワード一致信号が同時に発行されることもある。これらワード一致信号の全ては、次に、プライオリティエンコーダに入力される。プライオリティエンコーダは、予め定められた優先順位に従って一つの一致信号を選択し、対応するメモリワードのアドレスを出力する。
【００１５】
一般に、検索処理に関係のないビットの比較を無効化するために、検索キーレジスタのいくつかのビットをマスクする手段も設けられる。検索キーレジスタのいずれかのビットがマスクされた場合、そのメモリワードの比較器の全ては、このビットとメモリワード内に格納されているワードのビット（すなわち、メモリワード内で、検索キーレジスタ内でマスクされたビットの位置と同じ位置にあるビット）との差を廃棄する。この検索により、マスクされていないビットの全てについて一致するデータを有するメモリワードの全てにより、ワード一致信号が出力されることとなる。
【００１６】
図１に、従来のＣＡＭメモリに格納されているデータの例を示す。この例では、データワード“ＡＢＣＤ”は分割され、“ＡＢ”がメモリワードWi-1の最後の２文字に格納され、“ＣＤ”がメモリワードWiの最初の２文字に格納されている。
【００１７】
ＡＢＣＤワードを見つけるために、比較ユニット内のＡＢＣＤワードの取り得る位置の一つと同じビット位置に同じＡＢＣＤワードを含むデータを、検索キーレジスタ内にロードし、検索キーレジスタ内の他の全てのビットをマスクする必要がある。比較ユニット内のＡＢＣＤワードの位置は不知であるので、一致を発見するまで、全ての可能な位置を試行しなければならない。さらに、例示されているように、ワードＡＢＣＤは、二つのワードに分割されることがあるので、ＡＢＣＤワードが二つの部分に分割される位置（一つのワードの終端位置および次のワードの開始位置）を考慮する必要がある。
【００１８】
図２に、ワードＡＢＣＤの可能な配置の全てに対応するために検索キーレジスタにロードしなければならない８つの異なるパターンを示す。これらのパターンの一つをロードした後、ＣＡＭはそのパターンを検索するように操作される。そのパターンが見つからなければ、他のパターンがロードされ、「一致」が見つかるか全てのパターンの試行が完了するまで、この処理が繰り返される。図２のパターンにおける星（＊）文字は、検索キーレジスタ内で比較のためにマスクされたビットを表す。
【００１９】
このようなシステムの一つの欠点は、データが連続してＣＡＭ内にロードされた場合であっても、図１に示したデータ例のように、検索されるワードが二つの隣接ワードに分割される可能性があることである。その場合、検索データの一部のみを含むパターンを用いて検索処理を実行しなければならない。この場合、「一致」は、メモリワードの一部のみが一致する場合（この例では、＊＊＊＊＊ＡＢ）に得られる。このような場合、完全な「一致」でない可能性が残る。例えば、次のワードの最初の先頭２文字を占める次の２文字が検索文字（この例ではＣＤ）ではない場合もある。従って、これらの次の２文字をチェックし、それらを検索文字列の残りの部分（ＣＤ）を比較する必要がある。文字が一致しない場合、後続の検索へ一致信号を発行しないように、見つかったＡＢワードを変更し、その後、同じパターン（＊＊＊＊＊ＡＢ）を用いてさらなる検索処理を実行することが必要となる。そして、この手順は、完全な「一致」が見つかるまで繰り返される。これらの一連の検索処理は、格納されたデータのタイプに応じて、膨大な数の検索処理を必要とする。この方法のさらなる欠点は、検索プロシージャが、メモリデータになされた変更を記憶でき、検索処理の最後に元のデータを戻すことができなければならない
従来技術の複雑さおよび効率の低さは、格納されたデータがアルファベット文字（２６文字）のランダムである例によって、明らかになるであろう。この場合、“ＡＢＣＤ”ワードに比較して、さらに、平均して２６＊２６＝６７６回の“ＡＢ”ワードが存在する。この例では、検索サイクルの最大数は、６７６＋８＝６８４であり、一般に、必要な検索サイクルの平均数はおよそ４７と計算されることが、理解されるであろう。各検索サイクルは、検索を行うステップ、チェックを行うステップ、変更を行うステップ、および最終的なデータを戻すステップを含む。
【００２０】
上述のように、一般的なＣＡＭでデータを検索するとき、ＣＡＭの検索機能を実現するために、機能強化された高価なハードウェアを用いたとしても、必要とされる検索サイクルの数が非常に大きくなる可能性がある。この用途に用いられる一般的なＣＡＭの他の欠点は、検索時間の値が広範囲にわたることである。すなわち、検索処理のためにわずかな検索サイクルが必要な場合もあれば、膨大な検索サイクルが必要な場合もある。必要とされる検索サイクルの数は予測不可能であり、このため、より大きなシステムにＣＡＭを統合する際に、同期について難しい問題を生ずる可能性がある。これらの欠点のために、これまで、コンピュータシステムにおいてＣＡＭを広く使用することができなかった。また、今日においても、ＣＡＭの適用分野は主として通信システムに限定されている。
【００２１】
本発明の方法およびシステムについて、以下に詳細に説明する。本発明は、以下に記載する実施形態や添付された図面に限定されるものではない。また、本発明の実現は、特許請求の範囲内において、他の多様な方法によって可能である。
【００２２】
本発明の目的は、ＣＡＭがランダムな位置のデータワードを見つけるために用いられる際の検索サイクルの数を大きく削減するという目的と共に、ＣＡＭについての効率的なアーキテクチャを提供することにある。本発明によれば、ランダムな位置のワードを最小の検索サイクル数で検索できるコンテントアドレッサブルメモリ（ＣＡＭ）を設計することが可能となる。本発明にかかるシステムおよび方法は、また、ＰＣＴ出願（出願番号ＰＣＴ／ＩＬ  ００／００１２１；ＰＣＴ／ＩＬ  ００３２７；ＰＣＴ／ＩＬ  ０１／０００８８；ＰＣＴ／ＩＬ  ０００９６）に開示されているようなＣＯＭメモリ（コールアウトメモリ）にも適用可能である。本発明にかかるシステムのさらなる利点によれば、ワードの発見に必要な検索サイクル数のばらつきも、大きく削減される。
【００２３】
図３に、本発明にかかるＣＡＭの原理を示す。一般的なＣＡＭは、メモリワードSW0〜SWnを有する。しかし、これらのワードは、アプリケーションで必要とされる最小サイズが与えられている。例えば、アプリケーションがアルファベット文字（Letter Characters）を検索するように設計されている場合、このサイズは、一般的に８ビットとなる。通信システムにおけるアプリケーションの場合、上記のサイズは１ビットとなる可能性がある。これらのワードを、従来のＣＡＭで用いられるワードと区別するために、サブワードと称する。
【００２４】
図４に、関連する回路と共に、メモリの８ビットBo〜B7を含む１つのサブワードSWiを示す。
【００２５】
図４に示すように、各サブワードは、データラインによってデータバスに接続されている。データは、一般的なメモリについて知られているように、各サブワードに対して格納および／または取り出しが可能である。従来のＣＡＭと同様に、各サブワードSWiは比較器を有する。検索処理を実行するとき、各サブワードSWiの比較器は、データライン上のデータとそれ自身のデータとを比較する。両者が等しい場合、または両者が所定の関係を満たす場合、この比較器は、一致信号Miを出力する。
【００２６】
一般に、データラインは、検索されるワードを格納するために用いられる検索キーレジスタから発行される。
【００２７】
本発明にかかる可変の比較ユニットを実現するために、複数のコマンド信号が定義されている。これらのコマンド信号は、コマンドバス等の様々な手段により設定される。図３に示すように、各サブワード（SWi）位置に、コマンド信号の一つ（Ci）が関連付けられている。このコマンド信号は、ＯＲ関数における前段のサブワード（SWMi-1）からのサブワード一致信号（後に定義する）と結合される。このＯＲ関数の結果は、次に、ＡＮＤ関数内で、サブワードの一致出力（Mi）と結合され、サブワード一致出力（SWMi）を生成する。各サブワード一致信号SWMiは、次に、ＡＮＤ関数内で、次のサブワードSWi+1に関連付けられているコマンド信号Ci+1と結合され、ワード一致信号WMiを生成る。コマンド信号の数は、原理的には無制限であり、図３の実施形態に示したように、各サブワードについて一つのコマンド信号を定義することが可能である。しかし、コマンド信号の数を減らすために、複数のサブワードに対して単一のコマンド信号を定義しても良い。
【００２８】
ここで、比較ユニットを、論理レベル１の二つのコマンド信号の間のサブワードの一群として定義する方法について説明する。
【００２９】
例えば、ｓが整数であり、コマンド信号CiとCi-sの両方が論理レベル１であり、コマンド信号Ci-s+1からCi-1までの全てが論理レベル０である場合を想定する。一致信号の論理結合の結果として、一致信号Mi-1がセットされ、全てのサブワードSWMi-s、SWMi-s+1からSWMi-2までがセットされた場合にのみ、サブワード一致出力SWMi-1がセットされる。これは、サブワードSWi-s〜SWi-1のデータ列全体が、これらのサブワードに接続されたデータバスラインにセットされた対応するデータ列に一致することを意味する。この場合、全てのサブワード信号SWMi-s、SWMi-s+1からSWMi-1まではセットされるが、ワード一致信号WMi-s、WMi-s+1からWMi-2まではセットされない。なぜなら、コマンド信号Ci-s+1、Ci-s+2からCi-1までの全てが、論理レベル０にあるからである。コマンド信号Ciがセットされていることにより、ワード一致信号WMi-1のみがセットされる。従って、この信号WMi-1は、サブワードSWMi-s、SWMi-s+1からSWMi-1までに格納されたデータ列全体と、データバス上にセットされた対応するデータとの間の比較結果を含む。
【００３０】
この結果、ここでセットされたコマンド信号は、比較ユニットの境界を定義する。すなわち、セットされたコマンド信号Ciの各々は、サブワードSWi-1を１つの比較ユニットの最終サブワードとして定義し、サブワードSWiを次の比較ユニットの先頭サブワードとして定義する。コマンド信号を選択的にセットすることにより、任意のサイズおよび任意の位置で比較ユニットを定義することが可能となる。
【００３１】
従来のＣＡＭおよびＰＣＴ出願（出願番号ＰＣＴ／ＩＬ  ００／００１２１；ＰＣＴ／ＩＬ  ００３２７；ＰＣＴ／ＩＬ  ０１／０００８８；ＰＣＴ／ＩＬ  ０００９６）に開示された新しいＣＯＭのように、ワード一致出力の全ては、次に、プライオリティエンコーダに入力され、定義された特定の優先順位に従って、プライオリティエンコーダはワード一致信号がセットされたサブワードの一つのアドレスを出力する。
【００３２】
以下に、本発明にかかるＣＡＭと少数の検索サイクルを用いた検索処理の方法の一例について説明する。
【００３３】
図５は、図１の例のワード“ＡＢＣＤ”を検索するために用いられるパターンの組み合わせを示す。検索キーサイズは８サブワードであり、各サブワードは１文字を格納する。検索されるワードは、４つのサブワードからなる。検索キーを検索キーレジスタにロードするとき、第１のサブワードの位置を選ぶために８つの選択肢がある。すなわち、“ＡＢＣＤ”という文字列を検索キーレジスタのサブワードのいずれかを先頭としてロードすることができる。しかし、比較ユニットの開始位置とサイズを定義できることを鑑みれば、検索されたキーと同じキーを検索キーレジスタに２回ロードすることが可能である。なぜなら、検索キーレジスタのサイズは、検索されたワードの２倍であるからである。また、検索キーレジスタのサイズをループ状に巡る（looping around）検索文字列を書くことも可能である。すなわち、検索された文字列をロードする際に、検索されたキーレジスタの最後に到達した場合、検索キーレジスタの最初のサブワードからロードを続ける。検索キーレジスタにパターンをロードするたびに、比較ユニットのサイズを検索されたパターンに適合させるために、コマンド信号はセットされる。
【００３４】
この例では、“ＡＢＣＤ”ワードを検索するために、検索キーレジスタの異なるパターンを４つだけ適用すれば良い。
【００３５】
図５において、これらの４つの検索パターンを示す。同時に、太い線により、論理レベルにセットされるコマンド信号（これらのパターンで実行される検索の各々についての１つのコマンド信号）を示す。この特定の例では、コマンド信号は、循環的な順序でセットされ、そのサイクル期間は８サブワードである。ｋは整数を表し、例えば８ｋ＋０のような記号表示は、ライン０，８，１６・・・等の全てがセットされた場合の、コマンド信号の循環的な設定を表す。
【００３６】
図５を再度参照すれば、パターン３が「一致」であることが分かる。この一致は、検索されたワードの全体での一致である。なぜなら、この検索において、追加の読み出しや検索サイクルを不要とするためにワードＡＢＣＤの全体を含む比較ユニットを定義するコマンドライン８ｋ＋２と８ｋ＋６がセットされているからである。また、ＡＢＣＤワードを見つけるために必要とされるサイクルの最大数は４である。一方、平均数は２．５サイクルである。
【００３７】
本発明にかかるＣＡＭは、メモリワードを見つけるために必要な検索サイクル数を大きく削減できることが分かる。
【００３８】
この結果、本発明にかかるＣＡＭは、従来の方法およびシステムに対して、以下の利点を有する。
【００３９】
ａ）非常に早い検索処理が可能となる、
ｂ）検索されるデータワードが、検索処理を可能とする所定の順序に従ってメモリ内に配置されていることを必要としない。
【００４０】
本発明にかかるシステムおよび方法のさらなる利点は、データをメモリ内にそのままの順序でロードすることができるので、データを格納するために必要なメモリ空間がかなり削減され、さらに、ロードに要する時間も削減されることにある。
【００４１】
信号ラインのセットは、特定のアプリケーションの必要に応じて、様々な異なる方法で実行することが可能であることは、言うまでもないであろう。
【００４２】
このように、例えば、好適な実施形態において、コマンドバスは、複数のラインを含むことがある。このラインの数は、検索キーレジスタのサブワード数の倍数である。この形態において、コマンド信号は、コマンドバスに対して循環的な接続を有しても良い。循環サイクルの長さは、コマンドバスラインの数である。このように、例えば、検索キーが８個のサブワードを含み、コマンドバスが１６本のラインを含む場合、コマンド信号Ｃ０，Ｃ１６，Ｃ３２・・・は、コマンドバスライン０に接続され、コマンドラインＣ１，Ｃ１７，Ｃ３３・・・は、コマンドバスライン１等に接続される。
【００４３】
他の好適な実施形態では、検索キーレジスタは、コマンドバスのライン数の倍数に等しい数のサブワードを含んでも良い。この第２の実施形態では、コマンド信号は、コマンドバスに対して、循環的な接続を有しても良い。循環サイクルの長さは、コマンドバスラインの数である。例えば、検索キーが８個のサブワードを含み、コマンドバスが４本のラインを含む場合、コマンド信号Ｃ０，Ｃ４，Ｃ８・・・は、コマンドバスライン０に接続され、コマンド信号Ｃ１，Ｃ５，Ｃ９・・・は、コマンドバスライン１等に接続される。
【００４４】
さらに他の好適な実施形態において、コマンド信号を、サブワードに格納された値の論理結合によりセットしても良い。この好適な実施形態に適合するアプリケーションとしては、テキスト内でのワード検索である。テキスト内では、通常は、空白、ドット、あるいは他の文字（以降、「分離記号」と称する）により、ワードが分離されている。論理回路は各サブワードに関連付けられ、サブワードが分離記号を格納する場合、論理回路の出力はセット信号となる。この信号は、そのサブワードに対するコマンド信号として用いられる。これにより、比較ユニットのサイズは、ワードサイズに適応し、ＣＡＭに格納されたテキストの各ワードが、１つの比較ユニットを定義する。
【００４５】
上述した実施形態の全てにおいて、ワードの検索は、検索されたワードを検索キー上に数回配置することによって行われる。このとき、「一致」が見つかるまで、毎回、検索キー内のワードの先頭文字の位置をシフトする。上述したように、ワード全体をロードする容量がない場合、検索キー内にワードを配置し、先頭文字の位置をシフトするとき、そのワードの残りの部分は、ループ状に巡回する方法（Looping Around fashion）で、すなわち検索キーの最初のサブワードから再出発するように、ロードされる。
【００４６】
本発明の利点の一つによれば、任意のサイズのサブワードについて適用可能であり、このサイズはＣＡＭアレイ内部で可変とすることができる。
【００４７】
本発明は、また、サブワードの全てがコマンド信号に関連付けられていない場合であっても適用可能である。この場合、ＣＡＭの仕様に応じて、非接続のサブワード位置において、その位置の特定の論理回路の状態に応じて、ワード一致信号が発行される。例えば、どのコマンド信号もサブワードSWiに関連づけられていない場合、論理回路を、あたかも固定の状態を持つコマンドラインが関連付けられているように、同等の機能を提供するように設計するようにしても良い。これにより、複数の固定位置において、固定の境界定義を実現することができる。論理回路としては、公知の任意の種類の回路を用いることが可能である。
【００４８】
本発明の方法および回路は、ＣＡＭやＣＯＭに用いられているプライオリティ回路の種類に依存しない。従って、ＣＡＭまたはＣＯＭと共に用いて、これらのデバイスに追加の機能を与え、応用分野を拡大することが可能である。
【００４９】
ここでは、本発明の原理を、メモリサブワードの増加する順について説明した。同じ原理は、メモリサブワードの減少する順についても適用可能であることは明らかである。さらに、サブワードの順序は、任意に定義することが可能であり、特に、メモリサブワードの通常のアドレスによって定義された順序と同じでなくとも良い。さらに、好適な実施形態を、検索されたデータが検索キーレジスタにロードされる方法およびシステムとして説明したが、本発明について他の設計を適用することが可能である。これにより、例えば、検索されるデータが、データラインによってサブワードに直接に接続されていても良い。
【００５０】
本発明にかかるメモリシステムの他の側面によれば、本発明は、ワード列の入力ストリーム内で、与えられたワードリスト内の１つまたは複数のワードの存在を検出するために応用することも可能である。この応用例において、ワードリストはメモリに予め格納され、コマンド信号は、格納されたワードに一致する比較ユニットを定義するようにセットされる。そして、入力ストリームは、検索キーと同じサイズのパケットによりロードされ、各パケットは、ＣＡＭ内で、予め格納されたワードと比較される。一致が発生すると、予め格納されたワードの少なくとも一つが入力ストリーム内に存在することを意味する。
【図面の簡単な説明】
【００５１】
【図１】一般的なコンテントアドレッサブルメモリ（ＣＡＭ）と、このＣＡＭにロードされたワードＡＢＣＤを含むテキストの例を示す図
【図２】検索キーレジスタにロードされ、ＣＡＭ内にロードされたデータ内でワードＡＢＣＤを見つけるためにＣＡＭ内で検索されるパターンの数を示す図
【図３】本発明のメモリシステムの構成を示す図
【図４】一つのメモリワードと、本発明のメモリシステム内で対応する回路の詳細を示す図
【図５】本発明のメモリシステム内に図１と同じデータが格納された場合に、ワードＡＢＣＤを見つけるために検索キー内にロードされるパターンの数が削減された様子を示す図
【図１】
2004526274.tif 000003
【図２】
2004526274.tif 000004
【図３】
2004526274.tif 000005
【図４】
2004526274.tif 000006
【図５】
2004526274.tif 000007
【国際公開パンフレット】
2004526274.tif 000008
2004526274.tif 000009
2004526274.tif 000010
2004526274.tif 000011
2004526274.tif 000012
2004526274.tif 000013
2004526274.tif 000014
2004526274.tif 000015
2004526274.tif 000016
2004526274.tif 000017
2004526274.tif 000018
2004526274.tif 000019
2004526274.tif 000020
2004526274.tif 000021
2004526274.tif 000022
2004526274.tif 000023
2004526274.tif 000024
2004526274.tif 000025
2004526274.tif 000026
2004526274.tif 000027
2004526274.tif 000028
2004526274.tif 000029
2004526274.tif 000030
2004526274.tif 000031
【国際調査報告】
2004526274.tif 000032
2004526274.tif 000033
2004526274.tif 000034