はじめに
コンピュータの処理速度・処理性能を向上させるには、CPUのコア数や周波数などが重要ですが、
高速なメモリアクセスも不可欠です。その中でも、CPUキャッシュは特に重要な役割を果たしています。
本記事では、このCPUキャッシュの仕組みや重要性について詳しく解説し、
コンピュータシステム全体の性能向上にどのような影響を与えるかを探求します。
さらに、CPUキャッシュの基本動作から具体的な利用方法、課題とその解決策までを幅広く取り扱います。
CPUキャッシュの重要性を理解し、その効果的な活用法について深く考察していきましょう。
CPUキャッシュの基本
概要
CPUキャッシュは、CPUとメインメモリ（RAM）の間に位置する高速なデータストレージで、
一般的にSRAM（Static RAM）を使用してます。
その主な役割は、CPUが頻繁にアクセスするデータや命令を一時的に保存することです。
これにより、CPUは必要な情報を素早く取得でき、処理速度が向上します。
CPUキャッシュの概要
※ALU：算術論理演算器
メモリ階層とキャッシュの位置づけ
CPUキャッシュには複数のレベル（L1,L2,L3など）があり、それぞれ異なる速度と容量を持っています。
CPUコアに最も近いレベルのキャッシュはL1キャッシュであり、最も高速ですが容量は小さいです。
L1キャッシュ、L2キャッシュ、L3キャッシュと階層的に配置されており、
L3キャッシュ以降は各CPUコアと共有されることがあります。
また、最後（最後段）のキャッシュをLLC（Last-Level-Cache、Longest-Latency-Cache）と呼びます。
LLCはメインメモリに最も近く、全てのCPUコアで共有される最後のレベルのキャッシュです。
CPUによって異なりますが、一般的に各レベルのキャッシュの速度と容量は、
以下のようなヒエラルキーになります。
性能とエネルギー効率のカギ
CPU キャッシュの存在は、計算機の性能向上に大きく寄与しています。
頻繁にアクセスするデータを高速に取得でき、メインメモリへのアクセス回数を減らすことができます。
これにより、プログラムの実行速度が向上し、システム全体の応答性が向上しています。
また、CPUキャッシュはエネルギー効率にも貢献しています。
メインメモリへのアクセスに比べて消費電力が少ないため、省電力化にも役立っています。
CPUキャッシュの動作
基本動作
CPUキャッシュの基本的な動作原理には、キャッシュヒットとキャッシュミスという概念があります。
キャッシュヒットは、CPUが必要なデータをキャッシュ内で見つけることができた場合を指し、
データアクセスが成功したことを示します。
一方、キャッシュミスは、CPUが必要なデータをキャッシュ内で見つけることができなかった場合を指し、
メインメモリからデータを取得する必要があることを示します。
データの単位と転送
CPUキャッシュは、メインメモリからデータを転送する際、
キャッシュラインと呼ばれる固定サイズのデータ単位で操作します。
メインメモリからキャッシュへのデータ転送はキャッシュライン単位で行われるため、
1つのデータを取得すると、周囲のデータも一緒に取得されます。
データの選別と置換
キャッシュが一杯になった場合、新しいデータを格納するために古いデータを置き換える必要があります。
この際に使用されるのが置換アルゴリズムです。いくつか代表的なアルゴリズムを紹介します。
- LRU（Least Recently Used）
最近最も使用されていないデータを置換するアルゴリズム - FIFO（First In, First Out）
最初に格納された最も古いデータを置換するアルゴリズム - ランダム
ランダムに選択して置換するアルゴリズム
それぞれのアルゴリズムには、独自の特性と優劣があります。
キャッシュの置換アルゴリズムを理解することで、キャッシュの効率的な運用と性能最適化ができます。
アルゴリズムのメリットとデメリット
それぞれの置換アルゴリズムについて、メリットとデメリットを簡単にまとめます。
| メリット | デメリット | |
| LRU | 優れたキャッシュヒット率： 最も最近使用されていないデータを置換するため、より頻繁にアクセスされるデータがキャッシュに保持されやすくなります。 データ局所性を考慮： 最近使用されたデータが再度アクセスされる可能性が高いため、データの局所性を考慮したキャッシュヒットが期待できます。 |
実装の複雑さ： 最も古いアクセスされたデータを特定する必要があるため、実装が複雑になります。 遅いアクセス時間： 最も古いデータを特定するための追加的な処理が必要であり、アクセス時間が遅くなる可能性があります。 |
| FIFO | 実装が容易： キャッシュ内のデータがキューのように扱われるため、実装が比較的簡単です。 予測可能な振る舞い： キャッシュの置換が常に最も古いデータに対して行われるため、予測可能な動作が期待できます。 |
データ局所性を無視： 最も古いデータが置換されるため、最近アクセスされたデータが頻繁に置換される場合があります。 低いキャッシュヒット率： 最も古いデータが優先的に置換されるため、キャッシュヒット率が低下する可能性があります。 |
| ランダム | 単純な実装： ランダムにデータを選択するため、実装が非常に単純です。 データアクセスパターンに左右されない： データのアクセスパターンに影響を受けず、公平なキャッシュ置換が行われます。 |
不均一な置換： ランダムに選択されるため、キャッシュ内の重要なデータが置換される可能性があります。 予測不可能な性能： アクセスパターンに応じて最適なキャッシュ置換を行わないため、性能が一定しない場合があります。 |
CPUキャッシュの効率的な利用方法
これまでの解説で、CPUキャッシュのヒット率を上げれば性能が向上することが分かりました。
ここでは、どのようなことに注意すればヒット率を向上できるのかをご紹介いたします。
局所性
CPUキャッシュにおける「局所性」は、データ局所性と命令局所性の2つがあり、
CPUキャッシュの効率的な利用に不可欠な概念となります。
データ局所性は、プログラムがアクセスするデータが時間的または空間的に集中していることを示し、
命令局所性は、プログラムが頻繁に実行する命令が集中していることを示します。
これらの局所性を最大化することで、CPUキャッシュのヒット率を向上させ、
性能を最適化することができます。
コーディング手法
CPUキャッシュの効率的な利用を目指したプログラミング手法のことを
「キャッシュフレンドリーなコーディング手法」と言います。
これには、データの局所性を最大限に活用するようなアルゴリズムやデータ構造の選択、
メモリアクセスパターンの最適化などが含まれます。
また、データの配置やアクセス方法を最適化することで、キャッシュミスを減らし、
プログラムの性能を向上させることができます。
例として、QiitaにCPUキャッシュに関する投稿がありましたのでご紹介します。
以下のようなプログラムを記述した場合、どちらの方がCPUキャッシュのヒット率が高くなるでしょうか？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#define LEN (1024*8) int array[LEN][LEN]; int i, j, value; // Type1: 外側の添え字からインクリメントしてアクセス for (i = 0; i < LEN; i++) { for (j = 0; j < LEN; j++) { value += array[i][j]; } } // Type2: 内側の添え字からインクリメントしてアクセス for (i = 0; i < LEN; i++) { for (j = 0; j < LEN; j++) { value += array[j][i]; } } |
正解はType1です。Qiitaの記事によると、Type2との処理速度の差は約 2.5 倍とのことです。
なぜこのようなことが起きるのか、キャッシュラインのことを思い出しながら考えてみましょう。
最初のループで、array[0][0]にアクセスした際、キャッシュラインの仕組みによって
array[0][0...n]がCPUキャッシュに読込まれます。
そのため、次のループでarray[1][0]にアクセスするより、array[0][1]にアクセスした方がキャッシュのヒット率が向上し、処理性能が最適化されるというカラクリです。
ハードウェアとソフトウェアの連携
CPUキャッシュの最適化とチューニングは、ハードウェアとソフトウェアの連携によって行われます。
ハードウェアの側面では、キャッシュのサイズやアーキテクチャ、置換アルゴリズムなどが調整されます。
一方、ソフトウェアの側面では、アプリケーションの設計や実装、コンパイラの最適化などが行われます。
ハードウェアとソフトウェアが相互に連携し合うことで、CPUキャッシュの性能が最大限に引き出され、
システム全体の性能が向上します。
あとは普通に実装すればコンパイラが最適化してくれます。
CPUキャッシュの課題と解決策
その１：マルチプロセッサ環境
マルチコアのプロセッサ環境では、複数のコアが同じデータをキャッシュすることがあります。
キャッシュされた共有のデータは、プロセッサ間でのデータの競合を引き起こし、
キャッシュの効率的な利用や性能の向上を妨げる可能性があります。
そのため、キャッシュコヒーレンシ（一貫性）は、マルチプロセッサ環境において超重要です。
複数のコアが同じメモリ領域にアクセスする場合、それぞれのキャッシュが一貫性を保つ必要があります。
もし、一貫性が欠如している場合、マルチプロセッサの性能や信頼性に大きな影響を与えます。
イメージしやすいように、以下のように3つのプロセッサを備えている場合を考えてみます。
キャッシュコヒーレンシの問題
- CPU1 は変数 x に対して読取り操作を実行し、メモリから値 8 をフェッチしてキャッシュ
- CPU2 も、同様に変数 x を読取り、値 8 をキャッシュ
- CPU1 は変数 x に対して書込み操作を実行し、キャッシュされたコピーを 10 に更新
- CPU3 が、変数 x に対して読取り操作を実行
この流れで処理が実行された場合、最後に CPU3 が読込む値は 8 でしょうか？ それとも 10 でしょうか？
この問題を解決するためには、適切なプロトコルやアルゴリズムを使用して、
複数のキャッシュ間でデータの一貫性を維持する必要があります。
以下に、いくつかの具体的な手法を紹介します。
- コヒーレンシプロトコル
複数プロセッサが同じメモリ領域にアクセスする際にデータの一貫性を保つための手法です。
代表的なプロトコルには MESI（Modified, Exclusive, Shared, Invalid）プロトコルがあります。
各キャッシュエントリが状態管理し、データの読込みや書込みが行われる際に状態を更新します。 - ライトスルーとライトバック
ライトスルーは、データを書込む際にキャッシュを介さずに直接メモリに書込む手法です。
これにより、他のプロセッサが同じデータにアクセスする際に一貫性が保たれます。
一方、ライトバックは、データの書込みがキャッシュに行われ、後でメモリに書込む手法です。
ライトバックはキャッシュの性能を向上させる反面、一貫性を維持するための制御が必要です。 - インクリメンタルチェック
キャッシュの内容を定期的にチェックし、他のプロセッサとの不整合を検出する手法です。
キャッシュ内のデータが他のプロセッサから変更された場合、
それを検出してキャッシュを更新することで一貫性を保ちます。 - ハードウェアとソフトウェアの協調
キャッシュコヒーレンシの実装において、ハードウェアとソフトウェアを協調させる手法です。
ソフトウェア側は、キャッシュの更新や無効化を適切に管理し、
ハードウェア側は、キャッシュコヒーレンシプロトコルなどの機構を提供して一貫性を保ちます。
キャッシュコヒーレンシの実装方法や一貫性の維持に関する具体的な手法は、
実際にはプロセッサ間の通信やキャッシュ制御に関連する様々な技術を組み合わせています。
その２：性能と容量のバランス
キャッシュのサイズとアクセス遅延は、性能と容量のトレードオフの関係にあります。
キャッシュのサイズを増やすことで、より多くのデータをキャッシュに保持できますが、
同時にキャッシュするためのアクセス遅延も増加します。
一方、キャッシュのサイズを減らすと、アクセス遅延は減少しますが、
より少ないデータをキャッシュに保持することになり、性能を向上させづらくなります。
ここで、キャッシュの配置例として、第12世代 Intel CPU の構成を紹介します。
第12世代 Intel CPU の例（出典：Intel.com）
ハイパフォーマンスな P コアは、各コアに L2 キャッシュを備えており、
L3 キャッシュは、全コアで共用するアーキテクチャとなっていることが分かります。
一方、E コアは、4 つのコアで L2 キャッシュも共用してる構成となっています。
性能と容量、および CPU 自体の販売価格が最適となるように設計されています。（と思う。）
さいごに
本記事「CPU のキャッシュメモリ」はいかがでしたでしょうか？
CPU キャッシュは、コンピュータの性能向上に不可欠な要素です。
高速なデータアクセス能力により、プログラムの実行速度を向上させ、
システム全体の応答性を高めることができます。
近年の技術の進化に伴い、CPU キャッシュも大きな変化を遂げています。
新しいアーキテクチャやメモリ技術の導入により、キャッシュの容量や効率が向上し、
性能が飛躍的に向上しています。
また、ハードウェアとソフトウェアの統合による最適化や、
メモリ技術の進歩がキャッシュ設計に与える影響も大きくなっています。
本記事で取り上げた内容をより詳しく学びたい方は、
以下の参考文献などをご参照いただくと、より理解が深まるかと思います。
参考文献
- Gregg, B., 西脇 靖紘 (監修), & 長尾 高弘 (翻訳). (2023). 詳解 システム・パフォーマンス 第2版. オライリー・ジャパン.
- CS 131: Fundamentals of Computer Systems, 2020
- キャッシュヒット、キャッシュミスとは, FUJITSU
- Why iterating through an array like this is inefficient in C, stackoverflow
- C言語 ~ 多次元配列のIndexとメモリアドレス, Qiita
- コーディング時に知ってはおきたい CPU のキャッシュの特性, Qiita
- Game Dev Guide for 12th Gen Intel® Core™ Processor
- Ever wondered how caching works across multiple processors? — Cache Coherence