データの局所性の例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/14 14:36 UTC 版)
以下は行列 A と B の積を求める擬似プログラムの例である。 for i in 0..n for j in 0..m for k in 0..p C[i][j] = C[i][j] + A[i][k] * B[k][j]; 大きな（キャッシュに入りきらない）行列を扱うとき、このアルゴリズムではメモリへのアクセスはかなり不連続的になる。C言語では同じ行の要素が連続してメモリ上に配置されるので、なるべく同じ行の要素に続けてアクセスした方が使用するメモリアドレスも連続的になり、空間的局所性が高い。つまり行のインデックスよりも列のインデックスの方が頻繁に変わるようにすると効率が上がる。j は2つの行列 B,C の列のインデックスなので、頻繁に変化する最も内側のループのカウンタにするとよい。このようにjとkのループを入れ替えることで、数学的には同値なアルゴリズムだが効率は上がり、特に行列が大きいと性能の向上は劇的なものとなる。 さらに時間的局所性を利用するには「ブロック化」と呼ばれる技法を使う。大きな行列を等しいサイズの部分行列に分け、短い時間に同じ部分行列を複数回参照する。 for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) for (i = ii; i < ii + BLOCK_SIZE; i++) for (k = kk; k < kk + BLOCK_SIZE; k++) for (j = jj; j < jj + BLOCK_SIZE; j++) C[i][j] = C[i][j] + A[i][k] * B[k][j]; この方法ではii,jj,kkが変化しない間、つまり内側3つの繰り返しの間に同じメモリが何度もアクセスされ、キャッシュに残り易くなっている（時間的局所性）。また、jを最も内側で変化させて空間的局所性も考慮している。なお、以上はメモリ上で配列の同じ行の要素が連続している Row-major order（英語版）の場合であり、FORTRANなどでは逆に Column-major order になっているため注意が必要である。
※この「データの局所性の例」の解説は、「参照の局所性」の解説の一部です。
「データの局所性の例」を含む「参照の局所性」の記事については、「参照の局所性」の概要を参照ください。
- データの局所性の例のページへのリンク
