計算速度

質問

a(m,n) m=20000 n=10000
のとき
do j=1,n
do i=1,m
x=x+a(i,j)
end do
end do
の計算速度と
do j=1,n
do i=1,m
x=x+a(j,i)
end do
end do
の計算速度が違うのはなぜですか？

回答No.4

ok-kaneto

>キャッシュにヒットする確率が高くなる理由

「メモリアクセスの局所性」で調べてみてください。
時間的局所性、番地の局所性等。

似たようなことをしているのは↓
http://ja.wikipedia.org/wiki/%E5%8F%82%E7%85%A7%E3%81%AE%E5%B1%80%E6%89%80%E6%80%A7#.E3.83.A1.E3.83.A2.E3.83.AA.E3.81.AB.E3.81.8A.E3.81.91.E3.82.8B.E3.83.87.E3.83.BC.E3.82.BF.E3.81.AE.E5.B1.80.E6.89.80.E6.80.A7

レポートなら、丸写しはしないでね＾＾

補足

回答ありがとうございます．

レポートではないので，その点は安心してください．

回答No.3

ok-kaneto

レポートなら、なぜメモリー上に配置された順にアクセスすると早くなるのかを書いた方がいいでしょうね。
答えは「キャッシュにヒットする確率が高いから」です。

FORTRANでしょ？じゃあ間違いじゃないと思うけど。

お礼

回答ありがとうございます．
少し理解が深まりました．

おっしゃる通りFORTRANです．

キャッシュにヒットする確率が高くなる理由まで知りたくなってしまいた．

回答No.2

maiko0318

別の例も作りました。
2重ループする際、10000×20000と20000×10000ではどちらが早いでしょう。

for ( int i = 0 ; i < 10000 ; i++ ) {
for ( int j = 0 ; j < 20000 ; j++ ) {
Sum+=x1[i][j];
}
}
for ( int i = 0 ; i < 20000 ; i++ ) {
for ( int j = 0 ; j < 10000 ; j++ ) {
Sum+=x2[i][j];
}
}

前者が78ミリ秒後者が85ミリ秒でした。
理由はわかりますか？

お礼

回答ありがとうございます．

回答No.1

maiko0318

プログラムが間違っているので、このままでは動きませんし、意図も伝わりません。

例えば、
for ( int i = 0 ; i < 10000 ; i++ ) {
for ( int j = 0 ; j < 10000 ; j++ ) {
Sum+=x[i][j];
}
}

と
for ( int i = 0 ; i < 10000 ; i++ ) {
for ( int j = 0 ; j < 10000 ; j++ ) {
Sum+=x[j][i];
}
}

を比べるなら、

メモリーには[0][0],[0][1],[0][2],・・・[1][0],[1][1],[1][2]・・・と入っていますので、
前者はメモリーに並んでいる順に計算できるのに対して、
後者はメモリーをあちこちバラバラに計算しなくてはなりません。
時間を測ったところ、前者は0.04秒、後者は2.121秒でした。

お礼

簡単にいうと以下のようなことですか？
iから固定するならiを行にしたほうがよい．なぜならメモリーに並んでいる順番と計算の順番が同じだから．