メモリ階層と性能
2次元配列の1行の大きさが4096バイト(2の累乗)のとき、列方向に要素をたどると、キャッシュの容量に余裕があってもミスが多くなることがある。その対策として効果があるものはどれか。
- A各行の末尾に詰め物を足し、行の大きさを2の累乗からずらす
- B配列の型を、同じ大きさの別の型に変える
- C配列全体を、大きな2の累乗のアドレス境界にそろえて置き直す
答えと解説を見る
正解：A. 各行の末尾に詰め物を足し、行の大きさを2の累乗からずらす
1行が4096バイトちょうどだと、列方向にたどる要素のアドレスはどれも4096の倍数ずつ離れ、インデックスのビットが同じになって、同じセットに集中します。連想度より多い行をたどると、容量に余裕があっても追い出し合う競合ミスが起こります。各行に1ライン分程度の詰め物(パディング)を足せば、要素ごとに対応するセットがずれて分散します。2の累乗のアドレスにそろえても問題は変わらず、同じ大きさの型に変えても効果はありません。
- A. 正しい。行の大きさをずらすと、要素が別々のセットに分散します。
- B. 同じ大きさの型では、アドレスの並びは変わりません。
- C. 2の累乗にそろえても、同じセットに集中する問題は残ります。