合計アドレスデコーダ

CPU 設計において、合計アドレス デコーダ (SAD)または合計アドレス メモリ (SAM) デコーダの使用は、 CPU キャッシュアクセスとアドレス計算 (ベース + オフセット)のレイテンシを削減する方法です。これは、アドレス生成合計操作とキャッシュSRAMのデコード操作を融合することによって実現されます。

L1データ キャッシュは通常、最も重要な CPU リソースに配置する必要があります。これは、データ キャッシュを大きくするほど直接的にサイクルあたりの命令数 (IPC) を向上させるものはほとんどなく、データ キャッシュが大きいほどアクセスに時間がかかり、データ キャッシュをパイプライン化すると IPC が悪化するからです。L1 データ キャッシュ アクセスのレイテンシを短縮する 1 つの方法は、アドレス生成合計操作とキャッシュ SRAM のデコード操作を融合することです。

メモリ パイプ内の他のユニットは結果の仮想アドレスを使用するため、アドレス生成の合計演算は依然として実行する必要があります。その合計は、ここで説明する融合加算/デコードと並行して実行されます。

高速化に最も効果的な繰り返しは、ロードの後に​​、別のロードにつながる整数演算のチェーンでそのロードを使用することです。ロード結果が整数結果と同じ優先度でバイパスされると仮定すると、プログラムがリンク リストに従っているかのように、この繰り返しをロードの後に​​別のロードが続くものとして要約できます。

このページの残りの部分では、単一のアドレス指定モード (レジスタ + オフセット)、仮想インデックス付きデータ キャッシュ、および可変幅の符号拡張ロードを備えた命令セット アーキテクチャ (ISA) を想定しています。ほとんどのRISC ISA はこの説明に当てはまります。Intel x86などのISA では、3 つまたは 4 つの入力を合計して仮想アドレスを生成します。複数入力の加算は、キャリー保存加算器を使用した 2 入力の加算に減らすことができます。残りの問題は、以下で説明するとおりです。したがって、重要な繰り返しは、加算器、デコーダ、SRAM ワード ライン、SRAM ビット ライン、センス アンプ、バイト ステアリングマルチプレクサ、およびバイパス マルチプレクサです。

この例では、ダブルワード (8 バイト) に揃えられた値を返す直接マップされた 16  KBデータ キャッシュを想定しています。SRAM の各行は 8 バイトで、2048 行あり、Addr[13:3] でアドレス指定されます。合計アドレス指定の SRAM の考え方は、セット アソシエイティブ キャッシュにも同様に適用されます。

この例の SRAM デコーダには、11 ビットの入力 Addr[13:3] と、デコードされたワード ラインである 2048 の出力があります。1 つのワード ラインは、それぞれの固有の Addr[13:3] 値に応じてハイに駆動されます。

最も単純な形式のデコーダでは、2048 行のそれぞれが論理的にAND ゲートになります。11 ビット (A[13:3] と呼ぶ) とその補数 (B[13:3] と呼ぶ) がデコーダに入力されます。各行では、11 ビットまたは補数が 11 入力 AND ゲートに入力されます。たとえば、10 進数の 1026 は 2 進数の 10000000010 に相当します。行 1026 の機能は次のようになります。

ワードライン[1026] = A[13] & B[12] & B[11] & B[10] & B[9] & B[8] & B[7] & B[6] & B[5] & A[4] & B[3]

加算器とデコーダの両方のキャリー チェーンは、アドレスのインデックス部分全体の幅からの情報を結合します。幅全体にわたって情報を 2 回結合するのは冗長です。合計アドレス指定の SRAM は、加算器とデコーダを 1 つの構造に実装することで、情報を 1 回だけ結合します。

SRAM は加算の結果でインデックス付けされることを思い出してください。加数を R (レジスタ) および O (そのレジスタへのオフセット) と呼びます。合計アドレス指定デコーダは R+O をデコードします。各デコーダ ラインのライン番号を L と呼びます。

デコーダが各デコーダ ライン上で R と O の両方を駆動し、各デコーダ ラインが次のように実装されているとします。

ワードライン[L] = (R+O)==L

(R+O)==L <=> R+OL==0
         <=> R+O+~L+1==0
         <=> R+O+~L==-1==11..1.

フルアダーのセットは、R+O+~L を S+C に減らすために使用できます (これはキャリー保存加算です)。S+C==11..1 <=> S==~C。最終的な加算ではキャリーは発生しません。C はキャリーの行であるため、1 ビットシフトされ、R[13:3]+O[13:3]+~L[13:3] == {0,S[13:3]} + {C[14:4],0} となることに注意してください。

この定式化では、デコーダーの各行は、ベース レジスタ、オフセット、行番号をキャリー保存形式に縮小する全加算器のセットと、コンパレーターです。このハードウェアのほとんどは、以下で冗長であることが証明されますが、今のところは、すべてのハードウェアが各行に存在すると考えるのが簡単です。

上記の式は、加算の結果全体をチェックします。ただし、CPU キャッシュ デコーダーでは、加算の結果全体がバイト アドレスであり、キャッシュは通常、より大きなアドレス (この例では 8 バイト ブロック) でインデックス付けされます。アドレスの LSB のいくつかは無視することが望ましいです。ただし、2 つの加数の LSB は、アドレス指定されたダブルワードを変更するキャリー アウトを生成する可能性があるため、無視できません。

R[13:3]とO[13:3]を加算してインデックスI[13:3]を取得する場合、実際のアドレスAddr[13:3]は、R[2:0]+O[2:0]がキャリーアウトを生成するかどうかに応じて、I[13:3]またはI[13:3] + 1のいずれかになります。偶数アドレスと奇数アドレスの2つのSRAMバンクがある場合は、IとI+1の両方をフェッチできます。偶数バンクはアドレス000xxx、010xxx、100xxx、110xxxなどを保持し、奇数バンクはアドレス001xxx、011xxx、101xxx、111xxxなどを保持します。R[2:0]+O[2:0]からのキャリーアウトを使用して、後でフェッチされる偶数または奇数のダブルワードを選択できます。

2 つのハーフサイズ SRAM バンクからフェッチすると、センス アンプとデータ ステアリング ロジックでのスイッチングが増えるため、1 つのフルサイズ バンクからフェッチする場合よりも多くの電力が消費されることに注意してください。

隣の図を参照すると、I[13:3]==101またはI[13:3]==110のとき、偶数バンクはライン110をフェッチします。I[13:3]==100またはI[13:3]==101のとき、奇数バンクはライン101をフェッチします。

一般的に、奇数SRAMバンクは、I[13:3]==2NまたはI[13:3]==2N+1のいずれかのときに、ラインLo==2N+1をフェッチする必要があります。2つの条件は次のように記述できます。

I[13:3] = Lo-1 => R[13:3] + O[13:3] + ~Lo+1 = 11..11
               => R[13:3] + O[13:3] + ~Lo = 11..10
I[13:3] = Lo => R[13:3] + O[13:3] + ~Lo = 11..11

比較の最後の桁を無視します: (S+C)[13:4]==11..1

同様に、偶数SRAMバンクは、I[13:3]==2NまたはI[13:3]==2N-1のいずれかのときにラインLe==2Nをフェッチします。条件は次のように記述され、ここでも比較の最後の桁は無視されます。

I[13:3] = Le-1 => R[13:3] + O[13:3] + ~Le = 11..10
I[13:3] = Le => R[13:3] + O[13:3] + ~Le = 11..11

    R 13 ... R 6   R 5   R 4   R 3 
    O 13 ... O 6   O 5   O 4   O 3 
    L 13 ... L 6   L 5   L 4   L 3
--------------------------
    S 13 ... S 6   S 5   S 4   S 3 
C 14 C 13 ... C 6   C 5   C 4

行間の冗長性を解消する前に、次の点を確認してください。

2つのバンクのそれぞれのデコーダーの各行は、加算する3つの数値（R[13:3]、O[13:3]、およびL）を2つの数値（S[14:4]およびC[13:3]）に減算する全加算器のセットを実装します。LSB（==S[3]）は破棄されます。キャリーアウト（==C[14]）も破棄されます。行は、S[13:4] == ~C[13:4]、つまり&(xor(S[13:4], C[13:4]))の場合に一致します。

L 入力は定数なので、全加算器を 2 入力 AND、OR、XOR、XNOR に部分的に特化することができます。結果の式はデコーダーのすべての行に共通であり、下部に集めることができます。

S 0;i   = S(R i , O i , 0) = R i xor O i 
S 1;i   = S(R i , O i , 1) = R i xnor O i 
C 0;i+1 = C(R i , O i , 0) = R iかつ O i 
C 1;i+1 = C(R i , O i , 1) = R iまたは O i。

_{各桁の位置では、 S i は}2 つだけ、 C _{i は}2 つだけ、そしてそれらの間の XOR は 4 つだけ可能です。

L i =0 かつ L i-1 =0: X 0;0;i = S 0;i xor C 0;i = R i xor O i xor (R i-1かつ O i-1 )
L i =0 かつ L i-1 =1: X 0;1;i = S 0;i xor C 1;i = R i xor O i xor (R i-1または O i-1 )
L i =1 かつ L i-1 =0 の場合: X 1;0;i = S 1;i xor C 0;i = R i xnor O i xor (R i-1かつ O i-1 ) = !X 0;0;i 
L i =1 かつ L i-1 =1 の場合: X 1;1;i = S 1;i xor C 1;i = R i xnor O i xor (R i-1または O i-1 ) = !X 0;1;i

この例の 1 つのデコーダーは、ビット 4..13 のそれぞれに対してこれらの 4 つの式を計算し、デコーダーの 40 本の配線すべてを駆動します。デコーダーの各行は、各ビットに対して 4 本の配線の 1 つを選択し、10 入力の AND で構成されます。

より単純なデータ キャッシュ パスには、加算器の後に従来のデコーダーが続きます。この例のキャッシュ サブシステムの場合、クリティカル パスは、真の値と補数値を生成する 14 ビット加算器と、デコーダーの各行の 11 ビット AND ゲートになります。

合計アドレス指定設計では、デコーダーの最後の AND ゲートはそのまま残りますが、ビット幅は 11 ではなく 10 です。加算器は、各ビットの 4 入力論理式に置き換えられました。レイテンシの節約は、加算器と 4 入力式の間の速度差によって実現され、おそらく単純なCMOSゲート 3 つ分の節約になります。

読者が、これはマルチサイクルのクリティカル パスにおける 3 つのゲートの改善のために、非常に頭を悩ませる作業であると感じたとしたら、読者は現代の CPU がどの程度最適化されているかをよりよく理解していることになります。

多くのデコーダ設計では、プリデコード ステージを採用することで、デコード ライン自体の高ファンインAND ゲートを回避しています。たとえば、11 ビットのデコーダは、それぞれ 4、4、3 ビットの 3 つのグループにプリデコードされることがあります。各 3 ビット グループはメイン デコード アレイの 8 本のワイヤを駆動し、各 4 ビット グループは 16 本のワイヤを駆動します。すると、デコーダ ラインは 3 入力 AND ゲートになります。この再編成により、実装領域を大幅に節約でき、電力もいくらか節約できます。

この同じ再構成は、合計アドレス指定デコーダにも適用できます。上記の非プリデコード式の各ビットは、ローカル 2 ビット加算として見ることができます。プリデコードでは、各プリデコード グループはローカル 3、4、または 5 ビット加算であり、プリデコード グループは 1 ビット重複します。

プリデコードを行うと、通常、デコーダを通過する配線の数が増加します。また、合計アドレス指定のデコーダでは、同等の単純なデコーダに比べて配線の数が約 2 倍になります。これらの配線は、実行可能なプリデコードの量を制限する要因となる場合があります。

• Paul Demone は、realworldtech の記事で合計アドレス指定キャッシュについて説明しています。
• Healdら^{[1]はISSCC 1998で、} Ultrasparc IIIの元の合計アドレスキャッシュがどのようなものであったかについて説明した論文を発表しました。
• 合計アドレス指定メモリは、

米国特許 5,754,819、1998 年 5 月 19 日、 低レイテンシ メモリ インデックス作成方法および構造。発明者: Lynch、William L. (カリフォルニア州パロアルト)、Lauterbach、Gary R. (カリフォルニア州ロスアルトス)、譲受人: Sun Microsystems、Inc. (カリフォルニア州マウンテンビュー)、出願日: 1994 年 7 月 28 日

• キャリーフリーアドレスのデコードに関連する特許に名前が記載されている発明者の少なくとも 1 人は、次の出版物を引用しています。

キャリー伝播なしのA + B = K条件の評価（1992）Jordi Cortadella、Jose M. Llaberia IEEE Transactions on Computers、[1] [2]

• 次の特許はこの作業を拡張し、プロセッサ全体で冗長形式の演算を使用するようにして、ALU 演算でも、または ALU 演算がメモリ アドレスにバイパスされる場合でも、キャリー伝播のオーバーヘッドを回避します。

米国特許 5,619,664、 冗長中間データ形式を転送することで算術命令のパイプライン処理を改善するアーキテクチャを備えたプロセッサ、1997 年 4 月 18 日付与、発明者: Glew; Andrew F. (オレゴン州ヒルズボロ)、譲受人: Intel Corporation (カリフォルニア州サンタクララ)、出願番号: 08/402,322、出願日: 1995 年 3 月 10 日