高速化の解説一覧：[link:高速化]
プログラムは，メインメモリとCPUとの間でデータをやり取りしています．特に画像や動画のようにサイズの大きいデータを扱うプログラムはその回数も多くなります．ここでは，その操作の効率化を目的として「キャッシュメモリ」について解説します．
*キャッシュメモリ
メインメモリ上に格納されたデータ（例えば画像データ）を読み出して，CPUで何かしらの演算を行いたいとします．そのためには，一旦データをCPUのレジスタまで運ぶ必要があります．
しかし，バス幅（一度に転送できる容量）やレジスタの容量（せいぜい数十B程度）の都合から，必要な画像データを一度の読み出しでレジスタに格納することはできません．そうなると，小さなデータの単位で何度もメインメモリからデータを読み出す必要があるのですが，それでは時間が掛かりすぎます．
[img:7vds]
{{small:図１}}
そこで登場するのが「キャッシュメモリ」です．
キャッシュメモリは，
・容量はメインメモリより小さいがレジスタよりは格段に大きい（数kB~数MB）
・読み書きの速度はメインメモリに比べ数倍～十数倍高速
という特徴があり，コンピュータはこのキャッシュメモリを中継地としてデータのやり取りを効率化しています．
[img:r5l7]
{{small:図２}}
例えば，①メインメモリーから画像のある画素のデータ（例：アドレス1000のデータ）をレジスタまで運んだとします．その際に，「メインメモリ上で近いアドレスにあるデータは今後使う可能性が高い」と考えて，ついでにキャッシュメモリまで運んでおきます．②次に，隣の画素のデータ（例：アドレス1001のデータ）を読み出すときは，まずキャッシュメモリをチェックして，そこにデータがある場合はそこからデータを読み出すようにすることで，メインメモリまでアクセスせずに済ますことができます．
この時に重要になるのは，「メインメモリ上で近いアドレスにあるデータは今後使う可能性が高い」という仮説に基づいたハードウェアの挙動で，うまくその仮説に合わせてプログラムを組んでやることで，処理時間を短縮できる場合があります．
なお，以上の説明は基礎的なもので，キャッシュメモリの挙動についてもう少し詳しく学びたい場合は，下記のリンクが参考になります．
{{small:ascii CPUとメモリーの速度差を埋めるキャッシュの基礎知識：[link:http://ascii.jp/elem/000/000/563/563800/] }}
{{small:マイナビ ライトスルーとライトバック：[link:https://news.mynavi.jp/article/architecture-142/] }}
*具体例
ハードウェアの動作を大雑把に理解したところで，実際にプログラムを見ながらキャッシュメモリの効果を見てみます．
下記２つのプログラムは，出力結果（dstの中身）は同じになりますが，ループの順番を変えて計算しています．
{{small:srcとdstは画像を想定した配列で，srcの値を適当に掛けたり割ったりした後，dstに代入しています．}}
プログラム A
{#
const int w = 640;
const int h = 480;
int *src = new int[w * h];
int *dst = new int[w * h];
// { src dst を 適当な数値で初期化 }
for (int u = 0; u < w; u++) {
for (int v = 0; v < h; v++) {
const int p = v * w + u;
const int a = src[p];
dst[p] = a * a / 2;
}
}
#}
プログラム B
{#
const int w = 640;
const int h = 480;
int *src = new int[w * h];
int *dst = new int[w * h];
// { src dst を 適当な数値で初期化 }
for (int v = 0; v < h; v++) {
for (int u = 0; u < w; u++) {
const int p = v * w + u;
const int a = src[p];
dst[p] = a * a / 2;
}
}
#}
そして，ループの部分の処理時間は次のような結果になりました．
{| プログラム A && 1.532603[ms] || プログラム B && 0.249204[ms] |}
Aに比べてBは６倍程度高速に動作しているようです．
具体的に話をすると，まず，Aのループではpの値はwずつ変化します．その場合，src[p]やdst[p]は，繰り返し毎に離れたアドレスにあるデータにアクセスするため，キャッシュメモリを有効的に利用できません．
一方，Bのループではpの値は１ずつ変化します．その場合，src[p]やdst[p]は，繰り返し毎に近いアドレスにあるデータにアクセスするため，キャッシュメモリに格納しておいたデータを有効活用できそうです．
このように，キャッシュメモリを有効活用することで，メインメモリにアクセスする回数が減り，計算時間を大幅に短縮できます．