(57)【特許請求の範囲】
【請求項１】
アドレス合計比較(A+B=K)演算のための方法であって、AおよびBが、所与のアドレス入力信号であり、Kが、複数のメモリセルに格納された以前の値であり、
前記複数のメモリセルの各メモリセル中で、単一論理ゲート回路出力およびその反転を、前記メモリセルのアップデートに応答して生成するステップであって、各単一論理ゲート回路が、第1の入力として、関連するメモリセル出力を、第2の入力として、次に低い有効ビット隣接メモリセル出力を有するステップと、
前記メモリセルの各々において、各メモリセルに関連付けられた、前記A+B=K演算の一部分を、部分的ルックアップ比較回路内で生成するステップであって、前記対応するアドレス入力信号AおよびBが、読込みルックアップ比較演算中に、前記関連するメモリセル出力、ならびに前記生成された単一論理ゲート回路出力およびその反転と結合されるステップとを含む方法。
【請求項２】
各メモリセルに関連付けられた前記A+B=K演算の前記一部分が、3層のトランジスタ内で生成される、請求項1に記載の方法。
【請求項３】
前記トランジスタが、Nチャネル金属酸化膜半導体電界効果トランジスタ(NFET)である、請求項2に記載の方法。
【請求項４】
前記アドレス合計比較(A+B=K)演算が連想メモリ(CAM)中で使われる、請求項1に記載の方法。
【請求項５】
前記CAMが変換索引バッファ(TLB)中で使われる、請求項4に記載の方法。
【請求項６】
前記単一論理ゲート回路が、
第iのメモリセル(Mi)および第i-1のメモリセル(Mi-1)を入力として有し、出力信号Si=(!Mi&!Mi-1)|(Mi&Mi-1)を生じる排他的NOR回路を備える、請求項1に記載の方法。
【請求項７】
A+Bが、前記格納されたK個の値の1つと等しいとき、各メモリセル中でヒット指示を生成するステップをさらに含む、請求項1に記載の方法。
【請求項８】
A+Bが、前記格納されたK個の値の1つと等しくないとき、連想メモリ中のタグアレイにA+Bを書き込むステップをさらに含む、請求項1に記載の方法。
【請求項９】
前記メモリセルの各々において、前記A+B=K演算の一部分を生成する前記ステップが、
A+BがKと等しくないと判定すると、第1の極小項回路内でA+B=Kの第1の部分を計算して、ミス指示を生成するステップと、
A+BがKと等しくないと判定すると、第2の極小項回路内でA+B=Kの第2の部分を計算して、ミス指示を生成するステップとを含む、請求項1に記載の方法。
【請求項１０】
前記第2の極小項の結果との論理ORがとられた、前記第1の極小項回路の結果が、完全なA+B=K演算を含む、請求項9に記載の方法。
【請求項１１】
アドレス合計比較(A+B=K)演算のための装置であって、AおよびBが、所与のアドレス入力信号であり、Kが、メモリセルに格納された以前の値であり、
第1の入力として、関連するメモリセル出力を、第2の入力として、次に低い有効ビット隣接メモリセル出力を有し、前記メモリセルのアップデートに応答して出力信号Sおよびその論理否定信号!Sを生成する、各メモリセルに含まれる単一論理ゲート回路と、
前記メモリセルの各々において、ルックアップ比較演算用に、各メモリセルに関連付けられた前記A+B=K演算の一部分を生成するアドレス合計比較回路であって、前記比較演算中、前記対応するアドレス入力信号AおよびBが、前記関連するメモリセル出力ならびに前記S信号および!S信号と結合可能にされるアドレス合計比較回路とを備える装置。
【請求項１２】
出力信号Pi=(Ai&!Bi)|(!Ai&Bi)を生じるPi回路と、
前記Pi出力信号の論理否定を生じる!Pi回路と、
出力信号Gi=Ai&Biを生じるGi回路と、
出力信号Zi=!Ai&!Biを生じるZi回路とを備え、
&が論理的AND関数であり、|が論理的OR関数であり、!が論理的否定関数である
請求項11に記載の装置。
【請求項１３】
A+BがKと等しくないと判定すると、不一致を示す、!Pi&[(Gi-1&!Mi)|(Pi-1&Si)|(Zi-1&Mi)]に従って動作する第1の極小項回路をさらに備える、請求項12に記載の装置。
【請求項１４】
A+BがKと等しくないと判定すると、不一致を示す、Pi&[(Gi-1&Mi)|(Pi-1&!Si)|(Zi-1&!Mi)]に従って動作する第2の極小項回路をさらに備える、請求項12に記載の装置。
【請求項１５】
A+BがKと等しくないと判定すると、不一致を示す、Cin&[(!PLSB&!MLSB)|(PLSB&MLSB)]に従って動作する第1の最下位ビット(LSB)極小項回路をさらに備える、請求項12に記載の装置。
【請求項１６】
A+BがKと等しくないと判定すると、不一致を示す、!Cin&[(PLSB&!MLSB)|(!PLSB&MLSB)]に従って動作する第2の最下位ビット(LSB)極小項回路をさらに備える、請求項12に記載の装置。
【請求項１７】
アドレス合計比較(A+B=K)演算のための方法であって、AおよびBが、所与のアドレス入力信号であり、Kが、複数のメモリセルに格納された以前の値であり、
2つの隣接メモリビット(Mi、Mi-1)を結合して、メモリビット(Mi、Mi-1)の排他的NORとしての出力信号Siおよびその論理否定信号!Siを生成するステップと、
2つの隣接ビット(Ai、Ai-1、Bi、Bi-1)を、ルックアップ比較演算のためにメモリビットMi、!Miおよび出力Si、!Siと結合して、不一致を検出するステップであって、!が論理的否定関数であるステップとを含む方法。
【請求項１８】
出力信号Pi=(Ai&!Bi)|(!Ai&Bi)を生じるステップと、
前記Pi出力信号の論理否定を生じるステップと、
出力信号Gi=Ai&Biを生じるステップと、
出力信号Zi=!Ai&!Biを生じるステップとを含み、
&が論理的AND関数であり、|が論理的OR関数であり、!が論理的否定関数である
請求項17に記載の方法。
【請求項１９】
A+BがKと等しくないと判定すると、不一致を示す第1の極小項回路を、!Pi&[(Gi-1&!Mi)|(Pi-1&Si)|(Zi-1&Mi)]に従って操作するステップをさらに含む、請求項18に記載の方法。
【請求項２０】
A+BがKと等しくないと判定すると、不一致を示す第2の極小項回路を、Pi&[(Gi-1&Mi)|(Pi-1&!Si)|(Zi-1&!Mi)]に従って操作するステップをさらに含む、請求項18に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は概して、連想メモリを使う、仮想アドレスから物理アドレスへの変換の分野に関し、より詳細には、変換索引バッファ(TLB)中で使用するためのアドレス比較関数の合計の実施に関する。
【背景技術】
【０００２】
セルフォン、ラップトップコンピュータ、個人情報端末(PDA)などのような、多くの可搬型製品が、通信およびマルチメディアプログラムなどのプログラムを実行する処理システムを使用している。このような製品用の処理システムは、複数のプロセッサと、プログラムおよびデータを格納する仮想メモリハードウェアおよび技法を使う複合メモリシステムと、コントローラと、通信インターフェースなどの周辺デバイスと、たとえば単一チップ上に構成された固定関数論理ブロックとを含み得る。同時に、可搬型製品は、バッテリの形の限られたエネルギー源しかもっておらず、それらのバッテリは、高性能演算をサポートするよう処理システムからしばしば求められる。バッテリ寿命を増大させるために、こうした演算を可能な限り効率的に実施することが所望される。全体的エネルギー消費を削減するように効率的に設計された、多くのパーソナルコンピュータも開発中である。
【０００３】
仮想メモリは、プログラム開発および使用のための非常に大きい「仮想」メモリ空間を提示するとともに、物理容量がより少ない複合メモリシステム内の仮想メモリ空間の管理を可能にする技法である。複合メモリシステムは従来、キャッシュメモリの容量および性能に基づいて階層状に編成され、性能が最も高く、容量が最も低いキャッシュが、プロセッサの最も近くに置かれる。たとえば、レベル1命令キャッシュおよびレベル1データキャッシュが一般的に、プロセッサに直接結合されることになる。レベル2ユニファイドキャッシュは、レベル1(L1)命令およびデータキャッシュに接続される。さらに、システムメモリは、レベル2(L2)ユニファイドキャッシュに接続される。レベル1命令キャッシュは通常、プロセッサ速度で動作し、レベル2ユニファイドキャッシュは、レベル1キャッシュより遅く動作するが、アクセス時間はシステムメモリより速い。さらに、仮想メモリキャッシュサブシステムは、命令TLB(ITLB)中の命令と、データTLB(DTLB)中のデータの両方に対して仮想/物理メモリアドレスの高速変換を行うための変換索引バッファ(TLB)を含み得る。キャッシュおよびTLBは一般的に、連想メモリ(CAM)を使用して、たとえば、変換プロセスにおいて使われるアドレスまたはアドレスの一部分を格納する。TLBに対して、CAMは、予め変換された仮想ページ番号を格納することができる。変換用に提示される仮想ページ番号により、予め格納されたアドレスタグすべてと並列して、TLB CAMアドレスタグ比較演算が起こる。マッチが検出されたとき、TLBの出力は、提示された仮想ページ番号に対応する物理ページ番号である。物理ページ番号は次いで、仮想アドレスからのページオフセットと連結され、変換されて、変換物理アドレスが生成され、このアドレスは次いで、メモリ階層中でキャッシュをアドレス指定するのに使うことができる。
【０００４】
TLB中で、たとえば、TLBに格納された値にアクセスするために、CAMは一般的に、ベースプラスオフセット算出によって生成されたような有効アドレスを必要とし、このアドレスは、CAMに格納されたアドレスタグと比較される。この演算は一般的に、A+B=K演算と記述され、A+Bは仮想アドレスであり、Kは、アドレスタグに予め格納された仮想アドレスまたはその部分である。そのようなA+B=K演算は、命令およびデータキャッシュならびに命令およびデータTLB中で使うことができる。一手法では、A+B値を生成するための加算器が使用され、次いで、A+B値を、CAMエントリの各々と比較するための比較器がCAM中で提供される。ただし、この手法は、加算器内の桁上げ生成パスに依存することによって遅くなる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Jordi CortadellaおよびJose M. Llaberia、「Evaluation of A+B=K Condition Without Carry Propagation」、IEEE Transactions On Computers、 Vo. 41、 No. 11、1992年11月
【発明の概要】
【課題を解決するための手段】
【０００６】
いくつかの態様の中でも、本開示は、アドレス合計比較関数のためにより効率的な方法および装置を提供することにより、プロセッサシステムにおいて性能を向上し、電力要件を削減することができると認識している。そのような目的、ならびにそれ以外のために、本発明の実施形態は、アドレス合計比較(A+B=K)演算のための方法に対処し、この演算において、AおよびBは、所与のアドレス入力信号であり、Kは、複数のメモリセルに格納された以前の値である。複数のメモリセルの各メモリセル中で、単一論理ゲート回路出力およびその反転が、メモリセルのアップデートに応答して生成され、各単一論理ゲート回路は、第1の入力として、関連するメモリセル出力を、第2の入力として、次に低い有効ビット隣接メモリセル出力を有する。メモリセルの各々において、各メモリセルに関連付けられたA+B=K演算の一部分が、部分的ルックアップ比較回路内で生成され、対応するアドレス入力信号AおよびBは、読込みルックアップ比較演算中に、関連するメモリセル出力、ならびに生成された単一論理ゲート回路出力およびその反転と結合される。
【０００７】
別の実施形態は、アドレス合計比較(A+B=K)演算のための装置に対処し、この演算において、AおよびBは、所与のアドレス入力信号であり、Kは、メモリセルに格納された以前の値である。各メモリセルは、第1の入力として、関連するメモリセル出力を、第2の入力として、次に低い有効ビット隣接メモリセル出力を有するとともに、メモリセルのアップデートに応答して出力信号Sおよびその論理否定信号!Sを生成する単一論理ゲート回路を含む。メモリセルの各々において、アドレス合計比較回路が、ルックアップ比較演算用に、各メモリセルに関連付けられたA+B=K演算の一部分を生成し、比較演算中、対応するアドレス入力信号AおよびBは、関連するメモリセル出力ならびにS信号および!S信号と結合可能にされる。
【０００８】
別の実施形態は、アドレス合計比較(A+B=K)演算のための方法に対処し、この演算において、AおよびBは、所与のアドレス入力信号であり、Kは、複数のメモリセルに格納された以前の値である。2つの隣接メモリビット(Mi、Mi-1)が結合されて、メモリビット(Mi、Mi-1)の排他的NORとしての出力信号Siおよびその論理否定信号!Siが生成される。2つの隣接ビット(Ai、Ai-1、Bi、Bi-1)が、ルックアップ比較演算のためにメモリビットMi、!Miおよび出力Si、!Siと結合されて、不一致が検出され、ここで!は論理的否定関数である。
【０００９】
本発明の他の実施形態が、本発明の様々な実施形態が例として示され記載されている以下の詳細な説明から、当業者には容易に明らかになることが理解されよう。了解されるように、本発明は、他の実施形態および様々な実施形態が可能であり、そのいくつかの詳細は、本発明の精神および範囲からすべて逸脱することなく、他の様々な点において修正が可能である。したがって、図面および詳細な説明は、制限ではなく、本質的に例示と見なされるべきである。
【００１０】
本発明の様々な態様を、限定ではなく例として、添付の図面に示す。
【図面の簡単な説明】
【００１１】
【図１】ワイヤレス通信システムを示す図である。
【図２】効率的なA+B=K実装形態を有する連想メモリで構成されたキャッシュを有する例示的なプロセッサシステムを示す図である。
【図３】変換索引バッファ(TLB)内で使用するための例示的なA+B=K連想メモリ(CAM)回路を示す図である。
【図４】図3に示すA+B=K CAM回路の例示的な第j行タグメモリを示す図である。
【図５Ａ】図3に示すA+B=K CAM回路での使用に適したアドレス合計比較(SAC)信号論理回路を示す図である。
【図５Ｂ】図3に示すA+B=K CAM回路での使用に適したアドレス合計比較(SAC)信号論理回路を示す図である。
【図５Ｃ】図3に示すA+B=K CAM回路での使用に適したアドレス合計比較(SAC)信号論理回路を示す図である。
【図５Ｄ】図3に示すA+B=K CAM回路での使用に適したアドレス合計比較(SAC)信号論理回路を示す図である。
【図５Ｅ】単一メモリセルを示す図である。
【図６Ａ】メモリセル入力値に依存する出力Sおよび!Sを有するS信号回路を示す図である。
【図６Ｂ】図4のメモリセルとともに使用するための新規SAC回路を示す図である。
【図６Ｃ】図4の最下位ビット(LSB)メモリセルとともに使用するための終端SAC回路を示す図である。
【図７】A+B=K関数を、メモリセルビットに依存する第1の論理関数セットと、アドレス入力信号に依存する第2の論理関数セットとに分離することによって、レイテンシが低いA+B=K関数を生成するための比較プロセスを示す図である。
【発明を実施するための形態】
【００１２】
添付の図面に関する下記の詳細な説明は、本発明の様々な例示的実施形態の説明として意図されており、本発明が実施され得る最良の実施形態を表すように意図されているわけではない。詳細な説明は、本発明の完全な理解をもたらす目的で、具体的な詳細を含んでいる。しかし、本発明がこれらの具体的な詳細なしに実行され得ることが、当業者には明らかであろう。場合によっては、本発明のコンセプトを曖昧にするのを回避する目的で、周知の構造および構成要素がブロック図の形式で示されている。
【００１３】
図1は、本発明の実施形態が有利に利用され得る例示的なワイヤレス通信システム100を示す。説明のために、図1は、3つの遠隔ユニット120、130、150および2つの基地局140を示す。一般的なワイヤレス通信システムは、これより多くの遠隔ユニットおよび基地局を有し得ることが理解されよう。構成要素125A、125C、125B、125Dでそれぞれ表されるハードウェア構成要素、ソフトウェア構成要素、またはその両方を含む遠隔ユニット120、130、150、および基地局140は、さらに後で論じるように、本発明を実施するように適合されている。図1は、基地局140から遠隔ユニット120、130、150への順方向リンク信号180および遠隔ユニット120、130、150から基地局140への逆方向リンク信号190を示している。
【００１４】
図1では、ワイヤレスローカルループシステムにおいて、遠隔ユニット120は移動電話として示され、遠隔ユニット130は可搬型コンピュータとして示され、遠隔ユニット150は定位置遠隔ユニットとして示されている。例として、遠隔ユニットは代替的には、セルフォン、ページャ、ウォーキートーキー、ハンドヘルド個人通信システム(PCS)ユニット、個人情報端末などの可搬型データユニット、またはメータ読取り機器などの定位置データユニットでもよい。図1は、本開示の教示に従った遠隔ユニットを示すが、本開示は、これらの例示的な示されたユニットには限定されない。本発明の実施形態は、本明細書において言及するA+B=K計算を必要とする、キャッシュ、変換索引バッファ(TLB)、および固定関数デバイスなど、どのデバイスにおいても適切に利用することができる。
【００１５】
図2は、後でより詳しく説明するが、図1の構成要素125A、125C、125B、125D内で適切に利用され得る効率的A+B=K実装形態を使う連想メモリ(CAM)で構成されたキャッシュおよびTLBを有する例示的なプロセッサシステム200を示す。プロセッサシステム200は、制御論理214に従って命令実行パイプライン212中の命令を実行するプロセッサ210を含む。パイプライン212は、パイプ段階状に編成される、様々なレジスタまたはラッチ216、および1つまたは複数の算術論理ユニット(ALU)218を含む。汎用レジスタ(GPR)ファイル220は、命令実行パイプライン212が使用するための登録値を提供する。パイプライン212は、命令変換索引バッファ(ITLB)224によって管理されるメモリアドレス指定および許可を用いて、命令キャッシュ(Icache)222から命令をフェッチする。データ変換索引バッファ(DTLB)228によって管理されるメモリアドレス指定および許可を用いて、データキャッシュ(Dcache)226からデータがアクセスされる。Icache222および/またはDcache226中でのミスにより、メモリインターフェース232の制御下で、メインメモリ230がアクセスされる。プロセッサ210は、ハードディスクコントローラ、ユニバーサルシリアルバス(USB)コントローラ、対話型表示デバイス、コントローラを送受信機に結合する無線デバイス、メモリコントローラ、別のバス相互接続デバイスを相互接続するブリッジデバイスなどのような、様々な周辺デバイス236へのアクセスを制御する入力/出力(I/O)インターフェース234も含み得る。プロセッサ210の多数の変形が可能であることが当業者には理解されよう。たとえば、メモリ230は、レベル2キャッシュ、レベル3キャッシュなどのメモリデバイス階層、バルクメモリ、TLB階層などからなり得る。プロセッサシステム200は概して、命令およびデータ変換索引バッファ(ITLB224およびDTLB228)を使って、仮想/物理アドレス変換をサポートする。さらに、プロセッサ210など、1つまたは複数のプロセッサが、処理システム200に含まれてよい。ある特定のアプリケーションに必要とされるプロセッサ、周辺デバイス、およびメモリデバイスの実際の数は、処理要件および設計制約に応じて変わり得る。プロセッサシステム200は、特定用途向け集積回路(ASIC)技術、フィールドプログラマブルゲートアレイ(FPGA)技術、または他のプログラマブル論理、個別ゲートもしくはトランジスタ論理、または意図されるアプリケーションに適した他のどの利用可能技術を使って実装されてもよい。
【００１６】
プロセッサ210は、たとえば、命令キャッシュを通して利用可能であり得るように、プロセッサとローカルに直接関連付けられた、または周辺デバイスメモリインターフェースを通してアクセス可能なコンピュータ可読記憶媒体に格納されたプログラムから命令を実行するように構成され得る。様々なメモリは、ランダムアクセスメモリ(RAM)、動的ランダムアクセスメモリ(DRAM)、同期動的ランダムアクセスメモリ(SDRAM)、フラッシュメモリ、読出し専用メモリ(ROM)、プログラマブル読出し専用メモリ(PROM)、消去可能なプログラマブル読出し専用メモリ(EPROM)、電気消去可能プログラマブル読出し専用メモリ(EEPROM)、コンパクトディスク(CD)、デジタルビデオディスク(DVD)、他のタイプの取外し可能ディスク、または他のどの適切な記憶媒体も含み得る。
【００１７】
プロセッサ210は、処理システム200内の様々なメモリにある命令およびデータにアクセスするための仮想アドレス指定技法を使用することができる。仮想アドレスは概して、上位部分および下位部分に分けられる。上位部分は、物理ページ番号に変換されるべき仮想ページ番号を表す。下位部分は、ページへのオフセットを表し、下位部分が変換されないように、仮想アドレスと物理アドレスとの間で同じである。異なるシステムでは、ページサイズは変わる可能性があり、8Kバイト、4Kバイト、または2Kバイトのページを有するシステムがあることは珍しくないことを認識されたい。ページサイズ選択が影響を及ぼすものの1つは、変換されるべき仮想アドレス区画の上位部分中のビット数である。たとえば、4Kバイトのページを有する32ビットの仮想アドレスをもつシステムにおいて、仮想アドレスは、上位20ビット部分、すなわちビット[31:12]と、下位12ビット部分、すなわちビット[11:0]とに分けられることになる。上位20ビット部分は、物理ページ番号に変換されるべき仮想ページ番号を表す。下位12ビット部分は、ページへの4Kバイトのオフセットを表し、変換されない。
【００１８】
仮想アドレスは、ベースアドレスにオフセットを加える算出、索引付け、または加算もしくは数学演算を必要とする他のアドレス生成関数によって形成することができる。たとえば、最初にベースアドレスにオフセットを加算し、その後に別個のCAM比較演算を行うことによって仮想アドレスを形成するのではなく、アドレス合計比較(SAC)関数とも呼ばれるA+B=K関数がCAMに結合され得る。この方法を用いる手法が、参照により全体が本明細書に組み込まれているJordi CortadellaおよびJose M. Llaberiaによる論文「Evaluation of A+B=K Condition Without Carry Propagation」、IEEE Transactions On Computers、Vo. 41、No. 11、1992年11月に記載されている。上記のものなど、SAC関数の一般的実装形態に伴う問題は、関数を生成するのに最悪のケースのタイミングパスに対して実装形態が与える影響である。
【００１９】
現在の手法の一態様に関連して記載した通り、CAM格納メモリ値に対する論理演算に関連付けられた、新規SAC回路部分が、CAM比較読出し動作に先立って評価され、そうすることによって、SAC関数全体を解くためのレイテンシを削減する。たとえば、このような論理演算は、CAMメモリセルのアップデート中に評価され得る。新規SAC回路は、加算および比較演算を論理結合して、A+B=K演算を実行するための資源およびレイテンシを削減する。以下の説明において使われる論理演算は、加算用の「+」、論理的AND関数用の「&」、論理的否定関数用の「!」、および論理的OR関数用の「|」である。新規SAC回路は、2つの隣接ビット(Ai、Ai-1、Bi、Bi-1)を、対応するメモリビット(Mi、Mi-1)と論理結合する。入力ビットAiおよびBiの3つの論理結合Pi、Gi、およびZiが検査されるが、ここで、以下のようになる。
式1
Pi=(Ai&!Bi)|(!Ai&Bi)  ここで、{Ai,Bi}={1,0}または{0,1}のとき、Pi=1である。
式2
Gi=Ai&Bi  ここで、{Ai,Bi}={1,1}のとき、Gi=1である。
式3
Zi=!Ai&!Bi  ここで、{Ai,Bi}={0,0}のとき、Zi=1である。
【００２０】
P、G、およびZの2つの隣接値、すなわち{Pi,Gi,Zi}および{Pi-1,Gi-1,Zi-1}は、結合されると、以下のテーブルに列挙する9つの結合を生じ、ここから、下でより詳しく説明する1組のミスマッチ式を生成することができる。
【００２１】
【表１】
0005389280.tif 000002
【００２２】
こうしたミスマッチ式は、式4に示すように、2つの隣接ビットと、キャリーインCi-1との合計に基づく。
式4
Ai Ai-1+Bi Bi-1+Ci-1=Ri Ri-1
Gi=1およびGi-1=1であるGi Gi-1結合に対して、式4は、Ci-1の2つの可能状態{0,1}に関して評価され得る。Gi=1であるので、{Ai,Bi}={1,1}であり、Gi-1=1であるので、{Ai-1,Bi-1}={1,1}である。式4の評価により、キャリーイン値に依存して、Ri Ri-1という2つの結果を生成する以下の2つの状況が生じる。
【００２３】
【表２】
0005389280.tif 000003
【００２４】
A+B=KというSAC式において、結果Ri Ri-1は、メモリ値Mi Mi-1と比較される。第iのビットに関して比較すると、結果値Riは、キャリーイン値に依存せず、常に「1」である。したがって、Gi Gi-1結合の場合、Mi=0であるときに不一致が起こる。Gi Gi-1結合に関するミスマッチ式は、式5によって与えられる。
式5
mismatch-Gi Gi-1=Gi&Gi-1&!Mi
【００２５】
以下の1組のテーブルおよびそれに対応するミスマッチ式を、次のように列挙する。
【００２６】
【表３】
0005389280.tif 000004
【００２７】
式6
mismatch-Gi Pi-1=(Gi&Pi-1&Mi&Mi-1)|(Gi&Pi-1&!Mi&!Mi-1)
【００２８】
【表４】
0005389280.tif 000005
【００２９】
式7
mismatch-Gi Zi-1=Gi&Zi-1&Mi
【００３０】
【表５】
0005389280.tif 000006
【００３１】
式8
mismatch-Pi Gi-1=Pi&Gi-1&Mi
【００３２】
【表６】
0005389280.tif 000007
【００３３】
式9
mismatch-Pi Pi-1=(Pi&Pi-1&Mi&!Mi-1)|(Pi&Pi-1&!Mi&Mi-1)
【００３４】
【表７】
0005389280.tif 000008
【００３５】
式10
mismatch-Pi Zi-1=Pi&Zi-1&!Mi
【００３６】
【表８】
0005389280.tif 000009
【００３７】
式11
mismatch-Zi Gi-1=Zi&Gi-1&!Mi
【００３８】
【表９】
0005389280.tif 000010
【００３９】
式12
mismatch-Zi Pi-1=(Zi&Pi-1&Mi&Mi-1)|(Zi&Pi-1&!Mi&!Mi-1)
【００４０】
【表１０】
0005389280.tif 000011
【００４１】
式13
mismatch-Zi Zi-1=Zi&Zi-1&Mi
【００４２】
式5〜13の極小項を、以下で次のように列挙する。
【００４３】
【表１１】
0005389280.tif 000012
【００４４】
識別Pi=!Gi&!Ziおよび!Pi=Gi|Ziは、上記テーブルにある極小項AおよびI、BおよびJ、CおよびK、DおよびLを、8つの極小項からなる以下の一覧に結合するのに使われる。
【００４５】
【表１２】
0005389280.tif 000013
【００４６】
さらなる分析およびシミュレーションにより、上記のこれらの結合極小項および後でさらに詳しく記載するキャリーインの評価が、A+B=K演算に使われ得ることを検証する。
【００４７】
メモリ値のみに依存する、以下の変数Siおよび!Siが定義される。
式14
Si=(!Mi&!Mi-1)|(Mi&Mi-1)
式15
!Si=(!Mi&Mi-1)|(Mi&!Mi-1)
式14、15を使って、極小項BBとCCとFFとGGとが結合されて、先のテーブルの8つの極小項AA〜HHを、以下の最終極小項テーブル中の6つの極小項608〜610および614〜616に削減する。最終極小項テーブルについては、図6Bの記述とともに後でより詳しく説明する。
最終極小項のテーブル
【００４８】
【表１３】
0005389280.tif 000014
【００４９】
Siに関する式14および!Siに関する式15は、メモリ値のみに依存し、それにより、回路出力値Siおよび!Siは、CAMアップデートの書込み周期中に判定されることになる。したがって、Siおよび!Siを生成する際の遅延は有利には、読出し動作中に不一致を判定するためのレイテンシに影響しない。図6Aを参照すると、排他的NORゲート603などの単一論理ゲート回路が、Si信号602出力およびその反転!Si信号606を、各メモリセル中のインバータ607によって生成し、こうしてメモリセル出力MiおよびMi-1に応答する。メモリセル出力MiおよびMi-1は、概して読込みルックアップ比較演算よりも低い頻度で起こる、メモリセルのアップデートにより変わり得ることに留意されたい。図6Bを参照すると、Si信号602出力およびその反転!Si信号606の使用を含む6つの極小項618〜620および624〜626が、後でさらに詳しく記載するように、CAMタグアレイのメモリセルに含まれる新規SAC回路610中で使われる。
【００５０】
最下位ビット用の終端SAC回路が、Pi、Gi、ZiおよびCinの値から判定され、これらの値は、結合されると、下でより詳しく説明するように、1組のミスマッチ式をそこから生成することができる3つの結合を生じる。たとえば、最下位ビットi=12を使って、3つの結合が列挙される。
【００５１】
【表１４】
0005389280.tif 000015
【００５２】
こうしたミスマッチ式は、式16に示すように、2つの隣接ビットと、キャリーインCinとの合計に基づく。
式16
A12+B12+Cin=Ri
G12=1の場合、Cinの2つの可能状態{0,1}に関して式16を評価すればよい。G12=1であるので、{A12,B12}={1,1}である。式16の評価により、キャリーイン値に依存して、R12に対して2つの結果を生成する以下の2つの状況が生じる。
【００５３】
【表１５】
0005389280.tif 000016
【００５４】
Gi Cin結合に関するミスマッチ式は、式17によって与えられる。
式17
mismatch-G12 Cin=(G12&!Cin&M12)|(G12&Cin&!M12)
【００５５】
2つのさらなるテーブルおよびそれに対応するミスマッチ式は、次のように説明される。
【００５６】
【表１６】
0005389280.tif 000017
【００５７】
式18
mismatch-P12 Cin=(P12&!Cin&!M12)|(P12&Cin&M12)
【００５８】
【表１７】
0005389280.tif 000018
【００５９】
式19
mismatch-Z12 Cin=(Z12&!Cin&M12)|(Z12&Cin&!M12)
【００６０】
式17〜19の極小項を、以下で次のように列挙する。
【００６１】
【表１８】
0005389280.tif 000019
【００６２】
識別!Pi=Gi|Ziは、極小項AとEとBとFとを、図6Cの考察とともに下でより詳しく説明する、最終LSB極小項のテーブル中の4つの極小項からなる以下の一覧に結合するのに使われる。
最終LSB極小項のテーブル
【００６３】
【表１９】
0005389280.tif 000020
【００６４】
図3は、変換索引バッファ(TLB)内で使用するための例示的なA+B=K CAM回路300を示す。A+B=K CAM回路300は、パルスラッチインターフェース304、アドレス合計比較(SAC)信号論理回路306、タグメモリおよびSACアレイ308、ならびに新規タグT'書込みラッチおよびドライバインターフェース310を含む。A+B=K CAM回路300は、たとえば、図2のITLB224およびDTLB228内で使われ得るような、4Kバイトのページをもつ32ビット仮想アドレスを有するシステムにおいて、仮想変換に使われる。仮想アドレスは、上位20ビット部分、すなわちビット[31:12]と、下位12ビット部分、すなわちビット[11:0]とに分けられる。上位20ビット部分は、物理ページ番号に変換されるべき仮想ページ番号を表す。下位12ビット部分は、ページへの4Kバイトのページオフセットを表し、変換されない。
【００６５】
たとえば、ベースアドレスA[31:12]312をオフセット値B[31:12]314と加算することによって、仮想アドレスが形成される。仮想アドレスは次いで、タグメモリおよびSACアレイ308中の格納タグ値と比較されて、行単位ヒット指示316を生成する。複数の行単位ヒット指示316はまた、タグメモリおよびSACアレイ308において何らかのマッチが見つかった場合、結合されて、単一ヒット指示を生成する。タグメモリおよびSACアレイ308の各行は、上述した最終極小項テーブル中で使われるP、G、およびZ信号などのSAC信号を、SAC信号論理回路306から受信する。
【００６６】
アドレスが見つからないときはいつでも、TLBは、新規タグT'[31:12]318を、タグメモリおよびSACアレイ308に書き込んでよい。新規タグT'[31:12]318は、新規タグT'書込みラッチおよびドライバインターフェース310によって、ラッチされ、タグメモリおよびSACアレイ308に入れられ、行書込み信号320の制御下で、メモリに書き込まれる。タグメモリおよびSAC回路308中の行をより詳細に表したものを、図4に示し、後で説明する。
【００６７】
図4は、図3に示すA+B=K CAM回路300の例示的な第j行タグメモリ400を示す図である。第j行タグメモリ400は、格納タグ値の各ビット用のメモリセル、すなわちM[31:12]40431〜40412と、各メモリセルビット[31:13]に関連付けられた新規SAC回路40631〜40613と、格納タグ値の最下位ビットに関連付けられた終端SAC回路408と、ビット[31:13]41031〜41013向けのSおよび!S論理回路と、ヒット論理回路412とを含む。S[31:13]および!S[31:13]回路41031〜41013は、それぞれ、式14および式15に従って実装される。新規SAC[31:13]回路40631〜40613は、ルックアップ比較演算にタイミングが適した、図3のSAC信号論理回路306からのSAC信号Pi、Pi-1、Gi、およびZiを使って、上記の最終極小項テーブルに従って実装される。新規タグ値が第j行タグメモリ400に書き込まれるべきとき、図3の新規タグT'書込みラッチおよびドライバインターフェース310から、新規タグT'値がメモリセルM[31:12]に与えられる。新規タグT'値は、行書込み[j]信号414の制御下で、メモリセルに書き込まれる。
【００６８】
一実施形態では、各新規SAC回路のヒット出力は、ヒット信号418を引き下げる何らかのビットミスマッチに対する比較演算とのミスを示す。信号をロードするために、ヒット信号416を、SACヒット出力部分に接続してよい。したがって、行全体におけるマッチ比較を表すヒット信号出力418を生じるのに、ヒット回路412が使用される。
【００６９】
図5A〜図5Dは、図3に示すA+B=K CAM回路300での使用に適したアドレス合計比較(SAC)信号論理回路500、510、520、530をそれぞれ示す。各タグビット位置ごとに、図5AのパルスPi信号502、図5Bのパルス!Pi信号512、図5CのパルスGi信号522、および図5DのパルスZi信号532が生成される。一実施形態では、nチャネル金属酸化膜半導体電界効果トランジスタ(MOSFET)またはNFETが、SAC信号論理回路500を実装するのに使われる。パルスラッチインターフェース304から生成されたパルスアドレス信号Api、!Api、Bpi、および!Bpiが、Pi回路500、!Pi回路510、Gi回路520、およびZi回路530によって、入力として使われる。Pi回路500は、式1を実装する一実施形態を表す。!Pi回路510は、式1の論理補数を実装する一実施形態を表す。Gi回路520は、式2を実装する一実施形態を表す。Zi回路530は、式3を実装する一実施形態を表す。Pi回路500、!Pi回路510、Gi回路520、およびZi回路530は、それぞれ、キーパー回路504、514、524、534も使う。キーパー回路504、514、524、534は、それぞれの出力信号が、アクティブ駆動されていないときに浮動しないよう「キープ」する。クロック回路505、515、525、535は、プリチャージおよび評価状態とともに動作し、プリチャージ状態は、ルックアップ比較演算に適したタイミングで、パルスラッチインターフェース304から生成されるパルスアドレス信号Api、!Api、Bpi、および!Bpiの活動化より前に起こる。
【００７０】
図5Eは、例示的な単一メモリセル550を示す。メモリセル550は、メモリ信号Mi555を生じるバッファインバータ554と、反転メモリ信号!Mi557を生じるバッファインバータ556とを有する1対の交差結合インバータ552によって表される。新規タグ値が書き込まれるべきとき、第iのデータ入力(Di)564および(!Di)565などの新規タグT'値がメモリセルに与えられる。新規タグT'値は、図4の行書込み[j]信号414などの書込み信号568の制御下で、メモリセルに書き込まれる。
【００７１】
図6Aは、メモリセル入力値に依存するSiおよび!Si信号を有するS信号回路600を示す。Si信号602は、メモリセル信号Mi604および次に低い有効ビット隣接メモリセル信号Mi-1605に基づいて、式14に従って排他的NORゲート603によって生成される。!Si信号606は、インバータ607によって生成される。
【００７２】
図6Bは、図4のメモリセルとともに使用するための新規SAC回路610を示す。新規SAC回路610は、第1の極小項回路616、第2の極小項回路622、クロック回路628、およびキーパー回路630を備える。一実施形態では、新規SAC極小項回路616および622を実装するのに、NFETが使われる。第1の極小項回路616は、上記の最終極小項テーブルの結合極小項式に従って動作する。たとえば、Gi-1、!Mi回路618は、極小項!Pi&Gi-1&!Miに従って動作する。また、Pi-1、Si回路619は、極小項!Pi&Pi-1&Siに従って動作する。さらに、Zi-1、Mi回路620は、極小項!Pi&Zi-1&Miに従って動作する。第2の極小項回路622は、上記の最終極小項テーブルの結合極小項式に従って動作する。たとえば、Gi-1、Mi回路624は、極小項Pi&Gi-1&Miに従って動作する。また、Pi-1、!Si回路625は、極小項Pi&Pi-1&!Siに従って動作する。さらに、Zi-1、!Mi回路626は、極小項Pi&Zi-1&!Miに従って動作する。クロック回路628は、回路の動的性質に従って、また、対応する極小項によって支配される「第i」および「第i-1」の信号に従って、図5AのパルスPi信号502、図5Bのパルス!Pi信号512、図5CのパルスGi信号522、および図5DのパルスZi信号532とタイミングの合った評価フェーズとともに動作する。キーパー回路630は、それぞれのHi[j]信号632が、アクティブ駆動されていないときに浮動しないように「キープ」する。動的構造において、新規SAC回路610は有利には、図6Bに示すように3層NFETデバイススタックで実装され、そうすることによって、不一致を判定するレイテンシが削減される。
【００７３】
図6Cは、図4の最下位ビット(LSB)メモリセル40412とともに使用するための終端SAC回路650を示す図である。終端SAC回路650は、第1のLSB極小項回路656、第2のLSB極小項回路662、クロック回路668、およびキーパー回路670を備える。一実施形態では、終端SAC極小項回路656および662を実装するのに、NFETが使われる。第1のLSB極小項回路656は、上記の最終LSB極小項テーブルの結合極小項式に従って動作する。たとえば、!P12、!M12回路658は、極小項Cin&!P12&!M12に従って動作する。また、P12、M12回路659は、極小項Cin&P12&M12に従って動作する。第2のLSB極小項回路662は、上記の最終極小項テーブルの結合極小項式に従って動作する。たとえば、P12、!M12回路664は、極小項!Cin&P12&!M12に従って動作する。また、!P12、M12回路665は、極小項!Cin&!P12&M12に従って動作する。クロック回路668は、対応する極小項によって支配される「第12」の信号に従い、図5AのパルスPi信号502、図5Bのパルス!Pi信号512とタイミングの合った評価フェーズを有する回路の動的性質に従って動作する。キーパー回路670は、それぞれのH12[j]信号672が、アクティブ駆動されていないときに浮動しないように「キープ」する。動的構造において、終端SAC回路650は有利には、図6Cに示すように3層NFETデバイススタックで実装され、そうすることによって、不一致を判定するレイテンシが削減される。
【００７４】
図7は、A+B=K関数を、メモリセルビットに依存する第1の論理関数セットと、アドレス入力信号に依存する第2の論理関数セットとに分離することによって、レイテンシが低いA+B=K関数を生成するための比較プロセス700を示す。このプロセス700は、図2のプロセッサシステム200などのプロセッサシステムでの使用のために適切に利用され得る。ブロック702で、アドレス信号がTLBに与えられて、仮想アドレス/物理アドレス変換のためにTLBを調べる。ブロック704で、仮想アドレス算出が、比較演算と結合されて1つのA+B=K関数になり、メモリタグ書込み動作中に生成されたSおよび!S信号を用いるルックアップ比較演算に適したタイミングで、タグメモリおよびSACアレイ中のタグを調べる。決定ブロック706で、タグマッチがあるかどうか判定が行われる。タグマッチが検出されなかった場合、比較プロセス700は、ブロック708に進んでよい。ブロック708で、タグメモリおよびSACアレイに新規タグが書き込まれる。ブロック710で、メモリセルMiおよびMi-1に基づいてSiおよび!Si信号が判定される。ブロック712で、プロセス700は、TLBにおけるミスの後で演算を続ける。決定ブロック706に戻ると、タグマッチが検出された場合、比較プロセス700はブロック714に進む。ブロック714で、変換された物理アドレスがTLBから読み出される。ブロック716で、プロセス700は、TLB中のヒットの後で演算を続ける。
【００７５】
上記説明および図面に記載したA+B=Kプロセスは、正確な演算のためにシミュレートされ検証されている。図6Bおよび図6Cに示す3層NFETスタックが、システムタイミング問題に関して改善をもたらすことを検証するために、回路シミュレーション技法も用いられている。
【００７６】
タグ書込み動作は、ルックアップ読込み比較演算と比較して、TLB演算ではまれであることに留意されたい。たとえば、いくつかのシミュレーションでは、4回のタグ書込み動作ごとに、1,300回を超えるルックアップ比較演算が起きた。したがって、現在記載しているTLBに対する電力切換えは、部分的には、タグ書込み動作の後でのみ切り換え得るSiおよび!Si回路により、低い。
【００７７】
本明細書で開示する実施形態に関して説明した様々な例示的な論理ブロック、モジュール、回路、要素、または構成要素は、汎用プロセッサ、デジタル信号プロセッサ(DSP)、特定用途向け集積回路(ASIC)とともに利用され、フィールドプログラマブルゲートアレイ(FPGA)または他のプログラマブル論理構成要素、個別ゲートまたはトランジスタ論理、個別ハードウェア構成要素、または本明細書で説明する機能を実行するように設計されたそれらの任意の組合せを使って実装することができる。プロセッサは汎用マイクロプロセッサであり得るが、代替として、プロセッサは任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械であり得る。プロセッサは、コンピューティング構成要素の組合せ、たとえばDSPと汎用マイクロプロセッサとの組合せ、複数のマイクロプロセッサ、DSPコアと連携する1つまたは複数のマイクロプロセッサ、あるいは所望のアプリケーションに適した任意の他のそのような構成などとしても実装され得る。
【００７８】
本明細書で開示した実施形態と関連して説明した方法は、ハードウェアで直接実施され、プロセッサによって実行される1つまたは複数のソフトウェアモジュールによってサポートされ、またはその2つの組合せでよい。ソフトウェアモジュールは、RAMメモリ、フラッシュメモリ、ROMメモリ、EPROMメモリ、EEPROMメモリ、レジスタ、ハードディスク、リムーバブルディスク、CD-ROM、または当技術分野で知られている任意の他の形態の記憶媒体中に常駐することができる。記憶媒体は、プロセッサがその記憶媒体から情報を読み取り、その記憶媒体に情報を書き込むことができるようにプロセッサに結合され得る。代替として、記憶媒体はプロセッサと一体であり得る。
【００７９】
本発明を、プロセッサシステムにおいて使用するための例示的な実施形態のコンテキストにおいて開示したが、上記考察および添付の特許請求の範囲と整合する非常に様々な実装形態が当業者によって利用され得ることが理解されよう。たとえば、固定機能実装形態でも、本発明の様々な実施形態を使用することができる。
【符号の説明】
【００８０】
100  ワイヤレス通信システム
120  遠隔ユニット
125A  構成要素
125C  構成要素
125B  構成要素
125D  構成要素
130  遠隔ユニット
140  基地局
150  遠隔ユニット
180  順方向リンク信号
190  逆方向リンク信号
200  プロセッサシステム、処理システム
210  プロセッサ
212  命令実行パイプライン、パイプライン
214  制御論理
216  レジスタまたはラッチ
218  算術論理ユニット(ALU)
220  汎用レジスタ(GPR)ファイル
222  命令キャッシュ(Icache)
224  命令変換索引バッファ(ITLB)
226  データキャッシュ(Dcache)
228  データ変換索引バッファ(DTLB)
230  メインメモリ、メモリ
232  メモリインターフェース
234  入力/出力(I/O)インターフェース
236  周辺デバイス
300  A+B=K CAM回路
304  パルスラッチインターフェース
306  アドレス合計比較(SAC)信号論理回路
308  タグメモリおよびSACアレイ
310  新規タグT'書込みラッチおよびドライバインターフェース
400  第j行タグメモリ
406  新規SAC回路
408  終端SAC回路
412  ヒット論理回路
500  アドレス合計比較(SAC)信号論理回路、Pi回路
504  キーパー回路
505  クロック回路
510  アドレス合計比較(SAC)信号論理回路、!Pi回路
514  キーパー回路
515  クロック回路
520  アドレス合計比較(SAC)信号論理回路、Gi回路
524  キーパー回路
525  クロック回路
530  アドレス合計比較(SAC)信号論理回路、Zi回路
534  キーパー回路
535  クロック回路
550  メモリセル
552  交差結合インバータ
554  バッファインバータ
556  バッファインバータ
600  S信号回路
603  排他的NORゲート
607  インバータ
610  新規SAC回路
616  第1の極小項回路、新規SAC極小項回路
618  Gi-1、!Mi回路
619  Pi-1、Si回路
620  Zi-1、Mi回路
622  第2の極小項回路、新規SAC極小項回路
624  Gi-1、Mi回路
625  Pi-1、!Si回路
626  Zi-1、!Mi回路
628  クロック回路
630  キーパー回路
650  終端SAC回路
656  第1のLSB極小項回路、終端SAC極小項回路
658  !P12、!M12回路
659  P12、M12回路
662  第2のLSB極小項回路、終端SAC極小項回路
664  P12、!M12回路
665  !P12、M12回路
668  クロック回路
670  キーパー回路
【図１】
0005389280.tif 000021
【図２】
0005389280.tif 000022
【図３】
0005389280.tif 000023
【図４】
0005389280.tif 000024
【図５Ａ】
0005389280.tif 000025
【図５Ｂ】
0005389280.tif 000026
【図５Ｃ】
0005389280.tif 000027
【図５Ｄ】
0005389280.tif 000028
【図５Ｅ】
0005389280.tif 000029
【図６Ａ】
0005389280.tif 000030
【図６Ｂ】
0005389280.tif 000031
【図６Ｃ】
0005389280.tif 000032
【図７】
0005389280.tif 000033