JPH02501604A - 連想記憶メモリシステム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 連想記憶メモリシステム 本発明は連想記憶メモリシステムに関する０本発明は又能動メモリ回路及び１つ 又はそれ以上の能動メモリ回路を含んでなる連想記憶メモリシステムにも関する 。

各レコードが多数の属性又は多数の情報を含む様なレコード形式におけるデータ を多量に含むコンピュータシステムにおいて、各詳細レコードがその記憶ロケー ションのみに基いてアクセスされるとすれば特定の属性を有するレコードを見い 出すためのレコードのサーチの処理はかなりの量の計算時間を要することになろ う。

この問題はディスクの様な外部記憶装置に記録が格納される場合に一層強調され る。

この問題を緩和する１つの方法はレコードをその属性又は内容に基いてアクセス 可能な形で格納することである。この種のメモリシステムは連想記憶メモリシス テムとして知られそれを実現する１つの方法はレコードのファイルをビットマツ プマトリクスを形成する様にコード化することでありそれに基いてサーチが行な われて特定の命題を満足するレコードが見い出される。

ビットマツプマトリクスは各行が特定のレコードを表わし各列がビットマツプと して知られるビットの配列を具備している。用いられたコード化の形式に応じて 行内の各ビットは通常それぞれのレコードの予め定められた属性を表わす。その ビットが１であればレコードは属性を持ちそのビットがＯであればレコードは属 性を持たない、したがって、各ビットマツプはどのレコードが特定の属性を持ち どれが持たないかの指標を提供する。

どのレコードが特定の属性の組み合わせを持つかの様な複合した命題については その命題に対応する選択されたビットマツプに対する論理演算又は一連の論理演 算を行なってどのレコードが命題を満足するかに関する指標を提供するビットマ ツプを発生することによって解決される。

本発明の１つの目的はホストコンピュータと共に用いられ比較的安価であり比較 的高速にレコードをサーチすることが可能な連想記憶メモリシステム、特に速度 に関してはメモリシステムなしでホストコンピュータによってサーチが達成され るであろう速度の連想記憶メモリシステムを提供することである。

本発明の別の目的は、ビットマツプマトリクスに対する論理演算を達成すること が可能な活性メモリ回路を提供することである。

本発明のさらに別の目的は、１つ又はそれ以上の活性メモリ回路を含む連想記憶 メモリシステムを提供することである。

本発明によれば、複数のレコードを記憶するホストメモリとホストプロセッサバ スを有するホストコンピュータとの結合のための連想記憶メモリシステムであっ て、該メモリシステムは： 該ホストコンピュータに記憶されるレコードを表現するビットマツプマトリクス を記憶するためであって、使用において、該ホストプロセッサバスへ接続され該 ホストコンピュータによってアドレス可能なインデクスメモリ手段と、該メモリ 手段に記憶されたビットマツプをアクセスし該ビットマツプに対するビットマツ プ演算を達成し、使用において、該ホストプロセッサバスへ接続され該ホストコ ンピュータより制御されるインデクスプロセッサ手段と、該インデクスメモリ手 段と該インデクスプロセッサ手段との間に接続され、該メモリ手段と該プロセッ サ手段との間のビットマツプの通過のために採用されたメモリシステムバスとを 具備する連想記憶メモリシステムが提供される。

好適には前記インデクスメモリ手段は複数のインデクスメモリを具備し該複数の インデクスメモリの各々は：メモリセルのアレイと； シフトレジスタであって、該アレイへ接続されたパラレル人力／出力バスと、該 シフトレジスタの対向する端部におけるシリアル入力ポート及びシリアル出力ポ ートとを有し、該パラレル人力／出力バスは該アレイ内のデータの選択された行 のアクセスが可能であるシフトレジスタとを具備し：前記メモリシステムバスは ８亥インデクスメモリの８亥シリアル入力及び出力ポートを前記インデクスプロ セッサ手段へパラレルに接続し； 同時にアクセスされた該データの選択された行は少なくとも１つのビットマツプ を形成する。

本発明によれば行及び列に配置され少なくともビットマツプの一部を記憶するの に適するメモリセルのアレイと；少なくともビットマツプの一部を記憶するのに 適したシフトレジスタと； 該アレイと該シフトレジスタとの間に接続された論理ユニットとを具備し、 該アレイ、シフトレジスタ及び論理ユニットは集積回路よりなり、該シフトレジ スタは該アレイの選択された列をコピーすることが可能であり、該論理ユニット は該シフトレジスタの内容と該アレイの選択された列との選択された論理演算を 達成することが可能であり、該演算の結果は該シフトレジスタ内に記憶される能 動メモリ回路が提供される。

本発明によれば以上に定義した１つ又はそれ以上の能動メモリを含む以上に定義 した連想記憶メモリも又提供される。

本発明の好適な具体例が以下の添付図を参照して単なる例として記述される： 第１図はレコードの配列とレコードの配列に対して与えられた命題に対応するビ ットマツプの図であり；第２図は複合命題に呼応するビットマツプを発生する複 数の成分命題に呼応するレコードを表わす複数のビットマツプの図であり； 第３図はレコードのアレイに対するスーパーインポーズドコードインデクスを含 むビットマツプマトリクスの図であり；第４図はプール属性を表わすビットマツ プの図であり；第５図は２進数でコード化された属性に対する論理演算を含むビ ットマツプマトリクスのサーチの図であり；第６図はビットマツプマトリクスに 対して行なわれるより大／より小の分類の図であって分類を達成するアルゴリズ ムのリストを含む図であり； 第７図はいかにしてビットマツプマトリクスの最小値が見い出されるかを表わす 図であって最小値を決定するアルゴリズムのリストを含む図であり； 第８図はホストコンピュータに付属した本発明に係るメモリシステムのブロック 図であり； 第９図は第８図のシステム内のメモリの配置を示す図であり； 第１０図は第８図のシステム内のメモリの配置をさらに示す図であり； 第１１図は第８図のシステムが遂行することができるビットマツプ演算を表わす 図であり； 第１２図は第８図のシステムのメモ、リチップの図であり；第１３図は第８図の システムのメモリユニットの図であり：第１４図は第８図のシステムのインデク スプロセッサの図であり： 第１５図は第８図のシステムのデータの流れの図であり；第１６図は本発明に係 る能動メモリ回路のブロック図であり： 第１７図は第１６図の回路のより詳細なブロック図であり：第１８図は第１６図 の回路のシフトレジスタセルと論理セルの回路図であり； 第１９図は第１６図の能動メモリを採用するインデクスメモリシステムのアーキ テクチアの図であり；第２０図はスーパーインポーズドコードワード計算ユニッ トの図であり； 第２１図は呼応するレコードのアドレスを決定し記憶するためのユニットの図で あり； 第２２図は圧縮／拡大ユニットの図であり；第２３図は特殊なテーブル参照ユニ ットの図であり；第２４図は複数のカスケード接続された能動メモリの図であり ； 第２５図は第１６図の能動メモリ回路を採用した第８図のメモリシステムの図で ある。

第１図に示されるファイル２はコンピュータシステム内に組み込まれたメモリ内 又はディスクの様な二次記憶装置上に記憶され、多数のレコード４を具備してい る。ファイル２を指標付は又はサーチするにあたり、１組のレコード４が特定の 性質又は命題に合うか否かを決定する必要がある。例えば各レコード４は車両の 色、車両の所有者、車両が登録された州、及び登録の日付の様な車両登録に関す る情報を含んでいる。第１図に示される様に、成る命題はどの車両が赤色で、Ｎ 、Ｓ、Ｗ、州で登録され、１９８５年１月１日以後に登録されたかをファル２よ り決定することである。その様な命題に対応するレコードの組は第１図に示され る様にビットマツプ６から決定することができる。ビットマツプ６はレコード４ の１個あたり１ビツトのビット配列である。特定のレコード４に対応するビット はそのレコード４が命題を満足又は命題に呼応すれば′１となり呼応しなければ ０となる。かくして、ビットマツプ６は命題を満足するレコードの組の圧縮され た表現を与える０図示された例において、４０９６個のレコードのテーブル又は ファイル２はビットマツプ６のために４０９６ビツト又は５１２バイトを必要と する。

第１図は成る複合命題を表わしている。複合命題に呼応するビットマツプ６又は レコード４は第２図に示される様に複合命題を構成する成分の単一命題に呼応す るレコードを表わすビットマツプ８，１０、及び１２に対する簡単な論理演算に よって計算することができる。前の例にしたがって、命題はそれぞれレコード内 において車両が赤色であるレコード、Ｎ、Ｓ、Ｗ、州で登録されたレコード、登 録の日付が１９８５年１月１日以降であるレコードを示す３つのビットマツプ８ ．１０及び１２を決定するために３つの命題に分解することができる。

第２図に示される様に３つのビットマツプ８．１（ｌび１２へのＡＮＤ演算を行 なうと複合命題に呼応するレコードを表わすビットマツプ６が得られる。各ビッ トマツプがメモリ内に保持されれば、初等的なビットマツプ８，１０及び１２が 既に得られているとして最終的なビットマツプ６の計算は即座に行なえる。

高速のビットマツププロセッサによる充分な恩恵を受けるためには、それ以上に 初等的なビットマツプに対する論理演算によって初等的命題のビットマツプを計 算することが可能である必要がある。この事を達成する１つの方法は“Ｐａｒｔ ｉａｌ−Ｍａｔｃｈ　Ｒｅｔｒｉｅｖａｌ　ｖｉａ　Ｐｌｅｔｈｏｄ　ｏｆ　Ｓ ｕｐｅｒｉｍｐｏｓｅｄ　Ｃｏｄｅｓ”　Ｒｏｂｅ−ｒｔｓ　Ｃ，Ｓ、（１９７ ９）　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＩＥＥＥ　Ｖｏｌ、６７、Ｎａ１２．ｐ ｐ、１６２４−２６４２に記載のスーパーインポースドコードインデクス法を使 用することである。この方法を第３図を参照して概略的に記述する。レコード４ の配列はビットマトリクス１４としてスーパーインボーズドコードインデクス内 に表わされている。

前の例にしたがってどのレコード４が赤い車両を有しているかを決定するために 、予め定めた命題コード２ｏが発生される。コード２０は命題を満足するために は命題に呼応するレコードを示す最終的なビットマツプ２２を決定するためにビ ットマツプの列１６及び１８について論理的ＡＮＤ演算がなされなければならな いことを示している。マトリクス１４の各列はビットマツプであると考えられ命 題２ｏによって示される論理演算を達成することによってビットマツプ２２が得 られる。

スーパーインポーズドコードインデクスの利点は次の様である： １、　指標（インデクス）が圧縮されており例えば４０９６個のレコードに対す る指標はメモリを６４にバイトしか占有しない。

Ｚ　指標が第３図に示される様な列フォーマットで表わされれば、任意の特定の 命題に対して指標の一部のみが処理される。

スーパーインポーズドコードインデクスの威力は着目するレコードの属性がこの 形で表わされる様な方法を用いることによって増大される。

しかしながら、スーパーインポーズドコードの欠点は次の様である： １、　すべての順序情報が失なわれるのでより大きいかより小さいかの命題は達 成されないが、それらはしばしば不連続の属性の様に範囲をコード化することに よって近似される。

２、　誤選択が起こる成る（通常は小さい）Ｗｉ率が存在するので、命題に呼応 してつくられるビットマツプは命題を満足又は命題に呼応するレコードの組以上 を含んでいる。この事に関する主な問題点は非等値命題に呼応するレコード例え ばＮ、Ｓ、Ｗ、で登録されていない車両を見い出す目的でスーパーインポーズド コードを使用することはできないということである。

しかしながら指標を処理する別の方法がある。レコードのプール属性は単一のビ ットとしてコード化することができて、例えば属性が車両の所有者が登録費を支 払ったか否かであれば単に真又は偽の答えが要求される。第４図に示される様に レコードのプール属性は、レコード２８の配列２６についてのものであり属性を 表わす単一のビットを具備するビットマツプ２４を単に調べるだけで決定するこ とができる。ビットマツプ２４は属性が真であるかの即座の指示を捉供する。属 性が偽となる命題に対するビットマツプ３０は、第４図に示される様にマツプ３ ０の論理的反転をとることによって計算される。

これは第５図に示される様に、完全等値性命題がもたらされるプロセスに導かれ る。成る属性、例えば登録の州が２進数でコード化されその属性のテーブル３２ はプール属性の集まりであり、完全等値性命題は真及び偽のプール命題の連続と して配置することができる。非等値性命題は同様にして処理することができる。

第５図に示される様に、一連のプール演算又は論理演算がテーブル３２の列３４ 　、３６及び３８に関して実行されて登録の州がＮ、Ｓ、Ｗ、であるレコードを 示すビットマツプ３９が決定される。

しかしながら前述のアプローチの欠点は属性の有するビット数が少数（すなわち ５以下）でなければ命題に呼応するレコードの組を計算するためにスーパーイン ポーズドコード属性におけるよりも多大な時間を必要とすることである。しかし ながら、それは可能な値の数が非常に少ない属性については部分的ながら有益で ある。

第６図に示される様に、レコードの順序を決定することを含む命題はビットマツ プを用いて計算することができる。境界値よりも大きいか小さいかを決定するア ルゴリズムが第６図にＰＡＳＣＡＬ形式で詳述されており、ここでラベルＬ、Ｇ 及びＢ　［ｉ］　はビットマツプの列又はｋＸｆビットマトリクスを表わし、ｋ はテーブル４０内のレコードの数であり、ｎはテーブル４０内のコード化された レコードのビット数である。Ｗはテストワード４２でありより大又はより小命題 の基本となるコードを表わす。このアルゴリズムは命題内に設けられたテストワ ード４２に関してテーブル４０内のレコードの分類を達成する。アルゴリズムは テストワード４２より小であることが知られたレコードを表わすＬマツプ４４と テストワード４２より大であることが知られたレコードを表わすＧマツプよりな る２つの作業用ビットマツプを有している。テストワードとは異なる最初のビッ ト（最上位ビットから最下位ビットへと比較する）がテストワード内の対応する ビットよりも大であるならば所与のワード又はコード化されたレコードはテスト ワード４２より大である。そのビットはＯ又は１の値しかとれないので成るワー ドがテストワードより大であるならば最初に異なるビットテストワードにおいて Ｏでコード化されたレコード又はワードのそのビットは１であるはずである。テ ストワード内の成るビットがＯであるならば、そのビットが考慮中のビットであ る時テストワードより大であると決定されたコード化されたワードの組はそのビ ットにおいて１であるコード化されたワード又はレコードの組である。

同様にして、特定のビット位置においてテストワードが１を存するならば、その ピント位置の考慮においてテストワードより小であるコード化されたワードの組 はそのビット位置において０の値を有するコード化されたレコードの組である。

テストワード４２が特定のビット位置において０を有する時、テーブル４０の分 類されていない参照値或いはコード化されたワードはテスワード４２に等しくあ り続けるか又はテストワード４２より大であると決定されるかのいずれかである 。テストワード４２がそのビット位置において１である時、分類されていないコ ード化されたワードはテストワード４２と等しくあり続けるか又はテストワード ４２より小であると決定されるかのいずれかである。一度でもコード化されたワ ードがテストワードより大又は小と分類されたら、その分類は変更されない。分 類操作は１つの属性あたり数ピントマツプの操作が必要とされるので、本質的な 順序情報を保護する方法において粗な属性をコード化することは経済的であろう 。

例えば、１年の範囲を有する日付属性は９ビツトにコード化される。

連想メモリの文献からのアルゴリズムを採用することによって、第７図に示され る様に、属性の最小値及び最小値を含むレコードの位置を見い出すことがビット マツプ操作を用いて可能となる。第７図にリストされたアルゴリズムはＰＡＳＣ ＡＬ形弐でありラベルＭ及びＢ　［ｉ］　はビットマツプの行を表わしＷ［ｉ］ 　はビットマトリクス４８のうち最も小さい又は最小のコード化されたワードの １つのピントを表わす。アルゴリズムの完了後のＭビットマツプ５０はどのレコ ードがマトリクス４８のうち最小のコード化されたワードを含むかを示し、ｎは マトリクス４８のコード化されたレコード内のビット数である。このアルゴリズ ムは一度に左から右へ（最上位ビットから最下位ビットへ）マトリクス４８のビ ットマツプを解析することによって最小のワードＷ５２と共にＭビットマツプ５ ０を計算する。

マトリクス４８の任意の特定のビット位置においてビットマツプ５０は未だ捨て られていないレコードに関する指示を含みワードＷ５２はそれまでに決定された 最小ワードのピントを含むであろう。未だ捨てられていないレコードがそのビッ ト位置において値Ｏであるコード化されたワードを有する時、そのビット位置に おいてｌであるコード化されたワードを有するレコードは最小ではあり得ない、 そのビット位置において１であるコード化されたワードを有するレコードに対応 するビットマツプ５０内のビットはは必然的にＯとなる。最小のワードも又その ビット位置においてＯを有する。しかしながら、未だ捨てられていないレコード のすべてが考慮下のビット位置において１であれば、すべてのレコードは捨てら れず最小ワードはそのビット位置においてｌとなるであろう。

アルゴリズム内のステップ（Ｍ　ＡＮＤ　Ｂ［ｉ］）＝Ｍは演算（Ｍ　ＡＮＤＢ ［ｉ］）　ＸＯＲＭによって発生するビットマツプ内のビットがすべてＯである か否か（“オールゼロテスト″）のためのテストに帰着され、その理由はそれら がすべて０であればＭビットマツプ５０は不変であり演算される必要がないから である。

このステップは計算時間のかなりの部分を占めるので以下に示す能動メモリ回路 からのオールゼロ出力を用いてそれを減らすことによって、アルゴリズムはより 高速となりアルゴリズムを実用的なものとする。

以前に記述した様にビットマップインデクス上で多様な命題を達成することが可 能である。指標（インデクス）は好適にはスーパーインポーストコードワードの テーブルに、わずかの数の値、非等値命題が可能な命題、及び命題に対する情報 の順序が必要である属性の完全２進化コードを加えたものである。メモリ空間の 節約のために、すべての完全２進化属性は小数のビットでコード化される。

前述の演算をビットマツプマトリクス上で達成することを可能にする連想記憶メ モリシステム６２がホストコンピュータ６０に接続されて第８図に示されている 。ホストコンピュータ６０は中央処理ユニット６４、メモリ６６、多数のディス クの様な大容量記憶装置６８、及び外部機器のための入出カポ−ドア０とを具備 する市販のコンピュータシステムである。ホストプロセッサバス７２も又設けら れホストコンピュータ６０のユニット６４　、６６　、６８及び７０間でのデー タ転送を可能にする。

連想記憶メモリシステム６２はインデクスメモリユニット７４、インデクスプロ セッサ７６及びインデクスメモリユニット７４をインデクスプロセッサ７６へ接 続しメモリユニット７４とプロセッサ７６との間のデータ転送を可能にするメモ リシステムバス７８とを具備している。

インデクスメモリ回路７４とインデクスプロセッサ７６はホストプロセッサバス ７２へ接続されている。インデクスプロセッサ７６はインデクスメモリ７４との データの送受を行ない、ホストプロセッサバス７２を介してホストコンピュータ ６０から受け取った命令に応じてデータの演算を達成する。

ホストコンピュータ６０はホストプロセッサバス７２を介してインデクスメモリ ユニット７４からのデータをアクセスすることができ、コンピュータ６０にとっ てインデクスメモリユニット７４は１６ビツトワードの標準的なランダムアクセ スメモリに見える。メモリユニット７４がホストコンピュータ６０によってアク セスされている間でもメモリの競合なしでメモリシステムバス７８を介してイン デクスプロセッサ７６によってデータがインデクスメモリユニット７４からアク セスされる。この事はメモリシステム６２がホストコンピュータ６０に関して自 律的に動作するバス７８を含むためである。

インデクスメモリユニット７４はホストコンピュータ６０内に記憶されたレコー ドのコード化された表現であるビットマツプマトリクスを記憶するために用いら れる。インデクスプロセッサ７６はインデクスメモリユニット７４内に記憶され るマトリクスのビットマツプ演算を達成すべく設計されている。メモリシステム ６２のプロトタイプは組み立てられており、付属インデクスマシ（ＡＩＭ）とし て知られている。メモリシステム６２の残された記述としては、行の長さ４０９ ６ビントで列の長さ２５６ビツトのビットマトリクスを記憶し演算することの可 能なインデクスメモリユニット７４を含むＡＩＭの実現に関するものであろう。

メモリシステム６２は任意の現実的サイズのピントマトリクスを記憶し演算する ために用いることができることが理解される。

メモリシステム６２はビットマトリクスのビットを１つのレコードに対してシリ アルにアクセスし、すべてのレコードをパラレルにアクセスするビットシリアル ワードパラレルの連想記憶メモリシステムである。

インデクスメモリユニット７４は第９図に示される様に垂直なプリント回路ボー ド８２上に適合する様に４個のグループで配置された３２個のインデクスメモリ ８０を具備している。メモリ８０はまた２バンクに分けて配置されそれぞれは２ ５６　Ｘ　４０９６のビットマトリクスを記憶することのできる１６個のメモリ ８０を具備している。４０９６個のビット列又はビットマツプは第１０図に示さ れる様にメモリ８０内の対応する位置に１６個のインデクスフモリ８０中の２５ ６個のビット部分８２内に記憶される。

インデクスプロセッサ７６は第１１図に示される様にマトリクス８８から２つの ４０９６個のビット列又はビットマツプ８４及び８６をアクセスし列８４及び８ ６に対する選択されたビットマツプ演算を行ない結果の列あるいはビットマツプ ９０をマトリクス８８へ返すべく採用される。現在のところ、ＡＩＭはこの機能 を１回の１６マイクロ秒サイクル内で達成することができる。これはホストコン ピュータ６０に対してビットマツプ９０の全ビットがゼロであるかどうか、もし そうでなければ列９０内で１であるビットに関連するレコードのアドレスに関す る情報を提供することを含む。

インデクスメモリ８０は第１２図に示される様にＴＭＳ　４１６１ＥＶ４ビデオ メモリチツプを具備しており、これは６４にビットのダイナミックＲＡＭアレイ ９２と２５６ビツトのシフトレジスタ９４を含んでいる。メモリアレイ９２はパ ラレル２５６ビツトバス９６を介してシフトレジスタ９４へ接続されている。

ＴＭＳ　９１４１チツプ８０は基本的にはアレイ９２の任意の選択された行をア クセスすることのできるシフトレジスタ９４が設けられた標準的なＲＡＭである 。アレイ９２の行は４０９６個のビット列又はビットマツプの２５６ビツト部分 ８２を具備している。

アドレスライン９８によってアレイ９２内の特定の２５６ビツト行をアクセスし ＴＲ／ＱＥ入カライフカライン１００ブルにすることによってデータが行とシフ トレジスタ９４との間で転送される。転送の方向はリード／ライトライン１０２ で支配される。シフトレジスタ９４とアレイ９２の選択された行の間の転送を行 なうためには、インデクスプロセッサ７６によって転送要求が発せられ行が選択 される。この段階においてホストコンピュータ６０からの任意のアクセス要求と プロセッサ７６からの転送要求とを同期させる必要がありこのことはインデクス メモリユニット７４内の３ウ工−任意化回路（図示せず）によって達成される。

他の時間においてインデクスプロセッサ７６はホストコンピュータ６０からのア クセス要求を訪客することなくシフトレジスタ９４の内容を操作する。

シフトレジスタ９４は第１２図に示される様に一端にシリアル出力ポート１０４ を含み、他端にシリアル入力ボート１０６を含んでおり、これはシフトレジスタ ９４をクロックライン１０８に同期させることを可能とし、シフトレジスタ９４ の一端において出力ポート１０４を経てデータが出力され、シフトレジスタ９４ の他端において入力ポート１０６を経てデータが入力される。

インデクスメモリユニット７４は第１３図に示される様に２つのバンク１１０及 び１１２に配置されそれぞれは以前に述べた様に１６個のインデクスメモリ８０ を具備している。ビットマツプ演算が行なわれる時、１つのオペランドはバンク １１０から選択され他のオペランドはバンク１１２から選択される。オペランド はホストコンピュータ６０によって選択され各バンク１１０及び１１２内におい て予め定めた行が各バンク１１０及び１１２内のアレイ９２の各々においてアク セスされ予め定めた行の内容がバンク１１０及び１１２のシフトレジスタ９４に 転送される。バンク１１０及び１１２のシフトレジスタ９４はそれによって双方 ともビットマツプを包含する。第１のバンク１１０内のシフトレジスタ９４のシ リアル出力ポート１０４のすべてはパラレルに第１のバンク出力バス１１４　ヲ 経てメモリシステムバス７８へ接続されている。同様にして、第２のバンク１１ ２内のシフトレジスタ９４のシリアル出力ポート１０４のすべては１６ビツトの 第２のバンク出力バス１１６を経てメモリシステムバス７８へ接続されている。

２つのバンク１１０及び１１２内のレジスタ９４に記憶されているビットマツプ 演算のためのオペランドはクロックライン１０８を用いてレジスタ９４を同期さ せることによってバス１１４及び１１６を経てインデクスプロセッサ７６へ出力 される。２つのバンク１１０及び１１２のレジスタ９４内のビットマツプのビッ トはシリアルに出力されるが、第１０図に示される様に各部分８２のビットにつ いて１６ビツトが各バンク出力バス１１４及び１１６に沿ってインデクスプロセ ッサ７６へ同時に出力され、それらは１６ビツトワードとなる。インデクスプロ セッサ７６はバンク出力バス１１４及び１１６を経て入力される１６ビツトワー ドに対して選択されたビットマツプ演算を行ない結果の１６ビツトワードをメモ リシステムバス７８に沿って１６ビツトバンク入力バス１１８へ戻す。バス７８ は少なくとも３つの１６ビツトデータの経路を含んでいる。

バンク入力バス１１８はバンク１１０及び１１２内のレジスタ９４０１６個のシ リアル入力ポー目０６ヘパラレルに接続されている。したがって、１６ビツトワ ードがバンク出力バス１１４及び１１６を介して出力されると、結果の１６ビツ トワードがバンク１１０及び１１２内のシフトレジスタ９４の反対側の端部に記 憶される。選択されたビットマツプ演算の終りに、結果のビットマツプは第１の バンク１１０のシフトレジスタ９４及び第２のバンク１１２のシフトレジスタ９ ４内に記憶される。そこでインデクスプロセッサ７６は結果のビットマツプを第 １のバンク１１０又は第２バンク１１２のアレイ９２内のホストコンピュータ６ ０によって選択された予め定めた行へ転送する。

インデクスプロセッサ７６は双方向バス１２２を介してホストプロセッサバス７ ２に接続されたホストインターフェースボート１２０を含んでいる。

プロセッサ７６はまたそれぞれ双方向バス１２６及び１２８を介してホストイン ターフェースポート１２０とメモリシステムバス７８との間で接続されたシリア ルファンクションユニット１２４を含んでいる。

シリアルファンクションユニット１２４はホストインターフェースポート１２０ からの命令に応答して動作しシステムバス７８を経てユニット１２４へ入力され た１６ビツトワードへのビットマツプ演算を行なう。それはまた結果の１６ビソ トワードをテストワードと比較して、結果のワードのすべてのビットが０か否か を決定し結果のワード内の１であるビットのオフセットロケーション又はアドレ スロケーションを記録するための回路を含んでいる。シリアルファンクションユ ニット１２４はホストインターフェースポートでトリガされた時２５６サイクル を実行する様に構成することができ、各サイクルは２つの１６ビツトワードをア クセスすること、ワードに対するビットマツプ演算を行なうこと、結果のワード を解析すること及びバス７８へ結果のワードを出力することを含んでいる。

ホストインターフェースポート１２０は制御ユニットを含みホストコンピュータ ６０からの命令を受け取る。ホストコンピュータ６０から受け取った命令に答え て、ボート１２０はシリアルファンクションユニット１２４の演算及びインデク スメモリュニソト７４内及びその間のデータ転送を制御する。

インデクスメモリユニット７４とインデクスプロセッサ７６との間のデータの流 れが第１５図に示されているが、すべてのデータ経路は示されていない、ビット マツプ演算を行なうにあたり２つの１６ビツトワードがプロセッサ７６によって バンク１１０及び１１２からアクセスされ各ワードは同時にシリアルファンクシ ョンユニット１２４へ入力される。２つのワードはそれぞれゲート１３０及び１ ３２を通過されそれぞれマスクレジスタ１３４及び】３６の状態に従ってゲート 内でマスクされる。ゲート１３０及び１３２はプール論理ユニット１３８の入力 へ接続されそれはワードに対して選択された論理演算を行ない演算の１６ビツト の結果をシフト論理ユニッ［４０と−致論理ユニット１４２へ出力する。プール 論理ユニット１３８はＡＮＤ、　ＡＮＤ　ＮＯＴ、　ＯＲ，ＯＲＮＯＴ、　ＮＯ Ｔ、　ＸＯＲ，ＸＯＲＮＯＴ　ＯＲＣ０ＰＹの様な多数の論理演算を行なうこと ができる。　ｃｏｐｙは一方のオペランドをゼロにしＯＲ演算することにより達 成される。実行される演算はホストコンピュータ６０から受け取った命令に応じ てホストインターフェースポート１２０内の制御ユニット１４４によって選択さ れる。

０致論理ユニット１４２はプール論理ユニッ目３８によって出力される結果の１ ６ビツトワードをテストワードレジスタ１４８に格納される１６ビツトテストワ ードと比較する結果のソードがテストワードと一致すれば制御ユニット１４４は ＦＩＦＯヒツトレジスタ１５０内に一致する結果ワードのオフセット又はアドレ スロケーションを記憶する。オールゼロテストを達成するためにはテストワード レジスタ１３８にはすべてのビットがゼロであるワードがロードされる。シフト 論理ユニットは結果の１６ビツトワードを記憶し一方それらは０致論理ユニット １４２において比較され結果のワードはインデクスメモリユニット７４内のバン ク１１０及び１１２へ出力される。制御ユニット１３４は０致論理ユニット１４ ２とシフト論理ユニット並びにメモリシステム６２の他の要素を制御しホストコ ンピュータ６２からの命令を受け取りそれは命令レジスタ１５２に記憶される。

命令レジスタ１５２はシリアルファンクションユニット１２０内ルジスタ１３４ ．１３６．１４８及び１５０のバンクの一部として表わされているが、レジスタ １５２は通常制御ユニッ）　１４４の一部を形成する。

第１６図に示される様な能動メモリ回路又はチップ１５０は前述した様なビット マツプマトリクスに対するビットマツプ演算を遂行するために設計される。回路 １５０はビットのアレイを記憶することのできるメモリ部１５２、好適には双方 向であるシフトレジスタ１５４、論理ユニット又は回路１５６及び演算中のビッ トマツプを一時的に記憶するための０時記憶エリア又は部１５８を具備する。

チップ１５０は使用においてメモリ部１５２内に記憶されたビットのアレイを包 含する。ビットのアレイはビットマツプマトリクスを表わす、アレイの大きさは 重要でないが２５６　Ｘ　２５６ビツトが好ましい。ビットで表わされるチップ １５０内に保持されるデータは通常のメモリとは異なる形式で処理される。

レコードのテーブルへのインデクスの一部を具備するビットマトリクスは、使用 において、メモリ部１５２のアレイ上に直接マツピングされる。アレイ内の行１ ６０は単一のレコード（複雑なレコードに対して通常２５６ビツトで充分である ）を表わすインデクスピットを保持している。アレイの任意の列１６２は第１〜 ７図を参照して記述されたタイプのテーブル又はマトリクスのビットマツプを保 持する。

チップ１５０上のシフトレジスタ１５４は以前に言及したＡＩＭで用いられたメ モリバンク１１０及び１１２へのシフトレジスタ９４と同様である。

チップ１５０はメモリ部１５２内に記憶されたビットアレイから選択された列を バンク１１０及び１１２における様にシフトレジスタ１５４上にコピーすること ができる。シフトレジスタの内容を選択された列とシフトレジスタ１５４の以前 の内容に対してなされた論理演算の結果で置き換えることも可能である。

データはそれぞれシフトイン及びシフトアウトライン１６４及び１６６によって レジスタ１５４に対してシフトイン及びシフトアウトがなされる。チップ１５０ は行／列選択入カライン１６８と、連続した行におけるメモリ部１５２へのデー タの入出力のための打入／出カライン１７０も具備している。チップ又は回路１ ５０によってなされる演算の制御とメモリ部１５２及び１５８のメモリ要素の選 択のために複数の制御ライン１７２も又設けられている。シフトレジスタ１５４ に記憶される列のビットがすべてゼロでない場合はいつでも低レベルになるオー ルゼロ出カライン１７４も又設けられている。オールゼロライン１７４は最小限 のアルゴリズムで実際上遂行されることを可能とする。コマンドライン１７２は 特に、シフトレジスタ１５４、論理ユニット１５６及びメモリ部１５２と一時記 憶部１５８からのビットマツプの入出力の動作を制御する信号を入力する。

ライン１７２の入力はチップ又は回路１５０に対して以前に記述したビットマッ プインデクス動作を達成するために次の機能を達成することを命令する。

（ｉ）シフトレジスタ１５４の内容と選択されたビットマツプ１６２とのＡＮＤ をとりその結果をシフトレジスタ１５４に記憶する。

（ｉｉ）シフトレジスタ１５４の内容と選択されたビットマツプとのＯＲをとり その結果をシフトレジスタ１５４に置く。

（ｉｊ）シフトレジスタ１５４の内容と選択されたビットマツプ１６２とのＸＯ Ｒをとりシフトレジスタ１５４へ入力する。

（ｉｖ）選択されたビットマツプ１６２をシフトレジスタ１５４ヘコピーする。

（Ｖ）シフトレジスタ１５４の内容をメモリ部１５２の選択された列１６２ヘコ ピーする。

（ｖｉ）シフトレジスタ１５４の内容の反転を行なう。

（カ）シフトレジスタ１５４の内容を１ビツトシフトアツプする。

（ｖｉｉ）シフトレジスタ１５４の内容を１ビツトシフトダウンする。

より大／より小への分類操作を含む多くの目的のために、一度にシフトレジスタ １５４に記憶することのできないいくつかの追加的な列又はビットマツプが記憶 される一時記憶部１５８を有することが便利である。その列は論理演算において メモリ部１５２に記憶されたビットアレイの列と同様に関与する。回路１５０は 前に記述したすべてのビットマツプ論理演算が半導体チップの基板上で完遂され ることを可能とする。命題の処理の上で最終的なビットマツプは命題に呼応する レコードを同定するために検討することが可能となる。この検討はシフトアウト ライン１６６を通してビットマツプをアクセスする外部回路によって達成される 。テーブル又はファイルに対する指標は多数のチップ１５０上に記憶されるので 、そして数レコードのみが命題に呼応するのであろうから、最終的なビットマツ プを記憶するシフトレジスタ１５４内のビットのほとんどはすべて０となるであ ろう。したがってオールゼロライン１７４はチップ１５０内に記憶されるコード インデクスに対応するレコードを詳細に調べる必要があるか否かの指示を提供す る。オールゼロ出力１７４が高レベルであればそのチップ１５０に関連するレコ ードについてはそれらは命題に呼応しないものとして捨てられる。したがってオ ールゼロ出カライン１７４があれば、オールゼロ出カライン１７４上に低レベル の信号を有するチップのみについて命題に呼応するレコードを決定するためにそ れぞれのシフトレジスタ１５４内に記憶された最終的なビットマツプを抽出する ために検討すれば足りるので、所与のファイルに関するすべてのチップ１５０を サーチする必要はない。

チップ１５０上に記憶されるインデクスは外部記憶装置からチップ１５０上ヘロ ードされねばならず更新されなければならない。チップ１５０はインデクスを列 形式で処理するが、外部的な記憶及び更新についてメモリ部１５２の行をアクセ スできるようにすることが便利でありこれはビットアレイ内の選択された行内へ ／から直接的にビットをシフトさせるシリアル入／出力ボート１７０を介してシ リアルにデータを入力することによって達成される。この動作の速度は１又は２ 　ＭＨｚであり２５ＭＨ２又はそれ以上になるシフトイン／シフトアウト動作よ り遅い。行の入力／出力機能は標準的な単一ビットアクセスポートを用いても適 切に達成することができる。

能動メモリ回路１５０は第１９図により詳細に示される様に行列アドレスデコー ダ１８４によってアドレス可能な多数の１ビツト記憶要素１８２を具備するメモ リアレイ１８０を具備している。１ビツト記憶要素１８２のアレイ１８６も又設 けられ一時記憶部１５８を形成している。アレイ１８６は一時ビントマップアド レスデコーダ１８８を介してアクセスされる。デコーダ１８４及び１８８は選択 された行／列及びアドレス入力１９０に基いてアレイ１８２及び１８６をアクセ スする。これらの入力１９０は以前に記述された制御人力１７２の一部と行／列 選択入力１６８とを形成する。１ビツトメモリ要素１８２の各々はビン出力Ｍ１ ９２とビット出力の反転■１９４を供給する。データは制御人力１７２の一部を 形成する入力１９７を受け取るメモリ制御ユニット１９６から受け取った入力に 応じて選択された要素１８２のそれぞれラインＭ及び■１９２及び１９４上で書 き出される。双方向シフトレジスタ１５４はマスタースレーブフリップフロップ １９８のアレイを具備している。フリップフロップ１９８の内容はフリップフロ ップ１９８の内容を反転することもできるそれぞれのシフト／反転ユニット１０ ０によってシフトアップ又はシフトダウンされる。論理ユニット１１０２は各フ リップフロップ１９８が以前に記述した様なシフトレジスタ１５４の内容とメモ リアレイ１８０の列との選択された論理演算を達成する様に設けられる。シフト ／反転ユニット１１００と論理ユニット１１０２とはコマンドデコーダ１１０４ から受け取る入力によって制御されて各シフト反転ユニット１１００又は各論理 ユニッ目１０２は同時に同じ形式で機能する。したがって、論理、シフト及び反 転演算はビットマツプを形成するビットの列に対して行なわれる。コマンドデコ ーダ１１０４は制御ライン１７２の一部を形成するコマンドライン１１０６を介 して受け取られる入力に応じてユニット１１００及び１１０２へ信号を出力する 。シフトレジスタ１５４は双方向であるのでデータはそれぞれシフトイン／シフ トアウト頂部ライン１１０８又はシフトイン／シフトアウト底部ライン１１１０ を用いてレジスタ１５４の頂部又はレジスタ１５４の底部を通してレジスタ１５ ４に対してシフトイン及びシフトアウトされる。オールゼロ出力１７４は多入力 ＮＯＲゲート１１１２内でフリップフロップ１９８の内容に対するＮＯＲ演算を 行なうことによって得られる。

助動メモリ回路１５０が単一の半導体チップ上に構成されるとき、シフト／反転 ユニット１１００の各々及びフリップフロップ１９８のそれぞれは第１８図に示 される様に単一のシフトレジスタセル１１５０を形成する。シフトレジスタセル １１５０はマスタースレーブフリップフロップ１１５２とそのほとんどがコマン ドデコーダ１１０４からの出力を受け取る制御ラインによって制御される複数の ＭＯＳ　ＦＥＴ　）ランジスタ１１５４とを具備している。

ルックスルー制御ライン１１５６はフリップフロップ１１５２の入力Ｓｉｎを介 してデータの入出力を可能にし反転制御ライン１１５８は高レベルにセットされ るときシフトレジスタ１１５２の内容を反転する。オールゼロライン１１６０は フリップフロップ１１５２の出力５１１６２が高レベルである時は常に低レベル にされる。シフトダウン制御ライン１１６４が高レベルであるときより上位のシ フトレジスタセル１１５０のフリップフロップの内容がフリップフロップ１１５ ２の入力Ｓｉｎ　１１６４へ通過される。同様にしてシフトアップ制御ラインが 高レベルであるときより下位のシフトレジスタセル１１５０のフリップフロップ の内容がフリップフロップ１１５２の入力１１６４へ通過される。

第１０図に示される様に論理ユニット１１０２のセル１１７０はＯＲゲート１１ ７２．ＡＮＤゲート１１７４及びＸＯＲゲー）　１１７６を具備しこれらは出力 ライン１１６６に出現したフリップフロップレジスタ１１５２の内容とラインＭ １１７Ｂ上に出現した選択されたメモリセル１８２の内容との論理演算を達成す る。ＸＯＲ機能を達成するためにはＸＯＲゲート１１７６はそれぞれフリップフ ロップ１１５２の内容と選択されたメモリセル１８２の内容の反転であるライン １１８０及び１１８２からの入力を必要とする。選択された演算に従ってＯＲ制 御ライン１１８４、Ａ　Ｎ　Ｄ　１ｔｌＪ御１１８６又はＸＯＲ１１８Ｂが高レ ベルになると論理演算が遂行され選択された演算の結果はフリップフロップ１１ ５２の入力１１６４のみに出力される。高及び低電圧ライン１１９０及び１１９ ２は第１８図に示される様にＯＲゲート１１７２とＡＷＤゲート１１７４のため に設けられている。

ラインＭ＞Ｓ　１１９４が高レベルになるとき選択されたメモリセル１８２の内 容はライン１１７８を通してフリップフロップ１１５２の入力１１６４へ入力さ れる。同様にして、ＳＵＭライン１１９６が高レベルになるときフリップフロッ プ１１５２の内容はうイン１１６２を通して選択されたメモリセル１８２へ出力 される。

メモリセル１８２はそれらの内容がシフトレジスタ１５４にシフトイン及びシフ トアウトされそれらに論理演算が実行されるべくデコーダ１８４及び１８８によ って選択された時アレイ１８０又はアレイ１８６からくる列内に選択される。

能動メモリ回路の主な用途は連想記憶メモリに関するものであり、以前に言及し たＡＩＭにおけるような情報の検索のためのインデクス及びより特殊な参照テー ブルを提供することを目的とする。

コプロセッサとして設計された能動メモリを有するサブシステム１２００は第１ ９図に示す様にホストシステムバス１２０２を介してホストシステムに接続され る。多数の能動メモリチップ又は回路１５０を具備する能動メモリはアドレス及 び制御論理回路１２０６と共にメモリシステム１２００へ組み込まれる。特定の 機能を実現するための能動メモリの制御は論理サブシステム１２０４内に組み入 れられた特殊な論理ユニット１２０８によってなされる。ホストシステムバス１ ２０２へのアクセス、データの転送、及び全体の制御は命令デコード／解釈ユニ ッ）　１２１０により達成される。

一般の指標付けに対しては論理ユニッ目２０８は第１〜７図を参照して記述され た動作を達成する。スーパーインポーズドコード化はこれらの動作の中で最も複 雑である。第２０図は入力としてこま切れの定数を受け入れコードワード（レジ スタＲ１１２２２内に）及びメモリサブシステム１２００内に呼応するレコード のビットマツプのいずれか又は双方を形成するスーパーインポーズドコードワー ド計算ユニット１２２０を表わしている。このユニッ）　１２２０において用い られる乱数は線形順序回路を用いて計算される。

指標付は動作の結果はメモリシステム１２００内の呼応するレコードのビットマ ツプである。ホストアプリケーションはビットマツプそれ自体でなく主として呼 応するレコードのロケーションに関心がある。第２１図はオールゼロを報告しな い回路１５０すなわちオールゼロ出カライン上に低レベルの信号を出力する回路 のシフトレジスタからの呼応するビットマツプを抽出するための複数の能動メモ リ回路又はチップ１５０を保持し呼応するビットマツプ内の１ビツトに対応する アドレスをＦＩＦＯ記憶ユニッ）　１２３２内に記憶するユニン）　１２３０を 表わしている。好適には、プロセスをパイプライン化することによってホストは アドレスが生成されるや否やそれを獲得する。

ユニット１２３２は自動的に次のアドレスを計算しそれらをＦＩＦＯユニット１ ２３２内に記憶する。呼応するビットマツプ全体がスキャンされる前にＦＩＦＯ ユニット１２３２が満杯になったらユニッ）１２３２はホストがその要求又は命 題を取り下げるかＦＩＦＯ１２３２からアドレスを取り出すまで一時停止する。

呼応するビットマツプはビットレジスタ１２３１内に記憶され制御は選択／制御 ユニット１２３３によって行なわれる。

高度にダイナミックな応用において、第１６図を参照して以前に記述された様に 行入力／出力ライン１７０を用いてインデクス全体の挿入又は削除を行なうこと が頻繁に必要となってくる。また、所与の通用期間内に多数のデータ全体を一度 に取り除くごみ処理が必要とされることもある。その様な動作を達成する１つの 方法は第２２図に示す様な圧縮／拡張ユニット１２３４を使用することである。

ユニット１２３４はビットマツプの制御のもとに能動メモリ回路又はチップ１５ ０内に記憶されるインデクスの行を圧縮又は拡張する。圧縮モードにおいて、ビ ットマツプは除去されるべきインデクスの行の位置の各々に１を有している。ユ ニットは各行をさらにその行バツフア１２３６ヘコピーする。ユニット２３４は 除去されるまでの行の数のカウントを保持しそれを行バッファ１２３６の内容ヘ コピーすべき行を決定するために用いる。拡張はその逆に動作する。ビットマツ プは行が挿入されるべき位置の各々には１を有しておりコピー動作が最も高い行 アドレスから最低へと遂行される。空いた行にはゼロが挿入される。ビットマツ プ内に１つのビットがセットされていれば１つの行が挿入又は削除される。圧縮 ／拡張ユニッ）　１２３４は選択／制御ユニット１２３５で制御され制御ビット マツプ記憶装置１２３７はどの行において圧縮又は拡張が行なわれるかを示すビ ットマツプを記憶する。

複数の能動メモリ回路又はチップ１５０は仮想記憶のサポート、データフローコ ンピュータのノードスイッチング、及びＣＡＤシステム内の対象物のトラックの 保持の様な高速テーブル参照への多くの応用に用いることが可能である。これは 能動メモリ回路１５０の非常に簡単な応用であり、たとえあっても等値性テスト のみを必要とし１つのヒツトのみが期待されるのみであるから、第１９図の精巧 なアーキテクチャは必要とされない。第２３図は集積された能動メモリチップ１ ５０を有する特殊なテーブル参照ユニット１２３６の好適な具体例を示している 。ホストはテストワードレジスタ１２３９内に記憶するためのテストワードを供 給しユニット１２３９はテーブル内のテストワードアドレスに関する指示をヒツ トレジスタ１２４０に返す、ユニット１２３８は制御ユニッＨ２４１を含んでい る。

能動メモリチップ１５０は好適には０時記憶アレイ１８６によって供給される追 加の列と共にメモリ要素１８２の正方形のアレイ１８０を有している。アレイ１ ８０を行から見た場合と列から見た場合とでは異なるのでビットに対する記憶要 素１８２の配置が対称である必要がないことは回路１５０の重要な応用から明ら かである。１００．０００レコードのファイルに対する指標は多くの場合１２８ ビツトに適合する。テーブル参照は１行あたり３２ピントのみが必要であるが多 数の行がある。したがってそれはカスケード接続可能なユニット１２５０の３２ ビツト正方形として能動メモリ回路１５０を設計することが好ましい。

第２４図に示される様に高密度チップはこれら多数のカスケード接続可能なユニ ット１２５０を有する。

テーブル参照における゛用途において、テーブルの部分は各ユニット１２５０内 にあり初等的な演算はすべてのユニット１２５０において同時に達成される。一 般の指標付けの応用のためには、論理上の行は行方向にいくつかのユニット又は チップ１２５０にまたがって拡がる。最終的なビットマツプは１つの列内のすべ ての要素を選択する操作を用いて切れ切れに形成され最後に組み合わせのプロセ スがある。組み合わせのプロセスが選択されたシフトレジスタの内容をその行の 最も左のユニット１２５０のシフトレジスタへのコピーが可能であることが便利 である０列をカスケード接続することがシフトレジスタの論理的結合の最も簡単 な要求である。

能動メモリ回路１５０の最も容易に認識可能な応用は以前に記述した連想記憶メ モリシステム６２における応用である。

第２５図に示される様に能動メモリ回路１５０を採用した連想記憶メモリシステ ム６２はインデクスメモリユニット７４を形成する１６個のビデオメモリ８０と 、インデクスプロセッサ７６を形成する１６個の能動メモリ回路１５０を具備し ている。インデクスプロセッサ７６は能動メモリ回路１５０を制御するための以 前に記述したホストインターフェースポート１２０の様な制御ユニット（図示せ ず）も含んでいる。　４０９６ビツトの大きさを有するビットマツプ又は列は１ ６ビツトバス１５００を介して能動メモリ回路１５０上のビットマツプ記憶設備 へ転送される。能動メモリ回路１５０に記憶されるビットマツプに対するビット マツプ演算が実行され演算の結果は１６ビツトデータバス１５０２を介してイン デクスメモリユニット７４へ戻される。第２５図に示されたアーキテクチャは第 ８図のメモリシステム６２よりも非常に速い速度で複合ビットマツプ演算を達成 する。第２５図のアーキテクチャは同量のメモリと共に多量のビットマツプマト リクスを記憶することも又可能で、レジスタ９４のシリアル入力ポートにおける データ入力によって出力された以前のデータを回復する必要なくメモリユニット ７４内のレジスタ９４からデータをシフトアウトすることができる。データの転 送に必要バスは１６ビツトの大きさで良く、したがって第８図のメモリシステム ６２における様に３つの１６ビツトのワードの転送のかわりに１６ビツトワード の転送のみが監視される必要がある。アーキテクチャ２５のインデクスプロセッ サ７６は１マイクロ秒以下のサイクルにおいてビットマツプ演算を実行すること が可能である。

浄書（内容に変更なし） アルゴリズム　： Ｌ：＝０・　６二：Ｏ・ ｆｏｒ　ｉ：＝１　ｔｏ　ｎ　ｄ。

ｃａｓｅＷ［１ｌｏｆ Ｏ，：Ｇ：＝Ｇ　ｏｒ　ｎｏｔ　Ｌ　ａｎｄ　８［ｉ　］；１：　Ｌ：＝Ｌ　ｏ ｒ　ｎｏｔＧ　ａｎｄ　ｎｏｔ　８［；］ｅｎｄ・ −−−−兎−−−−−−−−−−−っ ｒ−一−−−−−−−−−−−コ 浄書（内容に変更なし） 浄書（内容に変更なし） 手続補正書く方式〉 特許庁長官　吉　１）文　毅　殿 １、事件の表示 ＰＣＴ／ＡＵ８７１００２８４ ２、発明の名称 連想記憶メモリシステム ３、補正をする者 事件との関係　特許出願人 住所　〒１０５東京都港区虎ノ門−丁目８番１０号５、補正命令の日付 平成１年１１月７日（発送日） ６、補正の対象 （１）特許法第１８４条の５第１項の規定による書面の「発明者の住所」「特許 出願人の代表者」の欄 （２）委任状 （３）明細書の翻訳文 （４）請求の範囲の翻訳文 （５）図面の翻訳文 ７、補正の内容 ＋１）　＋２）　別紙の通り （３）明細書の翻訳文の浄書 （内容に変更なし） （４）請求の範囲の翻訳文の浄書 （内容に変更なし） （５）図面翻訳文の浄書（内容に変更なし）８、添付書類の目録 （１）訂正した特許法第１８４条の５ 第１項の規定による書面　１通 （２）委任状及びその翻訳文　各２通 （３）　浄書した明細書の翻訳文　１通（４）浄書した請求の範囲の翻訳文　１ 通（５）浄書した図面の翻訳文　１通 国際調査報告 −１−、−、ｌ−＋、、、、、−，，，，−−−、、ＰＣＴ／ＡＵ　８７１００ ２８４に閃スπＬフΣ廚π？街＝ｌ廷９スＫ】でＰゴσｌｚαＭ　ＡＰＰＬＩＣ ＡＴＩＣＮ　ｈｌ：１．　Ｉ’ＣＴ　ＡＩＪ　８７００２８４ｔＥ　４２００９ ３５　ＤＥ　２８４９９４４　ＦＲ２４０８８６８ＧＢ　２００９４６９Ａ、％ ｌＥＸ　Ｔｏ　”ＷＥ　フ君＝Ｒ傅す−ＣＭ）Ｊ、５ＥＡＲＯＩ　ＲＥＰＣＲＴ 　ＧＪ酎耐χα貫ｃ記、にγＪひＴＴＧＩ史、にテへ〇　Ｏ７（イ）２８４　（ ＣＣＮＩ）髪ｐ）Ｏ５４４１２３１３ｃＡ　１１６Ｂ３７６　ＥＰ　６９７６４ 　ＷＯ８２０２６１５ＤＥ　３２３２６７５　ａ（６５８３２９ＪＰ　５Ｅ１０ ３９３４１　ｔ’ｓ　４４７６５２８ＥＸ）ＯＦ　ＡＮＮＥＫ

Claims (17)

【特許請求の範囲】
1. １．複数のレコードを記憶するホストメモリ（６６，６８）とホストプロセッサ バス（７２）を有するホストコンピュータ（６０）との結合のための連想記憶メ モリシステム（６２）であって、該メモリシステム（６２）は： 該ホストコンピュータ（６０）に記憶されるレコードを表現するビットマップマ トリクスを記憶するためであって、使用において、該ホストプロセッサバス（７ ２）へ接続され該ホストコンピュータ（６０）によってアドレス可能なインデク スメモリ手段（７４）と、 該メモリ手段（７４）に記憶されたビットマップをアクセスし該ビットマップに 対するビットマップ演算を達成し、使用において、該ホストプロセッサバス（７ ２）へ接続され該ホストコンピュータ（６０）より制御されるインデクスプロセ ッサ手段（７６）と、 該インデクスメモリ手段（７４）と該インデクスプロセッサ手段（７６）との間 に接続され、該メモリ手段（７４）と該プロセッサ手段（７６）との間のビット マップの通過のために採用されたメモリシステムバス（７８）とを具備する連想 記憶メモリシステム（６２）。
2. ２．前記インデクスメモリ手段（７４）は複数のインデクスメモリ（８０）を具 備し該複数のインデクスメモリ（８０）の各々は： メモリセルのアレイ（９２）と； シフトレジスタ（９４）であって、該アレイ（９２）へ接続されたパラレル入力 ／出力バス（９６）と、該シフトレジスタ（９４）の対向する端部におけるシリ アル入力ポート（１０６）及びシリアル出力ポート（１０４）とを有し、該パラ レル入力／出力バス（９６）は該アレイ（９２）内のデータの選択された行のア クセスが可能であるシフトレジスタ（９４）とを具備し；前記メモリシステムバ ス（７８）は該インデクスメモリ（８０）の該シリアル入力及び出力ポート（１ ０６及び１０４）を前記インデクスプロセッサ手段（７６）へパラレルに接続し ；同時にアクセスされた該データの選択された行は少なくとも１つのビットマッ プを形成する請求の範囲第１項記載の連想記憶メモリシステム（６２）。
3. ３．前記アレイ（９２）が前記ホストコンピュータ（６０）によりアクセスされ る一方、前記インデクスプロセッサ手段（７６）は前記シフトレジスタ（９４） をアクセスする請求の範囲第２項記載の連想記憶メモリシステム（６２）。
4. ４．前記インデクスメモリ（８０）は第１又は第２のバンク（１１０又は１１２ ）内に配置され、予め定めたビットマップ演算を達成するにあたり、前記インデ クスプロセッサ手段（７６）は該第１のバンク（１１０）から第１のビットマッ プを該第２のバンク（１１２）から第２のビットマップアクセスし、該第１及び 第２のビットマップは該演算のオペランドを形成する請求の範囲第２項又は第３ 項記載の連想記憶メモリシステム（６２）。
5. ５．前記演算を実行するに先立ちオペランドを形成する前記ビットマップはそれ ぞれのバンク（１１０，１１２）のシフトレジスタ（９４）に記憶され該演算中 において前記インデクスプロセッサ手段（７６）は各シフトレジスタ（９４）シ リアル出力ポート（１０４）からのビットを同時にアクセスし、該アクセスされ たビットは各バンク（１１０，１１２）からの２ワードを形成し、該ワードに対 する演算を実行し、少なくとも１つのバンク（１１０，１１２）のシフトレジス タ（９４）のシリアル入力ポート（１０６）へ演算の結果のワードを出力する請 求の範囲第４項に記載の連想記憶メモリシステム（６２）。
6. ６．前記演算は前記ビットマップが４０９６ビットを具備すれば１６マイクロ秒 以下で達成される請求の範囲第５項記載の連想記憶メモリシステム（６２）。
7. ７．前記インデクスプロセッサ手段（７６）は：使用において該ホストプロセッ サバス（７２）へ接続されるホストインターフェースポート（１２０）と；該イ ンターフェースポート（１２０）と前記メモリシステムバス（２０）とに接続さ れたシリアル機能ユニット（１２４）とを包含し； 該インターフェースポート（１２０）は前記ホストコンピュータ（６０）に応答 して前記第１及び第２のビットマップをアクセスし該シリアル機能ユニットに該 第１及び第２のビットマップに対する予め定めたピットマップ演算を達成させる 請求の範囲第４項ないし第６項のいずれかに記載の連想記憶メモリシステム。
8. ８．前記シリアル機能ユニット（１２４）は前記メモリシステムバス（７８）を 介して前記シリアル出力ポート（１０４）へ結合する入力ラインと該メモリシス テムバス（７８）を介して前記シリアル入力ポート（１０６）へ結合する出力ラ インを有する論理ユニット（１３８）と該論理ユニット（１３８）の出力の監視 を可能にするディレイユニット（１４０）とを具備する請求の範囲第７項に記載 の連想記憶メモリシステム（６２）。
9. ９．行（１６０）及び列（１６２）に配置され少なくともビットマップの一部を 記憶するのに適するメモリセル（１８２）のアレイ（１８０）と； 少なくともビットマップの一部を記憶するのに適したシフトレジスタ（１５４） と； 該アレイ（１８０）と該シフトレジスタ（１５４）との間に接続された論理ユニ ット（１５６）とを具備し、該アレイ（１８０）、シフトレジスタ（１５４）及 び論理ユニット（１５６）は集積回路よりなり、該シフトレジスタ（１５４）は 該アレイ（１８０）の選択された列（１６２）をコピーすることが可能であり、 該論理ユニット（１５６）は該シフトレジスタ（１５４）の内容と該アレイ（１ ８０）の選択された列（１６２）との選択された論理演算を達成することが可能 であり、該演算の結果は該シフトレジスタ（１５４）内に記憶される能動メモリ 回路（１５０）。
10. １０．前記シフトレジスタ（１５４）はシフトレジスタセル（１１５０）の列を 具備し前記論理回路（１５６）は論理セル（１１７０）の列を具備し、該論理セ ル（１１７０）はそれぞれのシフトレジスタ（１１５０）とメモリセル（１８２ ）のそれぞれの行（１６０）とに結合される請求の範囲第９項に記載の能動メモ リ回路。
11. １１．前記論理セル（１１７０）は対応する制御ライン（１１８４，１１８６又 は１１８８）がイネーブルであるとき前記シフトレジスタセル（１１５０）の内 容と前記メモリセル（１８２）の選択された列（１６２）との論理演算を達成し 選択された論理演算の結果はシフトレジスタ（１１５０）へ書き込まれる請求の 範囲第１０項記載の能動メモリ回路。
12. １２．前記論理演算はＮＯＴ，ＡＨＤ，ＯＲ，ＸＯＲ，ＡＮＤＮＯＴ，ＯＲＮＯ Ｔ、及びＸＯＲＮＯＴを含む請求の範囲第１１項記載の能動メモリ回路。
13. １３．前記各シフトレジスタセル（１１５０）はシフトレジスタセル（１１５０ ）の列内にフリップフロップ（１１５２）とフリップフロップ（１１５２）の内 容を反転し別のフリップフロップ（１１５２）へ内容をシフトする回路とを含む 請求の範囲第１０項ないし第１２項のいずれかに記載の能動メモリ回路。
14. １４．前記論理セル（１１７０）は第１及び第２の記憶制御ライン（１１９６及 び１１９４）がイネーブルであるときそれぞれ前記シフトレジスタセル（１１５ ０）をメモリセル（１８２）の選択された列（１６２）内に記憶しメモリセル（ １８２）の選択された列（１６２）の内容を該シフトレジスタ（１１５０）に記 憶することを可能にする回路を含む請求の範囲第１０項ないし第１３項のいずれ かに記載の能動メモリ回路。
15. １５．前記シフトレジスタ（１５４）内に記憶されたピットの内容がすべて低レ ベルであるときその出力がＨレベルとなるＮＯＲゲート（１１１２）をさらに具 備する請求の範囲第９項ないし第１４項のいずれかに記載の能動メモリ回路。
16. １６．前記制御ライン（１１８４，１１８６，１８８８，１１９４及び１１９６ ）に接続された出力を有するコマンドデコーダ（１１０４）をさらに具備し、前 記デコーダ（１１０４）はコマンドライン（１１０６）を介して受けとる入力に 応答する請求の範囲第１１項ないし第１４項に記載の能動メモリ回路。
17. １７．前記インデクスプロセッサ手段（７６）は請求の範囲第９項ないし第１６ 項のいずれかに記載の１つ又はそれ以上の能動メモリ（１５０）を具備する請求 の範囲第１項ないし第３項のいずれかに記載の連想記憶メモリシステム（６２） 。