(57)【特許請求の範囲】
【請求項１】
第１の複数ビットの信号線、第２の複数ビットの信号線を入力とし、該第１の信号線と該第２の信号線の複数ビットの加算結果と比較される複数ビットの情報を記憶したメモリ集合体とを有し、該メモリ集合体の中の、複数のビット番号のメモリセルと接続するワイアードＯＲないしワイアードＡＮＤ信号を有し、該メモリ集合体のビットｎに対応するメモリセルが、上記第１の信号線のビットｎと上記第２の信号線のビットｎと上記第１の信号線のビット（ｎ−１）と上記第２の信号線のビット（ｎ−１）に依存する信号Ａ（１）か、あるいは上記第１の信号線のビットｎと上記第２の信号線のビットｎと上記第１の信号線のビット（ｎ＋１）と上記第２の信号線のビット（ｎ＋１）に依存する信号Ａ（２）のいずれか一方と、ビット番号（ｎ＋１）、ビット番号（ｎ−１）のいずれか一方のメモリセルの記憶情報を示す信号線とを入力し、上記信号Ａ（１）とビットｎのメモリセルの値とビット（ｎ−１）のメモリセルの値に依存する条件かあるいは上記信号Ａ（２）とビットｎのメモリセルの値とビット（ｎ＋１）のメモリセルの値に依存する条件かのいずれか一方によって上記ワイアードＯＲないしワイアードＡＮＤ信号をプルダウンあるいはプルアップし、
上記連想メモリの連想結果に従いワード線を介してアクセスされる第２のメモリをもち、上記第２のメモリは各々のメモリセルが２本のワード線と４本のデータ線を有する２ポートメモリであり、上記連想メモリは、上記第１の信号線値と上記第２の信号線値の加算の結果、下位からの桁上がりが０のケースに対応する第１のヒット線群と上記第１の信号線値と上記第２の信号線値の加算の結果、下位からの桁上がりが１のケースに対応する第２のヒット線の両方を上記第２のメモリに出力し、上記第２のメモリでは上記第１のヒット線群に従い上記第１のデータを読みだし、上記第２のヒット線群に従い第２のデータを読みだし、該当加算の下位からの桁上がり結果に従い上記第１のデータと上記第２のデータを選択することを特徴とする半導体連想メモリ集積回路装置。
【請求項２】
１ビットの記憶素子と複数のメモリセルにより共有されるヒット線と検索データ線とを有するメモリ部であり、１つの上記メモリセルに対応して上記ヒット線を少なくとも第１から第１０の１０個のＭＯＳトランジスタによりプルダウンあるいはプルアップし、上記ヒット線から順に該第１のＭＯＳトランジスタ、該第２のＭＯＳトランジスタ、該第３のＭＯＳトランジスタを経由して上記検索データ線に至る経路で上記ヒット線をプルアップあるいはプルダウンする第１の電流パスと、上記ヒット線から順に該第１のＭＯＳトランジスタ、該第４のＭＯＳトランジスタ、該第５のＭＯＳトランジスタを経由して上記検索データ線に至る経路でプルアップあるいはプルダウンする第２の電流パスと上記ヒット線から順に該第６のＭＯＳトランジスタ、該第７のＭＯＳトランジスタ、該第８のＭＯＳトランジスタを経由して上記検索データ線に至る経路でプルアップあるいはプルダウンする第３の電流パスと上記ヒット線から順に該第６のＭＯＳトランジスタ、該第９のＭＯＳトランジスタ、該第１０のＭＯＳトランジスタを経由して上記検索データ線に至る経路でプルアップあるいはプルダウンする第４の電流パスとを有することを特徴とする半導体メモリ集積回路装置。
【請求項３】
１ビットの記憶素子と複数のメモリセルにより共有されるヒット線と検索データ線とを有するメモリ部からなり、１つの上記メモリセルに対応して上記ヒット線を少なくとも第１から第６の６個のＭＯＳトランジスタによりプルダウンあるいはプルアップし、上記ヒット線から順に該第１のＭＯＳトランジスタ、該第２のＭＯＳトランジスタを経由して上記ヒット線に至る経路で上記ヒット線をプルダウンあるいはプルアップする第１の電流パスと、上記ヒット線から順に該第１のＭＯＳトランジスタ、該第３のＭＯＳトランジスタを経由して上記検索データ線に至る経路で上記ヒット線をプルアップあるいはプルダウンする第２の電流パスと、上記ヒット線から順に該第４のＭＯＳトランジスタ、該第５のＭＯＳトランジスタを経由して上記検索データ線に至る経路で上記ヒット線をプルアップあるいはプルダウンする第３の電流パスと、上記ヒット線から順に該第４のＭＯＳトランジスタ、該第６のＭＯＳトランジスタを経由して上記検索データ線に至る経路で上記ヒット線をプルアップあるいはプルダウンする第４の電流パスとを有することを特徴とする半導体メモリ集積回路装置。
【請求項４】
その内部に命令アドレス加算器及びデータアドレス加算器を有する中央処理ユニット、上記命令アドレス加算器と連動して動作する命令ＴＬＢ及び命令キャッシュ、上記データアドレス加算器と連動して動作するデータＴＬＢ及びデータキャッシュとが一つの半導体領域に集積化して内蔵され、上記命令アドレス加算器、命令ＴＬＢ及び命令キャッシュ及び上記データアドレス加算器、データＴＬＢ及びデータキャッシュは上記請求項１に記載の連想メモリ動作を遂行するようにされたことを特徴とする情報処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は絶縁ゲート型半導体集積回路装置及びそれを用いた情報処理装置に関するものであり、特に連想メモリ機能と加算機能を有する絶縁ゲート型半導体集積回路装置及びそれを用いた情報処理装置に関するものである。
【０００２】
【従来の技術】
連想メモリに関する従来技術がNeil Waste, Kamran Eshraghian: "Principles of CMOS VLSI Design - A System Perspective", Addison Wesley出版社 (1988年6月)の第３５１頁（以下、文献１と称する）に示されている。
【０００３】
A+B=Kの判定処理を高速に行う回路方式に関する従来技術が"Evaluation of A+B=K Conditions Without Carry Propagation", IEEE Trans. on Computers, Vol. 41, No.11, pp. 1484-1487,1992年11月（以下、文献２と称する）に示されている。
【０００４】
加算とアドレスデコードを高速に行う回路方式に関する従来技術が"Address Addition and Decoding without Carry Propagation", IEICE Trans. （電子情報通信学会英文誌）, Inf & Syst., Vol.E08-D, No.1, pp. 98-100 、1997年1月（以下、文献３と称する）に示されている。
【０００５】
高速な、統合された加算器およびＴＬＢ（Translate Lookaside Buffer）回路に関する従来技術が特開平8-212789（以下、文献４と称する）に示されている。
【０００６】
文献１では、content-addressable memory（CAM）なる比較機能を有するメモリの１ビット分が２個のＰチャネルMOSトランジスタと７個のＮチャネルMOSトランジスタで構成できることが示されている。
【０００７】
なお、以下ＰチャネルMOSトランジスタをPMOSと、ＮチャネルMOSトランジスタをNMOSとそれぞれ略す。
【０００８】
またメモリセルのBIT端子に！DATA （！は論理否定を示す。DATAは外部から与える比較データを意味する。) を、！BIT端子に DATAを供給することにより、比較で不一致があればMATCH線がローレベルにプルダウンされることが示されている。またこのメモリセルを用いて複数ビットの比較処理、つまり入力したｎビットのデータがメモリに格納したｎビットのデータと一致するか否かを判定する処理、を行うこともすでに公知である。複数ビットの比較動作を行うためには複数ビット間でMATCH線を共有すればよい。
【０００９】
またこのCAMのヒット線の結果で別のRAMをアクセスすることによって、計算機のTLB（Translation Lookaside Buffer、論理アドレスから物理アドレスへ変換するメモリ）が構成できることも公知である。
【００１０】
文献２では、複数ビットでのA+B=K（ここで、Kは固定値信号、AおよびBは入力信号）なる等式の成立を判定する場合に、従来はA+Bを演算するために加算器でのキャリ伝播処理時間が必要であると思われていたが、論理回路の組み方に工夫を行うことにより、該加算器でのキャリ伝幡が不要とできることが示されている。
【００１１】
文献３では、FAC（East-Adder-Comparator）という回路を用いることにより、第１の値と第２の値との加算結果でメモリのワード線のアドレスデコードを行う場合に、キャリ伝幡時間を待たずにアドレスデコード処理を開始できることが示されている。なお、その実現のために文献２のアルゴリズムを使用している。
【００１２】
文献４では、FACという回路を用いることにより、第１の値と第２の値との加算結果でＴＬＢを検索する場合に、第１の値と第２の値との加算結果が比較値に一致するか否かが高速に判定されると記載されている。高速化される部分は加算でのキャリ伝播時間の内の一部分である。なお、その実現のために文献２のアルゴリズムを使用している。
【００１３】
【発明が解決しようとする課題】
加算した値を検索データとして連想メモリを検索する動作はMOS型集積回路装置にて行うべき処理の一例である。その代表例として、多くの計算機では２つのデータを加算した値をアドレスとしてTLB等の連想メモリを検索する処理を有する。
【００１４】
文献４で開示された技術を用いると加算したアドレスを連想メモリに与えるケースにて比較対象の値、つまりメモリ値に一致するか否かが高速に判定されるが、ただし次の３つの問題がある。
【００１５】
第１の問題はトランジスタ数が多く、ＴＬＢ回路の論理規模が大きくなるという問題である。例えば文献４での１６頁、図９に記載された回路では、連想の必要とするメモリ、つまりタグメモリのメモリセル１ビットあたりインバータ１個、2入力ANDゲート１個、2入力ORゲート１個、EORゲート２個を要する。標準的なCMOS回路でインバータ１個は２トランジスタを、ANDゲート１個は６トランジスタを、ORゲート１個は６トランジスタを、EORゲート１個は１０トランジスタをそれぞれ要する。その結果メモリセル１ビットあたり合計３４個のトランジスタを要する。これを結果１と称する。
【００１６】
結果１の他に１エントリの連想の必要とするメモリビット長をｎとすると、ｎ入力のANDゲートが必要である。ｎ入力のANDゲートは（２ｎ＋２）個のトランジスタを要するので、セル１ビットあたり約２トランジスタを要する。これを結果２と称する。結果１と結果２を加え、メモリセル１ビットあたり３６個のトランジスタをメモリ回路とは別に要する。
【００１７】
検索機能を有しない、単純なメモリセルはCMOSタイプのＳＲＡＭ（Static Random Access Memory）であれば６トランジスタで構成できることが知られているから、文献４で開示された技術を用いるとメモリセル部分に関するトランジスタ数が単純なＳＲＡＭメモリの７倍になる。このことはＬＳＩで構成する場合、ＬＳＩチップ面積の増大をもたらす。
【００１８】
第２の問題はｎ入力のANDゲートに入力する信号を配線するためにｎ本の信号線が必要であり、メモリを配置したときにメモリのエントリ方向に最低でも（ｎ／２）本の信号線配置領域が必要であることである。このことも先と同様にＬＳＩで構成する場合、ＬＳＩチップ面積の増大をもたらす。
【００１９】
第３の問題は連想メモリのタグ部分のビット番号に下位ビットからの桁上がり信号が存在する場合、連想メモリがRAMに出力するRAMアクセスワード線の確定が下位からの桁上がり処理の結果よりも先に行うことができず、従って高速動作に限界がある点である。
【００２０】
なお、ここで下位ビットからの桁上がりについて説明する。
【００２１】
例えば、A[31:0], B[31:0]を加算し、その加算結果のビット[31:12]が連想メモリの[31:12]と等しいか否かを判定する場合、ビット11:0を下位ビットとよび、A[11:0], B[11:0]の加算結果の上位へのキャリを下位からの桁上がりとよぶ。
【００２２】
ビット31:12にのみ着目する仮の加算結果A[31:12]+B[31:12]、は下位からの桁上がり結果によって、インクリメントされる（この場合ビット12に対する＋1）可能性がある。文献４の連想メモリの出力は下位からの桁上がり結果に依存しているので、連想メモリがRAMに出力するRAMアクセスワード線が下位からの桁上がり処理の結果よりも先に実行することができない。そのため高速動作ができない。なおこの第３の問題は前記した第１、第２の２つの問題とは独立であると以下本願では扱う。
【００２３】
本発明で解決しようとする課題をまとめると以下の通りである。
【００２４】
本発明で解決しようとする課題の１つは、第１の値と第２の値との加算結果でＴＬＢを検索する場合に、第１の値と第２の値との加算結果が複数のメモリ値に一致するか否かが高速に判定されるという特徴を備えた半導体集積回路装置およびそれを用いた情報処理装置を提供することである。
【００２５】
本発明で解決しようとする課題の他の１つは、第１の値と第２の値との加算結果でＴＬＢを検索する場合に、トランジスタ数の増大を小さく抑えた半導体集積回路装置およびそれを用いた情報処理装置を提供することである。
【００２６】
本発明で解決しようとする課題の更に他の１つは、第１の値と第２の値との加算結果でＴＬＢを検索する場合に、第１の値と第２の値との加算結果が複数のメモリ値に一致するか否かが高速に判定されるという特徴を備え、かつ従来知られている方法を採用した場合に発生するメモリのエントリ方向に沿って走る信号線配置領域の増大を小さく抑えることである。
【００２７】
本発明で解決しようとする課題の更に他の１つは、第１の値と第２の値との加算結果でＴＬＢを検索する場合に、第１の値と第２の値との加算結果が複数のメモリ値に一致するか否かが高速に判定されるという特徴を備え、かつ従来知られている方法を採用した場合に発生する連想メモリがRAMに出力するRAMアクセスワード線が下位からの桁上がり処理の結果よりも先に実行できないため高速化できないという問題を解決するものである。
【００２８】
【課題を解決するための手段】
本発明では発明が解決しようとする課題の項で述べた上記第１および第２の問題点を解決するために、エントリ上の複数のビットに渡った共通のヒット信号線に関するワイアードAND あるいはワイアードORを設け、その信号を用いて一致したか否かのヒット信号を構成する。ワイアードAND あるいはワイアードORをもつことから、そのメモリは一種のＣＡＭ（Content Addressable Memory）とみなすことができる。
【００２９】
この方法を用いることにより、メモリに付加して必要なトランジスタ数は少なくとも６個のトランジスタで実現できる。実施例でその具体的な回路例を示す。本例で６個のトランジスタで構成するＣＭＯＳタイプのメモリセルと組み合わせて使用するならば、メモリセルと一致比較部を合わせ、少なくとも１２個のトランジスタでメモリセルを実現でき、従来知られている方法を採用した場合に発生するトランジスタ数の増大を著しく小さく抑えることができる。
【００３０】
また、ワイアードＡＮＤまたはワイアードＯＲを用いることにより、従来知られている方法を採用した場合に発生するメモリのエントリ方向に沿った信号線配置領域の増大を小さく抑えることが可能である。実施例で示す回路では、メモリのエントリ方向に必要な信号線配置領域は単純なＳＲＡＭと比較して、３本の付加で実現することができる。つまり、従来例での信号線配置領域である最低でも（ｎ/２）本と比較して配線面積を小さくすることが可能である。
【００３１】
従って、一つの半導体領域又は基板にこれらを他の回路機能部も含めたシステム全体を効率的に内蔵せしめることが可能となり、特にマイクロプロセッサのような情報処理装置のＬＳＩ化に適している。
【００３２】
例えば、本発明の一つにかかわる半導体集積回路装置は、一つの半導体領域（基板）表面に隣接して配置された第１メモリセルと第２メモリセル、両メモリセルに共通のヒット線を有し、各メモリセルはスタテイックメモリセル部とヒット線の電位を決定するヒット線電位決定回路部とで構成され、第１メモリセルのヒット線電位決定回路部は第２メモリセルのスタテイックメモリセル部の出力と第１メモリセルのスタテイックメモリセル部の出力とによって制御されるものであり、このようなメモリセルが多数縦横に行列状に配置され同様に動作するように構成されていることを特徴としている。
【００３３】
加えて本発明の好適な一つの実施例では上記第３の問題点を解決するために、連想メモリから第２のメモリ（つまりＲＡＭ）に対して第１の信号線値と第２の信号線値の加算の結果、下位からの桁上がりが０のケースに対応する第１のヒット線群と第１の信号線値と第２の信号線値の加算下位からの桁上がりが１のケースに対応する第２のヒット線の両方を第２のメモリに出力し、該第２のメモリでは第１のヒット線群に従い第１のデータを読みだし同時に第２のヒット線群に従い第２のデータを読みだし、該当加算の下位からの桁上がり結果に従い該第１のデータと第２のデータを選択することを特徴とする装置を構成することが可能である。
【００３４】
【発明の実施の形態】
本実施例を通じて、連想メモリで検索すべきデータはｎビットであり、データの最下位はビット番号ｓであるとする。つまり、連想メモリで検索すべきデータはビット番号の[s+n-1: s]であることとする。
【００３５】
実施例１  図１に実施例１で説明する一つの半導体領域に集積して形成された連想メモリの全体構成図を示す。１０１A、１０１Ｂはｎビットの入力信号であり、加算すべき２つの数のそれぞれビット番号[s+n-1: s]を示す。１０２は桁sへのキャリ入力信号を示す。
【００３６】
１０３は１０１A、１０１Ｂを処理して４ｎ本の信号をメモリ部に送る比較データ加工論理部である。それはビット毎に等価な論理回路１０８A、１０８Ｂ、・・・１０８Ｃからなる。
【００３７】
１０５はメモリマット部であり、メモリマット部には１ビットの記憶部分を有するメモリセルがアレイ状に縦横に配置されている。
【００３８】
１０６はメモリ部のＸ方向（図では横方向）の一列であり、連想メモリの１エントリ部である。１０９Ａ、１０９Ｂ、１０９Ｄ、１０９E、・・・１０９Ｇ、１０９Ｈは連想機能を備える１ビットのメモリセルである。１０９Ｃ、１０９Ｆ、・・・１０９Ｉは連想機能を備える１ビットのメモリセルであり、これらは連想部分の内最下位（ＬＳＢ）のビットのメモリセルであり、後述するように他のメモリセルとは内部の回路構成が異なる。
【００３９】
１１０はワードデコーダ部であり、メモリセルのワード線を制御する。その機能は半導体メモリの専門家には明らかであるので説明は省略する。１０７はワードデコーダに入力するｍビットのアドレス信号線である。１１１はメモリのデータ入出力回路部である。データ入出力回路部１１１の機能も半導体メモリの専門家には明らかであるので説明は省略する。
【００４０】
メモリ部１０５は他の回路部と次の接続を有している。比較データ加工論理部１０３から比較データ１１５Ａ、１１５Ｂ、１１５Ｃを受け取る。ワードデコーダ部１１０からワード線１１４Ａ、１１４Ｂ、１１４Ｃを介してアドレス信号を受け取る。データ入出力回路部１１１とデータ信号線１１２Ａ、１１２Ｂ、１１２Ｃを経由してデータの授受を行う。検索結果出力線１０４Ａ、１０４Ｂ、１０４Ｃに検索結果が出力される。
【００４１】
メモリ部をＹ方向（図では上下方向）に貫通する信号線１１５Ａ、１１５Ｂ、・・・１１５Ｃ、及び１１２Ａ、１１２Ｂ、・・・１１２Ｃに関しては図１からあきらかなように上下を通じてそれぞれ同一のノードである。１１３Ａ、１１３Ｄ、・・・１１３Ｇ、及び１１３Ｂ、１１３Ｅ、・・・１１３Ｈはメモリ部をＸ方向（図では左右方向）に接続する信号線であるが、１１３Ａと１１３Ｂ、１１３Ｄと１１３Ｅ、１１３Ｇと１１３Ｈのように隣あったメモリセルの間を結合する信号ノードは後述するように完全に同一ではない。
【００４２】
図２にこの実施例１に示すメモリセルの１０９Eの一例を示す。なお、１０９Ｅの内部回路構成は１０９Ａ、１０９Ｂ、１０９Ｄ、１０９Ｇ、１０９Ｈと同じである。
【００４３】
１０９Ｅは連想メモリの１ビット分の回路に相当している。その内２０１〜２０４はＭＯＳトランジスタを含む所謂スタテイックメモリセル部を示している。２０１、２０２はインバータ（論理反転素子）である。２０３及び２０４はＮＭＯＳＦＥＴである。インバータは２個のＭＯＳＦＥＴで構成される。２１５はメモリのワード線（図１の１１４Ｂに対応している）であり、２１６及び２１７はメモリのデータ線対である。２１５、２１６、及び２１７の信号を用いてこのメモリがＳＲＡＭメモリとしてアクセスできることはよく理解されているところである。
【００４４】
２１８、２１９、２２０、２２１は検索データ信号入力線である。これは図１で信号線１１５Ｂとして示されたものを詳細に表示したものである。
【００４５】
２２２及び２２３はメモリセル１０９Ｅの出力に、即ちＭＯＳＦＥＴ２０１〜２０４で構成されるスタテイックメモリセル部の出力ノードに、接続され当該メモリ値を左隣のメモリセル（図１の１０９Ｄに対応する）に伝達（出力）するための信号線である。２２３は２２２の論理反転の関係にある。
【００４６】
また、２２４及び２２５は同様に右隣のメモリセルの出力に、即ち右隣のスタテイックメモリセル部の出力ノードに、接続されそのメモリ値をこの１０９Ｅのメモリセルに伝達（入力）するための信号線である。隣のメモリのメモリ値を入力する場合、２２５は２２４の論理反転の関係にする。２２６はヒット線（又はマッチ線とも呼ばれる）である。従って、図から理解されるように、メモリセル１０９Eは左隣のメモリセル（１０９Ｄ）と２１５、２２２、２２３、２２６の４本の信号線で結合乃至接続されている。この信号線群は図１で１１３Dとして説明されたものに相当する。
【００４７】
一方、メモリセル１０９Eは右隣のメモリセルと２１５、２２４、２２５、２２６の４本の信号線で結合乃至接続されている。この信号線群は図１で１１３Eとして説明されたものに相当する。なお、上記したように２２４及び２２５は右隣のスタテイックメモリセル部の出力ノードに接続されている。
【００４８】
更に、図１でメモリ部１０５とデータ入出力回路部１１１とを結合乃至接続する信号線として説明された１１２Ｂは図２では２１６と２１７に相当する。
【００４９】
本実施例では、ヒット線２２６はメモリセル１０９Ｅの内部にヒット線２２６の電位をプルダウンさせるための直列接続されたＮ型ＭＯＳＦＥＴ２１０、２１３、２１４及びＮ型ＭＯＳＦＥＴ２１０、２１１、２１２からなる第１のプルダウンパス、並びに別に直列接続されたＮ型ＭＯＳＦＥＴ２０５、２０８、２０９及びＮ型ＭＯＳＦＥＴ２０５、２０６、２０７からなる第２のプルダウンパスが設けられ、これらのＭＯＳＦＥＴのゲート電極に当該メモリセル１０９Ｅ自身の出力信号即ちＭＯＳＦＥＴ２０３〜２０４で構成されるスタテイックメモリセル部の出力信号と右隣のメモリセルのスタテイックメモリセル部の出力信号とが印加されている。
【００５０】
即ち、ヒット線２２６の電位はプルダウンパスを介して当該メモリセルを構成しているスタテイックメモリセル部の出力信号と右隣のメモリセルを構成しているスタテイックメモリセル部の出力信号とによって制御され、所定の条件でヒット線２２６が有効に電源電位端子の基準電位にプルダウンされる。
【００５１】
例えばダイナミック制御をする場合なら、検索動作に先立って、ヒット線２２６をハイレベルにプリチャージしておく。また検索データ入力線２１８、２１９、２２０、２２１をローレベルにしておく。この時点ではメモリセル１０９Ｅの中でヒット線２２６に対するプルダウン電流は流れない。検索動作が開始するときに検索データ入力線２１８、２１９、２２０、２２１に検索データを与える。
【００５２】
なお、この図２の回路構成によるメモリセル部１０９Ｅは合計16個のトランジスタで構成されており、前述した従来のものに比べ著しくＭＯＳＦＥＴの個数が減じられている。
【００５３】
次に、図１における比較データを生成する論理回路部１０８Ｂについて図３の回路ブロック図を用いて説明する。なお、ビット毎の論理１０８Ａ、１０８Ｂは共通である。
【００５４】
３０１は２入力ＡＮＤゲートであり、２つの入力信号の論理積を出力する。３０２は２入力ＯＲゲートであり、２つの入力信号の論理和を出力する。３０３は２入力ＥＯＲゲートであり、２つの入力信号の排他的論理和を出力する。３０４、３０５は２入力ＥＮＯＲゲートであり、２つの入力信号の排他的論理和の論理否定を出力する。３０６、３０７は２入力ＮＡＮＤゲートであり、２つの入力信号の論理積の否定を出力する。３１０、３１１、３１２はインバータである。３０８、３０９は２入力ＮＯＲゲートであり、２つの入力信号の論理和の否定を出力する。
【００５５】
３１３、３１４はそれぞれ３０１、３０２のゲートの出力を左隣の比較データを生成する論理（図１での１０８Ａ）に伝達乃至出力する信号線である。３１５、３１６は同様にそれぞれ右隣の比較データを生成する論理回路部（その論理も論理１０８Bと同型である）の２入力ＡＮＤのゲート出力と２入力ＯＲのゲート出力を受け取るための信号線である。
【００５６】
丁度図３に示した配置で点線の箱１０８BをＸ方向（即ち左右方向）に重ね、端子３１３を左隣の回路部の３１５に、端子３１４を左隣の回路部の３１６に接続することによって、比較データ加工論理回路部１０３の全体が構成される。
【００５７】
３１７は検索イネーブル信号線である。検索イネーブル信号線３１７がローレベルのときには出力信号２１８、２１９、２２０、２２１は皆ローレベルに固定される。検索イネーブル信号３１７がハイレベルのときには出力信号２１８、２１９、２２０、２２１（この４本の信号線は図１の１１５Ｂに対応する）は１０１Ａ、１０１Ｂ、３１５、３１６の組み合わせ論理結果を有効に出力するように機能する。
【００５８】
次に、図１におけるメモリセルの内１０９Fについて図４を用いて説明する。なお、図４中での２０１、２０２、２０３、２０４及び２０６、２０７、２０８、２０９、２１５、２１６、２１７、２１８、２１９、２２２、２２３は図２で説明したものと同じ機能を有するので説明を省略し、図２では説明されない構成要素を以下説明する。
【００５９】
４３０、４３１はプリチャージ制御線である。４３２は検索結果線である。４３６はＬＳＢ１ビットのヒット線である。４３３、４３４はプリチャージ用ＭＯＳトランジスタである。４３５は2入力ＡＮＤゲートである。
【００６０】
プリチャージ用トランジスタ４３３はプリチャージ制御線４３０によって制御され、ヒット線２２６をハイレベルにプルアップする機能を有する。プリチャージ用トランジスタ４３４はプリチャージ制御線４３１によって制御され、ＬＳＢ１ビットのヒット線４３６をハイレベルにプルアップする機能を有する。また、このＬＳＢ１ビットのヒット線４３６はＮＭＯＳトランジスタ２０６、２０７、２０８、２０９によって形成される回路パスにてプルダウンされる。即ち、これらのトランジスタのゲートにスタテイックメモリセル部の出力信号と検索データ入力信号とが印可され、所定条件のもとにＬＳＢ１ビットのヒット線４３６が有効に電源電位端子の基準電位レベルにプルダウンされる。
【００６１】
次に、文献２の数式を用いながら説明すると図１、図２、図３、図４の回路の動作の説明ははるかに理解しやすくなるので、以下、数式にて本実施例を説明する。
【００６２】
比較する最下位のビット番号をsとし、比較するビット数をnとする。加算する２つの数を、
A = {a[s+n-1], a[s+n-2], ..., a[s]}
B = {b[s+n-1], b[s+n-2], ..., b[s]}
とする。また連想メモリに格納されている１エントリにのみ注目し、そのエントリのメモリの値を
K = {k[s+n-1], k[s+n-2], ..., k[s]}
とする。
【００６３】
A, Bの２つの加算式は A + B + cin[s](ビット番号sへのキャリイン) である。cin[s]はビット(s-1)からビット0までの加算結果により求められる。
【００６４】
x[i] = (a[i] eor b[i]) enr (a[i-1] + b[i-1]) (i>s)
y[i] = (a[i] eor b[i]) enr (a[i-1] * b[i-1]) (i>s)
とおく。i=sに関しては
x[s] = (a[s] eor b[s]) enr cin[s]
y[s] = (a[s] eor b[s]) enr cin[s]
とおく。
【００６５】
すると、ビット[n-1+s:s]に関しての
A+B+Cin[s]=K
の条件成立dは、
0004033609.tif 000002
(ここでk[s-1]=0とする)
となることが証明されている。その証明は文献２にて記載されているので省略する。
【００６６】
信号線４３２に上記の式dが得られることを、以下示す。なお、これ以降数学的議論が続くが、その前提として、プリチャージ線はレシオないしは、ダイナミック制御をすることにより本質的にプルダウン側のみを考察すれば十分であることは半導体メモリの専門家には明らかであるを前提とする。また、図３の論理を追うことにより、検索イネーブル線２１７がハイレベルのときには検索データ信号線２１８、２１９、２２０、２２１、にそれぞれx[s-1]， !x[s-1]， y[s-1]， !y[s-1]が得られていることを確認されたい。
【００６７】
定理１. ヒット線226がビット番号i (i=n-1+s, n-2+s, ..., s+1)に存在するメモリセルでプルダウンされる条件は  !e[i]  である
(証明)ここでx[i]=X， y[i]=Y， k[i]=L， k[i-1]=Mとおく。
【００６８】
図２に示すようにヒット226をプルダウンする電流パスは４つあり、それぞれ
!X !L !M ， !Y !L M ， X L !M ， Y L M
でプルダウンするから、ヒット線２２６がビット番号i(i=n-1+s, n-2+s, ..., s+1)に存在するメモリセルでプルダウンされる条件は、
!X !L !M + !Y !L M + X L !M + Y L M
である。一方 !e[i]も
0004033609.tif 000003
であり、両者は等しい。
【００６９】
定理２. ＬＳＢヒット線４３６がプルダウンされる条件は !e[s] である。
【００７０】
(証明)図４に示すようにヒット線４３６をプルダウンする電流パスは2つあり、
それぞれ
!X !L ， X L
でプルダウンするから、ヒット線４３６をプルダウンする条件は、
!X !L + X L
である。一方 !e[s]もk[s-1]=0なることに注意すれば、
0004033609.tif 000004
であり、両者は等しい。
【００７１】
以上の定理１、２と図１の全体図の接続、ＡＮＤゲート４３５に対して考察すると、(ヒット線２２６がハイレベルになることは接続するいずれのビット番号のメモリセルでもプルダウンされないことであることに留意し)、４３２がハイレベルなる条件は、ビット番号i(i=n-1+s, n-2+s, ..., s)に存在するメモリセルのいずれでもプルアップされないことであるとわかる。
【００７２】
つまり、４３２がハイレベルなる条件は、
0004033609.tif 000005
である。
【００７３】
以上でメモリエントリ１０６に関する連想動作を説明した。他のエントリに関してもまったく同様の議論が成りたつ。
【００７４】
実施例２  つぎに第２の実施例について説明する。第１の実施例での説明で明らかになったようにビット番号iのメモリセルで条件式 !e[i]でヒット線をプルダウンすることが本発明の一つの趣旨である。図５では上記動作を可能とする別のメモリセルを示す。これは１２個のトランジスタのメモリセルを用いたものである。図５は図２と一部の回路を共通とする。
【００７５】
５０１は１ビットのメモリセルである。２０１、２０２、２０３、２０４、２０５、２０６、２０８、２１０、２１１、２１３、２１５、２１６、２１７、２２２、２２３、２２４、２２５は図２で説明したものと同一の機能を有するので、説明は省略する。５２６はヒット線である。
【００７６】
５１８、５１９、５２０、５２１は検索データ入力である。５１８には２１８の信号の否定信号を、５１９には２１９の信号の否定信号を、５２０には２２０の信号の否定信号を、５２１には２２１の信号の否定信号をそれぞれ供給する。検索動作に先立って、２２６をハイレベルにしておく。また検索データ入力５１８、５１９、５２０、５２１をハイレベルにしておく。このときヒット線５２６にプルダウン動作は起こらない。
【００７７】
検索動作時、検索データ入力５１８、５１９、５２０、５２１にそれぞれ、定理１の証明で定義した!X、 X、 !Y、 Yを与える。なお、検索データの生成論理の構成方法は、図３の説明から十分である。検索動作時、検索データ線がハイならヒット線５２６のプルダウンは発生せず、検索データがローなら、検索データ線とヒット線の間を結ぶ直列接続のNMOSの導通条件によりヒット線５２６はプルダウンされる。プルダウン条件を数え上げると、
!X !L !M + !Y !L M + X L !M + Y L M
になる。これは図２のヒット線２２６のプルダウン条件と同一であるので結果として、図１と同様に連想メモリが構成できることは、ここまでの説明から十分明らかである。
【００７８】
実施例３  つぎに第３の実施例について説明する。第１の実施例での説明で明らかになったようにビット番号iのメモリセルで条件式 !e[i]でヒット線をプルダウンすることが本願方式の趣旨である。図６では上記動作を可能とする別のメモリセルを示す。
【００７９】
図６で６０１はメモリセルである。メモリセル６０１は１９トランジスタから成る。要するトランジスタ数は図２、図５で示したメモリセルよりも多いが、連想の回路的スピードは図２、図５で示したメモリセルより高速である。高速なる理由は、ヒット線をプルダウンするトランジスタが３個直列のＮＭＯＳでなく、１個のＮＭＯＳであること、およびヒット線にドレインを接続するＭＯＳが１セルあたり２個でなく１個であるためにヒット線の総負荷容量が小さいこと、の２つの理由からなる。
【００８０】
２０１、２０２、２０３、２０４、２１５、２１６、２１７、２１８、２１９、２２０、２２１、２２２、２２３、２２４、２２５は図２で説明したものと同一の機能を有するので、説明は省略する。６２６はヒット線である。
【００８１】
６３１、６３２、・・・、６３７はＮＭＯＳである。６４１、６４２、・・・、６４６はＰＭＯＳである。ヒット線６２６はこのメモリセル６０１の中でただ１個のＮＭＯＳ６３７によってプルダウンされる。プルダウン条件はＮＭＯＳ６３７のゲート電位＝Highなる条件に帰着する。
【００８２】
なお、このプルダウンＮＭＯＳ６３７はゲート電極には同図のようにＮＭＯＳ６３１〜６３６及びＰＭＯＳ６４１〜６４６の複数のＭＯＳが結合され、しかもこれらの複数のＭＯＳのゲート電極には実施例１と同様に当該スタテイックメモリセル部の出力と右隣のメモリセルのスタテイックメモリセル部の出力とに結合されている。従って、実施例１と同様に、ヒット線６２６の電位はこのプルダウンＮＭＯＳ６３７を介して当該スタテイックメモリセル部の出力と右隣のメモリセルのスタテイックメモリセル部の出力とによって制御されている。
【００８３】
６３１、６３２、・・・、６３６、６４１、６４２、・・・、６４６の接続を調べることにより、ＮＭＯＳ６３７のゲート電位は検索データ入力２１８、２１９、２２０、２２１のうちの排他的に１つ（常にちょうど１つ）と導通状態であることが分かる。
【００８４】
検索動作に先立って、ヒット線６２６をハイレベルにしておく。また検索データ入力２１８、２１９、２２０、２２１をローレベルにしておく。このときヒット線６２６にプルダウン動作は起こらない。
【００８５】
検索動作時、検索データ入力２１８、２１９、２２０、２２１にそれぞれ、定理１の証明で定義したX、 !X、 Y、 !Yを与える。ＮＭＯＳ６３７のゲート電位が２１８、２１９、２２０、２２１と導通状態になる条件式はそれぞれ
L !M, !L !M, L M, !L M
であるから、その結果NMOS６３７のゲート電位は
!X !L !M + !Y !L M + X L !M + Y L M
であり、ヒット線６２６のプルダウン条件は
!X !L !M + !Y !L M + X L !M + Y L M
になる。これは図2のヒット線226のプルダウン条件と同一であるので結果として、図1と同様に連想メモリが構成できることは、ここまでの説明から十分明らかである。
【００８６】
実施例４  次に第４の実施例について説明する。図７は図６のメモリセルを用いた連想メモリ、および連想結果に従いアクセスされるＲＡＭの方式を示す。
【００８７】
７０１はメモリセル６０１を用いた、連想メモリのうち最下位ビット、つまりビット(s)を除いた連想メモリである。７０２は最下位ビットの連想メモリである。７０３もまた最下位ビットの連想メモリである。７０５は検索データ処理論理であり、１０８Ａを用いれば実現可能である。
【００８８】
７０６は検索データ処理論理であるが、下位からの桁上がり信号cin[s]に相当する端子を0に固定している。そのためcin[s]の確定を待たずに検索結果（７０２の出力）を確定させることができる。７０７は検索データ処理論理であるが、下位からの桁上がり信号cin[s]の端子を1に固定している。そのため、（７０６の議論と同様に）cin[s]の確定を待たずに検索結果（７０２の出力）を確定させることができる。
【００８９】
７０４は２ポートメモリであり、ワード線を２組有する。その１つのポートを７０２の出力により、もう１つのポートを７０３の出力によりアクセスする。２ポートメモリ７０４の２組の出力データの一方をcin[s]信号７０９によって２入力セレクタ７０８で選択する。その選択ことにより、連想メモリおよび、それによりアクセスされるRAMの結果を得ることができる。
【００９０】
以上により、cin[s]信号７０９の確定を待たずにCAM７０１、７０２、７０３、２ポートRAM７０４のアクセスを実行することができ、高速な処理が可能となる。
【００９１】
図８は図７の連想メモリおよびメモリの１エントリ分を半導体での実現方式とともに説明する図である。８０１は連想メモリの１エントリである。１ビットのメモリセル６０１の集合からなる。ヒット線６２６の動作に着目する限りはプルダウントランジスタ６３７のみが重要なので、メモリセル６０１の中で６３７のみ記載されている。
【００９２】
８０２はＬＳＢ部分の連想メモリの１エントリであり、cin[s]=0に対応したメモリセル６０１(６３７のみが記載されている)とＡＮＤゲートからなる。ビット[n-1+s:1+s]のヒット条件とビット[s]のヒット条件のＡＮＤをとることによりビット[n-1+s:s]のヒット条件が得られる。またこの処理はcin[s]の確定を待たずに行える。８０３は８０２に対してcin[s]=0からcin[s]=1にのみ変更したものである。
【００９３】
８０４は2ポートメモリで、インバータ８１１、８１２、ＮＭＯＳ８１３、８１４、８１５、８１６、データ線８１７、８１８、８１９、８２０、ワード線８２１、８２２からなる。
【００９４】
図９は図１に示す連想メモリを用いたマイクロプロセッサＬＳＩチップ９００に内蔵された種々の回路ブロック図である。９０１はＣＰＵ（Central Processing Unit、中央処理ユニット）である。また９０１は整数ユニットとも称せられる。９０２はＦＰＵ（Floating Point Unit、浮動小数点ユニット）である。９０３はＣＰＵ９０１の内部に存在する命令アドレス加算器であり、９０３の加算結果を命令アクセスアドレスにする。９０４はＣＰＵ９０１の内部に存在するデータアドレス加算器である。
【００９５】
９０５は命令ＴＬＢ、９０６は命令キャッシュ、９０７はデータＴＬＢ、９０８はデータキャッシュである。命令ＴＬＢ９０５、命令キャッシュ９０６をアクセスするアドレスは９０３で生成されるが、互いに連動して動作する９０３，９０５，９０６の部分は図１で説明された高速な加算器および連想メモリが用いられ、遅延時間を削減している。
【００９６】
また、データＴＬＢ９０７、データキャッシュ９０８をアクセスするアドレスは９０４で生成されるが、これら互いに連動して動作する９０４、９０７、９０８の部分は同様に図１で説明された高速な加算器および連想メモリが用いられ、遅延時間を削減している。
【００９７】
９０９はバスインターフェース論理、９１０はマイクロプロセッサＬＳＩが内蔵する周辺論理の１つであるタイマユニットである。９１１はマイクロプロセッサＬＳＩが内蔵する周辺論理の１つであるシリアルインターフェースユニットである。９１２は周辺論理用のバスである。９１３は本ＬＳＩの外部導出用のピン（端子）である。
【００９８】
本発明をかかるマイクロプロセッサのような情報処理装置に適用することによって、前述したことから理解されるように特に、９０３、９０５、９０６の機能部分及び９０４、９０７、９０８の機能部分がチップ全体に占める占有面積を約２〜４％程度に抑えることができ、しかもそのマイクロプロセッサのような情報処理装置の処理スピードを改善することができるので、１枚のＳｉ半導体基板（チップ）の中に効率的にシステム全体を内蔵せしめることができる。
【００９９】
なお、図９の説明から明らかなように図１の連想メモリ以外に図５、図６、図７、図８の連想メモリ、また連想メモリを構成する部分回路を用いることも可能である。
【０１００】
なお、上記各実施例ではヒット線電位のプルダウンについて説明したが、必要に応じてプルアップしてもよいことは明らかであるので詳細な説明は省略する。
【０１０１】
【発明の効果】
加算結果でアクセスされる連想メモリにおいて、加算処理のキャリ伝播遅延を削減しつつ、かつ少ないトランジスタ数でメモリセルを構成できる。また、加算結果でアクセスされる連想メモリにおいて、加算処理のキャリ伝播遅延を削減しつつ、メモリのエントリ方向に沿った信号線配置領域の増大を小さく抑えることが可能である。
【０１０２】
更に、加算結果でアクセスされる連想メモリにおいて、従来知られている方法では検索対象より下位からのキャリ生成信号が確定した後でしかRAMアクセスを行うことができなかったが、本発明を用いることにより検索対象より下位からのキャリ生成信号が確定する以前にＲＡＭアクセスを行うことができる。
【図面の簡単な説明】
【図１】  本発明の実施例１にかかわる連想メモリの回路ブロック図である。
【図２】  実施例１でのメモリセルの回路図である。
【図３】  実施例１での検索データの生成論理部の回路図である。
【図４】  実施例１でのＬＳＢ部分のメモリセルの回路図である。
【図５】  本発明の実施例２にかかわるメモリセルの回路図である。
【図６】  本発明の実施例３にかかわるメモリセルの回路図である。
【図７】  本発明の実施例４にかかわる連想メモリおよび２ポートＲＡＭから成る回路ブロック図である。
【図８】  本発明の実施例４での１エントリ部分の半導体構成を説明する回路図である。
【図９】  本発明の連想メモリを用いたマイクロプロセッサＬＳＩチップに内蔵された回路ブロック図である。
【符号の説明】
１０１A：ｎビットの入力信号Ａ、１０１Ｂ：ｎビットの入力信号Ｂ、１０２：桁上がり信号、１０３：検索データ生成論理回路部、１０４Ａ、１０４Ｂ、１０４Ｃ：ヒット線、１０５：半導体メモリ部、１０６：連想メモリの１エントリ部、１０７：ＣＡＭアドレス信号、１０８Ａ、１０８Ｂ、１０８Ｃ：比較データ加工論理の１ビット分のブロック、１０９Ａ、１０９Ｂ、・・・、１０９Ｉ：メモリセル、１１０：ワードデコーダ部、１１１：データ入出力回路部、１１２Ａ、１１２Ｂ、１１２Ｃ：データ入出力信号線、１１３Ａ、１１３Ｂ、１１３Ｄ、１１３Ｅ、１１３Ｇ、１１３Ｈ：エントリのメモリセル間インターフェース信号群、１１４Ａ、１１４Ｂ、１１４Ｃ：ワード線、１１５Ａ、１１５Ｂ、１１５Ｃ：検索データ線、２０１、２０２：インバータ、２０３〜２１４：ＮＭＯＳＦＥＴ、２１５：ワード線、２１６、２１７：データ線、２１８〜２２１：検索入力信号線、２２２、２２３：隣接する左側メモリセルへメモリ出力を供給する線、２２４、２２５：隣接する右側メモリセルのメモリ出力を入力する線、２２６：ヒット線、３１３，３１４：隣接する左側のビットの検索データ生成論理への出力、３１５、３１６：隣接する右側のビットの検索データ生成論理からの入力、３１７：検索イネーブル信号、４３０、４３１：プリチャージ制御信号、４３２：検索結果出力線、４３６：ＬＳＢ部分のヒット線、５０１：メモリセル、５１８〜５２１：検索入力信号、５２６：ヒット線、６０１：メモリセル、６２６：ヒット線、７０１：半導体連想メモリ、７０２、７０３：ＬＳＢの連想メモリ、７０４：2 ポートＲＡＭ、７０５：検索データ生成論理回路ブロック、７０６、７０７：検索データ生成論理（ＬＳＢ）、７０８：セレクタ、７０９：桁上がり信号、８０１：連想メモリの１エントリ分、８０２、８０３：ＬＳＢの連想メモリの１エントリ分、８０４：2ポートRAMの１ビット分、９０１：ＣＰＵ、９０２：ＦＰＵ、９０３：命令アクセス加算器、９０４：データアクセス加算器、９０５：命令ＴＬＢ、９０６：命令キャッシュ、９０７：データＴＬＢ、９０８：データキャッシュ、９０９：バスインターフェース、９１０：タイマユニット、９１１：シリアルインターフェースユニット、９１２：周辺論理用のバス、９１３：ＬＳＩのピン（端子）。
【図１】
0004033609.tif 000006
【図２】
0004033609.tif 000007
【図３】
0004033609.tif 000008
【図４】
0004033609.tif 000009
【図５】
0004033609.tif 000010
【図６】
0004033609.tif 000011
【図７】
0004033609.tif 000012
【図８】
0004033609.tif 000013
【図９】
0004033609.tif 000014