マルチコアにおけるキャッシュコヒーレンシ方式の簡単なまとめ (1. キャッシュスヌープ方式)

久しぶりににヘネパタ(「コンピュータアーキテクチャ定量的アプローチ第5版」)を読み直していると面白い。少しマルチコアプログラミングについて確認したいことがあったので、マルチコアにおけるキャッシュコヒーレンシを保つための手法についてもう一度勉強し直した。

キャッシュコヒーレンシとは、マルチコアにおけるメモリアクセスの一貫性を保つための仕組み。例えば、複数コアにおいて1つのメモリアドレスに対して処理を行うと、各コアのキャッシュにデータが残っているため最新のデータを取得することができず、処理に矛盾が発生してしまう。

f:id:msyksphinz:20190204011647p:plain — マルチコアにおけるキャッシュ間の矛盾

コア0がある処理を行いメモリに書き込むと、その結果はコア0のキャッシュに書き込む。一方で、コア2も同様にある処理を行い同一メモリに書き込むと、そのメモリの最新の値はコア0のキャッシュの中にあるはずなのに、そのことを知らないコア2は勝手に自分のキャッシュにデータをアップデートする。すると、同じメモリアドレスのはずなのに異なる最新の値が異なるコアのキャッシュに格納されており、結果に矛盾が生じてしまう。

これを防ぐために様々な方法があるが、大きく分けて

キャッシュスヌーピング方式
ディレクトリ方式

の方法が存在する。キャッシュスヌーピングはコア数が少ない時は性能が良いが、スケーラビリティが足りない、一方でディレクトリ方式はコア数が少ない時は性能がいまいち出ないが、スケーラビリティが良くメニーコアで活用されている。

キャッシュスヌーピング方式

各コア内キャッシュは、各キャッシュラインが現在どのような状態であるのかを常に監視する。そのため、キャッシュ内で何らかのアクセスが発生すると、それを「スヌープバス」を通じて各コアにすぬーぷ情報を通知する。その方式に応じて、少しずつキャッシュスヌーピングの方式が異なる。大きく分けて以下のようなキャッシュスヌーピングの方式が存在する。

MSI (Modified, Share, Invalidate)
MOSI (Modified, Owned, Shared, Invalidate)
MESI (Modified, Exclusive, Shared, Invalidate)
MOESI (Modified, Owned, Exclusive, Shared, Invalidate)

いろいろ存在しているが、MSIがもっとも単純な方式、これの性能を上げるためにMOSI, MESI, MOESIなどの方式があると考えてよい。

MSI方式

キャッシュラインの状態は、各コアでのデータの共有状態に応じて Modified, Shared, Invalidate の3状態を取る。キャッシュの状態は、

Modified : データが何も入っていない状態
Shared : データがキャッシュに入っているが、メモリの状態と同じものである。
Invalidate : キャッシュ内データが無効な状態

の3種類に分けられる。

まず、メモリからデータを読み出す。キャッシュにデータが格納され、それは"Shared"状態としてマークされる。

キャッシュ内のデータがアップデートされる。これによりキャッシュ内データは"Modified"状態としてマークされる。

他のコア(コア2)から同じアドレスへのデータ読み込みが発生した場合、スヌープバスを通じて全コアにキャッシュラインの検査要求が入る。このとき、コア0のキャッシュには当該アドレスが入っており、それは"Modified"状態となっている。このデータはいったんメモリに書き戻される。その際、メモリ内のデータとコア0のキャッシュデータは一致するので、コア0内のキャッシュラインは"Shared"に変更される。

そして、コア2はメモリからアップデートされたデータをキャッシュに格納する。このコア2のキャッシュラインは"Shared"としてマークされる。

MOSIプロトコル

MSI プロトコルの問題点は、上記の操作の際にコア2がキャッシュデータをシェアするとき、一度メモリに書き戻しを行ってから、コア2がメモリからデータを読み込むということである。この方式のメリットは、複数コアがキャッシュでデータを共有しているとき、そのデータは必ずメモリに書き戻されており、最新のデータはメモリに存在しているということだ。

しかし、データを共有するにあたり、必ず一度メモリに書き戻さなければならないというのは面倒だ。しかしメモリにデータを書き戻さないと、各コアのキャッシュに格納されている最新のデータを、一体誰がメモリに戻せばよいのかが分からなくなる。これを解決するために、キャッシュの属性に"Owned"という状態を追加する。このOwnedとなっているキャッシュラインは、そのキャッシュがデータの所有権を保持しており、メモリに対して書き戻す責任を持っている。つまり、上記のメモリアクセスの3. 4. の操作において、

他のコア(コア2)から同じアドレスのデータ読み込みが発生した場合、スヌープバスを通じて全コアにキャッシュラインの検査要求が入る。このとき、コア0のキャッシュには当該アドレスが入っており、それは"Modified"状態となっている。このデータを、メモリを介さずにコア0はコア2に通知する。コア2のキャッシュは"Shared"状態となり、コア0のキャッシュラインは"Modified"から"Owned"となる。つまり、最終的にメモリに書き戻す責任はコア0に存在する。

MESIプロトコル

MSI プロトコルにおいて、キャッシュの書き込みが発生した場合、スヌープバスを通じて全コアのキャッシュラインの検査が入る。しかし、もし自分のコアしかそのデータを持っていない場合、いちいちスヌープバスに問い合わせをするのは面倒となる。したがって、そのデータを自分のコアのキャッシュしか持ってないことが分かっている場合、スヌープ操作を省略することができる。このため、「自分のコアしかデータを持っていない状態」としてキャッシュラインに新たに"Exclusive"という状態を設ける。

Exclusiveの状態を検出するためには、コア0がキャッシュに新たにデータを読み込む場合、コア全体に対して渡すスヌープ検査の結果を拡張する。MSI プロトコルでは、コア0のスヌープ操作に対してコア0以外のコアが「完了」(つまり、コア0が問い合わせたデータはメモリに入っていることが保証されている)、という応答を返すのだが、MESIプロトコルでは、コア0の甥合わせに対して「そのキャッシュラインのデータは持っていない」という応答を返すことができる。この応答がすべてのコアから帰ってきた場合、コア0は当該データをキャッシュしている唯一のコアとなるので、メモリから当該データを読み込んだ後、そのキャッシュラインを"Exclusive"として良い、ということになる。