計算速度

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 回答日時： 2014/04/24 11:02

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

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

似たようなことをしているのは↓
http://ja.wikipedia.org/wiki/%E5%8F%82%E7%85%A7% …

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

この回答への補足

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

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

補足日時：2014/04/24 19:27

No.3 回答者： ok-kaneto 回答日時： 2014/04/21 19:06

レポートなら、なぜメモリー上に配置された順にアクセスすると早くなるのかを書いた方がいいでしょうね。

答えは「キャッシュにヒットする確率が高いから」です。

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

この回答へのお礼

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

おっしゃる通りFORTRANです．

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

お礼日時：2014/04/22 09:30

No.2 回答者： maiko0318 回答日時： 2014/04/19 00:40

別の例も作りました。

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ミリ秒でした。
理由はわかりますか？

この回答へのお礼

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

お礼日時：2014/06/29 15:17

No.1 回答者： maiko0318 回答日時： 2014/04/18 23:16

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

例えば、
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を行にしたほうがよい．なぜならメモリーに並んでいる順番と計算の順番が同じだから．

お礼日時：2014/04/21 11:23