JPH03219326A - データ比較回路 - Google Patents

データ比較回路

Info

Publication number
JPH03219326A
JPH03219326A JP2015385A JP1538590A JPH03219326A JP H03219326 A JPH03219326 A JP H03219326A JP 2015385 A JP2015385 A JP 2015385A JP 1538590 A JP1538590 A JP 1538590A JP H03219326 A JPH03219326 A JP H03219326A
Authority
JP
Japan
Prior art keywords
data
signal
circuit
comparison
bits
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.)
Pending
Application number
JP2015385A
Other languages
English (en)
Inventor
Hideki Ando
秀樹 安藤
Hirohisa Machida
町田　浩久
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Mitsubishi Electric Corp
Original Assignee
Mitsubishi Electric Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Mitsubishi Electric Corp filed Critical Mitsubishi Electric Corp
Priority to JP2015385A priority Critical patent/JPH03219326A/ja
Priority to US07/643,987 priority patent/US5130692A/en
Publication of JPH03219326A publication Critical patent/JPH03219326A/ja
Priority to US07/874,921 priority patent/US5386528A/en
Pending legal-status Critical Current

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
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/12—Replacement control
    • G06F12/121—Replacement control using replacement algorithms
    • G06F12/123—Replacement control using replacement algorithms with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/02—Comparing digital values
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/10—Address translation
    • G06F12/1027—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Memory System Of A Hierarchy Structure (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野コ この発明は、一般にデータ比較回路に関し、特に、複数
のビットからなる２つのデータをより高速に比較するデ
ータ比較回路に関する。
［従来の技術］ 一般に、コンピュータを利用した演算処理において、２
つのデータの比較が頻繁に行なわれる。
たとえば、多数のデータの並び換えが行なわれるソーテ
ィング処理は、従来から主にソフトウェアによって行な
われている。その一方、ハードウェアを利用して２つの
データの比較を高速に行なう回路も知られる。
第１７図は、特開昭６２−１１８４３４号公報に示され
た１ビツトのデータの記憶および比較を行なうことがで
きるセル回路１０の回路図である。
このセル回路１０は、データをストアするためのＳＲＡ
Ｍ部５０と、トランジスタ５６，７１．７２と、ＮＡＮ
Ｄゲート７３とを含む。ビット線対ＢＬ、ＢＬを介して
データＤ、Ｄが与えられ、ＳＲＡＭ部５０中にストアさ
れたデータＭ、　Ｍと与えられたデータＤ、Ｄとが比較
される。２つのデータが一致するとき、ＮＡＮＤゲート
７３が高レベルの信号を出力する。その結果、トランジ
スタ５６がオンする。他方、２つのデータがＭ＜Ｄのと
き、トランジスタ７１および７２がオンするので比較ラ
インＣＭＬが低レベルにもたらされる。
逆に、２つのデータがＭＡＤであるとき、比較ラインＣ
ＭＬの電位が保持される。
各々が複数のビットからなる２つのデータを比較するた
めには、第１８図に示すように比較ラインＣＭＬを介し
て複数のセル回路１０を接続する必要がある。トランジ
スタＴ、およびインバータＩＮＶは、比較結果の伝送速
度を高めるために設けられている。その理由は、セル回
路１０中の伝送のためのトランジスタ５６が受動素子で
あるので、比較結果の伝送が遅延されるからである。
［発明が解決しようとする課題］ 複数のセル回路１０が比較ラインＣＭＬを介して接続さ
れるとき、比較結果を伝送するためのトランジスタ５６
が第１９Ａ図に示すように連続的に接続される。その等
節回路は、第１９Ｂ図に示される。すなわち、トランジ
スタ５６の連続接続は、第１９Ｂ図に示すような抵抗成
分Ｒおよび容量成分Ｃからなる遅延回路を構成する。こ
のことは、第１８図に示した回路接続において比較結果
を示す信号が遅延されることが避けられないことを意味
する。比較結果を示す信号か最も遅延されるのは、最下
位桁（Ｌ　Ｓ　Ｂ）での比較結果によって２つのデータ
の比較結果が決定される場合において生じる。すなわち
、この場合ＬＳＢを構成するセル回路１０における比較
結果を示す信号が比較ラインＣＭＬを介して最上位桁（
ＭＳＢ）のセル回路に向かって伝送される。その結果、
２つのデータの比較結果が出力されるまでに長い時間を
要する。すなわち、第１８図に示した従来の比較回路が
低い動作速度を有することが指摘される。
この発明は、上記のような課題を解決するためになされ
たもので、データ比較回路において、複数ビットからな
る２つのデータをより高速に比較することを目的とする
。
［課題を解決するための手段］ この発明にかかるデータ比較回路は、第１のデータの下
方のビットと第２のデータの下方のビットとを比較する
第１の比較手段と、第１のデータの上方のビットと第２
のデータの上方のビットとを比較する第２の比較手段と
を含む。第２の比較手段は、第２のデータの上方のビッ
トをストアする記憶手段と、記憶手段中にストアされた
データビットと第１のデータの上方のビットとの一致を
検出する一致検出手段とを備える。データ比較回路は、
さらに、一致検出手段に応答して第１の比較手段からの
比較結果を選択的に出力するスイッチング手段を含む。
［作用］ この発明におけるデータ比較回路では、一致検出手段が
記憶手段中にストアされたデータビットと第１のデータ
の上方のビットとの一致を検出する。一致が検出された
とき、スイッチング手段か一致検出手段に応答して第１
の比較手段から出力された下方のビットの比較結果を出
力する。すなわち、下方のビットの比較結果を示す信号
が上方のビットを比較するための第２の比較手段を介し
て伝送されないので、下方のビットの比較結果がより速
く出力される。
［発明の実施例］ 第１図は、この発明の一実施例を示すデータ比較回路の
回路ブロック図である。このデータ比較回路は与えられ
た４ビツトのデータと既にストアされている４ビツトの
データとを比較する。第１図を参照して、このデータ比
較回路は、比較ラインＣＭＬを介して直列に接続された
４つのセル回路３１ないし３４を含む。各セル回路３１
ないし３４は、外部から与えられる１ビツトのデータ信
号り、Ｄを受けるように接続される。加えて、各セル回
路３１ないし３４は、ワード選択信号Ｗおよびクロック
信号Ｔ、Ｔにより制御される。各セル回路３１ないし３
４には比較されるべきデータのデータビットが予めスト
アされている。データバスＤＢを介して比較されるべき
もう一方のデータＤ、Ｄのデータビットが各セル３１な
いし３４にそれぞれ与えられる。たとえば、セル回路３
１は、与えられたデータのデータビットとストアされて
いるデータのデータビットとを比較する。２つのデータ
ビットが一致するとき、セル回路３１は高レベルの伝達
信号ＰＲＯを出力する。各セル回路３１から出力される
伝達信号ＰＲＯはＡＮＤゲート３０に与えられる。一方
、２つのデータ信号が一致しないとき、比較結果を示す
信号ＣＯが出力される。各セル回路３１ないし３４から
出力される信号ＣＯは、比較ラインＣＭＬを介して上方
のセル回路へ与えられる。セレクタ３５は、その−万人
力ａがセル回路３１からの信号ＣＯを受けるように接続
され、他方人力すがより下方のデータビットの比較結果
を示す信号ＣＭＩを受けるように接続される。
第】図に示したセル回路３］ないし３４により４つのデ
ータビットの一致が検出されたとき、ＡＮＤゲート３０
が高レベルの信号をセレクタ３５に与える。したがって
、セレクタ３５は下方のビットの比較結果を示す信号Ｃ
ＭＩを信号ＣＭＯとして出力する。他方、４つのデータ
ビットのうち少なくとも１つが一致しないとき、ＡＮＤ
ゲート３０が低レベルの信号をセレクタ３５に与える。
したがって、セレクタ３５は比較ラインＣＭＬ上の信号
を信号ＣＭＯとして出力する。
第２図は、第１図に示したセル回路の一例を示す回路図
である。第２図を参照して、このセル回路は、データビ
ットをストアするためのＳ　ＲＡＭ部５０と、２つのデ
ータビットの一致を検出するためのＥＸＯＲゲート５５
と、下方のビットの比較結果を伝達するためのＮＭＯＳ
トランジスタ５６と、比較ラインＣＭＬをプリチャージ
するためのＮＭＯＳトランジスタ５７と、２つのデータ
ビットの比較結果に応答して比較ラインＣＭＬの電位を
制御するためのＮＭＯＳトランジスタ５８５９とを含む
。ＳＲＡＭ部５０は、クロスカップルされたインバータ
５１．５２と、ＮＭＯ３）ランジスタ５３５４とを含む
。
動作において、ＳＲＡＭ部５０は、高レベルのワード選
択信号Ｗに応答してデータ信号り、Ｄによって規定され
る１ビツトのデータをストアする。
与えられたデータビットＤとストアされているデータビ
ットＭとが一致するとき、ＥＸＯＲゲート５５が高レベ
ルの伝達信号ＰＲＯを出力する。トランジスタ５６が信
号ＰＲＯに応答してオンするので、下方のビットの比較
結果を示す信号ＣＩが信号ＣＯとしてトランジスタ５６
を介して伝送される。２つのデータビットが一致しない
とき、トランジスタ５６がオフする。この場合、２つの
データビットの比較結果に応答してトランジスタ５８お
よび５９かオンまたはオフするので、比較ラインＣＭＬ
の電位か比較結果に応答して変化される。
第３図は、第１図に示したデータ比較回路か用いられた
ワード比較回路をかす回路ブロック図である。第３図を
参照して、このワード比較回路は、各々か第１図に示し
たデータ比較回路を備えた３つのブロック４１ないし４
３からなる。各ブロック４１ないし４３は、パスライン
ＢＵＳを介して４ビツトのデータ信号り、Ｄを受けるよ
うに接続される。また、各ブロック４１ないし４３はワ
ード選択信号Ｗおよびクロック信号Ｔ、Ｔにより制御さ
れる。各ブロック４１ないし４３における比較結果を示
す信号ＣＭＯはより上位のブロックに与えられる。
第４図は、第３図に示したワード比較回路が用いられた
比較器の全体を示す回路ブロック図である。第４図を参
照して、この比較器は、第３図に示したワード比較回路
を備えた多数のワード部１００を含む。ワード部１００
は、パスラインＢＵＳ、ＢＵＳを介して１２ビツトのデ
ータ信号ＤＤを受ける。各データバスＢＵＳ、ＢＵＳを
プリチャージするため、ＮＭＯＳトランジスタ６ユおよ
び６２がそれぞれ設けられる。各パスラインＢＵＳ、Ｂ
ＵＳにはセンスアンプ／ドライバ回路４００により増幅
された１２ビットのデータ信号が与えられる。デコーダ
３００は、アドレス信号ＡＤに応答してワード部１００
を選択するためのワ−ド選択信号Ｗｎを出力する。ワー
ド選択信号Ｗｎにより選択されたワード部１００が比較
結果を示す信号ＣＭＯ＜ｎ＞を出力する。
第５図は、第１図ないし第４図に示した回路の動作を説
明するためのタイミング図である。第５図を参照して、
期間ＰＩＯにおいて高レベルの信号ＴＯかトランジスタ
６１および６２に与えられ、パスラインＢＵＳ、ＢＵＳ
がプリチャージされる。
クロック信号Ｔ１およびワード選択信号Ｗが期間ｐＨに
おいて立上がる。ワード選択信号Ｗによって選択された
ワード部１００において、既にストアされている１２ビ
ツトのデータ信号Ｄｏｌｌ：Ｓにロードされる。他方、
第２図に示した比較ラインＣＭＬは、クロック信号ＴＩ
（すなわちＴ）に応答してプリチャージされる。プリチ
ャージが終了すると、期間Ｐ１２において各セル回路に
おける比較動作か開始される。その結果、比較結果を示
す信号ＣＭＯ＜ｎ＞が出力される。
上記のように、第１図に示したデータ比較回路において
、２つのデータが一致するとき他方のビットの比較結果
を示す信号かセル回路３１ないし３４を介することなく
上方ビットのためのブロックへ伝達されるので、第１９
Ｂ図に示したような遅延回路か構成されない。したがっ
て、２つのデータの比較結果を示す信号をより高速に得
ることかできる。
各第６Ａ図ないし第６Ｄ図は、第１図に示したデータ比
較回路に適用可能なセル回路の例を示す回路図である。
これらのセル回路は第２図に示したセル回路に代えて適
用可能であり、かつ、同様に動作する。
各第７Ａ図および第７Ｂ図も、第１図に示したデータ比
較回路に適用可能なセル回路の例を示す回路図である。
第７Ａ図および第７Ｂ図では、比較されるべきデータが
ラッチ回路９０中にストアされる。第７Ａ図を参照して
、ラッチ回路９０がクロック信号Ｔに応答してデータＤ
Ｉをラッチする。出力可能信号ＯＥか立上がると、ラッ
チ回路９０中にラッチされたデータが参照ラインＲＦＬ
に与えられる。他方、比較線ＣＭＬはプリチャージ信号
ＰＲに応答して既にプリチャージされている。したがっ
て、２つのデータビットの比較結果に応答してトランジ
スタ９３および９４が動作するので、比較結果を示す信
号ＣＯが出力される。
他方、第７Ｂ図に示したセル回路は、第７Ａ図に示した
回路と比較すると、比較線ＣＭＬをプリチャージする必
要がないことが指摘される。
第８図は、２つのデータの比較に要する時間を示すグラ
フである。第８図を参照して、縦軸が所要時間を示し、
横軸は比較されるべきデータのビット数を示す。曲線Ｐ
はたとえば第１図に示したような回路、すなわち本願発
明が適用される場合を示す。曲線Ｑは第１８図に示した
回路、すなわちインバータＩＮＶおよびトランジスタＴ
７が適用される場合を示す。曲線Ｒは単にセル回路か連
続的に接続される場合を示す。第８図かられかるように
、４以上のビット数を有するデータの比較のために本願
発明か適用されると、比較のために要する時間か従来の
回路と比較して大幅に減じられることが指摘される。
本願発明が適用されたＴｒａｎｓ　ｌａｔ　１ｏｎＬｏ
ｏｋａｓｉｄｅ　　Ｂｕｆｆｅｒ（以下「ＴＬＢＪとい
う）について以下に説明する。
一般に、コンピュータシステムにおけるアドレシングに
おいて、論理アドレス（または仮想アドレス）から物理
アドレスへの変換か行なわれる。
この変換は通常メインメモリ上にあるセグメントマツプ
表やページマツプ表などを参照する必要がある。このこ
とは、１つの命令をコンピュータが実行するためには少
なくともメインメモリに対して３回アクセスする必要が
あることを意味する。
コンピュータによる処理速度を高めるためには、このア
クセスの回数を減らす必要がある。メインメモリ上のマ
ツプ表を参照することなく論理アドレスを物理アドレス
に変換することのできるレジスタとして、ＴＬＢか知ら
れる。ＴＬＢを備えたマイクロプロセッサの例か、たと
えば、“Ａ３２−ｂｉｔ　　ＣＭＯＳ　　Ｍｉｃｒｏｐ
ｒｏｃｅｓｓｏｒ　　ｗｉｔｈ　　０ｎ−Ｃｈｉｐ　　
Ｃａｃｈｅａｎｄ　　ＴＬＢ”と題された論文（Ｉ　Ｅ
ＥＥＪＯＵＲＮＡＬ　　　ＯＦ　　　５ＯＬＩＤ−３Ｔ
ＡＴＥＣＩＲＣＵＩＴＳ、ＶＯＬ、　　５Ｃ−２２，Ｎ
ｏ。
５．１９８７年１０月）に見られる。従来からいくつか
の種類のＴＬＢか知られているが、以下では本願発明が
適用可能なフルアソシアティブ方式のためのＴＬＢにつ
いて説明する。
ます、以下の説明では、３２ビツトのアドレス信号によ
り指定可能な４ギガバイトの論理空間か仮定される。こ
の論理空間において、９ビツトのアドレス信号により指
定可能な５１２バイトのデータか１ページとして規定さ
れる。第９図かられかるように、論理アドレスは、ペー
ジアドレスと、オフセットアドレスとを含む。
第１０図においてＴＬＢの構成の概念が示される。フル
アソシアティブ方式に従うＴＬＢは、般に、論理ページ
アドレスをストアするためのＣＡＭ部７］と、物理ペー
ジアドレスをストアするためのＳＲＡＭ部７２とを含む
。各ＣＡＭ部７１とＳＲＡＭ部７２は、それぞれ３２エ
ントリのアドレス記憶場所を備える。動作において、Ｃ
ＡＭ部７１に論理ページアドレスか与えられたとき、与
えられた論理ページアドレスと同じアドレスがストアさ
れている格納場所すなわちワードが検出される。この一
致検出は「ヒツト」と呼ばれる。
ヒツトしたワードに対応するＳＲＡＭ部７２がら物理ペ
ージアドレスか出力される。したがって、ＣＡＭ部７１
において成るワードがヒツトするとき、論理ページアド
レスから物理ページアドレスへの変換か１マシンサイク
ルで終了させることができる。
他方、ＣＡＭ部７１において一致か検出されないとき、
すなわち論理ページアドレスがヒツトされないとき、セ
グメントマツプ表またはページマツプ表などが参照され
物理ページアドレスが得られる。得られた物理ページア
ドレスは以後の処理のためにＣＡＭ部７１およびＳＲＡ
Ｍ部７２中に登録される必要かある。この登録のために
は、既にこのＴＬＢ中に登録されている少なくとも１つ
のワードのデータを削除し、削除された記憶、場所に新
しいデータを書込む必要かある。削除されるべきワード
または記憶場所を決定するためのアルゴリズムの一つと
して、Ｌｅａｓｔ　　Ｒｅｃｅｎｔｌｙ　　Ｕｓｅｄ（
以下「ＬＲＵＪという）か知られる。ＬＲＵのアルゴリ
ズムを実現するためには、さらに各ワードについてカウ
ンタが設けられる必要がある。
第１１図は、ＬＲＵに従ってＴＬＢ中のデータか更新さ
れる場合を説明する概念図である。第１１図を参照して
、ＴＬＢ７０中の各エントリまたは各ワードごとにカウ
ンタが設けられており、カウンタ部７３が構成されてい
る。与えられた論理ページアドレスがＴＬＢ７０中の成
るエントリでヒツトしたとき、そのエントリのカウンタ
値よりも小さいカウンタ値を有するエントリのカウンタ
をインクリメントする。同時に、ヒツトしたエントリの
カウンタかリセットされる。与えられた論理ページアド
レスかＴＬＢ７０中のどのエントリともヒツトしない場
合（ミスヒツトの場合）、最も大きなカウンタ値を有す
るエントリのデータか削除され、そこにあたらしいデー
タが書込まれる。
第１１図ではカウント値１５を有するエントりの値が削
除され、そこに新しいデータか書込まれる場合が示され
る。
第１２図は、この発明か適用されるＴＬＢの一例を示す
ブロック図である。第１２図を参照して、このＴＬＢは
、論理ページアドレスをストアするためのＣＡＭワード
部１と、物理ページアドレスをストアするためのＳＲＡ
Ｍワード部４と、各ワードについてのカウント値を計数
するためのＬＲＵワード部７と、各ワードを指定するた
めのアドレスデコーダ２と、ＣＡＭワード部１に対して
論理ページアドレスを書込および読出するためのセンス
アンプ／ドライバ３と、ＳＲＡＭワード部４に対して物
理ページアドレスを書込および読出するためのセンスア
ンプ／ドライバ５とを含む。
第１３図は、第１２図に示したＬＲＵワード部７を示す
ブロック図である。第１３図を参照して、このＬＲＵワ
ード部は、各々か４ビツトのアドレスデータを処理する
ための３つのＬＲＵブロック８１ないし８３を含む。各
ＬＲＵブロック８１ないし８３は、クロック信号Ｔｏ、
ＴＩおよびＴ３に応答して動作する。インバータ１０は
クロック信号Ｔ１を受け、反転されたクロック信号Ｔ１
を各ＬＲＵブロック８１ないし８３に与える。ＡＮＤゲ
ート１２はクロック信号Ｔ３およびカウンタ出力可能化
信号ＣＥを受け、カウンタリセット信号ＣＲを各ブロッ
ク８１ないし８３に与える。ＬＲＵブロック８１はアド
レス信号の上位の４ビツトを処理し、ＬＲＵブロック８
２は中間の４ビツトを処理し、ＬＲＵブロック８３が下
位の４ビツトを処理する。比較結果を示す信号ＣＭＯか
ブロック８３からブロック８１に向けてブロック８２を
介して出力される。ＡＮＤゲート１１はクロック信号Ｔ
３およびインバータ９によって反転された信号ＣＭＯを
受け、カウンタアップ信号ＣＵを出力する。各ＬＲＵブ
ロック８１ないし８３は、参照データ用バスＲＦＢを介
して各４ビツトの参照データＲＦを受けるように接続さ
れる。各ＬＲＵブロック８１ないし８３は、桁上げ出力
信号ＣＹＯを出力する。
第１４図は、第１３図に示したＬＲＵブロック８１を示
す回路ブロック図である。第１４図を参照して、このＬ
ＲＵブロックは、各々がアドレス信号の各ビットについ
て比較するための４つのＬＲＵセル１３１ないし１３４
と、各セル１３１ないし１３４から比較結果を示す信号
ＣＭＰを受けるＡＮＤゲート１５と、ＡＮＤゲート１５
の出力信号に応答して動作するセレクタ１４とを含む。
ＡＮＤゲート１５が低レベルの信号を出力するとき、セ
レクタ１４は入力端子ａに与えられた信号を比較結果信
号ＣＭＯとして出力する。逆に、ＡＮＤゲート１５が高
レベルの信号を出力するとき、セレクタ１４は入力端子
すに与えられた信号、すなわちより下位の比較結果を示
す信号ＣＭＩを信号ＣＭＯとして出力する。すなわち、
セレクタ１４は、ＬＲＵセル１３１ないし１３４によっ
て比較結果が決定されるとき、ＬＲＵセル１３１から出
力される比較結果信号ＣＯを信号ＣＭＯとして出力する
。逆に、ＬＲＵセル１３１ないし１３４によって比較結
果が決定されないとき、セレクタ１４はより下位のビッ
トの比較結果を信号ＣＭＯとして出力する。各ＬＲＵセ
ル１３１ないし１３４は、比較されるべき参照データＲ
Ｆのうちの１ビツトをそれぞれ受けるように接続される
。
第１５図は、第１４図に示したＬＲＵセル１３１を示す
回路図である。第１５図を参照して、このＬＲＵセルは
、カウンタアップ信号ＣＵおよびカウンタリセット信号
ＣＲを受けるラッチ回路２３と、クロック信号Ｔ１を受
けるラッチ回路２４と、桁上げ入力信号ＣＹＩを受は桁
上げ出力信号ＣＹＯを出力するインクリメンタ２５と、
ＥＸＯＲゲート２６と、信号伝達のためのＮＭＯＳトラ
ンジスタ１９と、比較ラインＣＭＬをプリチャージする
ためのＮＭＯ５）ランジスタ１８とを含む。
第１６図は、第１５図に示した回路の動作を説明するた
めのタイミング図である。第１２図ないし第１６図を参
照して、次に動作について説明する。
各ＬＲＵセルは、ＬＲＵアルゴリズムに従ったカウント
値の記憶／更新と、ヒツトしたエントリにおけるカウン
ト値とそれ自身が有するカウント値との比較とを行なう
。１つのマシンサイクルは、第１６図に示すように４つ
の期間ＰＯないしＰ３を含む。第１６図に示したような
波形を有するクロック信号ＴＯないしＴ３が与えられる
。ラッチ回路２３および２４とインクリメンタ２５とに
よって１ビツトのカウンタか構成される。二〇カウンタ
は、カウントアツプ信号ＣＵに応答してカウントアツプ
し、カウンタリセット信号ＣＲに応答してリセットされ
る。桁上げ入力信号ＣＹＩは、より下位のビットからの
桁上げの要求を示す。桁上げ出力信号ＣＹＯは、より上
位のビットへの桁上げの要求を示す。
参照ラインＲＦＬは予めプリチャージされている。参照
ラインＲＦＬはトランジスタ１６および１７によって駆
動される。すなわち、高レベルのカウンタ出力可能化信
号ＣＥが与えられると、ラッチ回路２３にラッチされて
いた信号に応答して参照ラインＲＦＬの電位か変化する
。ＥＸＯＲゲ−ト２６は比較伝達信号ＣＭＰを出力する
。比較ラインＣＭＬは期間Ｐ１においてプリチャージさ
れ、その後は次の表１に従う。
表１ 第１６図を参照して、論理ページアドレスがこのＴＬＢ
に与えられ、成るＣＡＭワード部１においてヒツトした
とき、ヒツト信号ＨＬＩが出力される。ＬＲＵワード部
７はこのヒツト信号ＨＬＩを比較出力可能化信号ＣＥと
して受ける。参照ラインＣＦＬは期間ＰＯにおいて既に
プリチャージされており、期間Ｐ１において信号ＣＥか
立上がるとヒツトしたワードのラッチ回路２３の値か参
照ラインＲＦＬに与えられる。他方、各ＬＲＵセル１３
１ないし〕３４の比較ラインＣＭＬは期間Ｐ］において
プリチャージされており、期間Ｐ２において参照ライン
ＲＦＬ上の信号とそれ自身のラッチ回路２３中にラッチ
された信号の値との比較が行なわれる。この比較結果に
応答して、期間Ｐ３においてカウンタアップ信号ＣＵお
よびカウンタリセット信号ＣＲが出力され、必要なカウ
ンタのカウント値のアップおよびリセットが行なわれる
。
このように、ＴＬＢにおいて、第１４図に示したように
本願発明を適用することにより、第１図に示した実施例
において説明したのと同様な効果か得られる。すなわち
、第１４図に示した回路において、より下位のビットの
比較結果を示す信号ＣＭＩかＬＲＵセル１３１ないし１
３４を通らないので、２つのアドレスの比較結果をより
高速に得ることかできる。
［発明の効果］ 以上のように、この発明によれば、比較されるべき２つ
のデータの一致に応答して、より下位のビットの比較結
果を出力するスイッチング手段を設けたので、２つのデ
ータをより高速に比較することのできるデータ比較回路
が得られた。
【図面の簡単な説明】
第１図は、この発明の一実施例を示すデータ比較回路の
回路ブロック図である。第２図は、第１図に示したセル
回路の一例を示す回路図である。 第３図は、第１図に示したデータ比較回路が用いられた
ワード比較回路の回路ブロック図である。 第４図は、第３図に示したワード比較回路か用いられた
比較器の全体の回路ブロック図である。第５図は、第１
図ないし第４図に示した回路の動作を説明するためのタ
イミング図である。各第６八図ないし第６Ｄ図および各
第７Ａ図および第７Ｂ図は、それぞれ第１図に示したセ
ル回路の他の例を示す回路図である。第８図は、２つの
データの比較に要する時間を示すグラフである。第９図
は、論理アドレスの構成を示すフォーマット図である。 第１０図は、ＴＬＢの構成の概念図である。第１１図は
、ＬＲＵに従ってＴＬＢ中のデータが更新される場合を
説明する概念図である。第１２図は、この発明の一実施
例か適用されるＴＬＢの全体のブロック図である。第１
３図は、第１２図に示したＬＲＵワード部を示すブロッ
ク図である。第１４図は、第１３図に示したＬＲＵブロ
ックを示す回路ブロック図である。第１５図は、第１４
図に示したＬＲＵセルを示す回路図である。第１６図は
、第１５図に示した回路の動作を説明するためのタイミ
ング図である。第１７図は、１ビツトのデータの記憶お
よび比較を行なう従来のセル回路の回路図である。第１
８図は、インバータを介してセル回路がカスケードされ
た従来の回路図である。第１９Ａ図は、第１８図に示し
た回路における信号の遅延を説明するための回路図であ
る。第１９Ｂ図は、第１９Ａ図に示した回路の等価回路
図である。 図において、３０はＡＮＤゲート、３１ないし３４はセ
ル回路、３５はセレクタ、４１ないし４３はブロック、
１００はワード部である。

Claims (1)

  1. 【特許請求の範囲】 各々が複数のビットからなる第１のデータと第２のデー
    タとを比較するデータ比較回路であって、第１のデータ
    の下方のビットと第２のデータの下方のビットとを比較
    する第１の比較手段と、第１のデータの上方のビットと
    第２のデータの上方のビットとを比較する第２の比較手
    段とを含み、 前記第２の比較手段は、 第２のデータの上方のビットをストアする記憶手段と、 前記記憶手段中にストアされたデータビットと前記第１
    のデータの上方のビットとの一致を検出する一致検出手
    段とを備え、 前記第１の比較手段の出力に接続され、前記一致検出手
    段に応答して前記第１の比較手段からの比較結果を出力
    するスイッチング手段を含む、データ比較回路。
JP2015385A 1990-01-24 1990-01-24 データ比較回路 Pending JPH03219326A (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2015385A JPH03219326A (ja) 1990-01-24 1990-01-24 データ比較回路
US07/643,987 US5130692A (en) 1990-01-24 1991-01-22 Improved data comparator for comparing plural-bit data at higher speed
US07/874,921 US5386528A (en) 1990-01-24 1992-04-29 Address translator having a high speed data comparator

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2015385A JPH03219326A (ja) 1990-01-24 1990-01-24 データ比較回路

Publications (1)

Publication Number Publication Date
JPH03219326A true JPH03219326A (ja) 1991-09-26

Family

ID=11887280

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2015385A Pending JPH03219326A (ja) 1990-01-24 1990-01-24 データ比較回路

Country Status (2)

Country Link
US (2) US5130692A (ja)
JP (1) JPH03219326A (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5943152A (en) * 1996-02-23 1999-08-24 Ciena Corporation Laser wavelength control device
US8752923B2 (en) 2010-03-12 2014-06-17 Ricoh Company, Ltd. Image forming apparatus

Families Citing this family (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5400007A (en) * 1992-04-30 1995-03-21 Sgs-Thomson Microelectronics, Inc. Multiple level parallel magnitude comparator
US5319347A (en) * 1992-04-30 1994-06-07 Sgs-Thomson Microelectronics, Inc. Parallelized magnitude comparator for comparing a binary number to a fixed value
US5471188A (en) * 1994-10-07 1995-11-28 International Business Machines Corporation Fast comparator circuit
JPH08212789A (ja) * 1995-02-06 1996-08-20 Mitsubishi Electric Corp 連想メモリ回路及びｔｌｂ回路
US5907842A (en) * 1995-12-20 1999-05-25 Intel Corporation Method of sorting numbers to obtain maxima/minima values with ordering
US6036350A (en) * 1995-12-20 2000-03-14 Intel Corporation Method of sorting signed numbers and solving absolute differences using packed instructions
US5809528A (en) * 1996-12-24 1998-09-15 International Business Machines Corporation Method and circuit for a least recently used replacement mechanism and invalidated address handling in a fully associative many-way cache memory
JP3573978B2 (ja) * 1998-11-10 2004-10-06 矢崎総業株式会社 符号化方法、及び符号化装置
FR2792475B1 (fr) * 1999-04-16 2001-08-17 St Microelectronics Sa Comparateur d'une valeur numerique ayant des niveaux de tension cmos et d'une valeur numerique ayant des niveaux de tension ecl
US7089352B2 (en) * 2002-12-23 2006-08-08 Micron Technology, Inc. CAM modified to be used for statistic calculation in network switches and routers
US20060143375A1 (en) * 2004-12-29 2006-06-29 Bharadwaj Pudipeddi Content addressable memory with shared comparison logic
CN113348012B (zh) 2019-01-24 2024-09-27 阿尔特医疗公司 医用腔室系统、引入系统及套件

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4225849A (en) * 1978-05-01 1980-09-30 Fujitsu Limited N-Bit magnitude comparator of free design
JPS62118434A (ja) * 1985-11-19 1987-05-29 Matsushita Electric Ind Co Ltd 比較回路
US4813002A (en) * 1986-07-21 1989-03-14 Honeywell Bull Inc. High speed high density dynamic address translator
JPH0769868B2 (ja) * 1986-09-25 1995-07-31 松下電器産業株式会社 高速アドレス変換装置
US4959811A (en) * 1986-11-03 1990-09-25 Texas Instruments Incorporated Content addressable memory including comparison inhibit and shift register circuits
US4852059A (en) * 1988-01-11 1989-07-25 Texas Instruments Incorporated Content addressable memory
CA1300758C (en) * 1988-03-07 1992-05-12 Colin H. Cramm Mechanism for lock-up free cache operation with a remote address translation unit
US4928260A (en) * 1988-05-11 1990-05-22 Advanced Micro Devices, Inc. Content addressable memory array with priority encoder
US5067078A (en) * 1989-04-17 1991-11-19 Motorola, Inc. Cache which provides status information
US5072422A (en) * 1989-05-15 1991-12-10 E-Systems, Inc. Content-addressed memory system with word cells having select and match bits
US5109496A (en) * 1989-09-27 1992-04-28 International Business Machines Corporation Most recently used address translation system with least recently used (LRU) replacement
US5053991A (en) * 1989-10-06 1991-10-01 Sanders Associates, Inc. Content-addressable memory with soft-match capability

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5943152A (en) * 1996-02-23 1999-08-24 Ciena Corporation Laser wavelength control device
US8752923B2 (en) 2010-03-12 2014-06-17 Ricoh Company, Ltd. Image forming apparatus
US8926076B2 (en) 2010-03-12 2015-01-06 Ricoh Company, Ltd. Image forming apparatus

Also Published As

Publication number Publication date
US5130692A (en) 1992-07-14
US5386528A (en) 1995-01-31

Similar Documents

Publication Publication Date Title
US5752260A (en) High-speed, multiple-port, interleaved cache with arbitration of multiple access addresses
US4724518A (en) Odd/even storage in cache memory
JP3657622B2 (ja) エントリ当たり可変ページ寸法の変換ルックアサイドバッファ
US5517441A (en) Content addressable memory circuitry and method of operation
US5319763A (en) Data processor with concurrent static and dynamic masking of operand information and method therefor
CN111949571B (zh) 存储器阵列页面表格寻选
US6356990B1 (en) Set-associative cache memory having a built-in set prediction array
US4602368A (en) Dual validity bit arrays
US5471189A (en) Comparator circuitry and method of operation
JPH03219326A (ja) データ比較回路
US6415374B1 (en) System and method for supporting sequential burst counts in double data rate (DDR) synchronous dynamic random access memories (SDRAM)
US5802567A (en) Mechanism for managing offset and aliasing conditions within a content-addressable memory-based cache memory
US5845317A (en) Multi-way cache expansion circuit architecture
EP0717360A2 (en) Processing system for performing address translations and method of operation
US6834024B2 (en) Reduced size multi-port register cell
US5854943A (en) Speed efficient cache output selector circuitry based on tag compare and data organization
US5584003A (en) Control systems having an address conversion device for controlling a cache memory and a cache tag memory
JPH0863975A (ja) スタティックｒａｍおよびこのスタティックｒａｍを有する処理装置
CN110580231B (zh) 处理电路、缓冲器、存储器及处理器
JPH027141A (ja) キャッシュメモリシステム
JP3559631B2 (ja) 半導体メモリ及びデータ処理装置
JPH0675856A (ja) キャッシュメモリシステム
JP2656538B2 (ja) アドレス変換装置
JPH0772879B2 (ja) キヤツシユメモリ装置
JPH06149679A (ja) キャッシュメモリ装置