連想メモリ装置
【発明の詳細な説明】
産業上の利用分野 本発明は、データ高速検索等に非常に有効な記憶素子、連想メモリに関するものである。
従来の技術 連想メモリは、通常のメモリ（例えばランダムアクセスメモリ）のような「アドレス信号を入力しその場所に格納してあるデータを読み出す」のではなく、逆に「データ（記憶内容）を入力し、これと一致するデータが内部に格納されている場合は、一致信号を出力、格納されていない場合には不一致信号を出力する」という基本機能を有する。更に応用分野に応じて、上記基本機能の他に入力データと格納データとの一致がある場合にその箇所のアドレスを出力したり、入力データを一種のタグとし、データの拡張部分（エクステンション）を出力したりするものもある。
何れにせよ連想メモリにおける特徴的な機能は並列的な一致検出機能である。従来より、この機能を実現するためには大別して２種類の方法が知られている。
第１は各メモリセルごとに一致検出機能、即ち排他的論理和の機能を持たせることで、セルの寸法は当然大きくなる。通常この形態はフルアソシアティブ形の連想メモリ（Full Associative Content−Addressable Memory;以後FA−CAMと記述する）と呼ばれている。参考文献1:T.Kohonen“コンテント アドレッサブル メモリーズ”（“Content−Addressable Memories"）Berlin,Heidelberg;1980 Springer−Verlag.参考文献2:H.Kadota et.al.“An 8Kbit Content−Addressable and Reentrant Memory"アイイイイ ジャーナル オブ ソリッド−ステイト サーキッツ（IEEE Journal of solid−State Circuits）,volSC−20 No.5 PP.951〜957 October 1985）
第２のものは、通常のランダムアクセスメモリ24（以後RAMと略述する）とその周辺に排他的論理和回路４を付加した第２図に示す構成のもので、検索用の入力ワードデータの一部のビットフィールド（以後この部分をアドレスフィールドと呼ぶ）をアドレスと考え、連想メモリのアドレスデコーダ21に入力し選ばれたワードに格納されている内容フィールド22のデータが読み出され、これが前述の検索用入力ワードデータの残りのビットフィールド（アドレスフィールドを除いたデータ）と同一であるかどうかが前述の排他的論理和回路４で判定され、同一であればこの検索用入力ワードデータは格納されていることを示し、不一致であれば検索用入力データは格納されていないことを示している。（この形の連想メモリをDirect−Mapping CAM,と呼び以後DM−CAMと略述する）。
しかし、このDM−CAM方法の欠点は、ランダムアクセスメモリ全体の中で未使用の格納場所（未使用ワード）がまた残っている状態でも、アドレスフィールドが同一で残りのビットフィールドが異なるデータは２個以上格納できないことである。（通常データの衝突と呼ばれる）
この衝突を回避するための色々の方法が提案されているが何れの方法を用いても素子全体の連想処理特性はかなり劣化する。
発明が解決しようとする課題 連想メモリは多くのデータに対して高速の検索を行ったりする場合非常に有効な素子であるが、従来技術の部分で述べたように、FA−CAMではセル面積が大きいので、通常のRAM程大容量のものが得られない。他方、DM−CAMでは衝突を回避するための回路などにより性能が劣化する（処理速度が遅くなる）。従って本発明の目的は、充分大容量でしかも素子全体の連想処理速度も速い連想メモリを提供することである。
課題を解決するための手段 本発明は、FA−CAM,DM−CAMおよびこの両者にデータの供給することができる配線、DM−CAMで衝突が起こった場合選択的FA−CAMのバリッドビットのフラグをたてる論理回路網から構成される。
作用 本発明は上記構成により、連想メモリへの書き込みをDM−CAMとFA−CAMに並行して行い、DM−CAM衝突が発生した場合にFA−CAMの書き込んだワードアドレスのバリッドビットフラグをたててその書き込まれたデータを有効にし、衝突が発生したい場合はこのフラグをたてずDM−CAM側のバリッドビットをたて、FA−CAM側のバリッドをたてずにおくため実質的にFA−CAMには書き込みがなされていないことにより書き込み動作時の性能劣化を防止し、装置全体として高速性を失うことなく大容量の連想メモリ装置が実現できる。
実 施 例 第１図に本発明の実施例を示す。連想メモリ要素１はFA−CAMである。FA−CAMの主要な動作は「書き込み」と「検索」である。書き込み動作では、空きアドレス（バリッドビットに有効フラグがたっていないアドレス）に優先順位がついており、もっとも優先順位が高いアドレスのワードに新しいデータが書き込まれる（書き込まれると同時にバリッドビットには有効フラグがたつ）。一方、検索動作では、検査用の入力ワードデータがメモリの全ワードに同時に供給され、各ワードに配置された一致検出回路（具体的には排他的論理和回路）により、入力ワードデータと格納されているデータとの一致、不一致がしらべられ、もし一致しているワードがあればそのワードの一致検出部から一致検出信号が（場合によってはそのアドレス情報も同時に）外部へ出力される。
次に、第１図の連想メモリ要素２はDM−CAMである。DM−CAMは実質的に複数I/Oのランダムアクセスメモリと一致検出回路４（具体的には排他的論理和回路）から構成されている。従って単位面積当りの記憶容量（メモリの集積度）はFA−CAMに比べてかなり大きいものが得られる。第２図にこのDM−CAMの構成とデータ入力の方法を示す。
入力ワードデータの各ビットはアドレスフィールドのビットと残りのフィールド（内容フィールドと以後略述する）に分けられる。アドレスフィールドの各ビット情報はRAMのアドレス入力としてアドレスデコーダに印加され対応したRAMの内容記憶部分のワードの読みだし動作を行う。読み出された各ビットは、前述の内容フィールドの各ビットとの一致検出回路で行われ、全ビットが同一の場合は一致しており、１ビットでも異なればデータは不一致で検索データは格納されていないことになる。
本実施例では、データの書き込み時（Wt）、検索時（Rv）何れも、連想メモリ要素１、要素２の両方に同時に処理を開始することを特徴としている。
まず、書き込みの時（Wt）には、連想メモリ要素１のFA−CAMに対しては、書き込みの優先度がもっとも高いワードに対して一応入力ワードデータの書き込みが行われるが、そのワードのバリッドフラグはまた１にしない。連想メモリ要素２のDM−CAMに対してはまずバリッドビットの読み出し（Rd）が行なわれ、読み出されたバリッドフラグが１の場合即ち、既にそのアドレスのワードが使用中の場合に先程保留状態にしておいた要素１のバリッドフラグを１（即ち使用中または有効）に設定する。逆に連想メモリ要素２のバリッドフラグが０の場合はそのアドレスは未使用なのでRAMのそのワードに対して書き込み（Wt）動作を行い同時にそのアドレスのバリッドフラグも１に設定する。これら一連の動作は制御回路部３で制御される。
次に検査の場合（Rv）は連想メモリ要素１に対して検索動作、連想メモリ要素２対して内容フィールドの読み出し動作が同時に実行され、各々のバリッドビットを読みだしも同時に実行され、各々の検出信号とバリッド信号の論理積信号の何れかが１であれば装置全体として検索データを格納していることを示し、何れも０であれば装置全体として検査データを格納していないことを示している。
また、事前に、複数のデータを同一アドレスに指定しなければならないことが分っている場合（即ち特定のアドレスで衝突が頻繁に発生する可能性がある場合）連想メモリ要素２のアドレス入力として、単純にアドレスフィールドの各ビットを直接印加するのではなく、種々のビットからある種の変換を行なって（通常この動作をハッシュ変換またはハッシングと呼ぶ）衝突の確立を下げることができる。
第３図はこの変換回路即ちハッシュコード発生回路５を設けた構成の連想メモリ装置を示している。衝突の確立が、アドレスによって非常に偏っている場合はハッシング等を行なわなければ、本発明においてもFA−CAMのワードが短時間で「フル」状態となり、しかもDM−CAM側は未使用アドレスがあるという不都合が発生する可能性がある。
発明の効果 実施例の動作説明より明らかなとうり、従来の連想メモリの二種類の問題点が解消できる。即ち、純粋のFA−CAMの場合問題となったメモリセルが大きいために充分大容量の連想メモリが得られないという欠点に対しては、大容量のDM−CAMを用いることで改善している。また、従来のDM−CAMでは、衝突が起こった場合の処理に時間を要し性能が低下していたが本発明の連想メモリ装置では、衝突が起こってもFA−CAMに即刻退避できほとんど、無駄時間なしで処理できるので高速性は失われない。つまり、大容量で高性能の連想メモリを実現できる。
【図面の簡単な説明】
第１図は、本発明の基本構成例を示すブロック図、第２図R>図は、ダイレクトマップ形の連想メモリの構成例を示すブロック図、第３図は、本発明の基本構成にハッシュコード生成回路を加えた別の構成例を示すブロック図である。
1,2……連想メモリ要素、３……制御回路、４……一致検出回路、５……ハッシュコード発生回路。
産業上の利用分野 本発明は、データ高速検索等に非常に有効な記憶素子、連想メモリに関するものである。
従来の技術 連想メモリは、通常のメモリ（例えばランダムアクセスメモリ）のような「アドレス信号を入力しその場所に格納してあるデータを読み出す」のではなく、逆に「データ（記憶内容）を入力し、これと一致するデータが内部に格納されている場合は、一致信号を出力、格納されていない場合には不一致信号を出力する」という基本機能を有する。更に応用分野に応じて、上記基本機能の他に入力データと格納データとの一致がある場合にその箇所のアドレスを出力したり、入力データを一種のタグとし、データの拡張部分（エクステンション）を出力したりするものもある。
何れにせよ連想メモリにおける特徴的な機能は並列的な一致検出機能である。従来より、この機能を実現するためには大別して２種類の方法が知られている。
第１は各メモリセルごとに一致検出機能、即ち排他的論理和の機能を持たせることで、セルの寸法は当然大きくなる。通常この形態はフルアソシアティブ形の連想メモリ（Full Associative Content−Addressable Memory;以後FA−CAMと記述する）と呼ばれている。参考文献1:T.Kohonen“コンテント アドレッサブル メモリーズ”（“Content−Addressable Memories"）Berlin,Heidelberg;1980 Springer−Verlag.参考文献2:H.Kadota et.al.“An 8Kbit Content−Addressable and Reentrant Memory"アイイイイ ジャーナル オブ ソリッド−ステイト サーキッツ（IEEE Journal of solid−State Circuits）,volSC−20 No.5 PP.951〜957 October 1985）
第２のものは、通常のランダムアクセスメモリ24（以後RAMと略述する）とその周辺に排他的論理和回路４を付加した第２図に示す構成のもので、検索用の入力ワードデータの一部のビットフィールド（以後この部分をアドレスフィールドと呼ぶ）をアドレスと考え、連想メモリのアドレスデコーダ21に入力し選ばれたワードに格納されている内容フィールド22のデータが読み出され、これが前述の検索用入力ワードデータの残りのビットフィールド（アドレスフィールドを除いたデータ）と同一であるかどうかが前述の排他的論理和回路４で判定され、同一であればこの検索用入力ワードデータは格納されていることを示し、不一致であれば検索用入力データは格納されていないことを示している。（この形の連想メモリをDirect−Mapping CAM,と呼び以後DM−CAMと略述する）。
しかし、このDM−CAM方法の欠点は、ランダムアクセスメモリ全体の中で未使用の格納場所（未使用ワード）がまた残っている状態でも、アドレスフィールドが同一で残りのビットフィールドが異なるデータは２個以上格納できないことである。（通常データの衝突と呼ばれる）
この衝突を回避するための色々の方法が提案されているが何れの方法を用いても素子全体の連想処理特性はかなり劣化する。
発明が解決しようとする課題 連想メモリは多くのデータに対して高速の検索を行ったりする場合非常に有効な素子であるが、従来技術の部分で述べたように、FA−CAMではセル面積が大きいので、通常のRAM程大容量のものが得られない。他方、DM−CAMでは衝突を回避するための回路などにより性能が劣化する（処理速度が遅くなる）。従って本発明の目的は、充分大容量でしかも素子全体の連想処理速度も速い連想メモリを提供することである。
課題を解決するための手段 本発明は、FA−CAM,DM−CAMおよびこの両者にデータの供給することができる配線、DM−CAMで衝突が起こった場合選択的FA−CAMのバリッドビットのフラグをたてる論理回路網から構成される。
作用 本発明は上記構成により、連想メモリへの書き込みをDM−CAMとFA−CAMに並行して行い、DM−CAM衝突が発生した場合にFA−CAMの書き込んだワードアドレスのバリッドビットフラグをたててその書き込まれたデータを有効にし、衝突が発生したい場合はこのフラグをたてずDM−CAM側のバリッドビットをたて、FA−CAM側のバリッドをたてずにおくため実質的にFA−CAMには書き込みがなされていないことにより書き込み動作時の性能劣化を防止し、装置全体として高速性を失うことなく大容量の連想メモリ装置が実現できる。
実 施 例 第１図に本発明の実施例を示す。連想メモリ要素１はFA−CAMである。FA−CAMの主要な動作は「書き込み」と「検索」である。書き込み動作では、空きアドレス（バリッドビットに有効フラグがたっていないアドレス）に優先順位がついており、もっとも優先順位が高いアドレスのワードに新しいデータが書き込まれる（書き込まれると同時にバリッドビットには有効フラグがたつ）。一方、検索動作では、検査用の入力ワードデータがメモリの全ワードに同時に供給され、各ワードに配置された一致検出回路（具体的には排他的論理和回路）により、入力ワードデータと格納されているデータとの一致、不一致がしらべられ、もし一致しているワードがあればそのワードの一致検出部から一致検出信号が（場合によってはそのアドレス情報も同時に）外部へ出力される。
次に、第１図の連想メモリ要素２はDM−CAMである。DM−CAMは実質的に複数I/Oのランダムアクセスメモリと一致検出回路４（具体的には排他的論理和回路）から構成されている。従って単位面積当りの記憶容量（メモリの集積度）はFA−CAMに比べてかなり大きいものが得られる。第２図にこのDM−CAMの構成とデータ入力の方法を示す。
入力ワードデータの各ビットはアドレスフィールドのビットと残りのフィールド（内容フィールドと以後略述する）に分けられる。アドレスフィールドの各ビット情報はRAMのアドレス入力としてアドレスデコーダに印加され対応したRAMの内容記憶部分のワードの読みだし動作を行う。読み出された各ビットは、前述の内容フィールドの各ビットとの一致検出回路で行われ、全ビットが同一の場合は一致しており、１ビットでも異なればデータは不一致で検索データは格納されていないことになる。
本実施例では、データの書き込み時（Wt）、検索時（Rv）何れも、連想メモリ要素１、要素２の両方に同時に処理を開始することを特徴としている。
まず、書き込みの時（Wt）には、連想メモリ要素１のFA−CAMに対しては、書き込みの優先度がもっとも高いワードに対して一応入力ワードデータの書き込みが行われるが、そのワードのバリッドフラグはまた１にしない。連想メモリ要素２のDM−CAMに対してはまずバリッドビットの読み出し（Rd）が行なわれ、読み出されたバリッドフラグが１の場合即ち、既にそのアドレスのワードが使用中の場合に先程保留状態にしておいた要素１のバリッドフラグを１（即ち使用中または有効）に設定する。逆に連想メモリ要素２のバリッドフラグが０の場合はそのアドレスは未使用なのでRAMのそのワードに対して書き込み（Wt）動作を行い同時にそのアドレスのバリッドフラグも１に設定する。これら一連の動作は制御回路部３で制御される。
次に検査の場合（Rv）は連想メモリ要素１に対して検索動作、連想メモリ要素２対して内容フィールドの読み出し動作が同時に実行され、各々のバリッドビットを読みだしも同時に実行され、各々の検出信号とバリッド信号の論理積信号の何れかが１であれば装置全体として検索データを格納していることを示し、何れも０であれば装置全体として検査データを格納していないことを示している。
また、事前に、複数のデータを同一アドレスに指定しなければならないことが分っている場合（即ち特定のアドレスで衝突が頻繁に発生する可能性がある場合）連想メモリ要素２のアドレス入力として、単純にアドレスフィールドの各ビットを直接印加するのではなく、種々のビットからある種の変換を行なって（通常この動作をハッシュ変換またはハッシングと呼ぶ）衝突の確立を下げることができる。
第３図はこの変換回路即ちハッシュコード発生回路５を設けた構成の連想メモリ装置を示している。衝突の確立が、アドレスによって非常に偏っている場合はハッシング等を行なわなければ、本発明においてもFA−CAMのワードが短時間で「フル」状態となり、しかもDM−CAM側は未使用アドレスがあるという不都合が発生する可能性がある。
発明の効果 実施例の動作説明より明らかなとうり、従来の連想メモリの二種類の問題点が解消できる。即ち、純粋のFA−CAMの場合問題となったメモリセルが大きいために充分大容量の連想メモリが得られないという欠点に対しては、大容量のDM−CAMを用いることで改善している。また、従来のDM−CAMでは、衝突が起こった場合の処理に時間を要し性能が低下していたが本発明の連想メモリ装置では、衝突が起こってもFA−CAMに即刻退避できほとんど、無駄時間なしで処理できるので高速性は失われない。つまり、大容量で高性能の連想メモリを実現できる。
【図面の簡単な説明】
第１図は、本発明の基本構成例を示すブロック図、第２図R>図は、ダイレクトマップ形の連想メモリの構成例を示すブロック図、第３図は、本発明の基本構成にハッシュコード生成回路を加えた別の構成例を示すブロック図である。
1,2……連想メモリ要素、３……制御回路、４……一致検出回路、５……ハッシュコード発生回路。
【特許請求の範囲】
【請求項１】入力ワードと各記憶ワードの全ビットに対して一括して一致検出する連想処理機能をもつ第１の連想メモリ要素と、前記入力ワードの一部ビットフィールドをアドレス情報とし、このアドレスの格納されているワードデータと前記入力ワードの残りのビットフィールドとを比較することで連想処理を行うランダムアクセスメモリと比較回路列からなる第２の連想メモリ要素と、制御論理回路網が同一半導体基板上に形成され、前記制御論理回路網は、（ｉ）データの書き込み時は、入力ワードの一部のビットフィールドに対応する前記第２の連想メモリ要素のアドレスが未使用の場合、そのアドレスに前記入力ワードの残りのビットフィールドデータを書き込み、もしそのアドレスに既に別のデータが書き込まれている場合は、前記入力ワードを前記第１の連想メモリ要素に未使用アドレスに書き込むよう各連想メモリ要素を制御し、（ii）データ検索時は入力ワードを第１および第２の連想メモリ要素に同時に供給し並列検索処理をするよう各連想メモリ要素を制御する構成を特徴とする連想メモリ装置。
【請求項２】第２の連想メモリ要素に直接入力ワードを供給せずハッシュコード発生回路を設け、これを介して前記入力ワードをハッシュ変換して供給することを特徴とする特許請求の範囲第１項記載の連想メモリ装置。
【請求項３】第１の連想メモリ要素は、各記憶ワードごとに、ワードデータを記憶し一致検出機能を持つ内容ビットフィールドと、入力ワードデータと記憶されているワードデータとの一致がある場合にそれを示す一致検出ビットと、記憶されているワードが有効かどうかを示すバリッドビットからなり、第２の連想メモリ要素のランダムアクセスメモリは入力ワードの一部またはこれをハッシュ変換したビットフィールドが供給されるアドレスデコーダと、各記憶ワードごとに残りのビットフィールドに対応する箇所を記憶する内容フィールドと、この内容フィールドに記憶が有効かどうかを示すバリッドビットからなり、前記制御論理回路網は、（ｉ）書き込み動作時には、第２の連想メモリ要素に対応するアドレスのバリッドビットを読みだし、これが無効の場合には、第２の連想メモリ要素の内容フィールドに入力ワードデータの残りのビットフィールドを書き込むと同時にそのアドレスのバリッドビットに有効フラグを書き込み、前記バリッドビットが有効な場合は、第１の連想メモリ要素の未使用ワードの一つに書き込むと同時にそのワードのバリッドビットに有効フラグを書き込むよう各連想メモリ要素を制御し、（ii）データ検索動作時には、前記第１、第２の連想メモリ要素の各バリッドビットを同時に読みだして有効の記憶ワードのみ一致検出出力候補とする動作をするよう各連想メモリ要素を制御する構成を特徴とする特許請求の範囲第１項または第２項記載の連想メモリ装置。
【請求項１】入力ワードと各記憶ワードの全ビットに対して一括して一致検出する連想処理機能をもつ第１の連想メモリ要素と、前記入力ワードの一部ビットフィールドをアドレス情報とし、このアドレスの格納されているワードデータと前記入力ワードの残りのビットフィールドとを比較することで連想処理を行うランダムアクセスメモリと比較回路列からなる第２の連想メモリ要素と、制御論理回路網が同一半導体基板上に形成され、前記制御論理回路網は、（ｉ）データの書き込み時は、入力ワードの一部のビットフィールドに対応する前記第２の連想メモリ要素のアドレスが未使用の場合、そのアドレスに前記入力ワードの残りのビットフィールドデータを書き込み、もしそのアドレスに既に別のデータが書き込まれている場合は、前記入力ワードを前記第１の連想メモリ要素に未使用アドレスに書き込むよう各連想メモリ要素を制御し、（ii）データ検索時は入力ワードを第１および第２の連想メモリ要素に同時に供給し並列検索処理をするよう各連想メモリ要素を制御する構成を特徴とする連想メモリ装置。
【請求項２】第２の連想メモリ要素に直接入力ワードを供給せずハッシュコード発生回路を設け、これを介して前記入力ワードをハッシュ変換して供給することを特徴とする特許請求の範囲第１項記載の連想メモリ装置。
【請求項３】第１の連想メモリ要素は、各記憶ワードごとに、ワードデータを記憶し一致検出機能を持つ内容ビットフィールドと、入力ワードデータと記憶されているワードデータとの一致がある場合にそれを示す一致検出ビットと、記憶されているワードが有効かどうかを示すバリッドビットからなり、第２の連想メモリ要素のランダムアクセスメモリは入力ワードの一部またはこれをハッシュ変換したビットフィールドが供給されるアドレスデコーダと、各記憶ワードごとに残りのビットフィールドに対応する箇所を記憶する内容フィールドと、この内容フィールドに記憶が有効かどうかを示すバリッドビットからなり、前記制御論理回路網は、（ｉ）書き込み動作時には、第２の連想メモリ要素に対応するアドレスのバリッドビットを読みだし、これが無効の場合には、第２の連想メモリ要素の内容フィールドに入力ワードデータの残りのビットフィールドを書き込むと同時にそのアドレスのバリッドビットに有効フラグを書き込み、前記バリッドビットが有効な場合は、第１の連想メモリ要素の未使用ワードの一つに書き込むと同時にそのワードのバリッドビットに有効フラグを書き込むよう各連想メモリ要素を制御し、（ii）データ検索動作時には、前記第１、第２の連想メモリ要素の各バリッドビットを同時に読みだして有効の記憶ワードのみ一致検出出力候補とする動作をするよう各連想メモリ要素を制御する構成を特徴とする特許請求の範囲第１項または第２項記載の連想メモリ装置。
【第１図】
【第２図】
【第３図】
【第２図】
【第３図】
【特許番号】第２５５８８２１号
【登録日】平成８年（１９９６）９月５日
【発行日】平成８年（１９９６）１１月２７日
【国際特許分類】
【出願番号】特願昭６３−１８５９５５
【出願日】昭和６３年（１９８８）７月２６日
【公開番号】特開平２−３５６８９
【公開日】平成２年（１９９０）２月６日
【出願人】（９９９９９９９９９）松下電器産業株式会社
【登録日】平成８年（１９９６）９月５日
【発行日】平成８年（１９９６）１１月２７日
【国際特許分類】
【出願日】昭和６３年（１９８８）７月２６日
【公開番号】特開平２−３５６８９
【公開日】平成２年（１９９０）２月６日
【出願人】（９９９９９９９９９）松下電器産業株式会社
[ Back to top ]