(57)【要約】  データ処理システムの連想記憶サポートシステムは、ｎ個のセルを有する連想メモリ装置を備える。連想記憶サポートシステムは、連想メモリ装置に命令を出すコントローラを備える。連想記憶サポートシステムは、連想メモリ装置及びコントローラに、１秒あたり所定の数のクロックサイクルを含む同期クロック信号を出力するクロック装置を備える。コントローラは、クロックサイクルの１つの間に、命令を、ｎ個のセルの全てに対して、同時に包括的に通信し、命令は、ｎ個のセルのそれぞれに等しく適用される。
2007536696.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システムの連想記憶サポートシステムにおいて、
ｎ個のセルを有する連想メモリ装置と、
上記連想メモリ装置に命令を出すコントローラと、
上記連想メモリ装置及び上記コントローラに、１秒あたり所定の数のクロックサイクルを含む同期クロック信号を出力するクロック装置とを備え、
上記コントローラは、上記クロックサイクルの１つの間に、上記命令を、上記ｎ個のセルの全てに対して、同時に包括的に通信し、
上記命令は、上記ｎ個のセルのそれぞれに等しく適用される連想記憶サポートシステム。
【請求項２】
データ処理システムの連想記憶サポートシステムにおいて、
ｎ個のセルを有する連想メモリ装置と、
上記連想メモリ装置のｎ個のセルにコマンドを発するコントローラとを備え、
上記コマンドは、上記ｎ個のセル内でデータを特定するために用いられるキーフィールドの構成を定義する連想記憶サポートシステム。
【請求項３】
データ処理システムの連想記憶サポートシステムにおいて、
ｎ個のセルを有する連想メモリ装置と、
上記連想メモリ装置に命令を出すコントローラと、
上記命令は、該命令の実行時に用いられるキーフィールドのサイズ及び性質を定義する連想記憶サポートシステム。
【請求項４】
上記キーフィールドは、上記ｎ個のセルの全てに適用されることを特徴とする請求項３記載の連想記憶サポートシステム。
【発明の詳細な説明】
【関連出願】
【０００１】
本出願は、現在、米国特許番号第６，７６０，８２１号が付与されている、２００１年８月１０日に出願された米国特許出願番号第０９／９２８，１５１号、発明の名称「データの検査及び処理のためのメモリエンジン（A MEMORY ENGINE FOR THE INSPECTION AND MANIPULATION OF DATA）」の優先権を主張する一部継続出願であり、更に、２００３年１２月４日に出願された米国特許出願番号第１０／７２８，２３４号、発明の名称「デカルトコントローラのためのデータ処理システム（DATA PROCESSING SYSTEM FOR A CARTESIAN CONTROLLER）」及び米国特許出願番号第１０／７２７，８１１号、発明の名称２００３年１２月４日に出願された「データ処理システムのセルエンジン（CELLULAR ENGINE FOR A DATA PROCESSING SYSTEM）」の全体は、引用により本願に援用される。
【技術分野】
【０００２】
本発明は、データ処理をするための連想記憶サポートに関し、詳しくは、データ処理速度及び柔軟性を高めるように改善された連想技術を用いたメモリエンジンに関する。
【背景技術】
【０００３】
文字列を表すシンボルを含むバッファ又は他のメモリ装置を検索し、与えられた又は所定のシンボルの文字列を照合する処理は、以下に限定されるものではないが、データベース、遺伝情報の処理、データ圧縮及び計算機言語の処理等の多くの分野に適用される基本処理である。新たなシーケンスを文字列に挿入し、又はシーケンスを削除することによって文字列を変更することも、これらの分野における基本処理であり、文字列処理に掛かる時間は、メインアプリケーションの実行時間に直接影響を及ぼす。
【０００４】
シリアル演算を実行する場合、すなわち、Ｍ個のシンボルを含むバッファにおいて、Ｎ個のシンボルの文字列の全ての出現を発見するための照合処理では、最大Ｎ＊Ｍ回のステップが必要になる。バッファ内に文字を挿入する必要がある場合、バッファにおいて、新たなセルの場所を空けるために、平均して半分のシンボルを１セル分右又は左に移動させなくてはならない。この場合、平均してＮ／２回のステップが必要である。
【０００５】
これらの処理を改善するために、ハッシュ法又はツリーデータ構造を含む幾つかの技術に基づくシリアルアルゴリズムが提案されている。ハッシュ法は、対象となる文字列が固定長のワードの場合に用いられる。この場合、各ワードは、インデクスとして用いられる固有の番号に関連付けられ、ワードは、辞書に保存される。この手法は、情報が固定されており、処理の間に位置を変えない場合しか機能しないという問題がある。更に、この番号を生成する処理は、高コストな処理であり、幾つかのワードが同じ番号に関連付けられてしまうこともあり、この場合、検索されたワードを発見するために更なる負荷が必要となる。また、バッファ内にある全てのサブ文字列（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 000003
【００９１】
行０、１、２から７までの順に示されるｌｉｎｅ−ｏｕｔ信号４２は、００００１０１１となる。同じ順のＬｉｎｅ−ｉｎ信号４３のＬｉｎｅ−ｉｎ［１］信号は、００００１０００であり、Ｌｉｎｅ−ｉｎ信号４３のＬｉｎｅ−ｉｎ［０］信号は、００００１１１１である。
・Ｃｏｌｕｍｎ−ｉｎ４５：Ｙトランスコーダ回路４０の各列は、２つの出力信号Ｃｏｌｕｍｎ−ｉｎ［０］及びＣｏｌｕｍｎ−ｉｎ［１］に関連し、列が２次元アレイの最初のマークされたセルを含む列であるか、列が最初のマークされたセルを含む列に等しいか又はそれ以上のアドレスを有するかを示す。
【００９２】
表１に示した８×８の２次元アレイの具体例では、７から０への降順の列に対応する信号について、Ｃｏｌｕｍｎ−ｉｎ信号４５の値は、００１０００００及び００１１１１１１となる。
【００９３】
ＣＭ２０６の外部のセルの構造
上述したｄａｔａ−ｉｎ、ｄａｔａ−ｏｕｔ及びｃｏｍ信号に加えて、図１３及び図１４に示すように、以下の信号が、シンボル及びマーカを含む基本的なセルと、周辺のデバイスとの間で送受される。
・Ｄａｔａ−ｌｅｆｔ−ｏｕｔ：このＮ＋２ビット信号２５は、前のセルに向かって伝送される情報を搬送し、セル及び関連するマーカビットに保存されているシンボルを搬送するＮ＋１ビットのｌｅｆｔ−ｃｅｌｌ−ｏｕｔ信号を含む。
・Ｌｅｆｔ−ｅｑ−ｏｕｔ（１）：セル内のコンパレータ５５によって生成される出力信号５４。
・Ｄａｔａ−ｒｉｇｈｔ−ｏｕｔ（Ｎ＋２）：このＮ＋２ビット信号１８は、次のセルに向かって伝送される情報を搬送し、セル及び関連するマーカビットに保存されているシンボルを搬送するＮ＋１ビットのｒｉｇｈｔ−ｃｅｌｌ−ｏｕｔ信号を含む。
・Ｒｉｇｈｔ−ｅｑ−ｏｕｔ（１）：セル内のコンパレータの出力信号５５。
・Ｄａｔａ−ｌｅｆｔ−ｉｎ（Ｎ＋２）：このＮ＋２ビット信号２６は、前のセルから受け取った情報を搬送し、前のセルに保存されているシンボルを関連するマーカビットと共に搬送するＮ＋１ビットのｌｅｆｔ−ｃｅｌｌ−ｉｎ信号５２及び前のセル内のコンパレータ５５の出力を搬送する１ビットのｌｅｆｔ−ｅｑ−ｉｎ信号５３を含む。
・Ｄａｔａ−ｒｉｇｈｔ−ｉｎ（Ｎ＋２）：このＮ＋２ビット信号は、次のセルから受け取った情報を搬送し、次のセルに保存されているシンボルを関連するマーカビットと共に搬送するＮ＋１＋ビットのｒｉｇｈｔ−ｃｅｌｌ−ｉｎ信号５８及び次のセル内のコンパレータ５５の出力である１ビットのｒｉｇｈｔ−ｅｑ−ｉｎ信号５６を含む。
・Ｌｉｎｅ−ｏｕｔ（１）は、マーカの逆の値を生成するドレイン開放型出力である。２次元アレイの同じライン上の全ての他のセルからの全てのＬｉｎｅ−ｏｕｔ信号４２に並列に接続されており、Ｘトランスコーダ回路３９への入力の１つになる。
・Ｃｏｌｕｍｎ−ｏｕｔ（１）は、１ビット信号４４であり、マークされたセルを含む第１のラインのみについて、マーカの逆の値を生成するドレイン開放型出力である。２次元アレイの同じ列内のセルの全てのＣｏｌｕｍｎ−ｏｕｔ出力に並列に接続されており、Ｙトランスコーダ回路４０の入力の１つになる。
・Ｌｉｎｅ−ｉｎ（２）：Ｘトランスコーダ回路３９が生成するＬｉｎｅ−ｉｎ［１］及びＬｉｎｅ−ｉｎ［０］は、Ｌｉｎｅ−ｉｎ信号４３を構成する。Ｌｉｎｅ−ｉｎ［１］は、セルが、２次元アレイの最初のマークされたセルを含むラインに属することを表す。Ｌｉｎｅ−ｉｎ［０］は、セルが、アレイの最初のマークされたセルを含むラインと等しい、又はこれより大きいアドレスを有するラインに属することを表す。
・Ｃｏｌｕｍｎ−ｉｎ（２）：Ｙトランスコーダ回路４０が生成するＣｏｌｕｍｎ−ｉｎ［１］及びＣｏｌｕｍｎ−ｉｎ［０］は、Ｃｏｌｕｍｎ−ｉｎ信号４５を構成する。
・Ｃｏｌｕｍｎ−ｉｎ［１］は、セルが、最初のマークされたセルを含む列に属することを表す。
・Ｃｏｌｕｍｎ−ｉｎ［０］：セルが、最初のマークされたセルを含む列から始まる列に属することを表す。
・Ｎｏ−ｅｑ：このドレイン開放型の出力信号１６は、発明の概要で説明したｃｆｉｎｄタイプのコマンドが成功したときにアクティブローとなる。
・Ｓｙｍｂｏｌ−ｄａｔａ（Ｎ＋１）：これらの双方向信号１０６により、セルのコンテンツ（Ｎビットシンボル及び１ビットマーカ）を外部のストレージ装置に／から書き込み又は読み出すことができる。
・Ｉｎｔｅｒｒｕｐｔ：この信号は、マーカがセットされ、保存されたシンボルが、無効のシンボル又はセルが空であることを示す予め定義された固有のバイナリパターンである場合に、セルによって生成される。この信号は、ドレイン開放型ドライバよって生成され、アレイ内のＭ個のセルが生成したＭ個の全ての割込信号の論理和に基づき、図３の割込信号１０１が生成される。
【００９４】
セルの内部構造
図１４は、セルの内部構造を示し、セルは、以下の回路を含む。
・ＲＥＧ回路６０は、セルに保存されている値及び関連するマーカビットの値を含む（Ｎ＋１）ビットレジスタである。
・ＭＵＸ−１回路６１は、Ｎ個の４入力のマルチプレクサの集合であり、ｃ１及びｃ２と呼ばれると呼ばれる選択コード６５、６６に応じて、幾つかの値の１つをＲＥＧに保存する。ＭＵＸ−１回路６１の可能な選択肢は以下の通りである。
【００９５】
＊ｄａｔａ−ｉｎ信号１０によって表現される外部の値
＊Ｓｙｍｂｏｌ−ｄａｔａ信号１０６によって表現される外部の値
＊ｌｅｆｔ−ｃｅｌｌ−ｏｕｔ信号５１によって搬送される前のセルからの値
＊ｒｉｇｈｔ−ｃｅｌｌ−ｉｎ信号５８によって搬送される次のセルからの値
＊レジスタＲＥＧ６０に保存された値。これにより、レジスタを動的に実現できる。
・ＭＵＸ−２回路６２は、４入力マルチプレクサであり、ｃ３及びｃ４と呼ばれる選択コード６７、６８に応じて、４つのビットの１つをＲＥＧの最上位ビットに格納する。ＭＵＸ−２回路６２の可能な選択肢は以下の通りである。
【００９６】
＊ＰＬＡ６３が生成したマーカ
＊Ｓｙｍｂｏｌ−ｄａｔａ信号１０６によって表現されるマーカビット
＊ｌｅｆｔ−ｅｑ−ｉｎ信号５３によって搬送される前のセルからのマーカ
＊ｒｉｇｈｔ−ｅｑ−ｉｎ信号５６によって搬送される次のセルからのマーカ
＊レジスタＲＥＧ６０に保存されたマーカ。これにより、このビットを動的に設定することができる。
・ＣＯＭＰ回路５５は、ｄａｔａ−ｉｎ信号１０の現在のシンボルがセルのＮビットコンテンツに等しい場合にのみ１ビット出力上に１を生成する組合せ回路であり、この信号は、ｒｉｇｈｔ−ｃｅｌｌ−ｏｕｔ信号５９によって搬送される。
・Ｓｙｍｂｏｌ−ｄａｔａ（Ｎ＋１）：この信号１０６は、所定のラインからセルのコンテンツを搬送し、又は外部のストレージエンティティにＲＥＧのＣＭ２０６セルのコンテンツを搬送する。伝送方向は、Ｒ／Ｗ信号１１２によって制御される。
・ＰＬＡアレイ回路６３は、プログラマブルロジックアレイによって実現できる組合せ回路であり、セル内で用いられるｃ１、ｃ２、ｃ３、ｃ４、ｃ５、ｃ６、ｃ７、ｃ８と呼ばれるコマンドビット６５、６６、６７、６８、６９、１０９、１１０、１１１と、Ｎｏ−ｅｑ信号１６及びＣｏｌｕｍｎ−ｏｕｔ信号４４の逆の値とを生成する。ドレイン開放型のインバータ２０は、Ｎｏ−ｅｑ信号１６を駆動する。インバータ７０は、Ｃｏｌｕｍｎ−ｏｕｔ信号４４を駆動する。ＰＬＡ６３には、以下のような幾つかの入力信号が供給される。
【００９７】
＊ＣＭ２０６によって実行されるコマンド（ｆｉｎｄ、ｃｆｉｎｄ、ｉｎｄｅｘ等）のバイナリ表現を搬送するコマンド信号１４
＊レジスタＲＥＧ６０の値
＊ｌｅｆｔ−ｅｑ−ｉｎ信号５３によって搬送される前のセルのコンパレータ５５の出力
＊ｒｉｇｈｔ−ｅｑ−ｉｎ信号５６によって搬送される次のセルのコンパレータ５５の出力
＊Ｎｏ−ｅｑ信号１６
＊Ｘトランスコーダが生成するＬｉｎｅ−ｉｎ信号４３及びＹトランスコーダ回路が生成するＣｏｌｕｍｎ−ｉｎ信号４５
ＰＬＡ６３は、レジスタＲＥＧ６０が、未使用の又は無効のセルをマークするために用いられる予め定義されたシンボルを含む場合及びレジスタＲＥＧ６０に関連しているマーカがセットされた場合に有効になる割込信号１０１を生成する。
【００９８】
レジスタＲＥＧ６０のＮビット出力は、レジスタＲＥＧ６０に格納されているシンボルを表し、信号ｃ５（６９）によって制御されるＮ個のトライステート反転ドライバ７１によって反転され、ｄａｔａ−ｏｕｔ信号１１になる。ドレイン開放型インバータ６４は、レジスタＲＥＧ６０に保存されているマーカビットを反転させ、Ｌｉｎｅ−ｏｕｔ信号４２を生成する。ドレイン開放型インバータは、ＰＬＡ６３に由来するＮｏ−ｅｑ信号１６を生成する。ドレイン開放型のインバータ７０は、Ｃｏｌｕｍｎ−ｏｕｔ信号４４を生成する。理論的には、２次元アレイ内の異なるセルからの全てのｄａｔａ−ｏｕｔ信号１１及びＮｏ−ｅｑ信号１６は、互いに連結され、１つのラインに属す全てのＬｉｎｅ−ｏｕｔ信号４２も互いに連結され、同じ列上のセルの全てのＣｏｌｕｍｎ−ｏｕｔ信号４４も互いに連結される。
【００９９】
トランスコーダ
図１５は、２つのトランスコーダ回路３９、４０の構成を示している。Ｘトランスコーダ回路には、以下の信号が供給される。
【０１００】
＊Ｌｉｎｅ−ｏｕｔｓ信号４２：√Ｎビットを含み、それぞれが２次元アレイのセルの各行から出力されたこれらの信号は、ライン上にマークされたセルが存在することを示すために使用される。
【０１０１】
＊Ａｄｄｒｅｓｓ−ｈｉｇｈ信号９６：ｌｏｇ（Ｎ）／２ビットを含み、ＣＭ２０６に供給されるアドレスの前半を表し、２次元アレイ内の√Ｎ個のラインから１つのラインを選択するために用いられる。
【０１０２】
＊５ビットコマンド信号１４：範囲設定（ｓｅｔ−ｌｉｍｉｔ）、アドレス範囲設定（ｓｅｔ−ｌｉｍｉｔ−ａｄｄｒｅｓｓ）、限定検索（ｌｉｍｉｔｅｄ−ｆｉｎｄ）、限定条件付き検索（ｌｉｍｉｔｅｄ−ｃｆｉｎｄ）、限定逆方向検索（ｌｉｍｉｔｅｄ−ｒｅｖｅｒｓｅ−ｆｉｎｄ）、限定逆方向条件付き検索（ｌｉｍｉｔｅｄ−ｒｅｖｅｒｓｅ−ｃｆｉｎｄ）、限定全書込（ｌｉｍｉｔｅｄ−ｗｒｉｔｅ−ａｌｌ）、ＲＡＭ読出（ｒａｍ−ｒｅａｄ）、ＲＡＭ書込（ｒａｍ−ｗｒｉｔｅ）等の二次的コマンドの実現のためのみに用いられる。
【０１０３】
Ｙトランスコーダ回路４０には、以下の信号が供給される。
【０１０４】
＊Ｃｏｌｕｍｎ−ｏｕｔｓ信号４４：それぞれがセルの２次元アレイの各列からの１つの列に対応し、関連する列に関してマークされたセルの出現を示す√Ｍビットの信号。マークされたセルは、セルが属すラインの最初のマークされたセルである。
【０１０５】
＊ａｄｄｒｅｓｓ−ｌｏｗ信号９７：所定のラインを選択するために用いられるアドレスの後半を表す√Ｍビットの信号。
【０１０６】
＊先に列挙した二次的コマンドの実現のためだけに用いられる５ビットのコマンド信号
両方のトランスコーダは、以下の回路を備える。
・Ｘトランスコーダ回路３９においてアドレス信号の前半を復号するために用いられる又はＹトランスコーダにおいて、アドレス信号の後半を復号するために用いられるデコーダＤＣＤ８３
・√Ｍ個の双方向マルチプレクサから構成され、ｃ９ビット９２を選択信号として用いるＭＵＸ−３回路８２
・論理関数ＯＲ（論理和）のためのプレフィックスネットワークＰＮ−ＯＲ回路９１
・ラッチ回路回路８５は、ＰＮ−ＯＲ信号の出力をラッチし、限定的な処理のためにＣＭ２０６のアクティブな部分を区切るために用いられる。ロードコマンドとしてｃ７ビット９３を用いる。
・ＭＵＸ−４回路８７は、ＭＵＸ−３回路８２と同じ構造を有し、選択信号としてｃ８ビット９４を用いる。
・線形ネットワークＸＯＲ−１回路８６：√Ｍ個の排他的論理和ゲートを用いて、ＭＵＸ−４回路８７によるバイナリコンフィグレーション出力における最初の１の出現を判定する。
・優先度エンコーダＰＥ８０は、ＸトランスコーダにおけるＬｉｎｅ−ｏｕｔｓ信号４２又はＹトランスコーダにおけるＣｏｌｕｍｎ−ｏｕｔｓ信号４４を符号化し、インデクスフィールドの前半を生成するＸトランスコーダのｉｎｄｅｘ−ｈｉｇｈ３８又はインデクスフィールドの後半を生成するＹトランスコーダのｉｎｄｅｘ−ｌｏｗ４６を生成する。
・ＲＰＥ優先度エンコーダ８１は、ＰＥ優先度エンコーダ８０と同じ入力を逆順に受け取り、これにより、ｃ−ｉｎｄｅｘフィールドの前半及び後半を生成する。
・ＰＬＡアレイ回路８４は、小さい組合せ論理ブロックであり、プログラマブルロジックアレイによって実現され、コマンド信号１４を復号し、トランスコーダ回路を制御するために用いられるｃ９ビット９２、ｃ１０ビット９３、ｃ１１ビット９４、ｃ１２ビット９５を生成する。
・ＸＯＲ−２回路８９は、ｐ／２入力ＡＮＤゲート８８に供給され、ｅｑ信号３６を生成するｐ／２ビット値を生成する。このｅｑ信号は、インデクスｉｎｄｅｘ−ｈｉｇｈ９８の前半をＸトランスコーダ回路３９内のＲＰＥ優先度エンコーダ８１が生成した逆のインデクスの前半のコンテンツと比較した結果、又はインデクスｉｎｄｅｘ−ｌｏｗ９９の後半をＹトランスコーダ回路４０内のＲＰＥ回路８１が生成した逆のインデクスの後半のコンテンツと比較した結果を示す。
【０１０７】
ＲＡＭコントローラ
図１６は、ＲＡＭコントローラ１２０の実現例を示し、図１７は、ＲＡＭコントローラ１２０の内部構造を示す回路図である。ＲＡＭコントローラは、ＲＡＭに保存された各ラインについて、２ビットのストレージを維持する。第１のビットは、ＲＡＭの各ラインについてＬビットを格納するレジスタＡＲ２０８に保存される。Ｌビットのコンテンツは、優先度エンコーダＰ−ＥＮＣ２１０に供給され、優先度エンコーダＰ−ＥＮＣ２１０は、１に設定された最小の重みのビットのバイナリ表現を出力する。優先度エンコーダ２１０の出力は、ラインアドレス２０１であり、これは、次のＣＭ２０６に対する読出又は書込処理のために選択されるＲＡＭのラインのアドレスである。例えば、ＡＲは、００１０１１１０を含む場合、Ｐ−ＥＮＣは、ラインアドレスに０１０を出力し、これは、１に設定されるＡＲの最下位ビットのアドレスである。また、ラインアドレス２０１は、マルチプレクサＭＵＸ−７（２１３）の０入力端子に供給され、マルチプレクサＭＵＸ−７（２１３）は、適切に選択されると、ラインアドレス信号のコンテンツをデコーダＡＤＣＤ２１４に供給する。このデコーダは、１個が有効で、Ｌ−１個が無効となるＬ個の出力を有する。有効な出力は、ＡＲ２０８における最下位の１ビットと同じ重みを有し、この重み又はアドレスは、Ｐ−ＥＮＣ２１０によって出力される。例えば、ラインアドレスが０１０である場合、ＡＤＣＤ２１４は、００００００１０を生成し、１に設定されたビットは、重み２を有する。ＡＤＣＤ２１４が出力するＬ個の信号は、Ｌ個のＸＯＲゲート２１５によって、ＡＲ２０８によるＬビット出力と排他的論理和処理され、ＡＲに保存されているバイナリパターンと同じバイナリパターンが生成され、ここで、ＡＲにおける最下位の１ビットは、０に設定される。同じ具体例を用いれば、ＡＲが００１０１１１０を含む場合、Ｐ−ＥＮＣは、０１０を出力し、ＡＤＣＤに供給されて００００００１０になり、００１０１１１０との排他的論理和によって、００１０１１００となり、ここで、０ビットは、ＡＲのコンテンツと、ＸＯＲゲート２１５の出力との間の相異を示す。ＸＯＲゲート２１５の出力は、マルチプレクサＭＵＸ−６（２０９）を介して、レジスタＡＲに供給され、ステップイネーブル信号２２２が有効である場合、次のクロックサイクルにおいて、保存される。この信号は、ｃｏｍグループの信号２０２の一部であり、ＣＥ２０５を制御する外部の処理エンティティに制御される。
【０１０８】
ＡＲ、Ｐ−ＥＮＣ、ＭＵＸ−７、ＡＤＣＤ、Ｌ個のＸＯＲゲート及びＭＵＸ−６の組合せは、ＡＲにバイナリ形式で保存される数Ｋから開始されると、ラインアドレスに和がＫに等しい２の逐次累乗を出力する回路を構成する。更に、この回路は、ステップイネーブル信号の制御の下で一定の間隔で、２の各累乗を生成する。ＡＲレジスタから全ての１ビットがなくなると、優先度エンコーダは、この状態を検出し、停止信号２２１を有効にし、これにより、外部の処理エンティティは、現段階で、これ以上のラインを処理する必要がないと判定する。この装置は、ループ処理で、２進数の１にセットされた全てのビットの連続する重みを自動的に生成し、各重みを１サイクルで出力する。
【０１０９】
このように、レジスタＡＲにおける１が連続的に消去される間、ＣＭ２０６において、ラインが処理され、文字列処理が実行される。これらの処理の最後に、ＣＭ２０６のコンテンツがラインに戻されると、ｎｏ−ｆｌａｇ信号１５の値が反転され、ｉｎｉｔ信号２２４と論理和処理され、ＬＤ−ｆｌｉｐ−ｆｌｏｐ２１８の１つであるＤ−ｆｌｉｐ−ｆｌｏｐに記録される。Ｌ個のグループにおいて選択されたフリップフロップのアドレスは、ＲＡＭのラインのアドレスと同じであり、フリップフロップの選択は、後述するように、ＡＤＣＤ回路２１４の出力を利用して実行される。これらのＬ個のフリップフロップは、処理の次のパスで処理する必要がある次のラインのグループを表す１及び０の新たなパターンを格納する。
【０１１０】
ＲＡＭコントローラを初期化するためには、処理する必要があるＲＡＭのラインのみの関連するＡＲビットが１にセットされるように、ＡＲのビットに１を保存する必要がある。これらの有効なラインは、ＲＡＭにおける連続するアドレスによって、隣接するブロックに保存され、ブロックにおける最小のアドレスは、０である。例えば、ＲＡＭの３つのラインだけが有効である場合、ＡＲレジスタの最下位の３ビットを１にセットし、他の全てのビットを０にセットする。この場合、有効なラインのアドレスは、０、１、２であるため、最も大きいアドレスを有するラインのアドレスは、２である。この場合、制御側の外部のエンティティは、最も大きいラインのアドレスをリミットアドレス信号２０７としてＲＡＭコントローラに送信し、ｉｎｉｔ信号２２４をアクティブ化する。これにより、ｌｉｍｉｔ−ａｄｄｒｅｓｓ信号パス上のｌｏｇ（Ｌ）個のアドレスは、マルチプレクサＭＵＸ−７を介して、ＡＤＣＤによってｌｉｍｉｔ−ａｄｄｒｅｓｓ信号のコンテンツに等しい重みを有する１つ以外は全てが０のＬ個の信号に復号される。
【０１１１】
マルチプレクサＭＵＸ−７の出力は、ｐｒｅｆｉｘ−ＯＲ回路ＯＲ−ＰＮ２１６に供給され、ｐｒｅｆｉｘ−ＯＲ回路ＯＲ−ＰＮ２１６は、値が０であり、唯一の１ビットの重みより小さい重みを有する全てのビットを１に変換する。例えば、ＯＲ−ＰＮ回路２１６に０００００１００が供給され、１ビットの重みが２である場合、ＯＲ−ＰＮ回路２１６は、０００００１１１を出力する。そして、これらのＬ個の信号は、Ｌ個のＯＲゲート２１９を介して、Ｌ個Ｄ−ｆｌｉｐ−ｆｌｏｐｓ２１８のＤ−ｉｎｐｕｔに供給される。Ｌ個のＤ−ｆｌｉｐ−ｆｌｏｐｓ２１８は、ＡＤＣＤ回路が生成するＬ個の信号によって個別にイネーブルにされ、ｉｎｉｔ信号２２４と個別に論理和処理される。１の出力がそれぞれＲＡＭの有効なラインに対応するＬ個のｆｌｉｐ−ｆｌｏｐｓ２１８のコンテンツは、マルチプレクサＭＵＸ−６（２０９）を制御するスタート信号をアクティブ化することによってレジスタＡＲ２０８にロードさる。
【０１１２】
図１８に示すように、ＣＥ２０５は、アクティブセル又は処理要素のアレイで構成され、コネックスメモリ（ＣＭ）２０６及び複数のベクトル４００を含むランダムアクセスメモリ（ＲＡＭ）として実現され、各ベクトルは、ＣＭ２０６と同じ記憶容量を有し、したがって、ＣＭ２０６の全体のコンテンツを選択的に保存できる。すなわち、ＣＥ２０５は、ｎ個のセル及びコントローラ２５５によって制御される関連するベクトル４００を有するＣＭ２０６を備える。本発明の一実施の形態においては、ベクトル４００の目的は、ＣＭ２０６内に格納できる長さより長い文字列に対して検索、挿入及び削除処理を実行し、後により詳細に説明するように、実現コスト及び消費電力を低減することである。
【０１１３】
ＣＥ２０５に供給されるコードは、コントローラ２５５によって実行される。ＣＥ２０５とコントローラ２５５の間のインタフェースは、図１８に示す、以下のような４つの特別なレジスタを利用する。
・ＩＮＲ４０１−データ入力レジスタ：一実施の形態では、全てのＣＥ２０５命令は、（コントローラ２５５が提供する）ＩＮＲ４０１から、必要に応じて、（即座に）データ引数を取得する。
・ＯＵＴＲ４０４−「マークがセットされていない」ビット及び値を含むデータ出力。少なくとも１つのセルがマークされている場合、ＯＵＴＲ４０４は、最初のマークされたセルに格納されている値に続いて０を格納する。この他の場合、ＯＵＴＲ４０４は、個別の具体例に応じた特定の値、例えば、「１１・・・１」に続いて１を格納する。
・ＯＰＲ４０６−現在のＣＥ２０５命令の命令コードを格納する命令レジスタ（ソースは、コントローラ２５５命令内の専用フィールドである）。
・ＶＡＲ４０８−ベクトルメモリのためのアドレスレジスタ。ＶＡＲ４０８レジスタは、特別なコントローラ２５５命令によって更新され、ベクトルを明示的に操作する命令に引数として用いられる。また、ＶＡＲ４０８レジスタは、セルに関連する汎用レジスタに関係する全ての処理の実行にも用いられる。
【０１１４】
更に図１８に示すように、入力／出力ライン４１０を選択的に用いて、ＣＭ２０６の両端にアクセスすることができる。本明細書では、入力／出力ライン４１０を以下のように表す。
・ｌｅｆｔ＿ｉｎ４１２＝｛ｗ，ｍａｒｋ，ｅｑ，ｆｉｒｓｔ｝：デフォルトでは、全てが０である（ｅｑ＝１とは、セル内の２つのオペランドが等しいことを意味する。ｆｉｒｓｔ＝１は、セルが最初のマークされたセルであることを意味する）。
・ｌｅｆｔ＿ｏｕｔ４１４＝｛ｗ，ｍａｒｋ，ｅｑ，ｆｉｒｓｔ｝：最初のセルから供給される。
【０１１５】
なお、ＣＥ２０５は、本発明のより広い側面から逸脱することなく、コントローラ２５５がＣＥ２０５にコマンドを発行でき、ＣＥ２０５からデータを受け取ることができる限り、回路固有の様々な構成を有することができる。したがって、本発明の重要な側面として、ＣＭ２０６内の各ｍビットセルは、データを格納することに加えて、データを能動的に処理できる必要がある。データ処理は、各ｍビットセル内で実行してもよく、又は所定のセルの左隣又は右隣のセルに影響を与えることによって実行してもよい。なお、このように、ＣＭ２０６内の各ｍビットセルの機能を強化することによって、本発明は、他のデータ処理システムの性能を超える、より複雑なシステムレベルの振る舞いを実現する。
【０１１６】
本発明のこの他の重要な側面として、本発明では、条件の一部又は属性として、各セルを「マークし」、そのセル自身又はＣＭ２０６内で隣接セルに対して、次のタスクを実行し又はオペランドを実行するセルとして指定することによって、ＣＭ２０６内のセルレベルでデータを能動的に処理することができる。
【０１１７】
また、本発明に基づくデータ処理システムの生来的な利点として、セルエンジン内の各セルは、単一のクロックサイクル内で命令を同時に実行するだけではなく、局所的な状態情報及び包括的な状態情報の両方を用いて、包括的にブロードキャストされた命令を実行するセルを動的に限定することができる。特に、これまでに知られていない新たな手法として、個々のセルレベルでマーカビットを用いることによって、連想メモリ内の実際のセルが、マークされたセルの左又は右のセルに影響を与えることができる。このように、本発明は、連想メカニズムによって、すなわち、特別に指定された位置アドレスではなく、ＣＭ２０６内の個々のセルのコンテンツの性質又はプロパティによって、システムレベルにおけるマークされた状態の選択的なアクティブ化又は変更を実現する。
【０１１８】
このように、本発明では、処理及びメモリを非常に緊密なレベルで結合し、すなわち、ＣＭ２０６の個々のセルは、その処理のために、個別のメモリブロックにアクセスする必要がない。更に、セルレベルにおいて、オペランドがローカル空間に常駐するため、処理結果は、適切な場所に維持され、通信及び処理時間を短縮でき、シリコン領域を節約でき、消費電力を低減できる。
【０１１９】
また、ＣＭ２０６の容量は、キーフィールド又はデータフィールドのいずれかの一部として、ｎ個のセル内に保存されるビットの任意の部分を選択的に利用されるため、ＣＭ２０６の柔軟性が高まる。すなわち、キーフィールド及びデータフィールドが厳密に定義される既知の連想メモリアーキテクチャとは異なり、ＣＭ２０６は、発行されたコマンド及び望まれる処理の性質に基づいて、メモリ内に保存されるビットのどの部分をキーフィールドビット又はデータフィールドビットであるとみなしてもよい。
【０１２０】
図１９は、典型的な連想メモリ５００のコンテンツを示している。図１９は、１２個の列を含むメモリセルの１個の行を有する連想メモリ装置を簡略化して示している。本発明は、このようなアーキテクチャに限定されるわけではなく、実際に、より多くのセルのより複雑なアレイを想定しており、図１９は、説明のために例示的に用いるに過ぎない。
【０１２１】
図１９に示すように、この具体例では、６列のキーフィールド５０２及び８列のデータフィールド５０４を示している。キーフィールド５０２及びデータフィールド５０４の実際の長さ又はサイズは、設計における選択の問題であり、既知の連想メモリエンジンは、全てのコマンド及び処理を通して、これらの２つのフィールドの間の区別を維持する。すなわち既知の連想メモリ装置では、キーフィールド及びデータフィールドの性質及びサイズが固定されている。具体例として、連想メモリを用いて高速データベースを実現し、データフィールドは、例えば、従業員に関する情報等の特定のデータコンテンツを表し、キーフィールドは、従業員の姓を表すと仮定する。典型的な連想メモリのコントローラは、単純なコマンドに基づき、キーフィールド５０２を検索し、「スミス（Smith）」に一致するかを判定し、実際に検索したいデータをデータフィールド５０４を得るために、キーフィールド５０２に「スミス」が含まれる全てのデータフィールド５０４に「タグ」を付し、検索されたデータの存在又は不在を示す。なお、この具体例では、キーは、６列以内でなくてはならない。
【０１２２】
一方、本発明のメモリエンジンでは、キーフィールドとデータフィールドの間の区別はなく、したがって、コントローラは、発行されたコマンドに基づいて、キーフィールド５０２又はデータフィールド５０４のいずれかに含まれているいずれのセルもキーの一部であると包括的に解釈及び評価することができる。
【０１２３】
なお、既知の連想データ処理システムと、本発明との間の違いは、構造の１つではなく、ソフトウェア及び発行されるコマンドのインプリメンテーションにある。すなわち、本発明では、コントローラは、発行された特別なコマンドに基づいて、連想メモリ装置内の全てのセルを「キー」の一部又は「データ」の一部として選択的に解釈することができる。したがって、特定のセルの「キー」としてのプロパティ又は「データ」としてのプロパティは、コマンド自体で表現され、連想メモリ装置の構造的な組織の機能ではない。
【０１２４】
図２０に示すように、コントローラは、１４セル行を有する１４セルの連想メモリ５１０において、特定のコマンドに関して（破線で示す、従来の手法であればキーフィールドとみなされる範囲内にある）セル２において、検索されたデータを検出することもでき、又は（破線で示す、従来の手法であればデータフィールドとみなされる範囲内にある）セル９において、検索されたデータを検出することもできる。したがって、本発明の連想メモリエンジンは、既知の連想メモリエンジンより遙かに柔軟性が高いことは明らかである。
【０１２５】
本発明によって、連想メモリ装置において、キーフィールドとデータフィールドとの間の区別が事実上なくなるため、メモリエンジンのプログラミング能力が著しく向上する。
【０１２６】
従業員の姓に関する上述した具体例で説明したような既知の連想記憶システムは、特定の用途に特化され、カスタマイズされるため、このシステムでは、根本的に異なる構造（例えば、１６列の鍵及び１０２４列のデータ）を有するデータを検索又は識別することができない。これとは対照的に、本発明では、キーフィールドとデータフィールドとを全く区別しないため、本発明は、個々のコマンドに基づいて、何を「キー」とするかについて、性質を選択的に再定義するので、本発明によって、本質的に汎用的な連想メモリシステムを実現することができる。
【０１２７】
具体例として、本発明に基づくデータ処理をするための連想記憶サポートシステムでは、まず、例えば、５セルのキーを用いて、全社員の姓を特定することができる。そして、コントローラが発行した次のコマンドでは、例えば２セルのキー等に基づいて、他の種類のデータを検索することもできる。このように、既知の連想記憶システムの場合とは異なり、本発明では、用途毎にマシンを再設計及び特化させる必要がない。すなわち、本発明では、発行されたコマンド毎に各キーを個別化でき、したがって、本発明は、キー及びコンテンツを単に選択するだけで、特化されたデータを選択的に検索できる汎用の連想メモリをサポートする。
【０１２８】
この点に関して、図３〜図１０を用いて上述したコマンドの実現例は、ＣＭ２０６内のキーフィールドとデータフィールドの間の従来の区別を取り除き、又は無視できるメモリエンジンの固有の能力に、少なくとも部分的に、依存している。
【０１２９】
また、メモリ装置は、ビットの位置にかかわらず、及びキーフィールドとデータフィールドを区別することなく、ｎ個のセルのそれぞれの全てのビットを使用できるので、コントローラ２５５は、ＣＭ２０６内のｎ個のセルのそれぞれに、１つのクロックサイクル内で所定のコマンドを包括的にブロードキャストでき、また、ｎ個のセルのそれぞれは、発行されたコマンドを単一のクロックサイクル内で処理できる。
【０１３０】
以上、好ましい実施の形態を用いて発明を説明したが本発明の基本的な範囲から逸脱することなく、これらの実施の形態を様々に変更し、実施の形態における要素を等価物で置換できることは当業者にとって明らかである。したがって、本発明は、ここに開示した特定の実施の形態に限定されず、添付の特許請求の範囲に含まれる全ての実施の形態を含む。
【図面の簡単な説明】
【０１３１】
【図１】本発明の一実施の形態に基づく、外部コントローラ及びクロック要素を含むメモリエンジンの汎用のアーキテクチャを示すブロック図である。
【図２】図１のメモリエンジンを、メモリエンジンの構成要素間で情報を交換するための異なるバスと共に示すブロック図である。
【図３】図１のメモリエンジンの包括的な処理の一実施の形態を示すフローチャートである。
【図４】図１のメモリエンジンの包括的な処理の他の実施の形態を示すフローチャートである。
【図５】図１のメモリエンジンによるｃｆｉｎｄコマンドの処理を示すフローチャートである。
【図６】図１のメモリエンジンによるｒｅａｄコマンドの処理を示すフローチャートである。
【図７】図１のメモリエンジンによるｉｎｓｅｒｔコマンドの処理を示すフローチャートである。
【図８】図１のメモリエンジンによるｄｅｌｅｔｅコマンドの処理を示すフローチャートである。
【図９】図１のメモリエンジンによるｎｅｘｔコマンドの処理を示すフローチャートである。
【図１０】図１のメモリエンジンによるｊｕｍｐコマンドの処理を示すフローチャートである。
【図１１】メモリエンジンのメモリ装置を周辺装置にインタフェースし、幾つかのメモリ装置を相互に接続するために必要な入力信号及び出力信号を示すブロック図である。
【図１２】２つのトランスコーダ回路を介して静的及び動的メモリセルの２次元アレイにアクセスするメモリ装置の内部構造の一実施の形態を示すブロック図である。
【図１３】メモリセルを周辺装置に動的にインタフェースする入力信号及び出力信号を示すブロック図である。
【図１４】発明の一実施の形態に基づき、シンボル及び関連するマーカを保存し、読み出し、放送されたシンボルと比較するためのシンボル及び関連するマーカのためのストレージを含むメモリセルの内部のアーキテクチャを示す回路図である。
【図１５】メモリセルの２次元アレイにアクセスでき、最初の又は最後のマークされたセルのアドレスを生成する本発明の一実施の形態に基づく図１２に示すトランスコーダ回路の内部のアーキテクチャを示す回路図である。
【図１６】ランダムアクセスメモリ（ＲＡＭ）とＲＡＭコントローラの組合せとしてバッファメモリのコンテンツを示す回路図である。
【図１７】図１６に示すＲＡＭコントローラの内部構造を示す回路図である。
【図１８】図１に示すメモリエンジンをより詳細に示すブロック図である。
【図１９】典型的な連想メモリ装置のコンテンツを示す図である。
【図２０】キーフィールドとデータフィールドの間の従来の区別がなくなった連想メモリ装置のコンテンツを示す図である。
【図１】
2007536696.tif 000004
【図２】
2007536696.tif 000005
【図３】
2007536696.tif 000006
【図４】
2007536696.tif 000007
【図５】
2007536696.tif 000008
【図６】
2007536696.tif 000009
【図７】
2007536696.tif 000010
【図８】
2007536696.tif 000011
【図９】
2007536696.tif 000012
【図１０】
2007536696.tif 000013
【図１１】
2007536696.tif 000014
【図１２】
2007536696.tif 000015
【図１３】
2007536696.tif 000016
【図１４】
2007536696.tif 000017
【図１５】
2007536696.tif 000018
【図１６】
2007536696.tif 000019
【図１７】
2007536696.tif 000020
【図１８】
2007536696.tif 000021
【図１９】
2007536696.tif 000022
【図２０】
2007536696.tif 000023
【国際調査報告】
2007536696.tif 000024