メモリ階層と性能
上の2つのループを1つにまとめる(ループ融合)と、Nが大きいときに速くなりやすい理由はどれか。
for (i = 0; i < N; i++) a[i] = b[i] * 2;
for (i = 0; i < N; i++) c[i] = a[i] + 1;- A掛け算と足し算が1つの命令にまとまり、計算の量が半分になるから
- Ba[i]を書いた直後に使えるので、配列aを主記憶から読み直さずに済むから
- Cループの回数がN回から2N回に増え、パイプラインが埋まりやすくなるから
答えと解説を見る
正解：B. a[i]を書いた直後に使えるので、配列aを主記憶から読み直さずに済むから
別々のループのままだと、最初のループで書いたaの全体がキャッシュに入りきらない大きさのとき、2つ目のループで先頭から読み直すたびにミスが起こります。融合すると、a[i]を書いた直後に同じ繰り返しの中で使うので、データがキャッシュやレジスタにある間に再利用でき、主記憶との通信が減ります。計算の量は変わらず、ループの回数は2N回からN回に減ります。
- A. 演算の数は変わらず、計算量は半分になりません。
- B. 正しい。書いた直後に再利用でき、配列aの読み直しが不要になります。
- C. ループの回数は2N回からN回に減ります。