FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

自作CPUの回路面積削減検討 (STQのフォワード論理削減検討2.)

現在の自作CPUは、結構面積が大きくて通常のFPGAに乗り切らない。どうにか乗り切れるように、面積削減を検討している。 LSUの中で圧倒的に面積が巨大なのがSTQだ。STQが巨大な要因はいくつかある。

  • LDQと異なり、各エントリはアドレスとデータの両方を管理する必要がある。
  • ロード命令のフォワーディングをサポートする必要がある。この時、バイト単位での細かいフォワーディングをサポートすると、論理が増大する。
  • ストアバッファへデータを移動する論理が必要である。データ移動時に、同じキャッシュラインへのマージ機能をサポートすると、論理が増大する。

それぞれについて対策を考える。

  1. アドレスの管理はどうしてもCAMになる必要がある。データの管理は、Distributed RAMに移動したい。
  2. フォワーディングを簡易化し、特定の条件でなければフォワーディングをサポートしない。複数エントリにヒットしてバイト単位でマージする必要がある場合などは、フォワーディングをキャンセルする。
  3. これにより、常にフォワーディングに必要なデータエントリを1つに限定し、Distributed RAMを使いたい。
  4. ストアバッファへのデータの移動時のマージ量を減らす。

2について考え、RTL実装を行った。複数エントリにヒットしてバイト単位でマージする方法を細粒度、1エントリのみをフォワードする方法を粗粒度と呼ぼう。 一応ランダムテストも含めてテストパタンはPASSする程度のクオリティに仕上がっている。

  • 性能面：Dhrystoneを実行して、ROIのサイクル数を計測した。

    • 細粒度：111,009
    • 粗粒度：111,103
    • 1パーセント未満の性能低下なので許容範囲内であろう。

  • 面積：

    • 細粒度：LUT=22,148 / LUTRAM=0 / FF=3,619
    • 粗粒度：LUT=15,090 / LUTRAM=704 / FF=2,154

LUTRAMに移ってきた感じだ。各STQエントリの面積はあまり変わらない。

  • STQエントリの面積：
    • 細粒度：LUT=184 / FF=83
    • 粗粒度：LUT=199 / FF=83

自作CPUの回路面積削減検討 (STQのフォワード論理削減検討)

現在の自作CPUは、結構面積が大きくて通常のFPGAに乗り切らない。どうにか乗り切れるように、面積削減を検討している。 LSUの中で圧倒的に面積が巨大なのがSTQだ。STQが巨大な要因はいくつかある。

  • LDQと異なり、各エントリはアドレスとデータの両方を管理する必要がある。
  • ロード命令のフォワーディングをサポートする必要がある。この時、バイト単位での細かいフォワーディングをサポートすると、論理が増大する。
  • ストアバッファへデータを移動する論理が必要である。データ移動時に、同じキャッシュラインへのマージ機能をサポートすると、論理が増大する。

それぞれについて対策を考える。

  1. アドレスの管理はどうしてもCAMになる必要がある。データの管理は、Distributed RAMに移動したい。
  2. フォワーディングを簡易化し、特定の条件でなければフォワーディングをサポートしない。複数エントリにヒットしてバイト単位でマージする必要がある場合などは、フォワーディングをキャンセルする。
  3. これにより、常にフォワーディングに必要なデータエントリを1つに限定し、Distributed RAMを使いたい。
  4. ストアバッファへのデータの移動時のマージ量を減らす。

次に、2について考える。フォワーディングをサポートするのをSTQのエントリ1つに限定する。 これにより、バイト・ストアx4 → ワード・ロードx1などのフォワーディングがサポートできなくなるが、そういうことはあまり起こらないと仮定して無視する代わりに、論理を簡単化できる。 また、フォワーディングに必要なデータの管理をDistributed RAMに移すことで、FPGAの資源を削減できる。

基本的な考え方としては、

sb x1, 0(x10)
sb x2, 1(x10)
sb x3, 2(x10)
sb x4, 3(x10)
lw x5, 0(x10)

このようなシーケンスにおいて、フォワーディングによって検知されるのはLWにとって最も近いストア命令、sb x4, 3(x10)のみである。 そうすると、それより前の3つのストア命令はすべてフォワーディングの対象とならない。

そうすると、lwの対象バイト・ストローブが0000_1111であるのに対して、sbがフォワードできるバイト・ストローブが0000_1000なので完全なフォワーディングを実現できず、LW命令としてはフォワーディングは行われない。 その代わりに、フォワード不完全ということでMSHRにリクエストが入り、L1Dにキャッシュ・ロードが行われる。

しかし問題はそのあとだ。上記のシーケンスで、L1Dキャッシュへのヒットが発生した場合、x1,x2,x3のストアを無視された状態ですべてのデータがそろってしまう(0000_1000はsb x4から、0000_0111はキャッシュから)ため、誤ったデータをロードする結果になってしまう。

これを防ぐためには、そもそもSTQに複数のエントリがヒットしたことを検知する必要があり、複数STQにフォワード対象がヒットした場合は、命令のハザードを発生しすべての命令がL1Dキャッシュに書き込まれるのを待つ必要がある。 このように、実装としては少し工夫が必要だが、全体としての論理が削減されるかどうか、観察していこうと思う。

自作CPUの回路面積削減検討 (STQの面積削減検討)

現在の自作CPUは、結構面積が大きくて通常のFPGAに乗り切らない。どうにか乗り切れるように、面積削減を検討している。 LSUの中で圧倒的に面積が巨大なのがSTQだ。STQが巨大な要因はいくつかある。

  • LDQと異なり、各エントリはアドレスとデータの両方を管理する必要がある。
  • ロード命令のフォワーディングをサポートする必要がある。この時、バイト単位での細かいフォワーディングをサポートすると、論理が増大する。
  • ストアバッファへデータを移動する論理が必要である。データ移動時に、同じキャッシュラインへのマージ機能をサポートすると、論理が増大する。

それぞれについて対策を考える。

  1. アドレスの管理はどうしてもCAMになる必要がある。データの管理は、Distributed RAMに移動したい。
  2. フォワーディングを簡易化し、特定の条件でなければフォワーディングをサポートしない。複数エントリにヒットしてバイト単位でマージする必要がある場合などは、フォワーディングをキャンセルする。
  3. これにより、常にフォワーディングに必要なデータエントリを1つに限定し、Distributed RAMを使いたい。

  4. ストアバッファへのデータの移動時のマージ量を減らす。

  5. が一番やりやすい。一度にマージできるSTQエントリの量をパラメタライズしておいたので、パラメータの量を減らした。 この部分の論理で重たいのは、各バイトにおいてデータ転送すべきデータを正確にセレクトすることだ。 STQエントリのマージできるサイズを減らすことで、この部分の論理を減らすことができる。

幸い、このパラメータの削減による性能への影響もわずかだった。面積もある程度減らせるし、引き続きこの方針でSTQの削減を続けていこう。

マルチポートRAMを使用するためのXOR Multiport RAMの実装

前のブログの記事では、LVTを用いたSingle Port RAMをMulti Portに複製するための方法について調査した。

msyksphinz.hatenablog.com

LVT(Live Value Table)を用いた手法では、各RAMインデックスについて、どのバンクRAMに最新の値が書き込まれているかを示すLVTエントリを用意する。 この手法は強力で便利なのだが、ポートの数が増えれば増えるほど、LVTの必要なビット幅は増加していく。

例えば、かなり高性能寄りCPUでは読み込みポートが12、書き込みポートが10とかいうとんでもない量のポートが必要になる。 また、物理レジスタの数を考慮すると256エントリなどのRAMを管理する必要があり、これを純粋にLVTで管理するとなると、必要となるLVTのFFの数は以下のように計算できる。

256 * $clog2(10) = 1024 FF

それでもって、このLVTをアップデートするための論理も結構きついものになってくる。単純に実装すると、10ポートのFFとなり、周辺の論理回路もかなり大きなものになるだろう。

always_ff @ (posedge i_clk, negedge i_reset_n) begin
  if (!i_reset_n) begin
    for (int i = 0; i < WORDS; i++)
      r_lvt[i] <= 'h0;
  end else begin
    for (int i = 0; i < WR_PORTS; i++) begin
      if (i_wr[i]) begin
        r_lvt[i_wr_addr[i]] <= i;
      end
    end
  end
end // always_ff @ (posedge i_clk, negedge i_reset_n)

そこで、LVTすら排除してしまう手法であるXOR Multi Port RAMについて調査する。この手法はLVTを除去することができるが、さらに余分にRAMが必要なる。

tomverbeure.github.io

基本的な考え方としては、例えば書き込みポートが2であるとして、それぞれRAM1とRAM2を使用しているとする。あるインデックスAにそれぞれVALUE1, VALUE2が書き込まれているとする。 ライトポート0に対してNEWが書き込まれたとする。この時、RAM1に対して以下のようにRAM2との値を使用して変更した値を書き込む。

RAM1 New Value = NEW ^ VALUE2

そして、読み出すときはRAM1の値(NEW ^ VALUE2)とRAM1の値(VALUE2)をXORして読み出す。すると、NEW ^ VALUE2 ^ VALUE2 = NEWとなり、NEWの値を読み出すことができる。

ただし、これでは問題がある。読み込みと書き込みが同時に発生したとき、書き込みにも既存の値を読み出すために読み込みポートが必要になる。単純に考えればこのためにポートを1つ増やす必要があるが、これを回避する方法がある。それ専用のRAMを新たに追加すればよいのだ。 これは自分以外の書き込んだデータを記憶しておくためのRAMなので、各書き込みポートあたり、書き込みポート数-1個が必要となる。

結果的に、全体的に必要なRAMの数は、

書き込みに必要なRAMの数 = 書き込みポート数 * (書き込みポート数-1)
読み出しに必要なRAMの数 = 書き込みポート数 * 読み出しポート数
全体で必要なRAMの数 = 書き込みに必要なRAMの数 + 読み出しに必要なRAMの数 = 書き込みポート数 * (書き込みポート数-1+読み出しポート数)

となる。上記の読み出しポート=12,書き込みポート数=10の場合でLVTと必要なRAMの数を比較すると、

  • LVTの場合 = 10 * 12= 120
  • XORの場合 = 10 * (10-1+12) =10 * 21 = 210

と、大幅に増加してしまう。しかしまあ、LVTというクリティカルパスを完全に削除することができるため、使いどころによっては有用であろう。

キャッシュのコヒーレンス・プロトコルについてまとめる (MOESIプロトコル)

マルチコアにおいて、キャッシュ・コヒーレンス・プロトコルというのは切っても切り離せない問題だ。 幾つかのプロトコルについてメモを書いたので、一応ここに残しておく。

MOESIプロトコル

前回まとめたMESIプロトコルに対して、O(Owned)状態を加える。

  • O(Owned): キャッシュ内にブロックが存在しているかつ、下位のキャッシュとブロックの値が異なっている。このブロックは他コアと共有されている。ブロックが置き換えられる際、下位のキャッシュに書き戻す責任を持っている。

O権限は他コアと共有している想定のため、読み出しはできるが書き込みはできない。 では、どのようにしてOwned状態になるのかステートマシンを確認してみる。バス側のリクエストに基づくステートマシンを見てみる。 (CPU側のリクエストでは、ブロックはOwned状態に変化できない)。

MOESIプロトコル、バス側からのリクエストに対するステートマシン

まず、自コアがキャッシュブロックに対して書き込みを行うと、他コアのブロックをInvalidateして自コアのブロックはModified状態になる。 これは、自身のみがキャッシュブロックを保持し、下位のキャッシュと最新データが共有されていないことを意味する。

この後、当該キャッシュブロックに対して他コアが読み込み要求を出すとどのようになるのか。 MESIプロトコルだと、自コアのキャッシュブロックをS権限に変更したうえで、他コアに共有する。 この時、コア全体がS状態になるためには、下位キャッシュに最新のブロックを書き戻す必要がある。

一方、MOESIプロトコルだと、わざわざ下位キャッシュに最新のブロックを戻すことなく、M状態のブロックを直接他コアに転送することができる。 こうすると、下位キャッシュへのアクセスが必要ないためより高速にデータを共有できるが、その代わりに読み込み権限のキャッシュブロックと、下位キャッシュのブロックのデータが一致しないまま全員が読み込み権限を持つブロックを保持していることになる。

そこで、もとももM状態であったブロックを持っていたコアが、ブロックを自コアから破棄する際に、下位キャッシュに書き戻す責任を持つために、Owned権限に移動する。 O権限のブロックは、読み込みのみが可能で、他コアの同一ブロックはすべてS権限のはずだ。 そして、O権限のブロックはキャッシュブロックを破棄するだけでなく、最終的に下位キャッシュに書き戻す必要がある。

CPU側のリクエストに関する挙動は以下の通り。コア側のリクエストではO権限に移動することはできないが、他コアからのRdSnoopによってのみ権限が変化する。 そして、再度O権限のブロックに書き込みを行いたい場合、M権限に移動しつつ、他コアのブロックをInvalidateする必要がある、というわけだ。

MOESIプロトコル、コア側からのリクエストに対するステートマシン

キャッシュのコヒーレンス・プロトコルについてまとめる (MSI/MESIプロトコル)

マルチコアにおいて、キャッシュ・コヒーレンス・プロトコルというのは切っても切り離せない問題だ。 幾つかのプロトコルについてメモを書いたので、一応ここに残しておく。

  • MSIプロトコル
  • MESIプロトコル
  • MOESIプロトコル

MSIプロトコル

キャッシュ内のブロックは以下の3つの状態のどれかを持つ。

  • I(Invalidate): キャッシュ内に当該ブロックは存在していない
  • S(Shared): キャッシュ内にブロックが存在しており、下位のキャッシュと値が一致している
  • M(Modified): キャッシュ内にブロックが存在しており、下位のキャッシュと値が一致していない、つまり書き込まれている)

この状態について、CPU側からの挙動と、バス(スヌーププロトコル側)からの動作をステートマシンにまとめる

CPU側からの挙動

  • I(Invalidate) からの挙動
    • CPUでRead Missが発生した場合、下位のキャッシュからデータを読み込むためのリクエストを発行する。当該ブロックはS(Shared)となる。
    • CPUでWrite Missが発生した場合、下位のキャッシュからデータを読むコムためのリクエストを発行する。当該ブロックはキャッシュに読み込まれ、さらに最新の値に更新され、M(Modified)となる。
  • S(Shared) からの挙動。基本的にキャッシュ内にブロックが存在しているのでHitのみを考える。同じインデックスに別のブロックが要求された場合のことは考えない。
    • CPUでRead Hitが発生する場合、特に何もせず、データをCPUに返す
    • CPUでWrite Hitが発生する場合、Sharedステートは書き込み権限を持っていないので、バスに対して書き込み権限取得要求を行い、完了後にデータを更新し、M(Modified)に移行する。また、他コアが持っている同様のS権限のブロックは古くなるため、他コアのブロックに対してInvalidateを通知する。
  • M(Modified)からの挙動。Hitのみを考える。
    • CPUでRead Hitが発生する場合、特に何もせず、データをCPUに返す
    • CPUでWrite Hitが発生する場合、既に書き込み権限を持っているので、特に何もせず、データを更新する。

バス側からの挙動

以下で説明するRdSnoop/WrSnoopというのは、他コアが当該ブロックをRead/Write要求したが存在せず、下位キャッシュに対してブロックを要求し、スヌープバスを通じて自コアに通知されるコマンドのことを言う。 つまり、バスからRdSnoopが来たということは、他コアが当該ブロックを読みたがっている、WrSnoopが来たということは、他コアが当該ブロックに書き込みたがっているということを意味する。

  • S(Shared)からの挙動
    • バスからRdSnoop (Read Snoop)が来た場合、自身のブロックと下位のキャッシュのブロックは一致しているので、自身がデータを転送する必要はない。特に何もしない。
    • バスからWrSnoop (Write Snoop)が来た場合、他のコアが当該ブロックを更新しようとしている。つまり自身のブロックは古くなることが確定しているので、自身のブロックを破棄しInvalidateとなる。
  • M(Modified)からの挙動
    • バスからWrSnoop が来た場合、Sと同じで自身のブロックを破棄しInvalidateする。
    • バスからRdSnoop が来た場合、自身のブロックが最新であるため、このブロックを転送し他コアと共有する。最新のブロックを他コアと共有している状態のため、ブロックの権限をS(Shared)とする。

MESIプロトコル

上記のMSIプロトコルに対して、E(Exclusive)状態を加える。

  • E(Exclusive): キャッシュ内にブロックが存在しているかつ、他コアは当該ブロックを持っていない。この権限では、読み込みは可能だが書き込みはできない。
    • この状態を付け加えることにより、E権限のブロックは他コアが同じブロックを共有していないことが保証されるため、ブロックを保持しているCPUが当該ブロックに書き込む際、システム全体にInvalidateを通知する必要がなくなる。

CPU側からの挙動

E権限に着目して説明する。

  • I(Invalidate)からの挙動
    • CPUでRead Missが発生すると下位キャッシュからブロックを持ってくるが、その時他コアが当該ブロックを保持していない場合、権限をS(Shared)ではなくE(Exclusive)とする。
  • E(Exclusive)からの挙動
    • Read Hitが発生しても特に何もしない。CPUぢデータを返す。
    • Write Hitが発生すると、他コアにInvalidateをブロードキャストせず、権限をM(Modified)に変更する。

バス側からの挙動

  • E(Exclusive)からの挙動
    • バスからWrSnoopが来た場合、他コアが最新の値を書き込むため、当該ブロックをInvalidateする。
    • バスからRdSnoopが来た場合、他コアとデータを共有することになるため、当該ブロックをS権限に変更する。

MOESIは次回にまとめる。

自作CPUのフロントエンドデータ幅とバックエンドデータ幅の分離検討

現在の自作CPUは、簡易的にフロントエンドとバックエンドのデータ幅を一致させている。 例えば、バックエンドのキャッシュラインの幅が64Bであれば、フロントエンドも64Bにしている。 しかし、さすがにフロントエンドのデコードラインで64Bを一気にデコードするのは回路規模的に厳しいので、フロントエンドのデータ幅を削減することを検討する。

基本的にパラメタライズしているのでデータ幅削減は問題ないのだが、ポイントはキャッシュラインの取り込みのバスをどのようにするかだ。 フロントエンドのデータ幅を64Bから16Bに落としても、L2への接続幅は64Bをキープしたほうが簡単なので、基本的にバスの幅を変更はしない。

その代わりに、命令キャッシュのキャッシュラインは64Bをキープしながら4バンクに分割し、キャッシュラインの読み出しリクエストは16B単位で行うようにする。

キャッシュのバンク化の部分の実装最適化はイマイチだが、とりあえず動く構成のRTLを作って、検証はとりあえず流れるようになった。 かなりパラメタライズしておいてよかった。半日以下の作業で済んだ。

とりあえず論理合成にて、あるコンフィグレーションでフロントエンドのデータ幅を16Bから8Bに削減した。データ幅は16Bを維持している。 その結果、フロントエンドの回路面積は34%程度削減できたようだった。ある程度は効果がありそうだな。

削減前

削減後