【手続補正書】
【提出日】平成20年1月31日(2008.1.31)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｎ（０より大きい既知の整数）個のセルを有する連想メモリ装置と、
上記連想メモリ装置のｎ個のセルにコマンドを発するコントローラとを備え、
上記コマンドは、上記ｎ個のセル内のデータを特定するために用いられるキーフィールドのサイズ及び位置を、該ｎ個のセルの各セル内で定義することを特徴とするデータ処理システム。
【請求項２】
データ処理のための連想記憶システムにおいて、
ｎ（０より大きい既知の整数）個のセルを有する連想メモリ装置と、
上記連想メモリ装置にインストラクションを発するコントローラとを備え、
上記インストラクションは、該インストラクションの実行に用いられるキーフィールドのサイズを定義することを特徴とする連想記憶システム。
【請求項３】
上記キーフィールドの定義されたサイズは、上記ｎ個のセルの全てに適用されることを特徴とする請求項２記載の連想記憶システム。
【請求項４】
データ処理のための連想記憶システムにおいて、
ｍ（０より大きい既知の整数）ビットのデータをそれぞれ記憶するｎ（０より大きい既知の整数）個のセルを有する連想メモリ装置と、
上記連想メモリ装置にインストラクションを発するコントローラとを備え、
上記インストラクションは、上記各ｎ個のセル内のいずれのｍビットが、該各ｎ個のセルのキーフィールドを表しているのかを選択的に定義することを特徴とする連想記憶システム。
【請求項５】
データ処理のための連想記憶システムにおいて、
ｍ（０より大きい既知の整数）ビットのデータをそれぞれ記憶するｎ（０より大きい既知の整数）個のセルを有する連想メモリ装置と、
上記連想メモリ装置にインストラクションを発するコントローラとを備え、
上記インストラクションは、上記発せられたインストラクションに基づいて、上記各ｎ個のセル内のいずれのｍビットがキーフィールドとして働くかを選択的に示すことを特徴とする連想記憶システム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【発明の名称】連想メモリ装置
【関連出願】
【０００１】
本出願は、現在、米国特許番号第６，７６０，８２１号が付与されている、２００１年８月１０日に出願された米国特許出願番号第０９／９２８，１５１号、発明の名称「データの検査及び処理のためのメモリエンジン（A MEMORY ENGINE FOR THE INSPECTION AND MANIPULATION OF DATA）」の優先権を主張する一部継続出願であり、更に、２００３年１２月４日に出願された米国特許出願番号第１０／７２８，２３４号、発明の名称「デカルトコントローラのためのデータ処理システム（DATA PROCESSING SYSTEM FOR A CARTESIAN CONTROLLER）」及び米国特許出願番号第１０／７２７，８１１号、発明の名称２００３年１２月４日に出願された「データ処理システムのセルエンジン（CELLULAR ENGINE FOR A DATA PROCESSING SYSTEM）」の全体は、引用により本願に援用される。
【技術分野】
【０００２】
本発明は、データ処理をするための連想記憶サポートに関し、詳しくは、データ処理速度及び柔軟性を高めるように改善された連想技術を用いたメモリエンジンに関する。
【背景技術】
【０００３】
記号(シンボル)からなる列(ストリング)を記憶したバッファ又は他のメモリ装置を検索して、与えられた、すなわち所定の記号列と一致する記号列を見つけることは、以下に限定されるものではないが、データベース、遺伝情報の処理、データ圧縮及び計算機言語の処理等の多くの分野に適用される基本処理である。新たなシーケンスを列に挿入し、又はシーケンスを削除することによって列を変更することも、これらの分野における基本処理であり、列の処理に掛かる時間は、メインアプリケーションの実行時間に直接影響を及ぼす。
【０００４】
シリアル演算を実行する場合、すなわち、Ｍ個のシンボルを含むバッファにおいて、Ｎ個のシンボルの列の出現を全て発見するための照合処理を行う場合、最大Ｎ＊Ｍ回のステップが必要になる。バッファ内に文字を挿入する必要がある場合、バッファにおいて、新たなセルの場所を空けるために、平均して半分のシンボルを１セル分右又は左にシフトさせなくてはならない。この場合、平均してＮ／２回のステップが必要である。
【０００５】
これらの処理を改良するために、ハッシング法（hashing）又はツリーデータ構造を含む幾つかの技術に基づくシリアルアルゴリズムが提案されている。ハッシング法は、対象となる列が固定長のワードの場合に用いられる。この場合、各ワードは、インデクスとして用いられる固有の番号に関連付けられて、ワードは、辞書に記憶される。この手法は、情報が固定されており、処理の間に位置を変えない場合しか機能しないという問題がある。更に、この番号を生成する処理は、高コストな処理であり、時には、幾つかのワードが同じ番号に関連付けられてしまうこともあり、この場合、検索されたワードを発見するために更なる作業が必要となる。また、バッファ内にある全ての部分列（substring）が記憶されるツリー構造であるサフィックスツリーも用いられる。ここでは、所定の列がバッファ内に存在しているかを確認する必要がある場合、列が発見され又は列がないことが確認されるまで、検索する列の１つの文字毎に、ツリーを辿る必要がある。いずれの場合も、列がＭ個のシンボルを含む場合、長さＬのバッファにその列があるかを判定するためには、最大Ｍ回のステップが必要である。この検索法は、高速であるが、サフィックスツリーの構築には、多くの場合、コンピュータ的には高価な時間が掛かる。
【０００６】
連想メモリ装置（Content Addressable Memory）、すなわちＣＡＭは、１回のメモリアクセスで所定のシンボル又はワードの位置を見つけるためのパラレルな解決策である。この手法は、固定長ワードには好適であるが、可変長の記号の列のシンボルに拡張することは困難である。バッファにおいて並行して検索を実行できる場合、すなわち、Ｍ回の比較を同時に実行できる場合、ステップの数をＮに削減することができる。列探索を高速化するために、パラレルコンパレータと、所定のシンボルに対する各比較の結果を記憶するマーカとを有するバッファも提案されている。これらの技術については、例えば、アルミー（Almy）他による米国特許番号第４，５７５，８１８号、マイヤー（Mayer）による米国特許番号第５，３１９，７６２号、エスカンダリ・ガーニン（Eskandari-Gharnin）他による米国特許番号第５，６０２，７６４号、サトー（Satoh）他による米国特許番号第５，４４８，７３３号に開示されている。これらの既知の装置は、通常、コンパレータを、実行された最後の比較の結果を記憶する１ビットのマーカと共にバッファの各セルに関連付ける。コンパレータ、メモリセル及びマーカは、バッファ内にある記号列からのシンボルがバッファの全てのコンパレータに送られるように動作する。これらのコンパレータは、所定のシンボルを関連するメモリセルに記憶されているシンボルと順番に比較する。比較の結果は、コンパレータ及びメモリセルに関連するマーカに記憶される。
【０００７】
バッファをシフトレジスタで実現することにより、内容を、クロック信号に同期して、並列に左又は右にシフトすることができる。この場合、バッファの全内容を、１回のステップでシフトすることができる。しかしながら、これらのバッファは、内容の一部だけをシフトすることができず、包括的にシフトするように動作する。更に、個別のコンパレータをバッファの各メモリセル用に一体化すると、全体として、デバイスのサイズ及び複雑性が増大し、したがって、コスト及びエネルギ消費が増大するという問題もある。
【０００８】
本発明は、上述の問題に鑑みてなされたものであり、本発明の目的は、コネックスメモリ（Connex Memory：本明細書では、ＣＭと略す。）と呼ばれる新たな種類のメモリ回路を用い、非常に高速な文字列検索、挿入及び削除を実現するメモリ装置を提供することである。
【０００９】
特に、本発明は、連想メモリと同様に動作するが、更に、これまでの連想メモリでは知られていない柔軟性を有するコネックスメモリ装置を提案する。
【００１０】
既知のデータ処理システムは、多くの場合、従来のアドレス方式を有するメモリ装置を採用している。すなわち、既知のデータシステムは、そこに定義された場所を有し、各場所が固有のアドレスを有するメモリ装置を利用する。ここでは、システムプロセッサがアドレスＡに記憶されている値に、アドレスＢに記憶されている値を追加しようとする場合、従来のメモリ装置は、メモリ装置内の特定の、アドレス指定された位置に進み、インタフェースを介してこれらの値をプロセッサに通信し、プロセッサが適切な加算処理を実行する。このようなシステムでは、一体のコンポーネントの性質及び能力、すなわち、プロセッサ及びメモリ装置の性質及び能力は、よく定義され、互いから独立している。
【００１１】
また、データ処理システムは、２つ以上のプロセッサ及びメモリ装置を含んでいてもよく、更に、これらの複数のコンポーネントは、複数のインストラクションのストリームを実行するシステムの一部であってもよいことも知られている。このようなマルチインストラクションストリーム、マルチデータストリーム（multiple instruction streams, multiple data streams device：ＭＩＭＤ）デバイスは、密接に接続されたＳＩＳＤデバイスの大きな集合であるとみなすことができ、システム内の各プロセッサは、他の統合されたプロセッサと連携しながら、より大きなタスクの特定の部分のみを請け負う。すなわち、ＭＩＭＤデバイスの有効性は、通常、解決すべき問題が、それ自体、複数の類似する相対的な個別の下位問題に解析できる領域に制限される。また、ＭＩＭＤデバイスのこれらの一体のコンポーネントの性質及び能力もまた、よく定義され、互いから区別される。
【００１２】
他の既知のデータ処理システムとしては、シングルインストラクション、マルチプルデータストリームデバイス（single instruction, multiple data streams device：ＳＩＭＤ）がある。これらのＳＩＭＤデバイスは、任意の数のプロセッサを使用し、これらのプロセッサは、全て、互いに同期して、同じプログラムを実行するが、各プロセッサは、現在のインストラクションで指定されるオペレータを異なるオペランドに適用し、この結果、それぞれ固有の結果を算出する。プロセッサは、ＳＩＭＤ機器に統合されたメモリ装置にアクセスし、オペランドを入手し、結果を記憶する。ここでも、ＳＩＭＤ機器の一体のコンポーネントの性質及び能力は、よく定義されており、互いから区別され、演算のためにメモリ装置への何らかのタイプのアクセスを有するプロセッサによって演算が実行される。
【００１３】
このように、既知のデータ処理システムは、大量のデータを処理できるが、プロセッサ及びメモリ装置の性質が定義され、不変であるために、様々な処理が遂行される速度及び効率が制限されている。
【００１４】
このため、以前に用いられていないメモリ装置の他のクラスを利用する様々なアーキテクチャも提案されている。これらのメモリ装置は、通常、「連想（associative）」メモリ装置と呼ばれ、この名の通り、データの各ビットをメモリ装置内の物理的な位置にカタログ化しない。これに代えて、連想メモリ装置は、データビットを、その性質又はそこに記憶されている情報の生来的な品質によってアドレス指定する。すなわち、連想メモリ装置内のデータは、メモリ装置内におけるそれらの物理的な位置の名称では特定されず、メモリ装置の各特定のセルに記憶されているデータのプロパティから特定される。
【００１５】
殆どの連想メモリ装置では、連想メモリ装置に記憶される全てのデータに、固定され又は限定的なサイズのキーフィールドが関連付けられる。そして、インストラクションに基づく後の処理のために、検索キーを用いて、指定された位置の如何にかかわらず、関連付けられたキーフィールドが検索キーに一致する特定のデータフィールド又は複数のデータフィールドを選択することができる。
【００１６】
これらの既知の連想メモリ装置では、記憶される全てのデータは、キーフィールドと、対応するデータフィールドとを含む。既知の連想検索及びデータ処理技術では、連想メモリ内のキーフィールドを調べ、所定のコマンドについて、対応するデータフィールドのどれが対応するデータを含むかを判定する。この判定の後、適切なキーフィールド内の１つ以上のビットの状態を変えることによって、継続的に検討される全てのデータフィールドに「タグ」又は「マーク」を付し、関連するデータフィールドが以降の検索又は処理コマンドにおいて最優先されるようにしてもよい。
【００１７】
したがって、既知の連想メモリ装置は、キーフィールドのコンテンツを観察し、対象となるデータフィールドを特定することができるコントローラを使用する。これらの既知の連想システムは、ある程度有用であるが、検索アーキテクチャの柔軟性に欠け、したがって、処理時間が長く、実用性が薄い。
【００１８】
本発明は、このような課題に鑑み、既知の連想メモリ装置の柔軟性を高め、実用性を高めると共に、処理時間を短縮させることを目的とする。
【発明の開示】
【発明が解決しようとする課題】
【００１９】
本発明の目的は、効率的なデータ処理システムを提供することである。
【００２０】
更に、本発明の他の目的は、データ処理速度及び効率を高めるアクティブ連想メモリ又は連想エンジン装置を実現するデータ処理システムのセルエンジンを提供することである。
【００２１】
更に、本発明の他の目的は、キーフィールド又はデータフィールドのいずれにおいても、如何なるセルも包括的に利用できるデータ処理システムのアクティブ連想メモリ又は連想エンジン装置を実現するセルエンジンを提供することである。更に、本発明の他の目的は、所定のコマンドのインプリメンテーションの間、連想メモリ装置のキーフィールドとデータフィールドとを区別しない、データ処理システムのアクティブ連想メモリ又は連想エンジン装置を実現するセルエンジンを提供することである。
【００２２】
更に、本発明の他の目的は、個々のセルが、それぞれの状態に基づいて、単一のクロックサイクル内で、パラレルに、所定のインストラクションを選択的に処理することができる、データ処理システムのアクティブ連想メモリ又は連想エンジン装置を実現するセルエンジンを提供することである。
【００２３】
更に、本発明の他の目的は、構造が均質であり、この結果、プログラムの実行の間、異なる時刻に全く同じ情報のピースをキーフィールド又はデータフィールド（の一部）として、メモリに記憶できるデータ処理システムのアクティブ連想メモリ又は連想エンジン装置を実現するセルエンジンを提供することである。
【００２４】
更に、本発明の他の目的は、アクティブ連想メモリ装置内で探索空間を動的に限定できる効率的なデータ処理システムのセルエンジンを提供することである。
【課題を解決するための手段】
【００２５】
本発明の一実施の形態では、データ処理システムの連想記憶サポートシステムは、ｎ個のセルを有する連想メモリ装置を備える。更に、連想記憶サポートシステムは、連想メモリ装置にインストラクションを発するコントローラを備える。更に、連想記憶サポートシステムは、連想メモリ装置及びコントローラに、１秒あたり所定の数のクロックサイクルを含む同期クロック信号を出力するクロック装置を備える。コントローラは、クロックサイクルの１つの間に、インストラクションを、ｎ個のセルの全てに対して、同時に包括的に通信し、インストラクションは、ｎ個のセルのそれぞれに等しく適用される。
【００２６】
本発明のこれらの及びこの他の目的、及び好ましい実施の形態は、以下に示す詳細な説明、添付の特許請求の範囲及び図面を参照して明らかとなる。
【発明を実施するための最良の形態】
【００２７】
コネックスメモリ（Connex Memory：ＣＭ）は、それぞれがメモリシンボルの有限集合からの値を取るワードの列を物理的にサポートし、各ワードは、更なるビットを「セット」することによって拡張され、これにより、ワードは、マークが付された状態及びマークが付されていない状態の２つの状態のいずれかにマークされる。本明細書では、用語「メモリシンボル」は、固定長の連続したビットの集合と解釈され、この長さは、アプリケーションに依存し、先験的にはセットされない。
【００２８】
本発明の構成により、現在のキャッシュメモリ技術において一般的に経験する遅延の約２倍の遅延で、全てのＣＭコマンドを１クロックサイクル内で実行することができる。本明細書において説明する構成は、より複雑な回路に繰り返し組み込むことができるスタンドアロンの回路である。図１は、本発明の一実施の形態に基づくメモリエンジン２０５の汎用のアーキテクチャを、外部のコントローラ２５５及び同期クロック回路２５６の両方との処理関係と共に示している。図１に示すように、外部のコントローラ２５５及びメモリエンジン２０５の動作は、同期クロック回路２５６から出力される共通のクロック信号を用いることによって、調整される。更に、本発明では、外部のコントローラ２５５は、メモリエンジン２０５にコマンドを発行し、及びメモリエンジン２０５からデータを受け取ることができる限り、本発明のより広い側面から逸脱することなく、様々な回路固有の構成を有することができる。
【００２９】
図２に示すように、ＣＭ２０６は、ＣＭ２０６のサイズに等しいサイズを有し、本明細書では、以下、コネックスエンジン（Connex Engine：ＣＥ）とも称するメモリエンジン２０５に制御されるバッファのプールとして組織化されたランダムアクセス装置からなるラインメモリ２００と連携する。ラインとも称するこれらのバッファの目的は、後で詳細に説明するように、ＣＭ２０６内に収容することができる長さより長い文字列に対して、検索、挿入及び削除処理を実行することであり、製造コストを低減し、消費電力を削減することである。
【００３０】
図３は、ＣＥ２０５の概略的な動作を示すフローチャートであり、処理は、ブロック３０２から開始され、このブロック３０２において、コントローラ２５５によって、検査のために予め選択された文字列が、連想ラインメモリ２０６にロードされる。文字列は、データシンボルの集合からなり、例えば、全体が完全に記憶されるまで、ラインメモリ２００内の１以上のバッファにロードされる。これにより、ラインメモリ２００内の各バッファは、文字列の異なる部分を含み、各部分は、上述したように、ＣＭ２０６のサイズと等しいサイズを有する。
【００３１】
図３のブロック３０４において、ＣＥ２０５は、検査する第１のバッファのコンテンツをデータＲＡＭバス１００を介してラインメモリ２００からＣＭ２０６にロードする。そして、ＣＭ２０６は、ブロック３０６において、コントローラ２５５から入力されるコマンドに基づいて、ロードされた文字列の一部に対する所望の文字列処理、すなわち検査を実行する。そして、ＣＭ２０６は、ブロック３０８において、検査された文字列の一部内に１つ以上のデータマーカをセットすべきかを判定し、選択的に、ブロック３０７において、必要なマーカをセットし、ブロック３０９において、マーカをリセットする。ＣＭ２０６にシフトされた所定の文字列の一部内に１つ以上のデータマーカをセットするか否かの判定は、後により詳細に説明するように、コントローラ２５５から入力される特定のコマンドに基づいて行われる。
【００３２】
ＣＭ２０６で文字列の一部を検査し、必要であれば、その中に１つ以上のマーカをセットした後に、ＣＥ２０５は、ＣＭ２０６のコンテンツを、ラインメモリ２００内の第１のバッファに戻して記憶し、第２のバッファのコンテンツをロードし、同様の処理を実行する。ＣＥ２０５は、文字列全体が処理されるまで、ＣＭ２０６にバッファから文字列の一部をロードし、ＣＭ２０６内で文字列を処理し、ＣＭ２０６のコンテンツをバッファに戻して記憶するというパターンを繰り返す。検索するシンボルの記号列に存在する極土星の度合いから、検索処理の回数が進むにつれて、ＣＭ２０６にロードされるバッファの数は、急速に減少し、処理の量は、少数のバッファに急速に限定される。
【００３３】
したがって、本発明の重要な側面は、コントローラ２５５から入力されるコマンドに応じて、セットされたマーカの存在（又は、不在）により、あるバッファを、その後の検索から除外することができるので、ラインメモリ２００内のバッファに記憶されている文字列データ全体を、繰り返し検査する必要がなくなるという点である。例えば、コントローラ２５５が発行したコマンドが、（後に詳細に説明するように）所定のデータ要素の集合を検索することをインストラクションするものであれば、ＣＭ２０６は、まず、ラインメモリ２００内のバッファ内の文字列のそれぞれを調べ、最初のデータ要素を検出すると、必要に応じてマーカをセットする。ラインメモリ２００内のバッファのその後の検査は、マーカがセットされたバッファに限定され、マーカがセットされていないバッファは除外できる。このように、本発明に基づくＣＭ２０６は、検索するデータ要素の全てのコンポーネントを含む可能性がないバッファを繰り返し検索する必要がなく、この結果、大量のデータを検査する必要性が、非常に且つ次第に減少し、これにより、高速な応答時間が実現される。
【００３４】
本発明の他の重要な側面として、ＣＭ２０６は、１クロックサイクル内において、複数の処理を並列して実行できる。したがって、ＣＭ２０６は、図３のブロック３０６、３０７、３０８、３０９等を１クロックサイクル内で並列処理することができる。このように、図３に含まれる個々のブロック、並びに添付の図面に含まれる他のブロックは、順次的に実行されるものとは解釈されず、ＣＭ２０６は、上述したように、１クロックサイクル内において、複数のブロックを並列処理することができる。
【００３５】
以下の章では、コントローラ２５５によって発行される特定のコマンドに関連して、ＣＭ２０６の動作及びＣＥ２０５の動作について、更に詳細に説明する。
【００３６】
ＣＭ２０６は、通常、コントローラ２５５からコマンド及びデータを受け取ることによって動作する。コマンドがデータオペランドを必要とする場合、例えば、現在ＣＭ２０６に記憶されている文字又はシンボル、それらの列において、所定のシンボル、すなわちデータ要素の全ての出現を検出する「検索（find）」コマンドの場合、コマンド及びシンボルの両方がＣＭ２０６に同時に供給される。ＣＭ２０６は、複数の種類のコマンドをサポートし、これらのコマンドは、主に、順方向コマンド（forward command）と、逆方向コマンド（reverse command）との２つのカテゴリに分類される。各グループは、メモリセルに関連するマーカをセット又はリセットするコマンドと、マーカがセットされたメモリセルに記憶されているワードにアクセスするコマンドと、マーカがセットされたメモリセルに記憶されているワードを変更するコマンドとの３つの種類のコマンドを含む。なお、本明細書では、記憶された各ワードに関連する１ビットのマーカを付けるが、本発明のより広い側面から逸脱することなく、複数のビットを用いて、各ワードの状態をコード化してもよい。
【００３７】
まず、順方向コマンドのグループに属すコマンドについて説明する。逆方向コマンドのグループに属するコマンドは、後述するように、この順方向コマンドのグループに属するコマンドに対して鏡像のように機能する。以下の説明において、シンボルという用語は、あらゆるビットの論理ブロックを表す。幾つかのアプリケーションでは、好ましい実施の形態として、シンボルは８ビットバイトとすることができる。他の実施の形態、例えば、ゲノム列の生物学的処理では、シンボルは、４ビットの単位（エンティティ）とすることができる。
【００３８】
順方向コマンド
列検索及び挿入処理では、入力データ列は、コマンドと共に、１シンボル（例えば文字）毎にＣＭ２０６に供給される。コマンドが検索である場合、各シンボルは、現在、ＣＭ２０６に記憶されている全てのシンボルと同時に比較される。ここでは、条件付き比較及び無条件比較の２つの種類の比較を実行できる。列の最初のシンボルは、無条件に検索され、後続するシンボルは、ＣＭ２０６において検出された前のシンボルによる条件付きで検索される。
【００３９】
処理が挿入の場合、ＣＭ２０６内の挿入点より右側のシンボルは、１ポジション分右にシフトされ、この挿入点に新たなシンボルが格納される。本発明の一実施の形態においては、挿入点は、マーカがセットされた最初のシンボルの位置である。
【００４０】
本発明の他の重要な目的は、上述したように、ＣＥ２０５のシステムアーキテクチャの効率がよく、検索及び挿入処理の両方を１クロックサイクル内で動作させることである。
【００４１】
列削除処理では、ＣＭ２０６内の削除点から連続したシンボルが読み出され、この削除点より右側の全てのシンボルが１ポジション分左にシフトされる。ここでも、削除点は、マーカがセットされた最初又は最後のメモリセルの位置である。この処理における読出及びシフトは、同時に実行され、１クロックサイクルで完了する。
【００４２】
以下、上述の処理を実施するコマンドについて説明する。
【００４３】
検索コマンド（以下、ｆｉｎｄコマンドと記す。）及び条件付き検索コマンド（以下、ｃｆｉｎｄコマンド）は、アクセスコマンドである。図３及び図４のフローチャートに示すように、ｆｉｎｄコマンドは、コントローラ２５５を介して、シンボルと共にＣＭ２０６に供給され、ＣＭ２０６は、このシンボルを、Ｍ個のメモリセルに含まれている全てのシンボルと連想的（associatively）に比較する。このｆｉｎｄコマンドの結果、コンテンツが所定のシンボルに一致するメモリセルに続く全てのメモリセルにマーカがセットされる。他の全てのマーカは、リセットされる。図３のブロック３０２〜３１４は、全てのコマンドの実行を包括的な用語で示しているが、図４のブロック３０４’、３０３及び３０５は、ｆｉｎｄコマンドの特定の実現例を示しており、この場合、後に更に詳細に説明するように、本発明の他の実施の形態に基づいて、ロードされた列の全体がＣＭ２０６内に格納される（図３のブロック３０４及び図４の対応するブロック３０４’）。図４にも示すように、ｆｉｎｄコマンドは、１クロックサイクル内で実行され、参照符号Ｅで示すように、図４のｆｉｎｄコマンドの実行の後に図３の汎用のフローチャートに戻る。以下では、例えば、ＣＭ２０６に、現在、列「ＲＯＮ  ＡＮＤ  ＲＯＢＥＲＴ」が記憶されており、マーカがセットされたシンボルを、括弧で括って表すことにする。ＣＭ２０６に対してコマンドｆｉｎｄ（Ｒ）を発行した結果、コンテンツは、「Ｒ［Ｏ］Ｎ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」に変更される。すなわち、図３のブロック３０８に示すように、検出するシンボルである「Ｒ」を含むメモリセルに続く２つのシンボル「Ｏ」の両方にマーカがセットされる。
【００４４】
「条件付き検索」のためのｃｆｉｎｄコマンドは、コマンドと共にシンボルがＣＭ２０６に供給され、ＣＭ２０６がこのシンボルの連想検索を実行するという点では、ｆｉｎｄコマンドと同様に機能するが、この場合、図５ブロック３２２に示すように、ラインメモリ２００内の前にマーカがセットされているメモリセル、すなわちバッファのみが比較される。この結果、一致したメモリセルに続くメモリセルにマーカがセットされる。他の全てのマーカは、リセットされる。上述した具体例において、両方のシンボル「Ｏ」にまだマーカがセットされたままであると仮定すると、コマンドｃｆｉｎｄ（Ｏ）は、連想比較をマークされたメモリセルだけに限定して行う。マークされたメモリセルは、いずれもシンボル「Ｏ」を含むので、比較はいずれも成功し、シンボル「Ｏ」を含むメモリセルの右隣のメモリセルにマーカがセットされ、「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」となる。ここで、コマンドｃｆｉｎｄ（Ｂ）が実行されると、２番目のマークされたメモリセルだけの比較が成功し、シンボル「Ｅ」のマーカがセットされ、「ＲＯＮ  ＡＮＤ  ＲＯＢ［Ｅ］ＲＴ」となる。この処理は、図５のブロック３２４〜３２６に示すように、全てのシンボル、すなわちデータ要素が検索されるまで続けられ、一致の成功（又は失敗）がコントローラ２５５に出力される。
【００４５】
上述の説明からも明らかなように、図３は、入力されるコマンドの全てに略適用することができる本発明の基本的な動作を示している。したがって、例えば、ブロック３０２に関連して説明した「文字列」は、発行されたコマンドの性質と、処理又は検査される特定のデータとに基づいて、１つ以上のデータ要素を含むことができる。更に、図３では、ロードされる文字列は、ＣＭ２０６内に収納できる長さよりも長い場合も考えており、したがって、検査のためにラインメモリ２００からＣＭ２０６への小刻みなシフトを必要とするが、これに当てはまらない場合もある。図４のブロック３０４’に示す他の具体例では、ＣＭ２０６に収容できるサイズの文字列をＣＭ２０６内に直接ロードする。ＣＭ２０６にロードされた文字列は、特定のコマンドに基づいて、ブロック３０３において検査され、ブロック３０５において、マーカが適切にセット又はリセットされる。
【００４６】
ＣＭ２０６が、検査するデータ全体を収納できる状況では、ＣＥ２０５及びラインメモリ２００を選択的にバイパスすることによって、処理時間及び消費されるエネルギを相当削減できることは明らかである。
【００４７】
また、本発明では、順方向読出コマンドを提案する。順方向読出コマンドにより、ＣＭ２０６は、マーカがセットされた最初の、すなわち、最も左のメモリセルに記憶されているシンボルを返す。この方法では、慣例に基づき、記憶容量をＭ個のシンボルと仮定すると、ＣＭ２０６の最も左のシンボルはアドレス０を有し、最も右のシンボルはアドレスＭ−１を有する。
【００４８】
読出処理が実行されると直ちに、読み出されたメモリセルのマーカがリセットされ、読み出されたメモリセルの１つ隣のメモリセルにマーカがセットされる。ここで、再び、ＣＭ２０６が「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含んでいると仮定する。順方向読出コマンドの結果、ＣＭ２０６によって、シンボル「Ｎ」が出力され、最も左のマーカが、「ＲＯＮ［  ］ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」に変更される。ここでは、スペース（空白）のシンボルがマークされている。図６は、この処理をブロック３３０として示しており、この処理は、順方向読出コマンドが発行された際に、図３のブロック３０８に含ませることができる。
【００４９】
また、本発明では、挿入コマンド（以下、ｉｎｓｅｒｔコマンドと記す。）を提案する。ｉｎｓｅｒｔコマンドは、シンボル「Ｘ」と共にＣＭ２０６に供給される。このｉｎｓｅｒｔコマンドは、ＣＭ２０６の最初の、すなわち最も左のマークされたメモリセルのみに有効である。シンボル「Ｘ」が挿入されると、マーカを含む最初のマークされたメモリセルの右側の全てのメモリセルのコンテンツ及び状態が、１ポジション分右にシフトされ、シンボル「Ｘ」は、最初のマークされたメモリセルの前の位置に記憶される。そして、この時点で新たなシンボルを受け取ったメモリセルのマーカがリセットされる。そして、このメモリセルの直ぐ右側のメモリセルにマーカがセットされる。例えば、ＣＭ２０６に「Ｒ［Ｏ］Ｎ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」が格納されているとすると、コマンドｉｎｓｅｒｔ（Ｘ）により、ＣＭ２０６のコンテンツは、「ＲＸ［Ｏ］Ｎ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」となる。図７は、ブロック３３２としてこの処理を示しており、この処理は、ｉｎｓｅｒｔコマンドが発行された際、図３のブロック３０８で実行してもよく、列は、ＣＭ２０６内に収納できる長さより長くてもよい。
【００５０】
また、本発明では、削除コマンド（以下、ｄｅｌｅｔｅコマンドと記す。）を提案する。ｄｅｌｅｔｅコマンドは、最初のマークされたメモリセルに記憶されているシンボルを削除し、このメモリセルの右側の全てのメモリセルのコンテンツを左にシフトする。ＣＭ２０６が「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含んでいるとすると、ｄｅｌｅｔｅコマンドにより、ＣＭ２０６は、「ＲＯ［  ］ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含む。図８は、この処理をブロック３３４として示しており、この処理は、ｄｅｌｅｔｅコマンドが発行された際に、図３のブロック３０８で実行してもよく、列は、ＣＭ２０６内に収納できる長さより長くてもよい。
【００５１】
また、本発明では、ネクストコマンド（以下、ｎｅｘｔコマンドと記す。）を提案する。ｎｅｘｔコマンドは、パラメータを有さず、最初の、すなわち最も左のマークされたメモリセルのマーカをリセットする。これにより、複数のマーカがセットされている場合、このｎｅｘｔコマンドを繰り返し用いることによって、ＣＭ２０６内の全てのマークされたメモリセルにアクセスすることができる。例えば、ＣＭ２０６が「Ｒ［Ｏ］Ｎ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」を含んでいるとすると、ｎｅｘｔコマンドを実行することにより、ＣＭ２０６のコンテンツは、「ＲＯＮ  ＡＮＤ  Ｒ［Ｏ］ＢＥＲＴ」に変更される。図９は、ブロック３３５としてこの処理を示しており、この処理は、ｎｅｘｔコマンドが発行された際に、図３のブロック３０８で実行してもよく、列は、ＣＭ２０６内に収納できる長さより長くてもよい。
【００５２】
図２に示すインデクス出力バス１３は、最初のマークされたメモリセルの線形アドレスをＣＭ２０６に供給する。例えば、ＣＭ２０６の最初の、すなわち最も左のメモリセルにマーカがセットされている場合、インデクス出力１３は、０を返す。また、２番目のメモリセルがマークされている場合、インデクス出力１３は、１を返す。また、ＣＭ２０６が列「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含み、列「ＲＯＮ」がＣＭ２０６の最も左のメモリセルに記憶されている場合、シンボル「Ｎ」は、ＣＭ２０６内のアドレス２に記憶されているので、インデクス出力１３は、２を返す。
【００５３】
また、本発明では、１回書込コマンド（以下、ｗｒｉｔｅ−ｏｎｅコマンドと記す。）を提案する。ｗｒｉｔｅ−ｏｎｅコマンドは、シンボル「Ｓ」と共にＣＭ２０６に供給され、シンボル「Ｓ」は、ＣＭ２０６の最初の、すなわち最も左のマークされたメモリセルに書き込まれる。このメモリセルのマーカは、リセットされ、後続するメモリセルにマーカがセットされる。
【００５４】
また、本発明では、全書込コマンド（以下、ｗｒｉｔｅ−ａｌｌコマンドと記す。）を提案する。ｗｒｉｔｅ−ａｌｌコマンドは、シンボル「Ｓ」と共にＣＭ２０６に供給され、シンボル「Ｓ」は、１クロックサイクル内で、ＣＭ２０６のマーカがセットされた全てのメモリセルに同時に書き込まれる。これらのメモリセルのマーカは、リセットされ、これらのメモリセルに続くメモリセルにマーカがセットされる。
【００５５】
また、本発明では、書込コマンド（以下、ｗｒｉｔｅコマンドと記す。）を提案する。ｗｒｉｔｅコマンドは、アドレスＡ及びシンボル「Ｓ」と共にＣＭ２０６に供給され、シンボル「Ｓ」は、ＣＭ２０６のアドレスＡのメモリセルに記憶される。このｗｒｉｔｅコマンドは、ランダムアクセスメモリにおける書込処理と類似している。そして、アドレスＡのメモリセルに関連するマーカがリセットされ、これに続くメモリセルにマーカがセットされる。
【００５６】
読出コマンド（以下、ｒｅａｄコマンドと記す。）は、アドレスＡと共にＣＭ２０６に供給され、ＣＭ２０６は、アドレスＡに対応したメモリセルのコンテンツを出力する。このｒｅａｄコマンドは、ランダムアクセスメモリの読出処理に類似している。この処理によってアクセスされたメモリセルのマーカは、変更されない。
【００５７】
また、本発明では、ジャンプコマンド（以下、ｊｕｍｐコマンドと記す。）を提案する。ｊｕｍｐコマンドは、同じプレフィックス及びサフィックスを有する異なる長さの文字列（すなわち、同じ２つの列から始まるシーケンス及び同じ２つの列で終わるシーケンス）がＣＭ２０６に格納されている場合にＣＭ２０６に適用される。このシーケンスの中間部分は異なっており、長さが異なる場合もある。更に、全ての列のプレフィックスの最後のシンボルがマークされる場合、ＣＭ２０６は、ジャンプと呼ばれる１つのオペランドを取る処理をサポートし、以下では、この処理を具体例を用いて説明する。
【００５８】
ＣＭ２０６は、特定のアプリケーションのためのデリミッタとして用いられる固有のシンボルを「％」として、メモリ装置の異なる部分に、２つの列「ＡＡＡ％ＢＢ％ＣＣＣＣ」及び「ＡＡＡ％ＤＤＤ％ＣＣＣＣ」を含むと仮定する。更に、例えば、コマンドｆｉｎｄ（Ａ）、コマンドｃｆｉｎｄ（Ａ）、コマンドｃｆｉｎｄ（Ａ）を実行することによってＡＡＡプレフィックスに続くマーカ「％」に関連するマーカがセットされたとする：「ＡＡＡ［％］ＢＢ％ＣＣＣＣ」「ＡＡＡ［％］ＤＤＤ％ＣＣＣＣ」。ｓをシンボルとして、コマンドｊｕｍｐ（ｓ）の目的は、マーカを、現在の位置からマークされていないＣＣＣＣサフィックスを開始する「％」シンボルにシフトし、これらをシンボル「ｓ」で置換することである。
【００５９】
例えば、コマンドｊｕｍｐ（＄）の最初の実行の後に、上述したＣＭ２０６の具体例の２つの列は、「ＡＡＡ％［Ｂ］Ｂ％ＣＣＣＣ」及び「ＡＡＡ％［Ｄ］ＤＤ％ＣＣＣＣ」に変更される。２回目のコマンドｊｕｍｐ（＄）を実行すると、列は、「ＡＡＡ％Ｂ［Ｂ］％ＣＣＣＣ」及び「ＡＡＡ％Ｄ［Ｄ］Ｄ％ＣＣＣＣ」になる。３回目のコマンドｊｕｍｐ（＄）を実行すると、列は、「ＡＡＡ％ＢＢ＄ＣＣＣＣ」及び「ＡＡＡ％ＤＤ［Ｄ］％ＣＣＣＣ」になる。４回目のコマンドｊｕｍｐ（＄）を実行すると、列は、「ＡＡＡ％ＢＢ＄ＣＣＣＣ」及び「ＡＡＡ％ＤＤＤ＄ＣＣＣＣ」になる。このように、ｊｕｍｐコマンドに基づいて、ＣＭ２０６は、以下の処理を実行する。マーカがセットされた全てのメモリセルは、そのシンボルを特定のデリミッタシンボル（この具体例ではシンボル「％」）と比較する。一致が検出された場合、特定のデリミッタをｊｕｍｐコマンド（この具体例ではシンボル「＄」）によって提供されたシンボル「ｓ」に置換し、そのメモリセルのマーカをリセットする。この他の場合、一致がなければ、そのメモリセルのマーカをリセットし、そのメモリセルの右隣のメモリセルのマーカをセットする。この結果、マーカが１ポジション分右にシフトする。図１０のブロック３３６は、ｊｕｍｐコマンドの特定の具体例を示しており、ここでは、ロードされた列の全体がＣＭ２０６内に収納されており（したがって、図３のブロック３０４及び図１０のブロック３０４’に対応する）、参照符号Ｅで示すように、図１０のｊｕｍｐコマンドの実行の後に図３の汎用のフローチャートに戻る。
【００６０】
ｊｕｍｐコマンドは、シンボルの記号列がフィールド識別子又はデリミッタと、データ値の対を含み、識別子の長さは固定されているが、データ値を含むフィールドの長さが固定されていないデータベースアプリケーションにおいて重要である。このように、本発明により、コンテンツの如何にかかわらず、文字列内の特定のデータフィールドをマークしながら、文字列内で各フィールドがランダムなサイズのデータ値を含むフィールドを検査することができる。更に、文字列内のマークされたメモリセルをそれぞれの比較は、１クロックサイクル内で実行できるため、文字列の検査を迅速且つ効率的に行うことができる。
【００６１】
本発明の他の重要な側面として、ｊｕｍｐコマンドは、文字列内のデリミッタシンボルを所定のロケータシンボルに置換する。これにより、ロケータシンボルを用いて、列の長さにかかわらず、特定のデータフィールドの最後をマークすることができ、又は、検索するデータフィールドに続くデータフィールドをマークすることができる。
【００６２】
上述したように、ｊｕｍｐコマンドにより、ＣＭ２０６に保存されている複数の文字列をパラレルに検査することができ、したがって、各文字列でデリミッタシンボルをパラレルに識別することができ、各識別及びデリミッタシンボルの選択的な置換を１クロックサイクル内で実行することができる。
【００６３】
逆方向コマンド
上述した検索、挿入及び削除メカニズムは、ＣＭ２０６の最初のマークされたメモリセルに適用されており、他のメモリセルに影響がある場合は、最初のマークされたメモリセルの右側のメモリセルに影響があった。ここで、ＣＭ２０６は、逆方向、すなわちリバース方向の検索、挿入、削除、ネクスト、インデクス処理もサポートし、これらの処理は、ＣＭ２０６の最後のマークされたメモリセルに適用される。これらの処理は、上述した順方向の検索、挿入、削除、ネクスト、インデクス処理と鏡像の関係にある。
【００６４】
逆方向ｆｉｎｄコマンドは、シンボル「ｓ」と共にＣＭ２０６に供給され、シンボル「ｓ」を含むメモリセルの左のメモリセルにマーカをセットする。他の全てのマーカは、リセットされる。ＣＭ２０６が「ＪＯＨＮ  ＡＮＤ  ＪＯＨＮＮＹ」を含む場合、コマンド逆方向ｆｉｎｄ（Ｎ）を実行することにより、以下のようにマーカがセットされる：「ＪＯ［Ｈ］Ｎ  ［Ａ］ＮＤ  ＪＯ［Ｈ］［Ｎ］ＮＹ」。
【００６５】
逆方向ｃｆｉｎｄコマンドは、逆方向の条件付き検索のコマンドであり、シンボル「ｓ」と共にＣＭ２０６に供給され、ＣＭ２０６は、マークされたメモリセルだけを連想検索する。ここでは、シンボル「ｓ」のコピーを含む全てのメモリセルの左隣のメモリセルにマーカがセットされる。全ての他のマーカは、リセットされる。ＣＭ２０６が「ＪＯ［Ｈ］Ｎ  ［Ａ］ＮＤ  ＪＯ［Ｈ］［Ｎ］ＮＹ」を含んでいる場合、コマンド逆方向ｃｆｉｎｄ（Ｈ）により、マーカは以下のように変更される：「Ｊ［Ｏ］ＨＮ  ＡＮＤ  Ｊ［Ｏ］ＨＮＮＹ」。
【００６６】
逆方向ｉｎｓｅｒｔコマンドは、シンボル「ｓ」と共にＣＭ２０６に供給されるコマンドである。最も左のマークされたメモリセル及びこのメモリセルより右側の全てのメモリセルのコンテンツは、１つ右にシフトされ、シンボル「ｓ」は、最も左のマークされたメモリセルに格納される。このメモリセルのマーカは、変化しない。例えば、「ＪＯ［Ｈ］Ｎ  ＡＮＤ  ＪＯ［Ｈ］ＮＮＹ」にＸを逆方向挿入すると、ＣＭ２０６コンテンツの新たなコンテンツは、「ＪＯ［Ｘ］ＨＮ  ＡＮＤ  ＪＯ［Ｈ］ＮＮＹ」となる。
【００６７】
逆方向ｄｅｌｅｔｅコマンドは、動作する最も左のメモリセル内のシンボルを読み出し、すなわち削除し、そのメモリセルの左側のコンテンツを１つ右にシフトする。最も左のマークされたメモリセルのマーカは、リセットされ、そのメモリセルに左側のメモリセルのマーカがセットされる。例えば、ＣＭ２０６が「ＪＯ［Ｈ］Ｎ  ＡＮＤ  ＪＯ［Ｈ］ＮＮＹ」を含んでいる場合、逆方向ｄｅｌｅｔｅコマンドを実行することによって、コンテンツは「Ｊ［Ｏ］Ｎ  ＡＮＤ  ＪＯ［Ｈ］ＮＮＹ」となる。
【００６８】
範囲限定コマンド
上述したように、ＣＭ２０６は、アドレスが、２つの更なるコマンドによってセットできる所定の数より大きいメモリセルだけに影響する処理をサポートする。処理の範囲が限界値より大きいアドレスを有するメモリセルに限定されるコマンドは、限定コマンドと呼ばれる。この場合、検索、挿入及び削除処理の範囲は、ＣＭ２０６内のＭ個のワード全体ではなく、より小さいセクションに限定される。この具体例では、ｆｉｎｄコマンド、ｃｆｉｎｄコマンド、ｉｎｓｅｒｔコマンド又はｄｅｌｅｔｅコマンドが実行されると、ＣＭ２０６のメモリセルに隣接するブロックのメモリセルだけが影響を受ける。メモリセルのこのブロックは、ＣＭ２０６のアドレス復号セクションに位置する特定のアドレスレジスタによって左端が定義され、ＣＭ２０６の最後の、すなわち最も右のメモリセルまでをその範囲とする。
【００６９】
範囲設定（set-limit）コマンドは、限定コマンドのための最も小さい限定アドレスを最初の、すなわち最も左のマークされたメモリセルに設定する。例えば、ＣＭ２０６が列「ＲＯ［Ｎ］  ＡＮＤ  ＲＯ［Ｂ］ＥＲＴ」を含む場合、最も左のマークされたシンボルは、ＣＭ２０６内のアドレス２の「Ｎ」であるので、範囲限定コマンドにより、限定アドレスは、２に設定される。
【００７０】
セットリミットアドレスは、アドレスＡと共にＣＭ２０６に供給されるコマンドであり、限定アドレスを維持する内部メモリ装置にこのアドレスを記憶する。
【００７１】
限定ｆｉｎｄコマンド、限定ｃｆｉｎｄコマンド、限定逆方向ｆｉｎｄコマンド、及び限定逆方向ｃｆｉｎｄコマンドは、ｆｉｎｄコマンド、ｃｆｉｎｄコマンド、逆方向ｆｉｎｄコマンド、及び逆方向ｃｆｉｎｄコマンドに類似するが、限定アドレス以上のアドレスを有するメモリセルに適用される限定コマンドである。
【００７２】
限定ｗｒｉｔｅ−ａｌｌコマンドは、シンボル「ｓ」と共にＣＭ２０６に供給され、ｗｒｉｔｅ−ａｌｌコマンドと同様の処理を行う。但し、限定ｗｒｉｔｅ−ａｌｌコマンドは、アドレスが限定アドレス以上のアドレスを有する全てのマークされたメモリセルのみにシンボル「ｓ」を書き込む。
【００７３】
ＣＭ２０６は、マークされたメモリセルの状態を反映する幾つかのブール信号を出力する。
（１）ＣＭ２０６内に最小の１つのマークされたメモリセルがある場合、ＣＭ２０６は、１つの信号を１にセットし、もしくは、０にセットする。
（２）全体のＣＭ２０６内にマークされたメモリセルが１つだけ存在している場合、ＣＭ２０６は、１つの信号を１にセットし、もしくは、０にセットする。
（３）最後の（順方向、逆方向、限定）ｃｆｉｎｄコマンドが失敗した場合（マーカがセットされなかった場合）、ＣＭ２０６は、１つの信号を１にセットし、幾つかのマーカをセットしている可能性があるｆｉｎｄ処理に自動的に戻る。
（４）ＣＭ２０６は、所定のバイナリパターンを有する１又は幾つかの文字の関連するマーカがセットされた場合、１つの信号を１にセットする。これらの文字は、空又は無効のシンボルの位置を表すために用いられ、処理によってセットされたマーカは、外部のコントローラ２５５によって処理する必要がある例外条件を表現する。
（５）ＣＥ２０５は、いずれのバッファもマーカがセットされたシンボルを含んでいないこと、又はＲＡＭコントローラがＣＭ２０６内の全てのバッファをロードし、ロードすべきバッファが残っていないことを示すために、１つの信号を１にセットする。
【００７４】
コネックスエンジン
上述のように、図２は、コネックスエンジン（ＣＥ）２０５を示している。コネックスエンジン２０５は、ＣＭ２０６及びランダムアクセスメモリによって実現されたラインとも呼ばれるラインメモリ２００内のバッファに保存されたシンボルの文字列を管理する。各ラインは、ＣＭ２０６と等しい容量を有し、（Ｎ＋１）ビットのＭ個のワードを格納する。ＣＥ２０５は、コンピュータ又はプロセッサ等の外部のエンティティによって制御され、ラインを含むラインメモリ２００（ＬＭ）又はバッファに／から書き込み又は読み出されるＣＭ２０６のフルコンテンツを交換することができる。書込処理は、ラインのコンテンツをＣＭ２０６に保存する。読出処理は、ＣＭ２０６のコンテンツをラインに保存する。両方の処理は、１つのサイクルで実行される。外部のプロセッサは、ｉｎｓｅｒｔコマンド又はｗｒｉｔｅコマンドを用いて、ＣＭ２０６に情報を書き込むことができ、データ入力（ｄａｔａ−ｉｎ）バス１０によってシンボルを供給することができる。ＣＥ２０５からは、２つのパスを介してシンボルを読み出すことができる。一方のパスは、ＣＭ２０６を介するパスであり、コマンドバス１４にｒｅａｄコマンドを発行し、例えば、データ出力バス１１上のシンボルを取得する。他方のパスは、実際の具体例に応じて、１又は複数のシンボルを含むワードを、ＬＭ２００のラインから直接読み出すパスである。この場合、ワードのアドレスは、ワードアドレスバス２０３を介してＣＥ２０５に供給され、ワードは、データワードバス２０４から取得される。データラム（ｄａｔａ−ｒａｍ）バス１００は、ＣＭ２０６のコンテンツをＬＭ２００の所定のラインに／から保存又は読み出すためのバスである。このバスは、Ｍ＊（Ｎ＋１）本のワイヤを有し、これにより、ＣＭ２０６の全体を１クロックサイクルで読み出し又は書き込むことができる。
【００７５】
図１６は、ＬＭ２００を構成する２つのコンポーネントのブロック図を示している。一方のコンポーネントは、ラインが格納されるランダムアクセスメモリ（random access memory：ＲＡＭ）１３０であり、他方のコンポーネントは、ＲＡＭコントローラ１２０である。ＲＡＭコントローラ１２０は、ＣＭ２０６にラインを高速に供給し、これにより、ＲＡＭ内のラインの集合に格納されたシンボルの記号列を高速に処理できる。このために、ＲＡＭコントローラ１２０は、ＲＡＭを介してパスを実行し、そこに格納されているラインの集合をスキャンし、処理のために選択されたサブセットをＣＭ２０６に供給する。ＲＡＭコントローラ１２０は、ＲＡＭ内の各ラインについて、２つのビットを記憶した状態を維持する。第１のビットは、現在のパスにおいて、関連付けられているラインをＣＭ２０６に供給するかを指定する。ＲＡＭコントローラ１２０は、自動的に及び一定の時間、ラインの連続するアドレスを生成し、このアドレスの第１のビットが１にセットされ、これらのコンテンツは、処理のためにＣＭ２０６に格納され、ＣＭ２０６から書き戻される。ＣＭ２０６によって処理されたラインがＲＡＭに戻されると、ノーフラグ（ｎｏ−ｆｌａｇ）信号１５の値は、ＲＡＭコントローラ１２０によって管理されるそのラインの第２のビットに格納される。現在のパスが終了すると、ＲＡＭコントローラ１２０は、全てのラインに関連する全ての第２のビットの値を関連する第１のビットにコピーする。このビットの新たな集合は、どのラインのマーカがセットされ、次のパスで処理するかを示す。
【００７６】
ＲＡＭ内の全てのラインが有効な情報を含んでいるわけではなく、一部のみが有効な情報を含んでいる場合であって、全てのラインが連続的に格納され、ラインアドレス０から開始されている場合、最後の有効なラインのアドレスをＲＡＭコントローラ１２０に指定し、初期のパスを有効なラインのグループに限定することができる。このアドレスは、リミットアドレス（limit-address）信号２０７を用いて、外部の処理装置によってＲＡＭコントローラ１２０に供給される。
【００７７】
ＬＭ２００のＬ本のラインの集合は、ＣＭ２０６を含む同じシリコンチップ上で実現してもよく、オフザシェルフメモリ回路（off-the-shelf memory circuitry）を用いて、シリコンチップの外部で実現してもよい。いずれの場合も、ＣＥ２０５を用いて、ラインに格納されている情報をＣＭ２０６に供給することによって、Ｌ本のラインに格納されている情報が管理され、例えば、上述したような列に対するコマンドが実行されると、ＣＭ２０６のコンテンツは、ラインに戻され、ＣＭ２０６におけるＭ個のシンボル記憶容量より遙かに長い列に対する処理を行うことができる。
【００７８】
挿入及び削除処理が必要な場合、ラインは、シンボルで満たされず、ラインの容量には余裕があるため、これらの処理の下で、ＣＭ２０６内のシンボルの列の拡大及び縮小が実現される。このような場合、有効なシンボルを含まないＣＭ２０６のメモリセルは、処理される列にはない所定のバイナリパターンによって初期化される。ＣＭ２０６は、外部の処理エンティティのために、図２に示すように、割込（interrupt）信号１０１を生成する。割込信号１０１は、この特別なバイナリパターンを含むＣＭ２０６の１又は複数のメモリセルにマーカがセットされたときに有効になる。
【００７９】
ＣＭ２０６及びその外部の接続
ここでは、２種類の接続を区別する。一方の種類は、ＣＭ２０６とその周辺との相互接続に対応し、他方の種類は、回路の拡張に必要な信号、すなわち、複数のＣＭ２０６回路を相互接続して、容量を増加させる場合に対応する。
【００８０】
以下では、ＣＭ２０６の基本的なブロックが、メモリのＭ個のワードを格納することができ、各ワードがＮ＋１ビットの長さを有し、Ｎビットがシンボルを表し、１ビットがマーカを表すと仮定する。
【００８１】
図１１に示すように、ＣＭ２０６のシステム接続は、以下の通りである。括弧内に数値が示されている場合、この数値は、各信号のビット数を表す。対数関数が用いられる場合、対数の底は２である。
・Ｄａｔａ−ｉｎ信号（Ｍ）：ＣＭ２０６内のシンボルの入力のためのＮビットワードのデータ入力信号１０。
・Ｄａｔａ−ｏｕｔ信号（Ｍ）：ＣＭ２０６からシンボルを読み出すためのＮビットワードのデータ出力信号１１。
・Ａｄｄｒｅｓｓ信号（ｌｏｇ（Ｎ））：ｌｏｇ（Ｎ）ビットのアドレス入力信号１２。ここで、ｌｏｇ（）は、２を底とする対数である。
・Ｄａｔａ−Ｒａｍ：双方向データ入力１００及びＭ＊（Ｎ＋１）ビットの出力信号。これにより、１つの記憶バッファ又はラインのコンテンツをラインメモリ２００内のラインに書き込み、又はラインから読み出すことができる。
・Ｉｎｄｅｘ（ｌｏｇ（Ｍ））：ｌｏｇ（Ｍ）ビットの出力信号１３。順方向処理又は逆方向処理のいずれが直前に実行されたかに応じて、最初の又は最後のマークされたメモリセルのアドレスを保持する。
・Ｉｎｔｅｒｒｕｐｔ信号（１）：この信号は、ＣＭ２０６によって、外部の処理エンティティのために生成され、空又は無効な条件を示すために用いられる予め定義されている特別なバイナリ構成を含む１つ以上のメモリセルにマーカがセットされたことを示す。
・Ｃｏｍｍａｎｄ信号（５）：ＣＭ２０６によって実行される処理を表すコマンドコードの５ビットの入力信号１４。
・Ｎｏ−ｆｌａｇ信号（１）：ＣＭ２０６がマークされたメモリセルを全く含んでいないことを示すバイナリの出力信号１５。
・Ｎｏ−ｅｑ信号（１）：最後の限定検索系のコマンド（順方向、逆方向又は限定ｃｆｉｎｄ）によっては、如何なるマーカもセットされなかったことを示すバイナリの出力信号１６。
・Ｏｎｅ−ｆｌａｇ信号：ＣＭ２０６がマークされたメモリセルを１つのみ含むことを示すバイナリ出力信号１７。
・ｃｌｏｃｋ：ＣＭ２０６の動作を制御するクロック信号のための入力信号２４。
【００８２】
ｄａｔａ−ｉｎ信号、ａｄｄｒ信号及びｃｏｍ信号は、関連するセットアップを有し、有効なクロックエッジに同期する。ｄａｔａ−ｏｕｔ信号、ｉｎｄｅｘ信号、ｎｏ−ｆｌａｇ信号、ｎｏ−ｅｑ信号及びｏｎｅ−ｆｌａｇ信号は、メモリへのアクセスに関連する遅延の後に安定する。この遅延は、クロック信号の有効なエッジに対して測定される。
【００８３】
複数のＣＭ２０６回路又はモジュールが１次元アレイとして相互に接続され、内部のシフトレジスタとして拡張される場合、ＣＭ２０６モジュールを線形にリンクするために幾つかの信号が用いられる。これらの信号については、図１１に示し、以下に説明する。
・Ｄａｔａ−ｌｅｆｔ−ｉｎ信号（Ｎ＋２）：前のモジュールから受け取った信号２６であり、シンボル（Ｍビット）のバイナリ表現、関連するマーカ（１ビット）及びマーカに関連するコンパレータの出力（１ビット）を表す。
・Ｄａｔａ−ｌｅｆｔ−ｏｕｔ信号（Ｎ＋２）：前のモジュールについて生成された信号２５であり、シンボル（Ｍビット）のバイナリ表現、関連するマーカ（１ビット）及びマーカに関連するコンパレータの出力（１ビット）を表す。
・Ｄａｔａ−ｒｉｇｈｔ−ｉｎ信号（Ｎ＋２）：次のモジュールから受け取った信号１９であり、シンボル（Ｍビット）のバイナリ表現、関連するマーカ（１ビット）及びマーカに関連するコンパレータの出力（１ビット）を表す。
・Ｄａｔａ−ｒｉｇｈｔ−ｏｕｔ信号（Ｎ＋２）：次のモジュールについて生成された信号１８であり、シンボル（Ｍビット）のバイナリ表現、関連するマーカ（１ビット）及びマーカに関連するコンパレータの出力（１ビット）を表す。
・Ｌｉｎｅ−ｉｎ信号（２）：Ｘトランスコーダ回路から受け取った２つの信号２３であり、構造を拡張するために用いられる。
・Ｌｉｎｅ−ｏｕｔ信号（１）：Ｘトランスコーダ回路のために生成された信号２２。
・Ｃｏｌｕｍｎ−ｉｎ信号：Ｙトランスコーダ回路から受け取った２つの信号２０であり、構造を拡張するために用いられる。
・Ｃｏｌｕｍｎ−ｏｕｔ信号：Ｙトランスコーダ回路のために生成された信号２１。
【００８４】
最後の４つの信号グループの詳細については、内部構造と題する以下の章で更に説明する。これらの８つの接続をメモリの拡張に用いない場合、ＣＭ２０６システムを適切に動作させるためには、従来の手法を用いて、これらを適切に接続及び／又は終端する必要がある。
【００８５】
ＣＭ２０６の内部構造
図１２は、ＣＭ２０６を含むメモリセル３０の２次元アレイと、この２次元アレイを他のＣＭ２０６又はＣＥ２０５回路にインタフェースする信号と、メモリセルを選択し、マークされたメモリセルの位置に関する状態情報を報告する回路とを示すブロック図である。メモリセルのアレイは、Ｎ＋１ビットのＭ個のメモリセルから構成され、２次元アレイとして組織化されている。２次元の次数は、以下の２つの理由のために選択されている。第１の理由は、シリコン領域の使用効率を最大化するためであり、第２の理由は、ＣＭ２０６内の信号の伝達に関連する遅延を最小化するためである。ＣＭ２０６は、実行されたコマンドに基づいてアドレスを符号化、復号及びトランスコードする必要があるので、ＲＡＭ回路で用いられる典型的なデコーダを用いることに代えて、トランスコーダ回路を用いる。２次元的手法では、各次元あたり１つ、合計２つのトランスコーダ回路を使用する必要がある。
【００８６】
これに代えて、本発明の広範な側面から逸脱することなく、ＣＭ２０６は、メモリセルの１次元アレイとして実現してもよい。
【００８７】
ＣＭ２０６の内部構造は、図１２に示すように、以下のサブシステムを含む。
・シンボルセル（Symbol Cell）：シンボルのためのメモリ装置又はダイナミックメモリ。メモリセルは、Ｍ個のメモリセルの２次元アレイからなる。１つのメモリセルがメモリに含まれた各シンボルに対応する（最初のメモリセルは、最初のライン上の２次元アレイの最初の列に位置する）。説明のため、表１（後述）においては、各ラインを上から下に０〜７の番号を付し、各列を左から右に０〜７の番号を付している。
・Ｄａｔａ−Ｒａｍ：Ｍ＊（Ｎ＋１）ビットの双方向のバス１００。これにより、外部データストレージに／から書き込み又は読み出すＭ個のシンボル及び関連するマーカを、ここでは、シンボルセルエリア（３０）に位置すると仮定する記憶ラインに記憶できる。この転送にかかわるラインの選択は、Ｘトランスコーダ回路３９が生成するｌｉｎｅ−ｓｅｌｅｃｔ信号１０６によって実行される。
・Ｉｎｔｅｒｒｕｐｔ信号：この１ビット信号は、空のメモリセル又は、無効のシンボルを含むメモリセルを表すために用いられる所定の固有のバイナリパターンを含むＣＭ２０６内の１又は複数のメモリセルによって生成され、これにより、このメモリセル又はこれらのメモリセルに関連するマーカがセットされる。
・Ｘ−ｔｒａｎｓｃｏｄｅｒ：Ｘトランスコーダ回路３９は、Ｙトランスコーダ回路４０と連携して、ＣＭ２０６内のメモリセルをアドレス指定し及びメモリセルにアクセスするために用いられるロジックを含む。
・Ｙ−ｔｒａｎｓｃｏｄｅｒ：Ｙトランスコーダ回路４０は、Ｙトランスコーダ回路３９と連携して、ＣＭ２０６内のメモリセルをアドレス指定し及びメモリセルにアクセスするために用いられるロジックを含む。
・２入力ＡＮＤゲート：２入力ＡＮＤゲート３４は、２つのトランスコーダ回路３９、４０が生成するｅｑ信号３６、４１を受信し、ｏｎｅ−ｆｌａｇ信号３５を生成する。
・２つのトランスコーダ回路３９、４０は、ＣＭ２０６のコンテンツを、最初のマークされたメモリセルの前に存在するメモリセルの集合、最初のマークされたメモリセル、及び最初のマークされたメモリセルから始まるメモリセルの集合の３つの領域に区切る。
【００８８】
以下に示す信号は、ＣＭ２０６回路の内部の部分に作用する。アレイがＭ個のメモリセルを含む２次元アレイであり、最小又は最大のアドレスを有するマークされたメモリセルのアドレスを算出する必要があるため、トランスコーダ回路は、以下に説明するような、ｌｉｎｅ−ｏｕｔ信号、ｌｉｎｅ−ｉｎ信号、ｃｏｌｕｍｎ−ｏｕｔ信号、ｃｏｌｕｍｎ−ｉｎ信号等の幾つかのキー信号を使用する。
・Ｌｉｎｅ−ｏｕｔ信号：ライン出力信号４２の数は、√Ｎ個である。ライン出力信号４２のそれぞれは、メモリセルの２次元アレイの１つの列に関連し、その列がマークされたメモリセルを含む場合、有効になり、この他の場合無効になる。
・Ｃｏｌｕｍｎ−ｏｕｔ信号：同様に、カラム出力信号４４は、メモリセルの２次元アレイの列に対応する√Ｎ個の番号を有する。カラム出力信号４４は、最初のアクティブなライン上に対応する列がマークされたメモリセルを含む場合、有効になり、この他の場合、無効になる。
・Ｌｉｎｅ−ｉｎ信号：ライン入力信号４３は、２√Ｎ個の番号を有する。２次元アレイの各列は、Ｘトランスコーダから２つの信号を受信し、Ｌｉｎｅ−ｉｎ［１］及びＬｉｎｅ−ｉｎ［０］は、行がマークされたメモリセルを含む最初の行であるか、行がマークされたメモリセルを含む最初の行又はその行より上の行であるかといった条件を示す。
【００８９】
例えば、表１に示すようなコンテンツを有する８×８のメモリセルの２次元アレイがあるとし、ここでは、マークされたメモリセル内のシンボルを括弧で表すとする。なお、最上列及び第１列に振られている番号は、アレイに格納されているシンボルでなく、ＣＭ２０６の行及び列にアクセスするために用いられる番号を意味する。
【００９０】
【表１】
2007536696.tif 000001
【００９１】
行０、１、２から７までの順に示されるｌｉｎｅ−ｏｕｔ信号４２は、００００１０１１となる。同じ順のＬｉｎｅ−ｉｎ信号４３のＬｉｎｅ−ｉｎ［１］信号は、００００１０００であり、Ｌｉｎｅ−ｉｎ信号４３のＬｉｎｅ−ｉｎ［０］信号は、００００１１１１である。
・Ｃｏｌｕｍｎ−ｉｎ信号４５：Ｙトランスコーダ回路４０の各列は、２つの出力信号Ｃｏｌｕｍｎ−ｉｎ信号［０］及びＣｏｌｕｍｎ−ｉｎ信号［１］に関連し、列が２次元アレイの最初のマークされたメモリセルを含む列であるか、列が最初のマークされたメモリセルを含む列に等しいか又はそれ以上のアドレスを有するかを示す。
【００９２】
表１に示した８×８の２次元アレイの具体例では、７から０への降順の列に対応する信号について、Ｃｏｌｕｍｎ−ｉｎ信号４５の値は、００１０００００及び００１１１１１１となる。
【００９３】
ＣＭ２０６の外部のメモリセルの構造
上述したｄａｔａ−ｉｎ信号、ｄａｔａ−ｏｕｔ信号及びｃｏｍ信号に加えて、図１３及び図１４に示すように、以下の信号が、シンボル及びマーカを含む基本的なメモリセルと、周辺のデバイスとの間で送受される。
・Ｄａｔａ−ｌｅｆｔ−ｏｕｔ信号：このＮ＋２ビットのＤａｔａ−ｌｅｆｔ−ｏｕｔ信号２５は、前のメモリセルに向かって伝達される情報を運び、メモリセルに記憶されている信号及び関連するマーカビットを運ぶＮ＋１ビットのｌｅｆｔ−ｃｅｌｌ−ｏｕｔ信号を含む。
・Ｌｅｆｔ−ｅｑ−ｏｕｔ信号（１）：メモリセル内のコンパレータ５５によって生成される出力信号５４。
・Ｄａｔａ−ｒｉｇｈｔ−ｏｕｔ信号（Ｎ＋２）：このＮ＋２ビットのＤａｔａ−ｒｉｇｈｔ−ｏｕｔ信号１８は、次のメモリセルに向かって伝達される情報を運び、メモリセルに記憶されている及び関連するマーカビットを運ぶＮ＋１ビットのｒｉｇｈｔ−ｃｅｌｌ−ｏｕｔ信号を含む。
・Ｒｉｇｈｔ−ｅｑ−ｏｕｔ信号（１）：メモリセル内のコンパレータ５５の出力信号。
・Ｄａｔａ−ｌｅｆｔ−ｉｎ信号（Ｎ＋２）：このＮ＋２ビットの信号２６は、前のメモリセルから受け取った情報を運び、前のメモリセルに記憶されているシンボルを関連するマーカビットと共に運ぶＮ＋１ビットのｌｅｆｔ−ｃｅｌｌ−ｉｎ信号５２及び前のメモリセル内のコンパレータ５５の出力を運ぶ１ビットのｌｅｆｔ−ｅｑ−ｉｎ信号５３を含む。
・Ｄａｔａ−ｒｉｇｈｔ−ｉｎ信号（Ｎ＋２）：このＮ＋２ビットのＤａｔａ−ｒｉｇｈｔ−ｉｎ信号は、次のメモリセルから受け取った情報を運び、次のメモリセルに記憶されているシンボルを関連するマーカビットと共に運ぶＮ＋１ビットのｒｉｇｈｔ−ｃｅｌｌ−ｉｎ信号５８及び次のメモリセル内のコンパレータ５５の出力である１ビットのｒｉｇｈｔ−ｅｑ−ｉｎ信号５６を含む。
・Ｌｉｎｅ−ｏｕｔ信号（１）は、マーカの反転値を生成するオープンドレインインバータの出力である。２次元アレイの同じライン上の全ての他のメモリセルからの全てのＬｉｎｅ−ｏｕｔ信号４２に並列に接続されており、Ｘトランスコーダ回路３９への入力の１つになる。
・Ｃｏｌｕｍｎ−ｏｕｔ信号（１）は、１ビットのＣｏｌｕｍｎ−ｏｕｔ信号４４であり、マークされたメモリセルを含む最初のラインのみについて、マーカの反転値を生成するオープンドレインインバータの出力である。２次元アレイの同じカラム内のメモリセルの全てのＣｏｌｕｍｎ−ｏｕｔ出力に並列に接続されており、Ｙトランスコーダ回路４０の入力の１つになる。
・Ｌｉｎｅ−ｉｎ信号（２）：Ｘトランスコーダ回路３９が生成するＬｉｎｅ−ｉｎ信号［１］及びＬｉｎｅ−ｉｎ信号［０］は、Ｌｉｎｅ−ｉｎ信号４３を構成する。Ｌｉｎｅ−ｉｎ信号［１］は、メモリセルが、２次元アレイの最初のマークされたメモリセルを含むラインに属することを表す。Ｌｉｎｅ−ｉｎ信号［０］は、メモリセルが、アレイの最初のマークされたメモリセルを含むラインと等しい、又はこれより大きいアドレスを有するラインに属することを表す。
・Ｃｏｌｕｍｎ−ｉｎ信号（２）：Ｙトランスコーダ回路４０が生成するＣｏｌｕｍｎ−ｉｎ信号［１］及びＣｏｌｕｍｎ−ｉｎ信号［０］は、Ｃｏｌｕｍｎ−ｉｎ信号４５を構成する。
・Ｃｏｌｕｍｎ−ｉｎ信号［１］は、メモリセルが、最初のマークされたメモリセルを含む列に属することを表す。
・Ｃｏｌｕｍｎ−ｉｎ信号［０］：メモリセルが、最初のマークされたメモリセルを含む列から始まる列に属することを表す。
・Ｎｏ−ｅｑ信号：このオープンドレインインバータの出力信号１６は、発明の概要で説明したｃｆｉｎｄタイプのコマンドが成功したときにアクティブローとなる。
・Ｓｙｍｂｏｌ−ｄａｔａ信号（Ｎ＋１）：これらの双方向のＳｙｍｂｏｌ−ｄａｔａ信号１０６により、メモリセルのコンテンツ（Ｎビットシンボル及び１ビットのマーカ）を外部のメモリ装置に／から書き込み又は読み出すことができる。
・Ｉｎｔｅｒｒｕｐｔ信号：この信号は、マーカがセットされ、記憶されたシンボルが、無効のシンボル又はメモリセルが空であることを示す所定の固有のバイナリパターンである場合に、メモリセルによって生成される。この信号は、オープンドレインドライバよって生成され、アレイ内のＭ個のメモリセルが生成したＭ個の全ての割込信号の論理和に基づき、図３の割込信号１０１が生成される。
【００９４】
メモリセルの内部構造
図１４は、メモリセルの内部構造を示し、メモリセルは、以下の回路を含む。
・レジスタＲＥＧ回路６０は、メモリセルに格納されている値及び関連するマーカビットの値を含む（Ｎ＋１）ビットレジスタである。
・ＭＵＸ−１回路６１は、Ｎ個の４入力のマルチプレクサの集合であり、ｃ１及びｃ２と呼ばれる選択コード６５、６６に応じて、幾つかの値の１つをＲＥＧに格納する。ＭＵＸ−１回路６１の可能な選択肢は以下の通りである。
【００９５】
＊ｄａｔａ−ｉｎ信号１０によって表現される外部の値
＊Ｓｙｍｂｏｌ−ｄａｔａ信号１０６によって表現される外部の値
＊ｌｅｆｔ−ｃｅｌｌ−ｏｕｔ信号５１によって運ばれる前のメモリセルからの値
＊ｒｉｇｈｔ−ｃｅｌｌ−ｉｎ信号５８によって運ばれる次のメモリセルからの値
＊レジスタＲＥＧ回路６０に格納された値。これにより、レジスタを動的に実現できる。
・ＭＵＸ−２回路６２は、４入力マルチプレクサであり、ｃ３及びｃ４と呼ばれる選択コード６７、６８に応じて、４つのビットの１つをＲＥＧの最上位ビットに格納する。ＭＵＸ−２回路６２の可能な選択肢は以下の通りである。
【００９６】
＊ＰＬＡ回路６３が生成するマーカ
＊Ｓｙｍｂｏｌ−ｄａｔａ信号１０６によって表現されるマーカビット
＊ｌｅｆｔ−ｅｑ−ｉｎ信号５３によって運ばれる前のメモリセルからのマーカ
＊ｒｉｇｈｔ−ｅｑ−ｉｎ信号５６によって運ばれる次のメモリセルからのマーカ
＊レジスタＲＥＧ回路６０に格納されたマーカ。これにより、このビットを動的に設定することができる。
・コンパレータ（ＣＯＭＰ回路）５５は、ｄａｔａ−ｉｎ信号１０の現在のシンボルがメモリセルのＮビットコンテンツに等しい場合にのみ１ビット出力上に１を生成する組合せ回路であり、この信号は、ｒｉｇｈｔ−ｃｅｌｌ−ｏｕｔ信号５９によって運ばれる。
・Ｓｙｍｂｏｌ−ｄａｔａ信号（Ｎ＋１）：このＳｙｍｂｏｌ−ｄａｔａ信号１０６は、所定のラインからメモリセルのコンテンツを運び、又は外部のメモリ装置にＲＥＧ内のＣＭ２０６メモリセルのコンテンツを運ぶ。伝送方向は、Ｒ／Ｗ信号１１２によって制御される。
・ＰＬＡアレイ回路６３は、プログラマブルロジックアレイによって実現できる組合せ回路であり、メモリセル内で用いられるｃ１、ｃ２、ｃ３、ｃ４、ｃ５、ｃ６、ｃ７、ｃ８と呼ばれるコマンドビット６５、６６、６７、６８、６９、１０９、１１０、１１１と、Ｎｏ−ｅｑ信号１６及びＣｏｌｕｍｎ−ｏｕｔ信号４４の反転値とを生成する。オープンドレインインバータ２０は、Ｎｏ−ｅｑ信号１６を駆動する。インバータ７０は、Ｃｏｌｕｍｎ−ｏｕｔ信号４４を駆動する。ＰＬＡ回路６３には、以下のような幾つかの入力信号が供給される。
【００９７】
＊ＣＭ２０６によって実行されるコマンド（ｆｉｎｄ、ｃｆｉｎｄ、ｉｎｄｅｘ等）のバイナリ表現を運ぶコマンド信号１４
＊レジスタＲＥＧ回路６０の値
＊ｌｅｆｔ−ｅｑ−ｉｎ信号５３によって運ばれる前のメモリセルのコンパレータ５５の出力
＊ｒｉｇｈｔ−ｅｑ−ｉｎ信号５６によって運ばれる次のメモリセルのコンパレータ５５の出力
＊Ｎｏ−ｅｑ信号１６
＊Ｘトランスコーダが生成するＬｉｎｅ−ｉｎ信号４３及びＹトランスコーダ回路４０が生成するＣｏｌｕｍｎ−ｉｎ信号４５
ＰＬＡ回路６３は、レジスタＲＥＧ回路６０が、未使用の又は無効のメモリセルをマークするために用いられる所定のシンボルを含む場合及びレジスタＲＥＧ回路６０に関連しているマーカがセットされた場合に有効になる割込信号１０１を生成する。
【００９８】
レジスタＲＥＧ回路６０のＮビット出力は、レジスタＲＥＧ回路６０に格納されているシンボルを表し、信号ｃ５（６９）によって制御されるＮ個のトライステート反転ドライバ７１によって反転され、ｄａｔａ−ｏｕｔ信号１１になる。オープンドレインインバータ６４は、レジスタＲＥＧ回路６０に格納されているマーカビットを反転させ、Ｌｉｎｅ−ｏｕｔ信号４２を生成する。オープンドレインインバータは、ＰＬＡ回路６３に由来するＮｏ−ｅｑ信号１６を生成する。オープンドレインインバータ７０は、Ｃｏｌｕｍｎ−ｏｕｔ信号４４を生成する。理論的には、２次元アレイ内の異なるメモリセルからの全てのｄａｔａ−ｏｕｔ信号１１及びＮｏ−ｅｑ信号１６は、互いに連結され、１つのラインに属する全てのＬｉｎｅ−ｏｕｔ信号４２も互いに連結され、同じ列上のメモリセルの全てのＣｏｌｕｍｎ−ｏｕｔ信号４４も互いに連結される。
【００９９】
トランスコーダ
図１５は、２つのトランスコーダ回路３９、４０の構成を示している。Ｘトランスコーダ回路には、以下の信号が供給される。
【０１００】
＊Ｌｉｎｅ−ｏｕｔｓ信号４２：√Ｎビットを含み、それぞれが２次元アレイのメモリセルの各行から出力されたこれらの信号は、ライン上にマークされたメモリセルが存在することを示すために使用される。
【０１０１】
＊Ａｄｄｒｅｓｓ−ｈｉｇｈ信号９６：ｌｏｇ（Ｎ）／２ビットを含み、ＣＭ２０６に供給されるアドレスの前半を表し、２次元アレイ内の√Ｎ個のラインから１つのラインを選択するために用いられる。
【０１０２】
＊５ビットコマンド信号１４：範囲設定（ｓｅｔ−ｌｉｍｉｔ）コマンド、アドレス範囲設定（ｓｅｔ−ｌｉｍｉｔ−ａｄｄｒｅｓｓ）コマンド、限定検索（ｌｉｍｉｔｅｄ−ｆｉｎｄ）コマンド、限定条件付き検索（ｌｉｍｉｔｅｄ−ｃｆｉｎｄ）コマンド、限定逆方向検索（ｌｉｍｉｔｅｄ−ｒｅｖｅｒｓｅ−ｆｉｎｄ）コマンド、限定逆方向条件付き検索（ｌｉｍｉｔｅｄ−ｒｅｖｅｒｓｅ−ｃｆｉｎｄ）コマンド、限定全書込（ｌｉｍｉｔｅｄ−ｗｒｉｔｅ−ａｌｌ）コマンド、ＲＡＭ読出（ｒａｍ−ｒｅａｄ）コマンド、ＲＡＭ書込（ｒａｍ−ｗｒｉｔｅ）コマンド等の二次的コマンドの実現のためのみに用いられる。
【０１０３】
Ｙトランスコーダ回路４０には、以下の信号が供給される。
【０１０４】
＊Ｃｏｌｕｍｎ−ｏｕｔｓ信号４４：それぞれがメモリセルの２次元アレイの各列からの１つのカラムに対応し、関連するカラムに関してマークされたメモリセルの出現を示す√ＭビットのＣｏｌｕｍｎ−ｏｕｔｓ信号。マークされたメモリセルは、メモリセルが属すラインの最初のマークされたメモリセルである。
【０１０５】
＊ａｄｄｒｅｓｓ−ｌｏｗ信号９７：所定のラインを選択するために用いられるアドレスの後半を表す√Ｍビットの信号。
【０１０６】
＊先に列挙した二次的コマンドの実現のためだけに用いられる５ビットのコマンド信号
両方のトランスコーダは、以下の回路を備える。
・Ｘトランスコーダ回路３９においてアドレス信号の前半を復号するために用いられる又はＹトランスコーダにおいて、アドレス信号の後半を復号するために用いられるデコーダＤＣＤ８３
・√Ｍ個の双方向マルチプレクサから構成され、ｃ９ビット９２を選択信号として用いるＭＵＸ−３回路８２
・論理関数ＯＲ（論理和）のためのプレフィックスネットワークＰＮ−ＯＲ回路９１
・ラッチ回路８５は、ＰＮ−ＯＲ信号の出力をラッチし、限定的な処理のためにＣＭ２０６のアクティブな部分を区切るために用いられる。ロードコマンドとしてｃ７ビット９３を用いる。
・ＭＵＸ−４回路８７は、ＭＵＸ−３回路８２と同じ構造を有し、選択信号としてｃ８ビット９４を用いる。
・線形ネットワークＸＯＲ−１回路８６：√Ｍ個の排他的論理和ゲートを用いて、ＭＵＸ−４回路８７によるバイナリコンフィグレーション出力における最初に出現した１を判定する。
・優先度エンコーダＰＥ８０は、ＸトランスコーダにおけるＬｉｎｅ−ｏｕｔｓ信号４２又はＹトランスコーダにおけるＣｏｌｕｍｎ−ｏｕｔｓ信号４４を符号化し、インデクスフィールドの前半を生成するＸトランスコーダのｉｎｄｅｘ−ｈｉｇｈ３８又はインデクスフィールドの後半を生成するＹトランスコーダのｉｎｄｅｘ−ｌｏｗ４６を生成する。
・ＲＰＥ優先度エンコーダ８１は、ＰＥ優先度エンコーダ８０と同じ入力を逆順に受け取り、これにより、ｃ−ｉｎｄｅｘフィールドの前半及び後半を生成する。
・ＰＬＡアレイ回路８４は、小さい組合せ論理ブロックであり、プログラマブルロジックアレイによって実現され、コマンド信号１４を復号し、トランスコーダ回路を制御するために用いられるｃ９ビット９２、ｃ１０ビット９３、ｃ１１ビット９４、ｃ１２ビット９５を生成する。
・ＸＯＲ−２回路８９は、ｐ／２入力ＡＮＤゲート８８に供給され、ｅｑ信号３６を生成するｐ／２ビット値を生成する。このｅｑ信号は、インデクスの前半であるｉｎｄｅｘ−ｈｉｇｈ９８とＸトランスコーダ回路３９内のＲＰＥ回路８１が生成した反転されたインデクスの前半のコンテンツと比較した結果、又はインデクスの後半であるｉｎｄｅｘ−ｌｏｗ９９とＹトランスコーダ回路４０内のＲＰＥ回路８１が生成した反転されたインデクスの後半のコンテンツと比較した結果を示す。
【０１０７】
ＲＡＭコントローラ
図１６は、ＲＡＭコントローラ１２０の実現例を示し、図１７は、ＲＡＭコントローラ１２０の内部構造を示す回路図である。ＲＡＭコントローラは、ＲＡＭに格納された各ラインについて、２ビットのメモリ装置を維持する。最初のビットは、ＲＡＭの各ラインについてＬビットを格納するレジスタＡＲ２０８に格納される。Ｌビットのコンテンツは、優先度エンコーダＰ−ＥＮＣ２１０に供給され、優先度エンコーダＰ−ＥＮＣ２１０は、１にセットされた最小の重みのビットのバイナリ表現を出力する。優先度エンコーダ２１０の出力は、ラインアドレス２０１であり、これは、次のＣＭ２０６に対する読出又は書込処理のために選択されるＲＡＭ内のラインのアドレスである。例えば、ＡＲは、００１０１１１０を含む場合、Ｐ−ＥＮＣは、ラインアドレスに０１０を出力し、これは、１にセットされるＡＲの最下位ビットのアドレスである。また、ラインアドレス２０１は、マルチプレクサＭＵＸ−７（２１３）の０入力端子に供給され、マルチプレクサＭＵＸ−７（２１３）は、適切に選択されると、ラインアドレス信号のコンテンツをデコーダＡＤＣＤ２１４に供給する。このデコーダは、１個が有効で、Ｌ−１個が無効となるＬ個の出力を有する。有効な出力は、ＡＲ２０８における最下位の１ビットと同じ重みを有し、この重み又はアドレスは、Ｐ−ＥＮＣ２１０によって出力される。例えば、ラインアドレスが０１０である場合、ＡＤＣＤ２１４は、００００００１０を生成し、１にセットされたビットは、重み２を有する。ＡＤＣＤ２１４が出力するＬ個の信号は、Ｌ個のＸＯＲゲート２１５によって、ＡＲ２０８によるＬビット出力と排他的論理和処理され、ＡＲに格納されているバイナリパターンと同じバイナリパターンが生成され、ここで、ＡＲにおける最下位の１ビットは、０にセットされる。同じ具体例を用いれば、ＡＲが００１０１１１０を含む場合、Ｐ−ＥＮＣは、０１０を出力し、ＡＤＣＤに供給されて００００００１０になり、００１０１１１０との排他的論理和によって、００１０１１００となり、ここで、０ビットは、ＡＲのコンテンツと、ＸＯＲゲート２１５の出力との間の相異を示す。ＸＯＲゲート２１５の出力は、マルチプレクサＭＵＸ−６（２０９）を介して、レジスタＡＲに供給され、ステップイネーブル信号２２２が有効である場合、次のクロックサイクルにおいて、格納される。この信号は、ｃｏｍグループの信号２０２の一部であり、ＣＥ２０５を制御する外部の処理エンティティに制御される。
【０１０８】
ＡＲ、Ｐ−ＥＮＣ、ＭＵＸ−７、ＡＤＣＤ、Ｌ個のＸＯＲゲート及びＭＵＸ−６の組合せは、ＡＲにバイナリ形式で格納される数Ｋから開始されると、ラインアドレスに和がＫに等しい２の逐次累乗を出力する回路を構成する。更に、この回路は、ステップイネーブル信号の制御下で一定の間隔で、２の各累乗を生成する。ＡＲレジスタから全ての１ビットがなくなると、優先度エンコーダは、この状態を検出し、停止信号２２１を有効にし、これにより、外部の処理エンティティは、現段階で、これ以上のラインを処理する必要がないと判定する。この装置は、ループ処理で、２進数の１にセットされた全てのビットの連続する重みを自動的に生成し、各重みを１サイクルで出力する。
【０１０９】
このように、レジスタＡＲにおける１が連続的に消去される間、ＣＭ２０６において、ラインが処理され、列処理が実行される。これらの処理の最後に、ＣＭ２０６のコンテンツがラインに戻されると、ｎｏ−ｆｌａｇ信号１５の値が反転され、ｉｎｉｔ信号２２４と論理和処理され、ＬＤ−ｆｌｉｐ−ｆｌｏｐ２１８の１つであるＤ−ｆｌｉｐ−ｆｌｏｐに記録される。Ｌ個のグループにおいて選択されたフリップフロップのアドレスは、ＲＡＭ内のラインのアドレスと同じであり、フリップフロップの選択は、後述するように、ＡＤＣＤ回路２１４の出力を利用して実行される。これらのＬ個のフリップフロップは、処理の次のパスで処理する必要がある次のラインのグループを表す１及び０の新たなパターンを格納する。
【０１１０】
ＲＡＭコントローラを初期化するためには、処理する必要があるＲＡＭのラインのみの関連するＡＲビットが１にセットされるように、ＡＲのビットに１を格納する必要がある。これらの有効なラインは、ＲＡＭにおける連続するアドレスによって、隣接するブロックに格納され、ブロックにおける最小のアドレスは、０である。例えば、ＲＡＭ内の３つのラインだけが有効である場合、ＡＲレジスタの最下位の３ビットを１にセットし、他の全てのビットを０にセットする。この場合、有効なラインのアドレスは、０、１、２であるため、最も大きいアドレスを有するラインのアドレスは、２である。この場合、制御側の外部のエンティティは、最も大きいラインのアドレスをリミットアドレス信号２０７としてＲＡＭコントローラに送信し、ｉｎｉｔ信号２２４をアクティブ化する。これにより、ｌｉｍｉｔ−ａｄｄｒｅｓｓ信号パス上のｌｏｇ（Ｌ）個のアドレスは、マルチプレクサＭＵＸ−７を介して、ＡＤＣＤによってｌｉｍｉｔ−ａｄｄｒｅｓｓ信号のコンテンツに等しい重みを有する１つ以外は全てが０のＬ個の信号に復号される。
【０１１１】
マルチプレクサＭＵＸ−７の出力は、ｐｒｅｆｉｘ−ＯＲ回路ＯＲ−ＰＮ２１６に供給され、ｐｒｅｆｉｘ−ＯＲ回路ＯＲ−ＰＮ２１６は、値が０であり、唯一の１ビットの重みより小さい重みを有する全てのビットを１に変換する。例えば、ＯＲ−ＰＮ回路２１６に０００００１００が供給され、１ビットの重みが２である場合、ＯＲ−ＰＮ回路２１６は、０００００１１１を出力する。そして、これらのＬ個の信号は、Ｌ個のＯＲゲート２１９を介して、Ｌ個Ｄ−ｆｌｉｐ−ｆｌｏｐｓ２１８のＤ−ｉｎｐｕｔに供給される。Ｌ個のＤ−ｆｌｉｐ−ｆｌｏｐｓ２１８は、ＡＤＣＤ回路が生成するＬ個の信号によって個別にイネーブルにされ、ｉｎｉｔ信号２２４と個別に論理和処理される。１の出力がそれぞれＲＡＭの有効なラインに対応するＬ個のｆｌｉｐ−ｆｌｏｐｓ２１８のコンテンツは、マルチプレクサＭＵＸ−６（２０９）を制御するスタート信号をアクティブ化することによってレジスタＡＲ２０８にロードさる。
【０１１２】
図１８に示すように、ＣＥ２０５は、アクティブセル又は処理要素のアレイで構成され、コネックスメモリ（ＣＭ）２０６及び複数のベクトル４００を含むランダムアクセスメモリ（ＲＡＭ）として実現され、各ベクトルは、ＣＭ２０６と同じ記憶容量を有し、したがって、ＣＭ２０６の全体のコンテンツを選択的に記憶できる。すなわち、ＣＥ２０５は、ｎ個のメモリセル及びコントローラ２５５によって制御される関連するベクトル４００を有するＣＭ２０６を備える。本発明の一実施の形態においては、ベクトル４００の目的は、ＣＭ２０６内に格納できる長さより長い列に対して検索、挿入及び削除処理を実行し、後により詳細に説明するように、実現コスト及び消費電力を低減することである。
【０１１３】
ＣＥ２０５に供給されるコードは、コントローラ２５５によって実行される。ＣＥ２０５とコントローラ２５５の間のインタフェースは、図１８に示す、以下のような４つの特別なレジスタを利用する。
・ＩＮＲ４０１−データ入力レジスタ：一実施の形態では、全てのＣＥ２０５インストラクションは、（コントローラ２５５が提供する）ＩＮＲ４０１から、必要に応じて、（即座に）データ引数を取得する。
・ＯＵＴＲ４０４−「マークがセットされていない」ビット及び値を含むデータ出力。少なくとも１つのメモリセルがマークされている場合、ＯＵＴＲ４０４は、最初のマークされたメモリセルに格納されている値に続いて０を格納する。この他の場合、ＯＵＴＲ４０４は、個別の具体例に応じた特定の値、例えば、「１１・・・１」に続いて１を格納する。
・ＯＰＲ４０６−現在のＣＥ２０５インストラクションのインストラクションコードを格納するインストラクションレジスタ（ソースは、コントローラ２５５インストラクション内の専用フィールドである）。
・ＶＡＲ４０８−ベクトルメモリのためのアドレスレジスタ。ＶＡＲ４０８レジスタは、特別なコントローラ２５５インストラクションによって更新され、ベクトルを明示的に操作するインストラクションに引数として用いられる。また、ＶＡＲ４０８レジスタは、メモリセルに関連する汎用レジスタに関係する全ての処理の実行にも用いられる。
【０１１４】
更に図１８に示すように、入力／出力ライン４１０を選択的に用いて、ＣＭ２０６の両端にアクセスすることができる。本明細書では、入力／出力ライン４１０を以下のように表す。
・ｌｅｆｔ＿ｉｎ４１２＝｛ｗ，ｍａｒｋ，ｅｑ，ｆｉｒｓｔ｝：デフォルトでは、全てが０である（ｅｑ＝１とは、メモリセル内の２つのオペランドが等しいことを意味する。ｆｉｒｓｔ＝１は、メモリセルが最初のマークされたメモリセルであることを意味する）。
・ｌｅｆｔ＿ｏｕｔ４１４＝｛ｗ，ｍａｒｋ，ｅｑ，ｆｉｒｓｔ｝：最初のメモリセルから供給される。
【０１１５】
なお、ＣＥ２０５は、本発明のより広い側面から逸脱することなく、コントローラ２５５がＣＥ２０５にコマンドを発行でき、ＣＥ２０５からデータを受け取ることができる限り、回路固有の様々な構成を有することができる。したがって、本発明の重要な側面として、ＣＭ２０６内の各ｍビットセルは、データを格納することに加えて、データを能動的に処理できる必要がある。データ処理は、各ｍビットセル内で実行してもよく、又は所定のメモリセルの左隣又は右隣のメモリセルに影響を与えることによって実行してもよい。なお、このように、ＣＭ２０６内の各ｍビットセルの機能を強化することによって、本発明は、他のデータ処理システムの性能を超える、より複雑なシステムレベルの振る舞いを実現する。
【０１１６】
本発明のこの他の重要な側面として、本発明では、条件の一部又は属性として、各メモリセルを「マークし」、そのメモリセル自身又はＣＭ２０６内で隣接メモリセルに対して、次のタスクを実行し又はオペランドを実行するメモリセルとして指定することによって、ＣＭ２０６内のセルレベルでデータを能動的に処理することができる。
【０１１７】
また、本発明に基づくデータ処理システムの生来的な利点として、セルエンジン内の各メモリセルは、１クロックサイクル内でインストラクションを同時に実行するだけではなく、局所的な状態情報及び包括的な状態情報の両方を用いて、包括的にブロードキャストされたインストラクションを実行するメモリセルを動的に限定することができる。特に、これまでに知られていない新たな手法として、個々のセルレベルでマーカビットを用いることによって、連想メモリ内の実際のメモリセルが、マークされたメモリセルの左又は右のメモリセルに影響を与えることができる。このように、本発明は、連想メカニズムによって、すなわち、特別に指定された位置アドレスではなく、ＣＭ２０６内の個々のメモリセルのコンテンツの性質又はプロパティによって、システムレベルにおけるマークされた状態の選択的なアクティブ化又は変更を実現する。
【０１１８】
このように、本発明では、処理及びメモリを非常に緊密なレベルで結合し、すなわち、ＣＭ２０６の個々のメモリセルは、その処理のために、個別のメモリブロックにアクセスする必要がない。更に、セルレベルにおいて、オペランドがローカル空間に常駐するため、処理結果は、適切な場所に維持され、通信及び処理時間を短縮でき、シリコン領域を節約でき、消費電力を低減できる。
【０１１９】
また、ＣＭ２０６の容量は、キーフィールド又はデータフィールドのいずれかの一部として、ｎ個のメモリセル内に記憶されるビットの任意の部分を選択的に利用されるため、ＣＭ２０６の柔軟性が高まる。すなわち、キーフィールド及びデータフィールドが厳密に定義される既知の連想メモリアーキテクチャとは異なり、ＣＭ２０６は、発行されたコマンド及び望まれる処理の性質に基づいて、メモリ内に記憶されるビットのどの部分をキーフィールドビット又はデータフィールドビットであるとみなしてもよい。
【０１２０】
図１９は、典型的な連想メモリ５００のコンテンツを示している。図１９は、１２個の列を含むメモリセルの１個の行を有する連想メモリ装置を簡略化して示している。本発明は、このようなアーキテクチャに限定されるわけではなく、実際に、より多くのメモリセルのより複雑なアレイを想定しており、図１９は、説明のために例示的に用いるに過ぎない。
【０１２１】
図１９に示すように、この具体例では、６列のキーフィールド５０２及び８列のデータフィールド５０４を示している。キーフィールド５０２及びデータフィールド５０４の実際の長さ又はサイズは、設計における選択の問題であり、既知の連想メモリエンジンは、全てのコマンド及び処理を通して、これらの２つのフィールドの間の区別を維持する。すなわち既知の連想メモリ装置では、キーフィールド及びデータフィールドの性質及びサイズが固定されている。具体例として、連想メモリを用いて高速データベースを実現し、データフィールドは、例えば、従業員に関する情報等の特定のデータコンテンツを表し、キーフィールドは、従業員の姓を表すと仮定する。典型的な連想メモリのコントローラは、単純なコマンドに基づき、キーフィールド５０２を検索し、「スミス（Smith）」に一致するかを判定し、実際に検索したいデータをデータフィールド５０４を得るために、キーフィールド５０２に「スミス」が含まれる全てのデータフィールド５０４に「タグ」を付し、検索されたデータの存在又は不在を示す。なお、この具体例では、キーは、６列以内でなくてはならない。
【０１２２】
一方、本発明のメモリエンジンでは、キーフィールドとデータフィールドの間の区別はなく、したがって、コントローラは、発行されたコマンドに基づいて、キーフィールド５０２又はデータフィールド５０４のいずれかに含まれているいずれのメモリセルもキーの一部であると包括的に解釈及び評価することができる。
【０１２３】
なお、既知の連想データ処理システムと、本発明との間の違いは、構造の１つではなく、ソフトウェア及び発行されるコマンドのインプリメンテーションにある。すなわち、本発明では、コントローラは、発行された特別なコマンドに基づいて、連想メモリ装置内の全てのメモリセルを「キー」の一部又は「データ」の一部として選択的に解釈することができる。したがって、特定のメモリセルの「キー」としてのプロパティ又は「データ」としてのプロパティは、コマンド自体で表現され、連想メモリ装置の構造的な組織の機能ではない。
【０１２４】
図２０に示すように、コントローラは、１４セル行を有する１４セルの連想メモリ５１０において、特定のコマンドに関して（破線で示す、従来の手法であればキーフィールドとみなされる範囲内にある）セル２において、検索されたデータを検出することもでき、又は（破線で示す、従来の手法であればデータフィールドとみなされる範囲内にある）セル９において、検索されたデータを検出することもできる。したがって、本発明の連想メモリエンジンは、既知の連想メモリエンジンより遙かに柔軟性が高いことは明らかである。
【０１２５】
本発明によって、連想メモリ装置において、キーフィールドとデータフィールドとの間の区別が事実上なくなるため、メモリエンジンのプログラミング能力が著しく向上する。
【０１２６】
従業員の姓に関する上述した具体例で説明したような既知の連想記憶システムは、特定の用途に特化され、カスタマイズされるため、このシステムでは、根本的に異なる構造（例えば、１６列の鍵及び１０２４列のデータ）を有するデータを検索又は識別することができない。これとは対照的に、本発明では、キーフィールドとデータフィールドとを全く区別しないため、本発明は、個々のコマンドに基づいて、何を「キー」とするかについて、性質を選択的に再定義するので、本発明によって、本質的に汎用的な連想メモリシステムを実現することができる。
【０１２７】
具体例として、本発明に基づくデータ処理をするための連想記憶サポートシステムでは、まず、例えば、５セルのキーを用いて、全社員の姓を特定することができる。そして、コントローラが発行した次のコマンドでは、例えば２セルのキー等に基づいて、他の種類のデータを検索することもできる。このように、既知の連想記憶システムの場合とは異なり、本発明では、用途毎にマシンを再設計及び特化させる必要がない。すなわち、本発明では、発行されたコマンド毎に各キーを個別化でき、したがって、本発明は、キー及びコンテンツを単に選択するだけで、特化されたデータを選択的に検索できる汎用の連想メモリをサポートする。
【０１２８】
この点に関して、図３〜図１０を用いて上述したコマンドの実現例は、ＣＭ２０６内のキーフィールドとデータフィールドの間の従来の区別を取り除き、又は無視できるメモリエンジンの固有の能力に、少なくとも部分的に、依存している。
【０１２９】
また、メモリ装置は、ビットの位置にかかわらず、及びキーフィールドとデータフィールドを区別することなく、ｎ個のメモリセルのそれぞれの全てのビットを使用できるので、コントローラ２５５は、ＣＭ２０６内のｎ個のメモリセルのそれぞれに、１つのクロックサイクル内で所定のコマンドを包括的にブロードキャストでき、また、ｎ個のメモリセルのそれぞれは、発行されたコマンドを単一のクロックサイクル内で処理できる。
【０１３０】
以上、好ましい実施の形態を用いて発明を説明したが本発明の基本的な範囲から逸脱することなく、これらの実施の形態を様々に変更し、実施の形態における要素を等価物で置換できることは当業者にとって明らかである。したがって、本発明は、ここに開示した特定の実施の形態に限定されず、添付の特許請求の範囲に含まれる全ての実施の形態を含む。
【図面の簡単な説明】
【０１３１】
【図１】本発明の一実施の形態に基づく、外部コントローラ及びクロック要素を含むメモリエンジンの汎用のアーキテクチャを示すブロック図である。
【図２】図１のメモリエンジンを、メモリエンジンの構成要素間で情報を交換するための異なるバスと共に示すブロック図である。
【図３】図１のメモリエンジンの包括的な処理の一実施の形態を示すフローチャートである。
【図４】図１のメモリエンジンの包括的な処理の他の実施の形態を示すフローチャートである。
【図５】図１のメモリエンジンによるｃｆｉｎｄコマンドの処理を示すフローチャートである。
【図６】図１のメモリエンジンによるｒｅａｄコマンドの処理を示すフローチャートである。
【図７】図１のメモリエンジンによるｉｎｓｅｒｔコマンドの処理を示すフローチャートである。
【図８】図１のメモリエンジンによるｄｅｌｅｔｅコマンドの処理を示すフローチャートである。
【図９】図１のメモリエンジンによるｎｅｘｔコマンドの処理を示すフローチャートである。
【図１０】図１のメモリエンジンによるｊｕｍｐコマンドの処理を示すフローチャートである。
【図１１】メモリエンジンのメモリ装置を周辺装置にインタフェースし、幾つかのメモリ装置を相互に接続するために必要な入力信号及び出力信号を示すブロック図である。
【図１２】２つのトランスコーダ回路を介して静的及び動的メモリセルの２次元アレイにアクセスするメモリ装置の内部構造の一実施の形態を示すブロック図である。
【図１３】メモリセルを周辺装置に動的にインタフェースする入力信号及び出力信号を示すブロック図である。
【図１４】発明の一実施の形態に基づき、シンボル及び関連するマーカを記憶し、読み出し、放送されたシンボルと比較するためのシンボル及び関連するマーカのためのストレージ(メモリ装置)を含むメモリセルの内部のアーキテクチャを示す回路図である。
【図１５】メモリセルの２次元アレイにアクセスでき、最初の又は最後のマークされたメモリセルのアドレスを生成する本発明の一実施の形態に基づく図１２に示すトランスコーダ回路の内部のアーキテクチャを示す回路図である。
【図１６】ランダムアクセスメモリ（ＲＡＭ）とＲＡＭコントローラの組合せとしてバッファメモリのコンテンツを示す回路図である。
【図１７】図１６に示すＲＡＭコントローラの内部構造を示す回路図である。
【図１８】図１に示すメモリエンジンをより詳細に示すブロック図である。
【図１９】典型的な連想メモリ装置のコンテンツを示す図である。
【図２０】キーフィールドとデータフィールドの間の従来の区別がなくなった連想メモリ装置のコンテンツを示す図である。