JPH0664911B2 - 内容でアドレス指定可能なメモリ・アレイ - Google Patents
内容でアドレス指定可能なメモリ・アレイInfo
- Publication number
- JPH0664911B2 JPH0664911B2 JP1117163A JP11716389A JPH0664911B2 JP H0664911 B2 JPH0664911 B2 JP H0664911B2 JP 1117163 A JP1117163 A JP 1117163A JP 11716389 A JP11716389 A JP 11716389A JP H0664911 B2 JPH0664911 B2 JP H0664911B2
- Authority
- JP
- Japan
- Prior art keywords
- bit
- word
- bits
- empty
- match
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G11—INFORMATION STORAGE
- G11C—STATIC STORES
- G11C15/00—Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
- G11C15/04—Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores using semiconductor elements
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/903—Querying
- G06F16/90335—Query processing
- G06F16/90339—Query processing by using parallel associative memories or content-addressable memories
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Computational Linguistics (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Executing Machine-Instructions (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Dram (AREA)
- Refuse Collection And Transfer (AREA)
- Non-Reversible Transmitting Devices (AREA)
- Indexing, Searching, Synchronizing, And The Amount Of Synchronization Travel Of Record Carriers (AREA)
- Bidet-Like Cleaning Device And Other Flush Toilet Accessories (AREA)
- Mechanical Treatment Of Semiconductor (AREA)
Description
【発明の詳細な説明】 関連出願の相互参照 この出願と同時に出願され、かつこの出願と同じ譲受人
に譲渡された同時係属米国特許出願第193,308号は、こ
こに開示される多重化アドレス命令およびフラグ情報を
有する、内容でアドレス指定可能なメモリに向けられた
請求項を有する。
に譲渡された同時係属米国特許出願第193,308号は、こ
こに開示される多重化アドレス命令およびフラグ情報を
有する、内容でアドレス指定可能なメモリに向けられた
請求項を有する。
この出願と同時に出願され、かつこの出願と同じ譲受人
に譲渡された同時係属米国特許出願第193,315号は、こ
こに開示される、内容でアドレス指定可能なメモリ・シ
ステムのアーキテクチャに向けられた請求項を有する。
に譲渡された同時係属米国特許出願第193,315号は、こ
こに開示される、内容でアドレス指定可能なメモリ・シ
ステムのアーキテクチャに向けられた請求項を有する。
発明の背景 発明の分野 この出願は、メモリ内のデータ位置よりもむしろメモリ
・データの内容に基づいてメモリがサーチされる、内容
でアドレス指定可能なメモリ（CAM）アレイを用いるシ
ステムに関するものである。
・データの内容に基づいてメモリがサーチされる、内容
でアドレス指定可能なメモリ（CAM）アレイを用いるシ
ステムに関するものである。
先行技術の説明 従来のまたはノイマン型のコンピュータならびに、計数
変数をそれらの位置の索引によってアドレス指定すると
いう原理を用いるコンピュータは特に、多くの課題にお
いて不十分なものであるとしばしばみなされてきた。オ
ペランドがそれらの記号名またはデータ内容によって、
場合によっては一時に多数呼出され得る構造をもって、
従来のランダム・アクセス・メモリに替えるため多くの
試みがなされてきた。ハイレベルのアルゴリズム言語お
よび問題向き言語はそのような特徴を大いに利用するで
あろう。この方向における開発が特に迅速ではなかった
理由は、少なくとも２つ存在する。それらのうちの１つ
は、ランダム・アクセス・メモリに比して、内容でアド
レス指定可能なメモリははるかに高価であることであ
る。もう１つの理由は、変数を記号でコード化するとい
う課題は既に効果的なソフトウェアによる解決を有して
おり、それは特別なメモリを必要としないということで
ある。しかしながらこれは、多くの課題において極めて
望ましいもう１つの特徴、すなわち、極めて多くの変数
をメモリから同時に検索するという特徴をもたらさな
い。
変数をそれらの位置の索引によってアドレス指定すると
いう原理を用いるコンピュータは特に、多くの課題にお
いて不十分なものであるとしばしばみなされてきた。オ
ペランドがそれらの記号名またはデータ内容によって、
場合によっては一時に多数呼出され得る構造をもって、
従来のランダム・アクセス・メモリに替えるため多くの
試みがなされてきた。ハイレベルのアルゴリズム言語お
よび問題向き言語はそのような特徴を大いに利用するで
あろう。この方向における開発が特に迅速ではなかった
理由は、少なくとも２つ存在する。それらのうちの１つ
は、ランダム・アクセス・メモリに比して、内容でアド
レス指定可能なメモリははるかに高価であることであ
る。もう１つの理由は、変数を記号でコード化するとい
う課題は既に効果的なソフトウェアによる解決を有して
おり、それは特別なメモリを必要としないということで
ある。しかしながらこれは、多くの課題において極めて
望ましいもう１つの特徴、すなわち、極めて多くの変数
をメモリから同時に検索するという特徴をもたらさな
い。
連想は本来、情報間の相互関係または相互参照の表記の
ためにのみ考慮されていたが、データをその部分的内容
によってサーチすることは、演算アルゴリズムの操作に
おいて効果的に利用され得るということが後程判明し
た。そのような内容によるアドレス指定は高度に並列し
て、すなわち極めて多数のデータ要素にわたって同時
に、通常比較的低レベルで、２進表現において生じる変
換を参照しながら、行なわれ得る。並列計算の課題はま
た、より高いレベルのアルゴリズム機能を並列に制御す
るために内容によるアドレス指定能力が使用されるとい
う、もつ１つの方向も有する。
ためにのみ考慮されていたが、データをその部分的内容
によってサーチすることは、演算アルゴリズムの操作に
おいて効果的に利用され得るということが後程判明し
た。そのような内容によるアドレス指定は高度に並列し
て、すなわち極めて多数のデータ要素にわたって同時
に、通常比較的低レベルで、２進表現において生じる変
換を参照しながら、行なわれ得る。並列計算の課題はま
た、より高いレベルのアルゴリズム機能を並列に制御す
るために内容によるアドレス指定能力が使用されるとい
う、もつ１つの方向も有する。
以下の定義はこの発明の主題となる事項に関して用いら
れ得る。
れ得る。
内容でアドレス指定可能なメモリ： データを多数のセ
ル内に記憶させる記憶装置。セルはそれらの内容に基づ
き、アクセスまたはロード可能である。
ル内に記憶させる記憶装置。セルはそれらの内容に基づ
き、アクセスまたはロード可能である。
内容でアドレス指定可能なプロセッサ： より複雑なデ
ータ変換が、内容に従って選択されたいくつかのセルの
内容について行なわれ得る、内容でアドレス指定可能な
メモリ、あるいはそのようなメモリを記憶または処理の
ために必須の構成要素として各々使用するコンピュータ
またはコンピュータ・システム。
ータ変換が、内容に従って選択されたいくつかのセルの
内容について行なわれ得る、内容でアドレス指定可能な
メモリ、あるいはそのようなメモリを記憶または処理の
ために必須の構成要素として各々使用するコンピュータ
またはコンピュータ・システム。
データに、それらの内容に基づいてアクセスすること
は、外部探索引数と、すべてのセル内に記憶された情報
の一部またはすべてとの何らかの比較を常に含む。これ
がソフトウェア、機械的走査または並列電子回路のいず
れによって行なわれるかは原則として重要ではないが、
しかしながら、「真正の」内容でアドレス指定可能なメ
モリは、すべての比較を並列して行なう。強調すべきも
う１つの事実は、探索引数と記憶された項目との間の同
等のマッチによる比較が、使用される唯一のモードでは
ないということである。記憶されたデータが数値を有す
る場合、内容でアドレス指定可能なサーチの目的は、そ
の内容が探索引数に関して、たとえば所与の限界より大
きいかまたは小さい、あるいは２つの特定の限界の間に
あるといった、一定の大きさの関係を満たすすべてのセ
ルの位置を突止めることであるかもしれない。内容でア
ドレス指定可能なサーチは、時には外部探索引数を参照
することなく行なわれ、たとえば１組の記憶された数に
おいて最大または最小の位置を突止める場合がそうであ
る。
は、外部探索引数と、すべてのセル内に記憶された情報
の一部またはすべてとの何らかの比較を常に含む。これ
がソフトウェア、機械的走査または並列電子回路のいず
れによって行なわれるかは原則として重要ではないが、
しかしながら、「真正の」内容でアドレス指定可能なメ
モリは、すべての比較を並列して行なう。強調すべきも
う１つの事実は、探索引数と記憶された項目との間の同
等のマッチによる比較が、使用される唯一のモードでは
ないということである。記憶されたデータが数値を有す
る場合、内容でアドレス指定可能なサーチの目的は、そ
の内容が探索引数に関して、たとえば所与の限界より大
きいかまたは小さい、あるいは２つの特定の限界の間に
あるといった、一定の大きさの関係を満たすすべてのセ
ルの位置を突止めることであるかもしれない。内容でア
ドレス指定可能なサーチは、時には外部探索引数を参照
することなく行なわれ、たとえば１組の記憶された数に
おいて最大または最小の位置を突止める場合がそうであ
る。
ハードウェアの、内容でアドレス指定可能なメモリは、
計算システムにおいて特殊な部分として使用されてきた
が、ある組織的解決においては、それによってCAMが、
データの移動および並べ換えに必要とされる迅速なバッ
ファ、チェックおよび計算システムの資源の利用状況の
監視および管理動作を効果的に行なうことが可能であ
る。このようにしてCAM装置は、オペランドを処理回路
に対してより直接的に利用可能にすることによって、通
常動作の速度に効果的に貢献することができる。
計算システムにおいて特殊な部分として使用されてきた
が、ある組織的解決においては、それによってCAMが、
データの移動および並べ換えに必要とされる迅速なバッ
ファ、チェックおよび計算システムの資源の利用状況の
監視および管理動作を効果的に行なうことが可能であ
る。このようにしてCAM装置は、オペランドを処理回路
に対してより直接的に利用可能にすることによって、通
常動作の速度に効果的に貢献することができる。
CAMアレイでのマスクされたサーチにおいては、探索引
数ワードのビットのサブセットのみがすべてのメモリ・
ワードの各々のビットと比較される。CAMにおけるマス
キングは通常、或るビットを完全にマスクすること、す
なわち使用禁止にすることを意味する。特定された（マ
スクされない）ビット位置において探索引数と一致す
る、記憶されたワードが次に読出される。
数ワードのビットのサブセットのみがすべてのメモリ・
ワードの各々のビットと比較される。CAMにおけるマス
キングは通常、或るビットを完全にマスクすること、す
なわち使用禁止にすることを意味する。特定された（マ
スクされない）ビット位置において探索引数と一致す
る、記憶されたワードが次に読出される。
発明の概要 先行技術を利用し、Ｎビット幅ワードおよびＭワード深
さの（たとえば、48ビット・ワードで、アレイ内に256
ワード存在する）構成を有するCAMアレイ・パッケージ
を提供し、かつ非多重化モードで動作するには、必要な
データ信号、制御信号、フラグ信号および電源信号を提
供するためにパッケージ上に多数のピンが必要となるで
あろう。たとえば、先行技術を使用する典型的な非多重
化256×48CAMアレイについては以下のピン総数が必要と
なるであろう。
さの（たとえば、48ビット・ワードで、アレイ内に256
ワード存在する）構成を有するCAMアレイ・パッケージ
を提供し、かつ非多重化モードで動作するには、必要な
データ信号、制御信号、フラグ信号および電源信号を提
供するためにパッケージ上に多数のピンが必要となるで
あろう。たとえば、先行技術を使用する典型的な非多重
化256×48CAMアレイについては以下のピン総数が必要と
なるであろう。
この発明によると、３つのメモリ・サイクルを使用し
て、48データ・ビットを16ビット・バスに時間多重化す
ることによって、必要とされるパッケージ・ピンの数の
実質的な削減が実現され得る。これを達成するために、
この発明は３つの48ビット内部レジスタを使用して、CA
Mデータ、マスクされないマッチ・ワードおよびマスク
・ビットを保持する。これらの３つの48ビットレジスタ
は３サイクルで16ビットＩ／Ｏバスからロードされる。
データ書込サイクルおよびデータ読出サイクルに加え
て、コマンド書込サイクルおよび状態読出サイクルがこ
の発明においては利用され、さらに16ビットバスへの、
およびそこからのアドレス情報、命令情報およびフラグ
情報を多重化する。この後者は、特別制御信号（Ｄ／
−データ／コマンド）を費してなされる。コマンド書込
サイクルの間、書込コマンドはコマンド・ワードのフォ
ーマットを採用し、オペレーショナル（OP）・コードは
ワード・ビットの一部にコード化され、アドレス情報は
ビットの他の一部にコード化される。状態読出動作の
間、フラグ状態に関する情報は状態ワード・ビットの一
部にコード化され、アドレス情報は状態ワード・ビット
の他の部分にコード化される。多重化技術を使用して、
コマンド書込および状態読出情報を利用し、16ビット・
バス上へのその配置を可能にするこの能力は、この発明
の実施例の重要な特徴である。
て、48データ・ビットを16ビット・バスに時間多重化す
ることによって、必要とされるパッケージ・ピンの数の
実質的な削減が実現され得る。これを達成するために、
この発明は３つの48ビット内部レジスタを使用して、CA
Mデータ、マスクされないマッチ・ワードおよびマスク
・ビットを保持する。これらの３つの48ビットレジスタ
は３サイクルで16ビットＩ／Ｏバスからロードされる。
データ書込サイクルおよびデータ読出サイクルに加え
て、コマンド書込サイクルおよび状態読出サイクルがこ
の発明においては利用され、さらに16ビットバスへの、
およびそこからのアドレス情報、命令情報およびフラグ
情報を多重化する。この後者は、特別制御信号（Ｄ／
−データ／コマンド）を費してなされる。コマンド書込
サイクルの間、書込コマンドはコマンド・ワードのフォ
ーマットを採用し、オペレーショナル（OP）・コードは
ワード・ビットの一部にコード化され、アドレス情報は
ビットの他の一部にコード化される。状態読出動作の
間、フラグ状態に関する情報は状態ワード・ビットの一
部にコード化され、アドレス情報は状態ワード・ビット
の他の部分にコード化される。多重化技術を使用して、
コマンド書込および状態読出情報を利用し、16ビット・
バス上へのその配置を可能にするこの能力は、この発明
の実施例の重要な特徴である。
情報の多重化に関するこの発明の教示を使用すると、必
要とされるピンの総数は以下のように削減される。
要とされるピンの総数は以下のように削減される。
この発明のもう１つの重要な局面によると、ワード内の
いずれかの、またはすべてのビットがマスク可能であり
得、かつアレイ内のいずれかの、またはすべてのワード
についてマスクおよびリセットが共に可能であり得るCA
Mアレイが提供される。
いずれかの、またはすべてのビットがマスク可能であり
得、かつアレイ内のいずれかの、またはすべてのワード
についてマスクおよびリセットが共に可能であり得るCA
Mアレイが提供される。
この発明のさらなる特徴は、特別なCAMプロセッサ・ア
ーキテクチャが用いられることである。このアーキテク
チャは以下の構造を含む。
ーキテクチャが用いられることである。このアーキテク
チャは以下の構造を含む。
1. CAMセル・アレイ CAMセルのアレイが所望の構成に配置される。ワード・
ラインおよびマッチ・ラインが同じ方向に延び、ビット
・ラインはワード・ラインに対して垂直に延びる。
ラインおよびマッチ・ラインが同じ方向に延び、ビット
・ラインはワード・ラインに対して垂直に延びる。
2. 行デコーダ Ｍデコーダのうちの１つが所望のワードのみを選択す
る。
る。
3. ビット・ライン・プリチャージ回路 これは高速非破壊セル読出のために、ビット・ラインを
最適レベルまでプリチャージする。
最適レベルまでプリチャージする。
4. ビット・ライン記述子回路 各関連ビットにつき１つ（すなわち、各ビット・ライン
対につき１つ）の記述子が設けられる。これはマスク・
レジスタ、被比較数レジスタ、センスアンプおよびプロ
グラム可能なビット・ライン書込回路からなる。
対につき１つ）の記述子が設けられる。これはマスク・
レジスタ、被比較数レジスタ、センスアンプおよびプロ
グラム可能なビット・ライン書込回路からなる。
データは、ワード・ラインが選択された状態で、ビット
・ラインを介してCAMセル内に書込まれ得る。被比較数
レジスタは、ビット・ライン上およびセル内に書込まれ
るべきデータとともに、プログラム可能なビット・ライ
ン書込回路をプログラムする。データは、ワード・ライ
ンが選択された状態で、ビット・ラインを介してCAMセ
ルから読出され得る。ビット・ライン上のセル信号は、
センスアンプによって増幅される。
・ラインを介してCAMセル内に書込まれ得る。被比較数
レジスタは、ビット・ライン上およびセル内に書込まれ
るべきデータとともに、プログラム可能なビット・ライ
ン書込回路をプログラムする。データは、ワード・ライ
ンが選択された状態で、ビット・ラインを介してCAMセ
ルから読出され得る。ビット・ライン上のセル信号は、
センスアンプによって増幅される。
非破壊的並列サーチ（マッチ）は、すべてのワード・ラ
インが選択されずに、すべてのアレイに対して行なわれ
得る。被比較数レジスタおよびマスク・レジスタ内のデ
ータは、プログラム可能なビット・ライン書込回路をプ
ログラムするために使用される。マッチ動作の間、CAM
セル・データは、関連するビット・ライン対上に現われ
るデータと同時に比較されるであろう。
インが選択されずに、すべてのアレイに対して行なわれ
得る。被比較数レジスタおよびマスク・レジスタ内のデ
ータは、プログラム可能なビット・ライン書込回路をプ
ログラムするために使用される。マッチ動作の間、CAM
セル・データは、関連するビット・ライン対上に現われ
るデータと同時に比較されるであろう。
マスク・レジスタ内のデータはプログラム可能なビット
・マスキングのために使用される。マスク・レジスタ内
の論理「１」は被比較数レジスタ内のデータを重ね書き
するであろうし、一方マスク・レジスタ内の論理「０」
は、被比較数レジスタ内の対応するデータがセル内への
書込のためにビット・ライン上に現われるのを可能にす
る。このようにしてビットのいずれか、またはすべてが
マスクさ得る。
・マスキングのために使用される。マスク・レジスタ内
の論理「１」は被比較数レジスタ内のデータを重ね書き
するであろうし、一方マスク・レジスタ内の論理「０」
は、被比較数レジスタ内の対応するデータがセル内への
書込のためにビット・ライン上に現われるのを可能にす
る。このようにしてビットのいずれか、またはすべてが
マスクさ得る。
5. ワード・マスキングおよびリセット回路 各関連ワードにつき１つが設けられ、スキップ・ビット
およびエンプテイ・ビットからなる。ワードのいずれか
またはすべてがスキップ・ビットまたはエンプティ・ビ
ットによって完全にマスクされ得る。すべてのエンプテ
ィ・ビットをリセットする（すべてをエンプティにセッ
トする）ことによって、アレイ全体がリセットされ得
る。データはデータバスを介して、これらのスキップ・
ビットおよびエンプティ・ビット内へ、またはそれらか
ら転送され得る。
およびエンプテイ・ビットからなる。ワードのいずれか
またはすべてがスキップ・ビットまたはエンプティ・ビ
ットによって完全にマスクされ得る。すべてのエンプテ
ィ・ビットをリセットする（すべてをエンプティにセッ
トする）ことによって、アレイ全体がリセットされ得
る。データはデータバスを介して、これらのスキップ・
ビットおよびエンプティ・ビット内へ、またはそれらか
ら転送され得る。
6. マッチ検出器 これは「マッチがない」、「単数マッチ」または「複数
マッチ」状態を検出し、かつチップ「フル」またはチッ
プ「エンプティ」状態を検出することができる。「フ
ル」、「マッチ」および「複数マッチ」フラグが16ビッ
ト・バス上において利用可能である。
マッチ」状態を検出し、かつチップ「フル」またはチッ
プ「エンプティ」状態を検出することができる。「フ
ル」、「マッチ」および「複数マッチ」フラグが16ビッ
ト・バス上において利用可能である。
7. 優先順位エンコーダ 単一マッチまたは複数マッチ状態の場合には、最高優先
順位のマッチの位置のアドレスがコード化されるであろ
う。
順位のマッチの位置のアドレスがコード化されるであろ
う。
「マッチがない」状態の場合、最高優先順位のエンプテ
ィの位置のアドレスかコード化されるであろう。
ィの位置のアドレスかコード化されるであろう。
8. 制御論理 16ビット・バスから受けられる命令は内部タイミングを
発生し、異なる動作を達成するであよう。
発生し、異なる動作を達成するであよう。
9. 以下のものを提供するために多重化された16ビット
・バス 行デコーダのためのアドレス・バス。
・バス 行デコーダのためのアドレス・バス。
CAMセルのためのデータ Ｉ／Ｏ。
マッチ・ワードのためデータ Ｉ／Ｏ（非比較数レジス
タおよびマスク・レジスタ）。
タおよびマスク・レジスタ）。
スキップ・ビットおよびエンプティ・ビットのためのデ
ータ Ｉ／Ｏ。
ータ Ｉ／Ｏ。
制御論理のための命令。
「フル」、「マッチ」、および「複数マッチ」のための
出力フラグ。
出力フラグ。
優先順位エンコーダからの「マッチ」位置または「エン
プティ」位置のいずれかのコード化されたアドレス。
プティ」位置のいずれかのコード化されたアドレス。
好ましい実施例の説明 第１図を参照すると、この発明のCAMセル・アレイ11は
Ｎビット幅ワードおよびＭワード深さで構成される。典
型的な、しかしながら限定的ではない、一実施例は48ビ
ット・ワードのアレイを含み、アレイ内には256のその
ようなワードが存在する。２つの特別なビット（スキッ
プ・ビットおよびエンプティ・ビット）がワード・マス
キングおよびリセットの目的のために各ワードに付与さ
れる。ラインBLおよび▲▼を介して、アレイ内の各
ビットにビット・ライン記述子回路１（第２図により詳
細に示される）が接続され、それはプログラム可能なビ
ット・ライン書込回路、被比較数レジスタ、マスク・レ
ジスタおよびセンスアンプを含む。記述子回路１はデー
タを16ビット・バス10と交換する。行デコーダ２が、複
数のワード・ラインWLを含むバスを介してアレイ11に接
続され、アレイ内の異なるワードを選択する。ビット・
ライン・プリチャージ回路３が複数のビット・ラインBL
および▲▼を介してアレイ11に接続され、そのよう
なビット・ラインの対がアレイ内のビットの各列に設け
られる。マッチ・ラインMLを介して、ワード・マスキン
グおよびリセット回路４、マッチ検出器５および優先順
位エンコーダ６がアレイ11の出力と通信する。制御論理
ネットワーク７は、バス10から受けた命令に応答して回
路４、５および６に入力を提供する。回路４、５および
６は直接バス10と通信し、バス10と回路４との間の通信
は双方向性である。これらの回路の細部は第２図に、よ
り詳細に示される。
Ｎビット幅ワードおよびＭワード深さで構成される。典
型的な、しかしながら限定的ではない、一実施例は48ビ
ット・ワードのアレイを含み、アレイ内には256のその
ようなワードが存在する。２つの特別なビット（スキッ
プ・ビットおよびエンプティ・ビット）がワード・マス
キングおよびリセットの目的のために各ワードに付与さ
れる。ラインBLおよび▲▼を介して、アレイ内の各
ビットにビット・ライン記述子回路１（第２図により詳
細に示される）が接続され、それはプログラム可能なビ
ット・ライン書込回路、被比較数レジスタ、マスク・レ
ジスタおよびセンスアンプを含む。記述子回路１はデー
タを16ビット・バス10と交換する。行デコーダ２が、複
数のワード・ラインWLを含むバスを介してアレイ11に接
続され、アレイ内の異なるワードを選択する。ビット・
ライン・プリチャージ回路３が複数のビット・ラインBL
および▲▼を介してアレイ11に接続され、そのよう
なビット・ラインの対がアレイ内のビットの各列に設け
られる。マッチ・ラインMLを介して、ワード・マスキン
グおよびリセット回路４、マッチ検出器５および優先順
位エンコーダ６がアレイ11の出力と通信する。制御論理
ネットワーク７は、バス10から受けた命令に応答して回
路４、５および６に入力を提供する。回路４、５および
６は直接バス10と通信し、バス10と回路４との間の通信
は双方向性である。これらの回路の細部は第２図に、よ
り詳細に示される。
この発明によるCAMシステムのアーキテクチャ全体の最
も重要な特徴が第２図に示される。第１図のビット・ラ
イン記述子回路１のエレメントは点線の囲い１内に示さ
れ、CAMレジスタ17、マスク・レジスタ18、被比較数レ
ジスタ19、センスアンプ14および、記述子エレメント36
内に含まれるプログラム可能なビット・ライン書込回路
を含む。
も重要な特徴が第２図に示される。第１図のビット・ラ
イン記述子回路１のエレメントは点線の囲い１内に示さ
れ、CAMレジスタ17、マスク・レジスタ18、被比較数レ
ジスタ19、センスアンプ14および、記述子エレメント36
内に含まれるプログラム可能なビット・ライン書込回路
を含む。
第２図の回路はまた、機能において第１図の行デコーダ
２に対応するアドレス・デコーダ30を示し、これはバス
10から供給される８つのアドレス・ビットをデコード化
し、アレイ11内の256ワードのうちの選択されるべき１
つを同定する。また、スキップ書込回路20を有するスキ
ップ・ビット・アレイ22および、エンプティ書込回路23
を有するエンプティ・ビット・アレイ24がアレイ11の出
力およびデコーダ30に接続されているのが示される。エ
レメント22および24からの出力はスキップ／エンプティ
・ビット・エレメント41に供給される。
２に対応するアドレス・デコーダ30を示し、これはバス
10から供給される８つのアドレス・ビットをデコード化
し、アレイ11内の256ワードのうちの選択されるべき１
つを同定する。また、スキップ書込回路20を有するスキ
ップ・ビット・アレイ22および、エンプティ書込回路23
を有するエンプティ・ビット・アレイ24がアレイ11の出
力およびデコーダ30に接続されているのが示される。エ
レメント22および24からの出力はスキップ／エンプティ
・ビット・エレメント41に供給される。
また第２図には、フル制御エレメント37によって制御さ
れ、かつ状態レジスタ40およびフル・レジスタ32に出力
を供給するフル検出器31が示される。状態レジスタ40
は、状態読出動作の間16ビットでバス10と通信する。
れ、かつ状態レジスタ40およびフル・レジスタ32に出力
を供給するフル検出器31が示される。状態レジスタ40
は、状態読出動作の間16ビットでバス10と通信する。
マッチ制御エレメント38によって制御されるマッチ検出
器28は、単一マッチ信号をマッチ・レジスタ29に供給す
る。フル・レジスタ32およびマッチ・レジスタ29からの
信号は、フル・フラグ・エレメント26およびマッチ・フ
ラグ・エレメント27に各々供給される。マッチ検出器28
はまた状態レジスタ40に、単数マッチ信号および複数マ
ッチ信号の双方を供給する。
器28は、単一マッチ信号をマッチ・レジスタ29に供給す
る。フル・レジスタ32およびマッチ・レジスタ29からの
信号は、フル・フラグ・エレメント26およびマッチ・フ
ラグ・エレメント27に各々供給される。マッチ検出器28
はまた状態レジスタ40に、単数マッチ信号および複数マ
ッチ信号の双方を供給する。
第２図はまた、マルチプレクサ制御エレメント33の制御
下において、エレメント28および31から優先順位エンコ
ーダへの情報を多重化する優先順位マルチプレクサ25を
示す。セグメント・カウンタ34は、バス10および、OPコ
ード発生器39の出力に接続されるカウンタ制御エレメン
ト35の制御下にある。カウンタ34は一方の出力を状態レ
ジスタ40に、もう一方の出力を出力フィールド・セレク
タおよびデータ・読出エレメント42に供給する。
下において、エレメント28および31から優先順位エンコ
ーダへの情報を多重化する優先順位マルチプレクサ25を
示す。セグメント・カウンタ34は、バス10および、OPコ
ード発生器39の出力に接続されるカウンタ制御エレメン
ト35の制御下にある。カウンタ34は一方の出力を状態レ
ジスタ40に、もう一方の出力を出力フィールド・セレク
タおよびデータ・読出エレメント42に供給する。
この発明のシステムは動作の４つのモードを有し、第２
図においてモード発生器13の出力上の対応するブロック
によって示されたように、それらはコマンド書込（C
W）、データ書込（DW）、状態読出（SR）、およびデー
タ読出（DR）である。データ書込モードにおいては、デ
ータが被比較数レジスタに書込まれる。モード発生器13
はピン上においてチップ可能化信号を、ピン上にお
いて出力可能化信号を、ピン上において書込可能化信
号を、さらにピンＤ／上においてコマンド／データ信
号を受ける。被比較数レジスタ19はバス10およびCAMア
レイ11間における主要なバッファである。データ書込動
作が行なわれた後、コマンド書込サイクルの制御下にお
いてオペレーション（OP）・コードのうちの１つが行な
われ、データをCAMアレイ11内またはマスク・レジスタ1
8内へと移動させる。
図においてモード発生器13の出力上の対応するブロック
によって示されたように、それらはコマンド書込（C
W）、データ書込（DW）、状態読出（SR）、およびデー
タ読出（DR）である。データ書込モードにおいては、デ
ータが被比較数レジスタに書込まれる。モード発生器13
はピン上においてチップ可能化信号を、ピン上にお
いて出力可能化信号を、ピン上において書込可能化信
号を、さらにピンＤ／上においてコマンド／データ信
号を受ける。被比較数レジスタ19はバス10およびCAMア
レイ11間における主要なバッファである。データ書込動
作が行なわれた後、コマンド書込サイクルの制御下にお
いてオペレーション（OP）・コードのうちの１つが行な
われ、データをCAMアレイ11内またはマスク・レジスタ1
8内へと移動させる。
コマンド書込サイクル下においては、コマンド書込命令
が16ビット・バス10上にコード化される。バス10上の16
ビットのうち４ビットが、この発明において用いられる
160Pコードをデコード化するために使用される。また、
アレイ11内のどの位置にデータが被比較数レジスタ19か
ら転送されるべきかをアドレス位置が示すために、バス
10上には８ビットが存在する。この発明において設いら
れるOPコードが以下に挙げられる。
が16ビット・バス10上にコード化される。バス10上の16
ビットのうち４ビットが、この発明において用いられる
160Pコードをデコード化するために使用される。また、
アレイ11内のどの位置にデータが被比較数レジスタ19か
ら転送されるべきかをアドレス位置が示すために、バス
10上には８ビットが存在する。この発明において設いら
れるOPコードが以下に挙げられる。
Op コード ０ 初期設定 すべてのスキップ・ビットはLOW（スキップしない）に
セットされ、すべてのエンプティ・ビットはHIGH（エン
プティ）にセットされる。／MATCHおよび／FULL出力が
能動化される。モードは48ビット・モードにセットされ
る。マスク・レジスタおよびセグメント・カウンタは０
にリセットされる。不履行の場合、その後のデータ書込
は被比較数レジスタへであり、その後のデータ読出は被
比較数レジスタからである。
セットされ、すべてのエンプティ・ビットはHIGH（エン
プティ）にセットされる。／MATCHおよび／FULL出力が
能動化される。モードは48ビット・モードにセットされ
る。マスク・レジスタおよびセグメント・カウンタは０
にリセットされる。不履行の場合、その後のデータ書込
は被比較数レジスタへであり、その後のデータ読出は被
比較数レジスタからである。
Op コード １ 出力制御 マッチ・フラグおよびフル・フラグがこのコマンドによ
って能動化または不能化される。
って能動化または不能化される。
Op コード ２ モード選択 使用者は16または48ビット・モード間を選択するために
このコマンドを使用できる。16ビット・モードでは、セ
グメント・カウンタが増加されることはない。
このコマンドを使用できる。16ビット・モードでは、セ
グメント・カウンタが増加されることはない。
Op コード ３ 被比較数レジスタをマクス・レジ
スタへ移動せよ 被比較数レジスタ・データの内容がマスク・レジスタへ
移される。
スタへ移動せよ 被比較数レジスタ・データの内容がマスク・レジスタへ
移される。
Op コード ４ マスク・レジスタを被比較数レジ
スタへ移動せよ マスク・レジスタ・データの内容が被比較数レジスタへ
移される。
スタへ移動せよ マスク・レジスタ・データの内容が被比較数レジスタへ
移される。
Op コード ５ スキップ・ビット・アレイおよび
エンプティ・ビット・アレイからＩ／Ｏポートへの出力
を可能化せよ その後のすべてのデータ・モード読出の結果、エンプテ
ィ・ビットおよびスキップ・ビットから出力バッファへ
のデータの流れが得られる。アドレスはコマンド・レジ
スタ・アドレス・フィールドによって特定される。
エンプティ・ビット・アレイからＩ／Ｏポートへの出力
を可能化せよ その後のすべてのデータ・モード読出の結果、エンプテ
ィ・ビットおよびスキップ・ビットから出力バッファへ
のデータの流れが得られる。アドレスはコマンド・レジ
スタ・アドレス・フィールドによって特定される。
Op コード ６ 被比較数レジスタをCAMに移動せ
よ 被比較数レジスタ・データの内容がCAMに移される。エ
ンプティ・ビットおよびスキップ・ビットは変化しな
い。CAMアドレスがコマンド・ワード・アドレス・フィ
ールドによって特定される。セグメント・カウンタは変
化しない。
よ 被比較数レジスタ・データの内容がCAMに移される。エ
ンプティ・ビットおよびスキップ・ビットは変化しな
い。CAMアドレスがコマンド・ワード・アドレス・フィ
ールドによって特定される。セグメント・カウンタは変
化しない。
Op コード ７ CAMを被比較数レジスタへ移動せ
よ コマンド・ワード・アドレス・フィールドによって特定
されたCAMデータの内容が被比較数レジスタへ移され
る。セグメント・カウンタは変化しない。スキップ・ビ
ット・アレイおよびエンプティ・ビット・アレイ情報は
変えられない。
よ コマンド・ワード・アドレス・フィールドによって特定
されたCAMデータの内容が被比較数レジスタへ移され
る。セグメント・カウンタは変化しない。スキップ・ビ
ット・アレイおよびエンプティ・ビット・アレイ情報は
変えられない。
Op コード ８ 予約された Op コード ９ スキップ・ビット制御 使用者はこのコマンドを使用してスキップ・ビット・ア
レイに書込可能である。１サイクルでアレイ全体に書込
むことが可能であり、または所望のアドレス位置を提供
することによって、いずれの個々のビットにも書込むこ
とが可能である。
レイに書込可能である。１サイクルでアレイ全体に書込
むことが可能であり、または所望のアドレス位置を提供
することによって、いずれの個々のビットにも書込むこ
とが可能である。
Op コード 10 エンプティ・ビット制御 使用者はこのコマンドを使用してエンプティ・ビット・
アレイに書込可能である。１サイクルでアレイ全体に書
込可能であり、または所望のアドレス位置を提供するこ
とによって、いずれの個々のビットにも書込可能であ
る。
アレイに書込可能である。１サイクルでアレイ全体に書
込可能であり、または所望のアドレス位置を提供するこ
とによって、いずれの個々のビットにも書込可能であ
る。
Op コード 11 被比較数レジスタからＩ／Ｏポート
への出力を可能化せよ その後のすべてのデータ読出の結果、被比較数レジスタ
・セグメントから出力バッファへのデータの流れが得ら
れる。
への出力を可能化せよ その後のすべてのデータ読出の結果、被比較数レジスタ
・セグメントから出力バッファへのデータの流れが得ら
れる。
Op コード 12 マスク・レジスタからＩ／Ｏポート
への出力を可能化せよ その後のすべてのデータ読出の結果、マスク・レジスタ
・セグメントから出力バッファへのデータの流れが得ら
れる。
への出力を可能化せよ その後のすべてのデータ読出の結果、マスク・レジスタ
・セグメントから出力バッファへのデータの流れが得ら
れる。
Op コード 13 CAMからＩ／Ｏポートへの出力を能
動化せよ その後のすべてのデータ読出の結果、CAMセグメントか
ら出力バッファへのデータの流れが得られる。CAMアド
レスはコマンド・ワード・アドレス・フィールドによっ
て特定される。
動化せよ その後のすべてのデータ読出の結果、CAMセグメントか
ら出力バッファへのデータの流れが得られる。CAMアド
レスはコマンド・ワード・アドレス・フィールドによっ
て特定される。
Op コード 14 被比較数レジスタをCAMに移動せよ
（エンプティ・ビットおよびスキップ・ビットを共にLO
Wにリセットせよ） 被比較数レジスタ・データの内容が、コマンド・ワード
・アドレス・フィールドによって特定されるアドレス
（CAMアドレス）内へ移される。対応するエンプティ・
ビットおよびスキップ・ビットは共にLOWにリセットさ
せる。
（エンプティ・ビットおよびスキップ・ビットを共にLO
Wにリセットせよ） 被比較数レジスタ・データの内容が、コマンド・ワード
・アドレス・フィールドによって特定されるアドレス
（CAMアドレス）内へ移される。対応するエンプティ・
ビットおよびスキップ・ビットは共にLOWにリセットさ
せる。
Op コード 15 ロード・セグメント・カウンタ 使用者はセグメント・カウンタを変化させ、３つのセグ
メントのいずれか１つに達することが可能である。
メントのいずれか１つに達することが可能である。
これらの16のOpコード命令は、16ビット・バス上のコマ
ンド・ワードの４つの上位ビットによってコード化され
る。典型的なコマンド・ワードは以下のようなものであ
る。
ンド・ワードの４つの上位ビットによってコード化され
る。典型的なコマンド・ワードは以下のようなものであ
る。
状態読出は通常、使用者がマッチ位置と、それが複数の
マッチであるか単数のマッチであるかと、さらにチップ
が依然としてフルであるかとを知ることを所望するマッ
チ動作に続くものである。状態レジスタ30の内容はバス
10上に読出され得る。２つのビットがセグメント・カウ
ンタ22から、８つのビットが優先順位エンコーダ21から
のアドレス位置表示から、さらに３つのフラグ・ビット
がフル検出器31ならびに、マッチおよび複数マッチ検出
器28から読出され得る。
マッチであるか単数のマッチであるかと、さらにチップ
が依然としてフルであるかとを知ることを所望するマッ
チ動作に続くものである。状態レジスタ30の内容はバス
10上に読出され得る。２つのビットがセグメント・カウ
ンタ22から、８つのビットが優先順位エンコーダ21から
のアドレス位置表示から、さらに３つのフラグ・ビット
がフル検出器31ならびに、マッチおよび複数マッチ検出
器28から読出され得る。
この発明において用いられる状態ワードは以下のように
説明され得る。以下に示されたように、状態ワードの下
位の８つのビットはコード化されたアドレスであり、使
用者に位置を示す。
説明され得る。以下に示されたように、状態ワードの下
位の８つのビットはコード化されたアドレスであり、使
用者に位置を示す。
典型的な状態ワード 上位の３つの11は、複数のマッチ・フラグ、フル・フラ
グおよび単数マッチフラグを含む状態フラグを固定す
る。これらの内部フラグは外部フラグと同様のものであ
るべきであるが、しかしながら出力が能動化されない場
合、フラグはハイであるであろう。
グおよび単数マッチフラグを含む状態フラグを固定す
る。これらの内部フラグは外部フラグと同様のものであ
るべきであるが、しかしながら出力が能動化されない場
合、フラグはハイであるであろう。
データ読出は、使用者がCAMレジスタ17、比較レジスタ1
9、マスタ・レジスタ18またはメモリ41からのスキップ
・ビット情報およびエンプティ・ビット情報から情報を
得られる読出動作である。したがって、データ読出動作
は、先のコマンド書込サイクルに応じて４つのレジスタ
のうちの１つから情報を読出すであろう。
9、マスタ・レジスタ18またはメモリ41からのスキップ
・ビット情報およびエンプティ・ビット情報から情報を
得られる読出動作である。したがって、データ読出動作
は、先のコマンド書込サイクルに応じて４つのレジスタ
のうちの１つから情報を読出すであろう。
この発明においては各ワードにつき２つの状態ビットが
用いられ、一方はスキップ・ビットであり他方はエンプ
ティ・ビットと呼ばれる。スキップ・ビットは使用者が
ワードを完全にマスクすることを可能にするために用い
られ、エンプティ・ビットはアレイ内のエンプティ・ビ
ット位置に関連して使用される。
用いられ、一方はスキップ・ビットであり他方はエンプ
ティ・ビットと呼ばれる。スキップ・ビットは使用者が
ワードを完全にマスクすることを可能にするために用い
られ、エンプティ・ビットはアレイ内のエンプティ・ビ
ット位置に関連して使用される。
この発明は、最高優先順位のアドレス位置の表示を提供
するために優先順位エンコーダ21を使用する。アレイ全
体の比較が行なわれるマッチ動作のために、この特徴は
マッチが存在する場合、マッチ位置の表示を提供するで
あろう。マッチが存在しなければ、優先順位エンコーダ
21は使用され得る次のエンプティ・アドレスを指摘する
であろう。複数マッチ状態においては、マッチ位置が１
つより多く存在する。この状態では、マッチしたすべて
の位置を同定できるまで、ワードごとに使用者が完全に
マスクすることが可能である。これはスキップ・ビット
・回路20およびスキップ・ビット・アレイ22によって示
されたスキップ・ビットの機能である。ここで、エンプ
ティ・ビットと呼ばれるもう１つのビットが使用され
る。エンプティ・ビットは、エンプティ書込回路23およ
びエンプティ・ビット・アレイ24によって示される。エ
ンプティ・ビットは２つの状態を有する。一方はエンプ
ティであり、他方はフルである。使用者は、ある特定の
ワード位置を使用し、かつこの特定のワード位置が占有
されていることを示すようにエンプティ・ビットをセッ
トすることができる。したがって、使用者がCAMセルに
書込もうとするときには、その中の一部の位置が既にデ
ータを格納していることがわかるであろう。
するために優先順位エンコーダ21を使用する。アレイ全
体の比較が行なわれるマッチ動作のために、この特徴は
マッチが存在する場合、マッチ位置の表示を提供するで
あろう。マッチが存在しなければ、優先順位エンコーダ
21は使用され得る次のエンプティ・アドレスを指摘する
であろう。複数マッチ状態においては、マッチ位置が１
つより多く存在する。この状態では、マッチしたすべて
の位置を同定できるまで、ワードごとに使用者が完全に
マスクすることが可能である。これはスキップ・ビット
・回路20およびスキップ・ビット・アレイ22によって示
されたスキップ・ビットの機能である。ここで、エンプ
ティ・ビットと呼ばれるもう１つのビットが使用され
る。エンプティ・ビットは、エンプティ書込回路23およ
びエンプティ・ビット・アレイ24によって示される。エ
ンプティ・ビットは２つの状態を有する。一方はエンプ
ティであり、他方はフルである。使用者は、ある特定の
ワード位置を使用し、かつこの特定のワード位置が占有
されていることを示すようにエンプティ・ビットをセッ
トすることができる。したがって、使用者がCAMセルに
書込もうとするときには、その中の一部の位置が既にデ
ータを格納していることがわかるであろう。
セグメント・カウンタ22は内部セグメントの跡を辿り、
その結果16ビット・バス10は48ビット動作のために使用
され得る。16ビット・モードの動作のスタートにおいて
は、カウンタ22内のセグメント・カウントが既に第１の
カウントにセットされている。しかしながら、使用者
が、上に示されたOPコード15を使用することによって、
第２のセグメント・カウントまたは第３のセグメント・
カウントに進むことが可能な、使用者がプログラム可能
な特徴も存在する。
その結果16ビット・バス10は48ビット動作のために使用
され得る。16ビット・モードの動作のスタートにおいて
は、カウンタ22内のセグメント・カウントが既に第１の
カウントにセットされている。しかしながら、使用者
が、上に示されたOPコード15を使用することによって、
第２のセグメント・カウントまたは第３のセグメント・
カウントに進むことが可能な、使用者がプログラム可能
な特徴も存在する。
２つの外部フラグが存在し、そのうちの一方は「フル」
フラグであり、エレメント26で示され、他方は「マッ
チ」フラグであり、エレメント27によって示される。マ
ッチがアレイ内に存在し、それがマッチ検出器28によっ
て検出され、マッチ・レジスタ29を介してフラグ27に伝
えられると、マッチ・フラグはローになるであろう。同
様に、アレイ11内のすべての位置がフルであり、それが
フル検出器31によって検出され、かつフル・レジスタ32
を介してフラグ26に伝えられると、フル・フラグはロー
となるであろう。フル・フラグ26がハイであるとき、こ
れはアレイ11内に依然としてエンプティの位置が使用者
のために存在することを意味し、マッチ・フラグ27がハ
イのままであるとき、これはマッチが存在しないことを
意味する。
フラグであり、エレメント26で示され、他方は「マッ
チ」フラグであり、エレメント27によって示される。マ
ッチがアレイ内に存在し、それがマッチ検出器28によっ
て検出され、マッチ・レジスタ29を介してフラグ27に伝
えられると、マッチ・フラグはローになるであろう。同
様に、アレイ11内のすべての位置がフルであり、それが
フル検出器31によって検出され、かつフル・レジスタ32
を介してフラグ26に伝えられると、フル・フラグはロー
となるであろう。フル・フラグ26がハイであるとき、こ
れはアレイ11内に依然としてエンプティの位置が使用者
のために存在することを意味し、マッチ・フラグ27がハ
イのままであるとき、これはマッチが存在しないことを
意味する。
マッチ・ラインおよびフル・ライン双方からの信号は、
優先順位マルチプレクサ25を介して優先順位エンコーダ
21内へ入る（第２図）。マッチが存在しなければ、エン
プティ位置もデコード化されるであろう。エンプティ情
報およびマッチ情報の双方が優先順位エンコーダ21に供
給される。フル検出器31は、アレイがフルまたはエンプ
ティのいずれであるかを検出するであろう。
優先順位マルチプレクサ25を介して優先順位エンコーダ
21内へ入る（第２図）。マッチが存在しなければ、エン
プティ位置もデコード化されるであろう。エンプティ情
報およびマッチ情報の双方が優先順位エンコーダ21に供
給される。フル検出器31は、アレイがフルまたはエンプ
ティのいずれであるかを検出するであろう。
マッチ検出器28はマッチ状態またはマッチがない状態を
検出し、一方優先順位エンコーダ21はマッチ・ワードの
アドレス位置を提供する。優先順位エンコーダ・マルチ
プレクサ25はエンプティ位置情報およびマッチ位置情報
を多重化し、その結果２つのうちの１つがエンコーダ21
内へと入ってくるであろう。
検出し、一方優先順位エンコーダ21はマッチ・ワードの
アドレス位置を提供する。優先順位エンコーダ・マルチ
プレクサ25はエンプティ位置情報およびマッチ位置情報
を多重化し、その結果２つのうちの１つがエンコーダ21
内へと入ってくるであろう。
第３図を参照すると、９つのトランジスタ・セルが示さ
れ、そのうちトランジスタM1、M2、M5、M6は基本的記憶
エレメントであり、かつ交差結合対である。ノードSTお
よび▲▼は記憶ノードであり、トランジスタM3、M4
は、記憶ノードをビット・ライン対BLおよび▲▼に
接続するアクセス・トランジスタである。セル・アクセ
スはWLを介するワード・ライン選択によって制御され
る。トランジスタM7、M8はマッチ・トランジスタであ
る。それらは、記憶ノードST、▲▼およびビット・
ライン対BL、▲▼が入力であり、マッチ・ノード
が出力である排他的NOR形状で接続される。セル・デー
タがビット・ライン上のそれに等しいとき、論理ローが
上に現われる。
れ、そのうちトランジスタM1、M2、M5、M6は基本的記憶
エレメントであり、かつ交差結合対である。ノードSTお
よび▲▼は記憶ノードであり、トランジスタM3、M4
は、記憶ノードをビット・ライン対BLおよび▲▼に
接続するアクセス・トランジスタである。セル・アクセ
スはWLを介するワード・ライン選択によって制御され
る。トランジスタM7、M8はマッチ・トランジスタであ
る。それらは、記憶ノードST、▲▼およびビット・
ライン対BL、▲▼が入力であり、マッチ・ノード
が出力である排他的NOR形状で接続される。セル・デー
タがビット・ライン上のそれに等しいとき、論理ローが
上に現われる。
−マッチ状態 同じワード内のすべてのＮビットがそれらの各々のビッ
ト・ライン対上にマッチング・データを有するとき、マ
ッチ状態が生じる。すべてのセル・マッチ・ノードが論
理ローであるので、マッチ・ライン上のプル・ダウン・
トランジスタM13はいずれもオンにはされ得ない。した
がって、マッチ・ラインは論理ハイのままであろう。対
照的に、いずれの非マッチ状態も、マッチ・ラインがロ
ーに引かれるという結果をもとらすであろう。
ト・ライン対上にマッチング・データを有するとき、マ
ッチ状態が生じる。すべてのセル・マッチ・ノードが論
理ローであるので、マッチ・ライン上のプル・ダウン・
トランジスタM13はいずれもオンにはされ得ない。した
がって、マッチ・ラインは論理ハイのままであろう。対
照的に、いずれの非マッチ状態も、マッチ・ラインがロ
ーに引かれるという結果をもとらすであろう。
−ビット・マスキング BLおよび▲▼が共にトランジスタM11およびM12によ
ってローにセットされるとき、マッチ・ノードはCAM
セル・データにかかわりなくローであろう。したがっ
て、この特定のビットはマッチに強制されるであろう。
ビット・マスキング状態は、マスク・レジスタ18を
「１」にセット（BL、および▲▼を共にローに強
制）することによって達成され得る。マスク・レジスタ
が「０」にセットされるとき、レジスタ19内のデータが
ビット・ライン対上に現われ得る。
ってローにセットされるとき、マッチ・ノードはCAM
セル・データにかかわりなくローであろう。したがっ
て、この特定のビットはマッチに強制されるであろう。
ビット・マスキング状態は、マスク・レジスタ18を
「１」にセット（BL、および▲▼を共にローに強
制）することによって達成され得る。マスク・レジスタ
が「０」にセットされるとき、レジスタ19内のデータが
ビット・ライン対上に現われ得る。
−ワード・マスキング ワードマスキングは、スキップ・ビットまたは／および
エンプティ・ビットのいずれかをハイにセットすること
によって達成され得る。どちらの場合においても、最終
のマッチ・ライン出力（ML′）は、マッチが存在しても
非マッチ状態を示すNANDゲート（47）およびNORゲート
（48）を介してローに強制されるであろう。
エンプティ・ビットのいずれかをハイにセットすること
によって達成され得る。どちらの場合においても、最終
のマッチ・ライン出力（ML′）は、マッチが存在しても
非マッチ状態を示すNANDゲート（47）およびNORゲート
（48）を介してローに強制されるであろう。
−アレイ・リセット すべてのエンプティ・ビットがハイにセットされると
き、すべてのＭワードはエンプティにセットされ、新し
いデータのために利用可能である。
き、すべてのＭワードはエンプティにセットされ、新し
いデータのために利用可能である。
第１図は、この発明のエレメントを示す機能ブロック図
である。 第２図は、この発明によるCAMアレイ・プロセッサの形
状の細部をさらに示すブロック図である。 第３図は、ワード・マスキングおよびワード・リセッテ
ィングまたはアレイ・リセッティングのためにこの発明
において使用される論理の一部を示し、第２図のCAMア
レイ中の１セルと、そのセルが含まれるワードに対応す
るスキップビットおよびエンプティビットと、第２図の
記述子36および関連の回路を示す図である。 図において、１はビット・ライン記述子回路、２は行デ
コーダ、３はビット・ライン・プリチャージ回路、４は
ワード・マスキングおよびリセット回路、５はマッチ検
出器、６は優先順位エンコーダ、７は制御論理ネットワ
ーク、10は16ビットバス、14はセンスアンプ、17はCAM
レジスタ、18はマスク・レジスタ、19は被比較数レジス
タ、36は記述子エレメントを示す。
である。 第２図は、この発明によるCAMアレイ・プロセッサの形
状の細部をさらに示すブロック図である。 第３図は、ワード・マスキングおよびワード・リセッテ
ィングまたはアレイ・リセッティングのためにこの発明
において使用される論理の一部を示し、第２図のCAMア
レイ中の１セルと、そのセルが含まれるワードに対応す
るスキップビットおよびエンプティビットと、第２図の
記述子36および関連の回路を示す図である。 図において、１はビット・ライン記述子回路、２は行デ
コーダ、３はビット・ライン・プリチャージ回路、４は
ワード・マスキングおよびリセット回路、５はマッチ検
出器、６は優先順位エンコーダ、７は制御論理ネットワ
ーク、10は16ビットバス、14はセンスアンプ、17はCAM
レジスタ、18はマスク・レジスタ、19は被比較数レジス
タ、36は記述子エレメントを示す。
フロントページの続き (72)発明者 ヒロシ・ヨシダ アメリカ合衆国、カリフォルニア州、サン タ・クララ ハルフォード・アベニュ、 1720、ナンバー・233 (72)発明者 ムーン・イー・ワン アメリカ合衆国、カリフォルニア州、クパ ーティノ ロス・オンダス・ウェイ、 10426
Claims (5)
- 【請求項１】各ワードにつきＮビットで構成されたビッ
トを含むセルのアレイを含む、内容でアドレス指定可能
なメモリ・アレイであって、 前記ワードの各々の前記ビットうち第１のビットはスキ
ップ・ビットであり、 前記アレイは、選択されたワードの位置を突止めるため
に、前記ワードの内容に基づいてサーチされ、 各ワードの前記ビットのうち第２のビットはエンプティ
・ビットとして同定され、 前記ワードを、その中のスキップ・ビットの存在を検出
するために、検査するための手段と、 前記ワードを、その中のエンプティ・ビットの存在を検
出するために、検査するための手段と、 前記ワードの１つにおける１つの前記スキップ・ビット
の検出に応答して、前記検出されたスキップ・ビットを
含む前記ワードを前記サーチから除去するための手段と
を含む、メモリ・アレイ。 - 【請求項２】前記ワードの選択されたもののうちの前記
スキップ・ビットを、予め定められた第１の値にセット
し、前記予め定められた第１の値にセットされた前記ス
キップ・ビットを有するワードの位置を前記スキップ・
ビット検査手段がスキップするようにする、特許請求の
範囲第１項に記載の、メモリ・アレイ。 - 【請求項３】前記ワードの選択されたもののうちの前記
エンプティ・ビットを、予め定められた第１の値にセッ
トし、前記予め定められた第１の値にセットされた前記
エンプティ・ビットを有するワードの位置を前記エンプ
ティ・ビット検査手段がスキップするようにする、特許
請求の範囲第１項に記載の、メモリ・アレイ。 - 【請求項４】前記ワードの各々の前記エンプティ・ビッ
トのすべてを、予め定められた第１の値にセットし、前
記アレイをエンプティ状態にリセットするために、前記
ワードのすべての前記セルのすべてを空白にする、特許
請求の範囲第１項に記載の、メモリ・アレイ。 - 【請求項５】前記ワードの選択されたもののうちの前記
エンプティ・ビットを、前記予め定められた第１の値に
セットし、前記エンプティ・ビットが前記第１の予め定
められた値を有する前記ワードの中の前記セルを前記エ
ンプティ・ビット検査手段がエンプティにするようにす
るための手段を含む、特許請求の範囲第１項に記載の、
メモリ・アレイ。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US193,312 | 1988-05-11 | ||
| US07/193,312 US4890260A (en) | 1988-05-11 | 1988-05-11 | Content addressable memory array with maskable and resettable bits |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0264994A JPH0264994A (ja) | 1990-03-05 |
| JPH0664911B2 true JPH0664911B2 (ja) | 1994-08-22 |
Family
ID=22713111
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1117163A Expired - Fee Related JPH0664911B2 (ja) | 1988-05-11 | 1989-05-10 | 内容でアドレス指定可能なメモリ・アレイ |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US4890260A (ja) |
| EP (1) | EP0341899B1 (ja) |
| JP (1) | JPH0664911B2 (ja) |
| AT (1) | ATE91561T1 (ja) |
| DE (1) | DE68907518T2 (ja) |
| ES (1) | ES2044105T3 (ja) |
Families Citing this family (29)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01196792A (ja) * | 1988-01-29 | 1989-08-08 | Mitsubishi Electric Corp | 半導体記憶装置 |
| US5155858A (en) * | 1988-10-27 | 1992-10-13 | At&T Bell Laboratories | Twin-threshold load-sharing system with each processor in a multiprocessor ring adjusting its own assigned task list based on workload threshold |
| US5036486A (en) * | 1989-07-31 | 1991-07-30 | Hitachi, Ltd | Associative memory device |
| US5101376A (en) * | 1989-07-31 | 1992-03-31 | Hitachi, Ltd. | Integrated microprocessor with associative memory device |
| US5134589A (en) * | 1989-10-30 | 1992-07-28 | Mitsubishi Denki Kabushiki Kaisha | Semiconductor memory device having a flash write function |
| SE9002558D0 (sv) * | 1990-08-02 | 1990-08-02 | Carlstedt Elektronik Ab | Processor |
| US5999434A (en) | 1992-01-10 | 1999-12-07 | Kawasaki Steel Corporation | Hierarchical encoder including timing and data detection devices for a content addressable memory |
| US5619446A (en) * | 1992-01-10 | 1997-04-08 | Kawasaki Steel Corporation | Hierarchical encoder including timing and data detection devices for a content addressable memory |
| US5351208A (en) * | 1992-04-27 | 1994-09-27 | Integrated Information Technology, Inc. | Content addressable memory |
| JP2695102B2 (ja) * | 1992-09-30 | 1997-12-24 | 川崎製鉄株式会社 | 内容アドレス式メモリ |
| US5444649A (en) * | 1993-06-10 | 1995-08-22 | Apple Computer, Inc. | Associative memory system having configurable means for comparing fields in an array of stored data words with corresponding one or more fields in a supplied argument word |
| JPH07105689A (ja) * | 1993-10-04 | 1995-04-21 | Kawasaki Steel Corp | 連想メモリ |
| KR950012218A (ko) * | 1993-10-04 | 1995-05-16 | 토자끼 시노부 | 연상 메모리 |
| US5422838A (en) * | 1993-10-25 | 1995-06-06 | At&T Corp. | Content-addressable memory with programmable field masking |
| US6122706A (en) * | 1993-12-22 | 2000-09-19 | Cypress Semiconductor Corporation | Dual-port content addressable memory |
| US5649149A (en) * | 1994-08-01 | 1997-07-15 | Cypress Semiconductor Corporation | Integrated content addressable memory array with processing logical and a host computer interface |
| US5860085A (en) * | 1994-08-01 | 1999-01-12 | Cypress Semiconductor Corporation | Instruction set for a content addressable memory array with read/write circuits and an interface register logic block |
| DE69625327D1 (de) * | 1996-03-20 | 2003-01-23 | St Microelectronics Srl | Zeitzuteilender interner Bus, insbesondere für nichtflüchtige Speicher |
| US5706224A (en) * | 1996-10-10 | 1998-01-06 | Quality Semiconductor, Inc. | Content addressable memory and random access memory partition circuit |
| US6115761A (en) * | 1997-05-30 | 2000-09-05 | Lsi Logic Corporation | First-In-First-Out (FIFO) memories having dual descriptors and credit passing for efficient access in a multi-processor system environment |
| US5946003A (en) * | 1997-06-02 | 1999-08-31 | Hewlett Packard Co | Method and apparatus for increasing object read-back performance in a rasterizer machine |
| US6336113B1 (en) * | 1998-12-30 | 2002-01-01 | Kawasaki Steel Corporation | Data management method and data management apparatus |
| US6317349B1 (en) | 1999-04-16 | 2001-11-13 | Sandisk Corporation | Non-volatile content addressable memory |
| US6166938A (en) * | 1999-05-21 | 2000-12-26 | Sandisk Corporation | Data encoding for content addressable memories |
| US6157558A (en) * | 1999-05-21 | 2000-12-05 | Sandisk Corporation | Content addressable memory cell and array architectures having low transistor counts |
| RU2168216C2 (ru) * | 1999-07-12 | 2001-05-27 | Военный университет войсковой противовоздушной обороны Вооруженных Сил Российской Федерации | Ассоциативная запоминающая матрица |
| US6591331B1 (en) * | 1999-12-06 | 2003-07-08 | Netlogic Microsystems, Inc. | Method and apparatus for determining the address of the highest priority matching entry in a segmented content addressable memory device |
| US7401181B1 (en) * | 2002-05-29 | 2008-07-15 | Core Networks Llc | System and method for comparand reuse |
| CN112729581B (zh) * | 2020-12-28 | 2022-06-28 | 潍柴动力股份有限公司 | 温度检测方法及装置 |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4296475A (en) * | 1978-12-19 | 1981-10-20 | U.S. Philips Corporation | Word-organized, content-addressable memory |
| US4377855A (en) * | 1980-11-06 | 1983-03-22 | National Semiconductor Corporation | Content-addressable memory |
| US4670858A (en) * | 1983-06-07 | 1987-06-02 | Tektronix, Inc. | High storage capacity associative memory |
| EP0175603A2 (en) * | 1984-08-21 | 1986-03-26 | FAIRCHILD CAMERA & INSTRUMENT CORPORATION | Content addressable memory cell |
| GB2182789B (en) * | 1985-11-08 | 1989-03-08 | Texas Instruments Ltd | A content addressable memory |
| NL8600342A (nl) * | 1986-02-12 | 1987-09-01 | Philips Nv | Woordgeorganiseerd naar inhoud adresseerbaar geheugen. |
-
1988
- 1988-05-11 US US07/193,312 patent/US4890260A/en not_active Expired - Lifetime
-
1989
- 1989-05-04 DE DE89304469T patent/DE68907518T2/de not_active Expired - Lifetime
- 1989-05-04 EP EP89304469A patent/EP0341899B1/en not_active Expired - Lifetime
- 1989-05-04 AT AT89304469T patent/ATE91561T1/de not_active IP Right Cessation
- 1989-05-04 ES ES89304469T patent/ES2044105T3/es not_active Expired - Lifetime
- 1989-05-10 JP JP1117163A patent/JPH0664911B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| ES2044105T3 (es) | 1994-01-01 |
| EP0341899A1 (en) | 1989-11-15 |
| JPH0264994A (ja) | 1990-03-05 |
| DE68907518D1 (de) | 1993-08-19 |
| DE68907518T2 (de) | 1993-10-28 |
| ATE91561T1 (de) | 1993-07-15 |
| EP0341899B1 (en) | 1993-07-14 |
| US4890260A (en) | 1989-12-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4928260A (en) | Content addressable memory array with priority encoder | |
| US4890260A (en) | Content addressable memory array with maskable and resettable bits | |
| US4888731A (en) | Content addressable memory array system with multiplexed status and command information | |
| US4975873A (en) | Content addressable memory with flag storage to indicate memory state | |
| US5890201A (en) | Content addressable memory having memory cells storing don't care states for address translation | |
| US5341500A (en) | Data processor with combined static and dynamic masking of operand for breakpoint operation | |
| US5239642A (en) | Data processor with shared control and drive circuitry for both breakpoint and content addressable storage devices | |
| JP2745949B2 (ja) | オペランド情報の静的および動的マスキングを同時かつ独立して行うデータ・プロセッサ | |
| US5752260A (en) | High-speed, multiple-port, interleaved cache with arbitration of multiple access addresses | |
| US4835733A (en) | Programmable access memory | |
| US4812969A (en) | Address translation unit | |
| EP0213843A2 (en) | Digital processor control | |
| US20060143428A1 (en) | Semiconductor signal processing device | |
| US8077492B2 (en) | Semiconductor memory device | |
| US4159538A (en) | Associative memory system | |
| US4580217A (en) | High speed memory management system and method | |
| US5220526A (en) | Method and apparatus for indicating a duplication of entries in a content addressable storage device | |
| JP2004520668A (ja) | 内容照合（連想）記憶装置に関する改良 | |
| US5390139A (en) | Devices, systems and methods for implementing a Kanerva memory | |
| US5093909A (en) | Single-chip microcomputer including an eprom capable of accommodating different memory capacities by address boundary discrimination | |
| US5577221A (en) | Method and device for expanding ROM capacity | |
| US4982379A (en) | Semiconductor memory device having associative function | |
| WO1991007754A1 (en) | Read-while-write-memory | |
| US7577784B1 (en) | Full-ternary content addressable memory (CAM) configurable for pseudo-ternary operation | |
| JP2564942B2 (ja) | 選択的連想記憶装置及びその制御方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |