メモリ階層と性能
大きな行列を転置する処理(b[j][i] = a[i][j])で、キャッシュのミスが多くなりやすい理由と、代表的な対策の組み合わせとして正しいものはどれか。
- A理由は計算が多いこと。対策は浮動小数点を整数に変えること
- B理由は読み出しが飛び飛びになること。対策は書き込み側だけを連続にすること
- C理由は読みか書きの片方が列方向になること。対策はブロックごとの転置
答えと解説を見る
正解：C. 理由は読みか書きの片方が列方向になること。対策はブロックごとの転置
転置ではaを行方向に読むとbには列方向に書き、逆にbを行方向に書けばaを列方向に読むことになり、どちらかは必ず飛び飛びのアクセスになります。そこで行列をキャッシュに収まる小さなブロックに分け、ブロックの中で転置すると、読み込んだラインを使いきってから次へ進め、ミスが大きく減ります。書き込み側だけを連続にしても読み出しが飛び飛びになるだけで、根本の解決になりません。計算量の問題でもありません。
- A. 転置はほとんど計算せず、型を変えても解決しません。
- B. 片方を連続にしても、もう片方が飛び飛びになるだけです。
- C. 正しい。必ず片方が列方向になるので、ブロックごとに転置します。