コンピュータ・アーキテクチャの勉強の一環として、C++を用いた行列-行列積演算の高速化を行ったうちの、「キャッシュメモリ編」として簡単にまとめていきます。
そもそもキャッシュメモリってなんだ？というところから、考察も交えながら勉強したことをまとめているので、間違いなどあればご指摘いただけると助かります。
ひとまず、キャッシュを意識した処理を行うことで、どの程度処理の高速化に効果が表れるのか評価するところまでやってます。
目次
※参考文献は本ページ末尾に記載
キャッシュメモリ概要
結局のところキャッシュメモリがどういったものなのか、現状の理解で図にしてみます。
一般にメモリと呼ばれるものは、キャッシュメモリとは別に「メインメモリ」や「グローバルメモリ」などと呼ばれて区別されることが多いです。パソコンを開けたときに、マザーボードのソケットに刺さっているやつのことを指します。
一方、キャッシュメモリはIntelやAMDから発売されている一般にCPUと呼ばれているものや、Macのアップルシリコン等のSoCの半導体素子の中にあらかじめ組み込まれてます。
役割と動作
処理中に演算器がデータを要求したとき、まずキャッシュメモリにデータの問い合わせを行い、キャッシュメモリ中に対象のデータがない場合、仕方なくメインメモリに問い合わせを行うというような挙動をするためのメモリです。
キャッシュへのデータの格納方法としては、メインメモリへアクセスしたとき、アクセスしたアドレスの近い位置に格納されているデータが、格納されます。これは、直近で利用されたデータは再度利用される可能性が高いことと、直近でアクセスされたデータの近くにあるデータを直後に利用する傾向が高いプログラムの特性を利用した、高速化戦略になっているらしいです。このような傾向を「局所性の法則」などといったりします。
プログラマ側で明示的に指示しなくてもデータは自動的にブロックといわれる単位で格納されてます。
処理を書いていく側としては、処理によってキャッシュ動作に明示的な動作を与えたい瞬間が出てきそうな気がしますが、「キャッシュメモリの挙動に寄り添った処理を書け」というのがプログラマ側に問答無用に要求されるということだと思います。
詳しくは、俗に「パタヘネ」といわれる界隈でよく知られた書籍を読むと詳しく載ってます。
メモリ階層
そもそもメモリはその名前の通りデータを記憶するための装置であり、コンピュータにはいくつかの記憶装置が搭載されることが一般的です。2010年代以降では主に以下のようなメモリが使用されています。
- レジスタ
- キャッシュ
- メインメモリ
- 外部記憶装置（SSD/HDD等）
アクセス時間はあくまで目安ですが、階層間によっては10倍～1000倍ほど速度の違いがあります。ここで、キャッシュはさらにL1（1次キャッシュ）から、L2（2次キャッシュ）といった階層に分けられていることが多いです。これは、マルチレベル・キャッシュと呼ばれている技法で、記憶の階層を増やすことでキャッシュの内に対象データが格納されていない場合のペナルティを低減させることを目的とした技法らしいです。
キャッシュメモリが高速動作する理由
そもそも、キャッシュメモリがメインメモリと比較して高速に動作する原理としては、以下のような理由が挙げられます。
１．プロセッサからの物理的な距離の近さ
人間にとっては、そこまで大きな違いのようには感じませんが、キャッシュメモリに限らず、演算器に物理的に近い位置にある記憶装置は、高速なアクセスが可能であることは、上述したメモリ階層の図からも明らかです。
電気信号が伝送される速度は、光の速度に比べても非常に遅く伝送経路がより短いほうがデータの伝送速度は高速になります。キャッシュに用いられるSRAMは、半導体素子で構成できるため、チップの中にメモリを収めることができ、メインメモリなどに用いられるDRAMと比較して構造的に演算回路の近くに配置しやすい特性もあります。
そのうえで、いくらチップ内に収めにくいDRAMであっても、マザーボード上でメインメモリがCPUに限界まで接近していない場合が散見される理由としては、設計上の制約や冷却の問題などを考慮している場合がどうも多いようです。
キャッシュメモリは、よく本棚に例えらますが、必要になったときに遠くの図書館（メインメモリ）に本（データ）を取りに行くよりも、作業場の本棚に本を置いていたほうが、高速に情報にアクセスすることができるイメージがキャッシュメモリの高速動作イメージです。
２．キャッシュサイズによる特性
いくらキャッシュ上に該当のデータが乗っていても、キャッシュメモリからそのデータを探し出す時間が長くなれば、高速化の効果は小さくなります。
キャッシュサイズが大きくなると、キャッシュ内のデータの配置やアクセス方法が複雑になることでキャッシュ内要素の検索時間が長くなるらしいです。本棚を大きくし過ぎると、該当の情報がその中に存在するか判断するだけでも時間がかかるといった具合らしいです。
ただ、キャッシュメモリの検索方法には、ダイレクト・マップ方式という、探索法でいうところのハッシュ法のような手法？が用いられていることが多いらしいので、なぜキャッシュメモリサイズが大きくなるだけで探索時間が増えるのか？（まだ理解しきれてないです）
３．SRAM,DRAMといったメモリ特性
そもそも、各メモリ自体の構成にも違いがあり、キャッシュメモリはSRAM、メインメモリ（DDR）はDRAMがよく使用されています。
DRAM：
DRAMでは、ビットをコンデンサ（キャパシタ）の充電の有無によって表現し、電荷でデータが保持されています。この蓄えられる電荷にアクセスするために、単一のトランジスタが用いられています。また、コンデンサに蓄えられた電荷は、永久に保持することができず、漏れ出てしまうため、リフレッシュといわれる、電荷を書き直す動作を定期的に行わなければいけません
SRAM：
SRAMでは、ビットを記憶構造をした集積回路（例：フリップフロップ）で表現し、電圧でデータが保持されています。電力が供給されている限り、データを保持することができるため、リフレッシュ動作の必要がなく、アクセス時間はサイクル時間に非常に近くなります。また、SRAMセルは対象型になっており差動信号処理を行うことで、ノイズによる誤動作を減らしたより安定した動作と、より少ない電圧の変化を容易に検出することによる高速な動作を可能としています。
すべてSRAMにできない理由
そこまでSRAMの動作が高速であるならDRAMを廃止して、すべてをSRAMにすればいいように思いますが、そうは現状なっていない理由として、以下のようなものがあります。
まず、DRAMがコンデンサに電荷を蓄えることで、ビットを保持しているという話がありましたが、DRAMの内部セルは以下のように構成されます。
単一のトランジスタにキャパシタが1つの非常にシンプルな構成です。このようなシンプルな構成ゆえに、高集積化が簡単でビットあたりの単価が安いです。
一方、SRAMは2つのインバータとデータの読み出し/書き込みのためのMOSトランジスタといった集積回路（例：フリップフロップ）によってビットを保持しています。1ビットを保持するにあたり、6～8個のトランジスタを必要とします。下の例では6個です。
複数のトランジスタを使用することからも分かるように、同じシリコンダイの面積中に乗せることのできるセルの数は、DRAMに比べて少なく高集積化は望めないと言えます。つまり、ビット当たりの単価も高くなることが分かります。
以上のような、金銭的なコストや面積上の制約などから、DRAMはメインメモリに、SRAMはその補助的なキャッシュに使われているようです。
評価に用いる行列-行列積（GEMM）
全ての要素に値を入れた密な行列AとBを入力として行列の積（General Matrix Multiply）を計算し、結果として行列Cを出力する処理を考えます。例を示すと以下のような処理です。
前提条件として「行列Ａの列数＝行列Ｂの行数」となっていることが挙げられます。得られる結果の行列Ｃの大きさは、「行×列」＝「行列Ａの行数×行列Ｂの列数」です。
行列積演算では、複数の配列により行列の要素を格納するので、多数のメモリアクセスが発生し、キャッシュメモリによる処理速度の差が表れやすい処理だと考えられます。
このような行列のデータ構造は、画像処理にも応用できるはずです。
キャッシュを意識したコード
実際、直近で近いアドレス位置にあるデータが近い時間に利用されるという性質は多くの場面で当てはまることが多いので、キャッシュメモリ格納の動作が近いアドレスのものが格納されるようになっているのでしょうから、このような性質に合わせてコードを考える必要があります。
データ構造
メモリの確保を行って、そこに行列データを用意していきます。
/* メモリ確保 */
int** a; // 入力行列A InputMatrixA
int** b; // 入力行列B InputMatrixB
long** c; // 出力行列C OutputMatrixC
// 行先頭位置
a = (int**) malloc(sizeof(int*) * ROW_A);
b = (int**) malloc(sizeof(int*) * ROW_B);
c = (long**) malloc(sizeof(long*) * ROW_A);
// 行配列
for(size_t i=0; i<ROW_A; i++) {
a[i] = (int*) malloc(sizeof(int) * COL_A);
c[i] = (long*) malloc(sizeof(long) * COL_B);
}
for(size_t i=0; i<ROW_B; i++) {
b[i] = (int*) malloc(sizeof(int) * COL_B);
}09～16行目で各行の要素を格納する行数個の配列をそれぞれの行列ぶん確保し、06～08行目で各行の配列先頭位置を格納する配列を確保しています。図にすると以下です。
疎行列などの特別な行列であれば、格納形式にも様々な方式があるようですが、今回は密行列なので特に工夫もなくメモリを確保しています。しいて意識するなら、メモリアクセスがランダムにならないようにメモリアライメントに気を使っておくべきなのかもしれませんが、今回はmallocの仕様に任せています。
計算精度
桁あふれを一応考慮して、Int型（4Byte）で入力行列を用意してlong型（8Byte）で計算結果を保持します。
キャッシュ考慮
上記で説明した行列-行列積の計算を行っています。コードの全文は、以下Githubに置いています。
https://github.com/sukima-log/parallel_test
キャッシュを意識していないコード
for(size_t i=0; i<ROW_A; i++) {
for(size_t k=0; k<COL_B; k++) {
for(size_t j=0; j<ROW_B; j++) {
c[i][k] += (long)a[i][j] * (long)b[j][k];
}
}
}キャッシュを意識したコード
for(size_t i=0; i<ROW_A; i++) {
for(size_t j=0; j<ROW_B; j++) {
for(size_t k=0; k<COL_B; k++) {
c[i][k] += (long)a[i][j] * (long)b[j][k];
}
}
}ここで、キャッシュの「局所性の法則」を意識したコードは、一見、考慮前とほとんど変わっていないようにも見えますが、02行目と03行目が入れ替わっています。これによって、最内ループで別の配列を飛び回りながら処理するといった動作がなくなりました。
これにより、出力行列Cの特定行の各要素を少しずつ更新しながら最終的に結果が確定するといった動作をします。このような処理の順序は人間が紙とペンを使って行列の積をするときには、すさまじい記述量となるため直感的に行わない処理ですが、記憶領域を更新していくコンピュータにとっては問題とはなりません。
メモリ律速
処理部に比べて、メモリからの読み出し速度が処理全体のボトルネックとなるとき、これを「メモリ律速」といい、メモリアクセスの速度が全体の処理時間に大きな影響を与えます。
現行のCPUでは、一般的に処理速度に比べてメモリからの読み出し速度が遅い場合が多いので、キャッシュメモリを効率よく用いることで処理の高速化が期待できるはずです。
今回のキャッシュメモリを用いた高速化手法では、キャッシュのヒット率（キャッシュ内で見つかる確率）を上げて、ミス率（キャッシュ内で見つからない確率）を下げることで、処理の高速化を狙っています。
速度評価
実装環境
main: main.o
g++ -o main -O2 -mcmodel=medium -std=c++11 -Ofast -fopenmp main.o
main.o: main.cpp
g++ -c -O2 -mcmodel=medium -std=c++11 -Ofast -fopenmp main.cpp
時間計測
図 行列サイズ変化による行列-行列積時間
処理時間を対数グラフにしているので、分かりやすいかと思いますが比較的大きな行列を用いた演算では実行時間に10倍以上の差があることが分かります。
キャッシュを意識するだけで、処理時間に体感できるほどの差が生じたことから、キャッシュメモリの存在を理解して処理を記述していく重要性をなんとなくでも感じることが出来ました。
高速化率が多少前後しているのは、データのやり取りの単位であるブロックサイズであったり、キャッシュメモリのサイズであったりするところが関係しているのかな？と現状では考えたりしてます。
キャッシュヒット率などを「pref」を用いて測定できるらしいですが、wsl2環境ではどうもできないらしいので今回は残念ながら測定できていません。
まとめ
今回の行列-行列積のような線形代数演算などの処理には、BLASなどのライブラリを用いるのが基本的に最速らしいので、今回のような処理を1から書く機会は少ないかもしれません。
ひとまず「キャッシュとか言われる高速なメモリがあって、使い方によっては高速な処理ができるんだなぁ」くらいに頭の隅に置いておくことが大切なんだろうなぁと思います。
参考：
"コンピュータの構成と設計 第5版 下",デイビッド・A・パターソン and ジョン・L・ヘネシー
"図説電子デバイス",菅, 博 and 川畑敬志 and 矢野満明 and 田中, 誠
ありがとうございました。これらに並列化を施したものも別途まとめています。
