導入
コンピュータアーキテクチャの教科書は数あれど、マルチコア、特にキャッシュコヒーレンス・プロトコルについて詳細に述べているものは多くありません。 ことMESIプロトコルについては、「MSIプロトコルにExclusive状態を導入する」という一言と二、三段落の解説で済まされている場合があります。
一方で、MESIプロトコルと呼ばれるキャッシュコヒーレンス・プロトコルには、少なくとも三通りの異なる実装方法が存在します。 本記事では、初めにMESIの四状態を概観したのち、代表的な三つの実装を紹介します。
筆者はこの記事の影響を受けています。 併せてご覧ください。
また、本記事の内容の一部はWikipediaの"List of cache coherency protocols"を参考に執筆しています。 これは著名なキャッシュコヒーレンス・プロトコルを網羅しているだけでなく、設計上の選択肢を網羅的に説明しています。 ぜひご覧ください。
MESIプロトコル
MESIプロトコルとは、キャッシュラインにM (modified), E (exclusive), S (shared), I (invalid) の四状態を用いるキャッシュコヒーレンス・プロトコル、またはそのようなプロトコルの総称です。 このような四状態を用いるモチベーションは実装ごとに大きく異なるものではありませんが、各状態の厳密な意味や状態遷移には違いがあります。
一部の文献は"a MESI-based protocol"とか"a variant of MESI protocols"とかといった表現を用いて、複数のうちの一つを用いることを強調します。 また、次に述べる具体的な名称でプロトコルを指定するものもあります。 しかしながら、単に「MESIプロトコル」とだけ書いて具体的にどう実装しているかの説明を欠く文献も存在します。 そのような文献に出会うと、筆者は「どれのことや」と頭を抱えます…。
筆者は、MESIの四状態を用いるプロトコルの設計上の選択肢を認識している人が一人でも増えることを願っています。 その道標になるよう、本記事では各プロトコルの特徴を概説するとともに、出典や背景も紹介します。
本記事で紹介するMESI四状態プロトコルは以下の三つです。
- Write-onceプロトコル
- Illinoisプロトコル
- 商用プロセッサのMESIプロトコル
Write-onceプロトコル
Write-onceプロトコルは「最初のMESIプロトコル」とか「古典MESIプロトコル」とか呼ばれるプロトコルです。 発表は1983年のISCA*1 およびSpring COMPCON*2です。 初めて共有バス型マルチプロセッサ*3に導入されたキャッシュコヒーレンス・プロトコルとされています。 マルチプロセッサの性能向上に加え、SMP型マルチプロセッサの実現可能性に対する貢献があり、SMP型マルチプロセッサ (コア) が一般的となった現代社会の礎を築いたといっても過言ではないでしょう*4。
Write-onceには、以下のような背景があります。
- 既存の共有バスをそのまま使いたい
- 特殊なトランザクションを必要としたくない
- 従来型キャッシュのデータ更新方式におけるトレードオフに対処したい
- Write-throughはキャッシュコヒーレンスの維持が容易だが、共有バスへの書き込みトランザクションが多い
- Write-backは共有バスへの書き込みトランザクションが少ないが、キャッシュコヒーレンスの維持が難しい
Write-onceは、Write-throughとWrite-backの中間的なデータ更新方式といえます。 データ更新方式自体がプロトコルという印象です。 ストア命令の度に書き込みトランザクションを発行するwrite-throughに対して、write-onceはあるキャッシュラインにおける最初のストアに対してのみトランザクションを発行します。 このトランザクションをスヌープすることで、他のキャッシュたちは当該キャッシュラインを無効化できます。 その後同一のラインに対して行われるストアは、write-backと同様にトランザクションを発行しません。 その結果、write-throughのように簡単にキャッシュコヒーレンスを維持しつつ、write-backのように書き込みトランザクションの発生を抑制できます。
設計上の選択肢として、write-allocateを行うかが挙げられます。 上記の論文では、ミス率とバスのトラフィックの観点からwrite-allocateを行うのが望ましいと述べられています。
CPUのキャッシュではあまり採用されていない印象のあるwrite-onceプロトコルですが、最近の採用例もあります。 例えば、CXLをEthernetに載せてRDMAっぽいことをする研究*5でwrite-onceが用いられているようです。
Illinoisプロトコル
Illinoisプロトコルは、現在主流となっている様々なキャッシュコヒーレンス・プロトコルのベースとなるプロトコルといえます。 発表は1984年のISCA*6です。
Write-onceはdirtyなキャッシュラインの書き戻しに加えて最初のストア時に必ず書き込みのトランザクションを引き起こすのでした。 一方で、Illinoisプロトコルでは、自身がストア対象のラインを保持する唯一のキャッシュだと明らかな場合 (M状態またはE状態) に、書き込みのトランザクションを発行せずキャッシュに書き込んで完了とします。 ここで、E状態へは、読み出しミスの際に他の全てのキャッシュに当該ラインが存在しないことを確認することで遷移します。 結果として、書き込みのトランザクションを抑制できます。 さらに、read-modify-writeなどの不可分操作の実装も比較的簡単になります。
また、IllinoisプロトコルではI状態以外のすべての状態 (M, E, S) において、読み出しのトランザクションを検出してキャッシュからデータを供給します。 このとき、メインメモリ*7へのアクセスを中断したり、読み出し結果を破棄したりします。 この動作を介入 (intervention)などと呼びます。 典型的なメインメモリはキャッシュに比べて遅いため、キャッシュからのデータ供給が性能向上に寄与します。
このように、Illinoisプロトコルの設計は非常に素朴です。 一方で、効率的な動作にはバスとの協調が重要です。 特に、複数のキャッシュがS状態のラインをバスに供給する際の調停に、設計上の選択肢が生じ得ます (後述)。 それでもやはり、キャッシュコヒーレンス・プロトコル単体で見たときのシンプルさが後世のプロトコル設計に影響を与えているといって差し支えないでしょう。
商用プロセッサのMESIプロトコル
これは、Pentium IIやPowerPC 604などの商用プロセッサに実装されたキャッシュコヒーレンス・プロトコルです。 Pentium IIは1997年に登場したプロセッサで、そのアーキテクチャを記述した書籍*8にてこのプロトコルの動作が説明されています。 PowerPC 604は1994年に登場したプロセッサです。
状態遷移図からもわかるように、このプロトコルの動作はIllinoisプロトコルにかなり似ています。 これらの違いとしては、キャッシュラインをキャッシュ間で融通する状態を制限するかどうかが挙げられます。
IllinoisプロトコルはM状態、E状態、そしてS状態のキャッシュラインをバスに共有し、キャッシュ間でデータを転送することで性能を向上するのでした。 一方で、このプロトコルは、S状態のラインを要求元のキャッシュに渡しません。 さらに、実装によってはE状態やM状態のラインさえもキャッシュ間で共有しません。 文献によると、Pentiumの実装ではM状態のラインのみを共有し、PowerPCの実装ではすべての読み出し要求をメインメモリが捌いたようです。
筆者はこのような設計を取る決定的な理由を理解していないのですが、以下のような背景があると想像します。 あくまで想像であることをご了承ください。
- キャッシュ間共有のための信号線をバスに実装するのが物理的に困難である。
- キャッシュ間でデータを共有する際の消費電力が無視できない。
- 複数のキャッシュがS状態のラインを保持し得るため、どのキャッシュからの応答を利用するかといった選択が生じ*9、コストに見合わない。
- 非同期バスをまたぐデータ共有にかかる時間が決定論的でない。
- 特に、コアの動作周波数が動的に変化する構成ではなおさら。
さて、M状態のデータは最新のものですから、キャッシュ間で共有しなければならないような気がします。 PowerPCがM状態でもキャッシュ間の転送を行わず、メインメモリからデータを読み出しても問題が起きないのは、読み出しトランザクションをスヌープしたときに暗黙のwrite-back (implicit write-back)が生じるためです。 シングルコアでは、write-backはキャッシュラインの追い出し時にdirtyだった場合に生じるものでした。 Illinoisプロトコルとその系譜を継ぐプロトコルでは、スヌープによってキャッシュラインがM状態からS状態を遷移させる際にもwrite-backを引き起こし、メインメモリとキャッシュの一貫性を維持します。 Write-backが完了すれば、メインメモリのデータは最新ですので、それを読み出せばよいわけです。
まとめと今後の課題
本記事では、MESIプロトコルと呼ばれることのある三つのキャッシュコヒーレンス・プロトコルを紹介し、それぞれの特徴と設計上の選択肢を説明しました。 実装上の課題と得られる利益 (性能etc...) を天秤にかけ、どのような選択を取るか決めていくことが重要でしょう。
今後はIllinoisプロトコルの系譜をたどり、MOESIプロトコル、MESIF (MERSI) プロトコル、そしてMDOEFSIプロトコルなどについて調査を行いたいと考えています。 また、筆者は現在マルチコアRISC-Vコンピュータを開発中です。 半年くらい放置しているので、さっさと復活したいところです。 よろしければご覧ください。
*1:James R. Goodman. 1983. Using cache memory to reduce processor-memory traffic. In Proceedings of the 10th annual international symposium on Computer architecture (ISCA '83). Association for Computing Machinery, New York, NY, USA, 124–131. https://doi.org/10.1145/800046.801647
*2:C. V. Ravishankar and J. Goodman, "Cache implementation for multiple microprocessors," Digest of Papers, Spring COMPCON 83, IEEE Computer Society Press, March 1983.
*3:当時は1プロセッサあたり1コアが一般的でした。マルチプロセッサはプロセッサを搭載した複数のボードを接続したり、一つのボードに複数のプロセッサを搭載したりして実現されていました。
*4:記述を読むとこのころはNUMAっぽいシステムが一般的だったようです。
*5:C. Wang, K. He, R. Fan, X. Wang, W. Wang and Q. Hao, "CXL over Ethernet: A Novel FPGA-based Memory Disaggregation Design in Data Centers," 2023 IEEE 31st Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Marina Del Rey, CA, USA, 2023, pp. 75-82, doi: 10.1109/FCCM57271.2023.00017.
*6:Mark S. Papamarcos and Janak H. Patel. 1984. A low-overhead coherence solution for multiprocessors with private cache memories. In Proceedings of the 11th annual international symposium on Computer architecture (ISCA '84). Association for Computing Machinery, New York, NY, USA, 348–354. https://doi.org/10.1145/800015.808204
*7:キャッシュを階層化する実装では下位のキャッシュです。
*8:Tom Shanley and CORPORATE MindShare, Inc. 1998. Pentium Pro and Pentium II system architecture (2nd ed.). Addison-Wesley Longman Publishing Co., Inc., USA.
*9:Illinoisプロトコルの文献では、デイジーチェーンのような優先度付きネットワークを用いて選択することが提案されています。
