オリジナル16ビットCPUコアMoscoviumに、FPGAボード(Sipeed Lichee Tang Primer)に内蔵されたSDRAMを接続してみました(こちら↓)。
「#19-7 SDRAMを使って見よう（１）」
「#19-8 SDRAMを使って見よう（２）」
「#19-9 SDRAMを使って見よう（３）」
SDRAMは96MHzで駆動したのですが、Moscoviumは24MHz動作なため、アクセスサイクル数はリード3サイクル、ライト2サイクル@24MHzと、内蔵RAM(リード／ライト共1サイクル@24MHz)に比べると少し遅めでした……。
まあ、良いのですよ。メインメモリは遅いもの、と相場が決まっているので。3サイクルリードと言うスピードよりも、8Mバイトと言う圧倒的なメモリ容量が特長なのですから。
PC等では、メインメモリの遅さをキャッシュメモリと言う装置で補っています。
こんなこと(↓)をしてくれる装置です。
本来、3サイクル掛かるリードアクセスが、1サイクルに短縮されるので、メモリアクセスが高速化したように見えます。これがキャッシュメモリの働きです。
「言うは易し」なんだけど、ハードウェアでこれを実行するには、どうしたら良いのか？って事です。
アドレスの検索方法について考えてみましょう。
フルアソシアティブ方式は、ヒット率が高いらしいです。
ただ、キャッシュの空き領域を探したり、キャッシュ内に目的のアドレスが記録されているかどうか検索するためのコストが大きいので、あまり使われないみたいです。
よく採用されている方式は、セットアソシアティブ方式ですので、これを採用します。以下、ブロック図です。
索引を作って、索引にアドレスが登録されているかどうか？を検索するひとまとまりの回路をウェイと呼びます。上図はウェイを2個持った、2ウェイセットアソシアティブ方式のブロック図となっています。PC等の用途では、4ウェイとか、もっと大きなウェイ数が選択されることも多いです。
今回、Moscovium用としては2ウェイを選択します。
セットアソシアティブ方式では、まず、アドレスを3つの部分(ビットフィールド)に分割します。下位ビットから順に、ライン／インデックス／タグの順です。
ブロック図に戻って、TAGアレイとデータアレイがRAMです。
NidxやNlin等のパラメータによって、必要なRAM容量が決まります。
RAM容量は有限なので、ターゲットとするRAM容量を決めると、ほぼ自動的にパラメータは決定できます。
※「自動的」は言い過ぎかも？？多少の自由度はあります（１＾＿＾；）。
今回は、キャッシュメモリ容量を4Kバイトとして、以下の様に決めました。
2ウェイなので、トータルでは上の計算値×2ウェイが、必要なRAM容量となります。データアレイ用RAM容量は、狙い通り4Kバイトとなりました。
データアレイ用RAMには、TD IDEのRAMマクロを使います。
一方、TAGアレイ用RAMは、バイト数換算で208バイト/ウェイと小さいため、普通にフリップフロップF/F等を使って作る場合も多いです。今回は、TD IDEの分散RAMを使います。
動作を追いながら、キャッシュメモリの動き方を説明します。
この動作(ミスした時も、ヒットした時も、両方)は、キャッシュメモリ処理のクリティカルパスとなります。必要以上に余計な論理を挟まないように注意して設計しなくてはなりません。コンパイル(論理合成・配置配線)後、STAでタイミングメットすることを確認できたら一安心です。
キャッシュメモリコントローラがカバーする領域は、以下図に示す24ビットアドレス空間の中で、SDRAM領域(8Mバイト)のみとします。
64Kバイト空間内のROM／RAMやI/Oレジスタなどは全て1サイクルアクセスなので、キャッシュメモリの出番はありませんし、24ビット空間内のリザーブ領域には、今のところアクセス可能なメモリが存在しないためです。
実はTAGアレイには、そのエントリが有効かどうかを示す、Vビットが必要です。
キャッシュメモリのカバー範囲をSDRAM領域に限定したことで、有効なTAGアドレスは、常に最上位ビット＝1となります。TAGアドレスの最上位ビットを記録する必要がなくなったため、このビットをVビットに割り当てることとします。
キャッシュメモリには、高速アクセス可能なSRAMが使われます。SRAMは高速だけど面積が大きいので、小容量なのが特徴です。なので通常、SRAMを使ってSDRAM全体をカバーすることはできないし、万一カバーできる様ならSDRAMは要りません。
この様に、キャッシュメモリのRAM容量は限られているため、暫く使っていると空き領域がなくなってしまいます。この場合、どこかの領域を解放(パージ)して、新しいTAGアドレスとデータを上書き(フィル)することで、動作を継続します。
複数のウェイを持っている場合、どのウェイをパージするか選択しなければなりません。パージするウェイを決めるポリシィとして、以下の様な選択肢があります。
ラウンドロビン＜ランダム＜LRU＜LFUの順番で、「ヒット率が向上する」と、言われています。同じ順番で、論理の複雑さや規模も増大します。
今回は2ウェイなので、それほど難しい論理にならないと見て、LFUを選択しました。以下、詳細に検討を進めます。
2の補数表現で符号付整数を表現する場合、カウンタの正負は最上位ビットだけで判定できるため、判定は高速に終了します。ここ、クリティカルパスの一部なので、速さは重要なのです。もたもたしていると、STAでバイオレーションを発生しかねません。
本節ではLFUカウンタのサイズ(ビット数)について考察します。
例として、文字列データのアクセスを考えます。
文字列データはウェイ1に格納されているとします。この文字列と別な文字列を比較するケース(strcmp()関数相当の処理)を考えてみましょう。
strcmp()関数では、文字列の先頭からシーケンシャルにデータを読み出して行きます。1ライン(16バイト)すべてが文字列データだった場合、16回のバイトアクセスが発生するのでLFUカウンタが＋16加算されます。文字列データだとすると、一回のシーケンシャルアクセスが終わったらそのデータは用済みで、暫くの間はアクセスされない可能性が高いです。
もし、逆のウェイ0に、もっとアクセス頻度の高いデータが記憶されていた場合、文字列処理のシーケンシャルアクセスによってLFUカウンタがひっくり返ってしまう様では、誤判定してしまうことになります。
従って、LFUカウンタは少なくとも絶対値16を超える数値をカウントできる必要があります。即ち符号無4ビットを超えるカウンタが必要です。かつ、カウンタ値は正負の値を取る符号付きなので、最低でも符号付5ビットを超えるカウンタが必要となります。即ち符号付6ビット以上です。
今回は、6ビット＋マージンに切り良く符号付8ビットのカウンタを使うことにしました。従って、LFUカウンタに必要なメモリ(RAM)は、8ビット×Nidx＝128バイトとなります。
このRAMも、RAMマクロを使うほどのサイズではないので、分散RAMを使いました。
※RAMマクロだと、最小サイズが1Kバイト程なので、128バイト程度だと、だいぶ余らせてしまって勿体ないです。しかも、LFUカウンタには読み出しレイテンシ0が必要なので、RAMマクロ(読み出しレイテンシ1)では機能的にも不足です。
キャッシュミスした時、前節の方法(LFU)でパージするウェイを選択したら、次はキャッシュフィルを実行します。
キャッシュフィルとは、SDRAMからデータを読み出してキャッシュメモリ内のデータアレイに書き込むことです。読み書きするデータは1ライン分であり、今回の例だとNlin＝16バイト＝4ロングワードとなります。
FPGAボードのSDRAMは32ビット品で、リード4バーストモードを選択しているので、丁度32ビット×4バーストリード＝16バイトです。1ライン分を1回のバーストリードで読み出すことができます(実は、そうなるようにラインサイズNlin＝16を決めた)。
折角4サイクル@96MHzで読み出したデータを、16ビット@24MHzのメモリバス経由で転送したらロスが大きすぎるので、少し知恵を絞りました。
キャッシュメモリのデータアレイには、デュアルポートRAMを使います。
16バイトのデータ転送は4サイクル@96MHzで完了します(下図)。
上図タイミング図について解説します。
キャッシュメモリコントローラ自体は、CPUと同じ24MHzで動作しており、データアレイへの書き込みだけが96MHzとなります。データアレイ(デュアルポートRAMマクロ)に書き込むのはSDRAMCなので、キャッシュメモリコントローラ自体に96MHzクロックで動作する回路はありません。
普通にSDRAMへアクセスした時がリード3サイクルアクセスなので、キャッシュミス時のペナルティはわずか1サイクル@24MHzと爆速です。
キャッシュヒット率をRhit[%]とすると、平均アクセスサイクル数は、4サイクル×(1−Rhit)＋1サイクル×Rhitで計算できます。キャッシュ無効の場合はリード3サイクルアクセスなので：
4×(1−Rhit)＋1×Rhit＜3 より、
Rhit＞約33% で、キャッシュを使った方が高速。
ヒット率Rhit＞75%とか言われると、「う〜ん、そんなにヒット率高いかな〜？」と、自信はないけど、Rhit＞33%なら、普通はクリアするんじゃないかな？
SDRAMアクセスには、リードだけでなく、ライトアクセスも発生します。
ライトアクセスが発生した時、キャッシュメモリだけに書き込む方式と、SDRAMとキャッシュメモリの両方に書き込む方式が存在しています。
前者をライトバック方式、後者をライトスルー方式と呼びます。
ライトアクセスがあると、キャッシュメモリのデータアレイだけにデータを書き込みます。
暫くの間、SDRAMのデータとキャッシュメモリ内のデータが不一致の状態で処理が進みます。
書き込んだアドレスからのリードアクセスが発生すると、書き込んだ新しいデータがキャッシュメモリ上に存在しているため、そのまま、キャッシュメモリから読み出して、CPUにデータを渡します。
暫くして、キャッシュメモリのデータをパージする必要が生じると、データアレイ内のデータをSDRAMに書き戻す必要があります(ライトバック)。CPUからのライトアクセスで書き込んだデータは、キャッシュメモリにだけ書き込まれていてSDRAMには書き込まれていないからです。
ライトバック(パージ)した時点でようやく、SDRAMへ新しいデータが書き込まれることになります。
ライトアクセスがあると、それをSDRAMとキャッシュメモリの両方に同時に書き込みます。
書き込んだアドレスからのリードアクセスが発生すると、書き込んだ新しいデータがキャッシュメモリ上にも存在しているため、そのまま、キャッシュメモリから読み出して、CPUにデータを渡します。
暫くして、キャッシュメモリのデータをパージする必要が生じても、書き込む時、同時にSDRAMにも書き込んでいるので、キャッシュメモリ内のデータとSDRAM内のデータは一致しており、そのまま(何もせずに)パージ可能です。
ライトバック方式の方が、ライトアクセス時のアクセスサイクル数が短くなるので、スピード的には有利です。とか言いながら、ライトスルーの方が制御(従って回路)が圧倒的に簡易なので、今回はライトスルー方式を採用します。
ライトスルー方式のタイミング図を下図に示して解説します。
キャッシュメモリコントローラの基本設計までを駆け足🏃で終わらせました。残りは次回に回します。
