2D配列A（i、j）の最適な構成を選択する方法

Question

うまくいけば、私はこのことを説明することができました。私は、Fortranでの作業と実際にCFDのトピックに私のコードを書いて、下記の（ちょうど簡単のために、ちょうど例えば）私の場合の短い説明をしているんだ：

1. 私は1次元配列Aを使用する必要があります（I 、j）と1D配列B（i）
2. 私は2回ループする必要があります。これは、最初のループは50,000回、2回目は5回（変更できません）です。
3. 上記のポイント番号2は10,000回ループする必要があります。

2つのバージョン（私はそれらをProg_AとProg_Bと呼んでいます）でコードを書きます。

PROGRAM PROG_A 
REAL*8, DIMENSION(50000,5):: A 
REAL*8, DIMENSION(50000)::B 
REAL*8:: TIME1,TIME2 
     !Just for initial value 
      DO I=1, 50000 
       A(I,1)=1.0 
       A(I,2)=2.0 
       A(I,3)=3.0 
       A(I,4)=4.0 
       A(I,5)=5.0 

       B(I)=I 
      END DO 
     !Computing computer's running time (start) 
      CALL CPU_TIME(TIME1) 
       DO K=1, 100000 
        DO I=1, 50000    !Array should be computed first for 50,000 elements (can't be changed) 
         DO J=1, 5 
          A(I,J)=A(I,J)+SQRT(B(I)) 
         END DO 
        END DO 
       END DO 
     !Computing computer's running time (finish) 
      CALL CPU_TIME(TIME2) 
      PRINT *, 'Elapsed real time = ', TIME2-TIME1, 'second(s)' 
END PROGRAM PROG_A 

第二つある：以下に示すように

最初のものである

PROGRAM PROG_B 
REAL*8, DIMENSION(5,50000):: A 
REAL*8, DIMENSION(50000)::B 
REAL*8:: TIME1,TIME2 
     !Just for initial value 
      DO J=1, 50000 
       A(1,J)=1.0 
       A(2,J)=2.0 
       A(3,J)=3.0 
       A(4,J)=4.0 
       A(5,J)=5.0 

       B(J)=J 
      END DO 
     !Computing computer's running time (start) 
      CALL CPU_TIME(TIME1) 
       DO K=1, 100000 
        DO J=1, 50000    !Array should be computed first for 50,000 elements (can't be changed) 
         DO I=1, 5 
          A(I,J)=A(I,J)+SQRT(B(J)) 
         END DO 
        END DO 
       END DO 
     !Computing computer's running time (finish) 
      CALL CPU_TIME(TIME2) 
      PRINT *, 'Elapsed real time = ', TIME2-TIME1, 'second(s)' 
END PROGRAM PROG_B 

別の私は2次元配列Aを用いる最初のもの（50000ためのものである見ることができるように、 5）、2番目には2DアレイA（5,50000）を使用しました。

私が知っているところでは、Fortranは「列メジャー」に基づいているため、2番目のケースは最初のものより高速です（2番目のケースでは、配列の最も内側のループを実行していますこの場合i = 1、...、5）。

しかし、gfortran（-O3最適化）でコンパイルした後、私は、2番目のものが最初のものよりずっと遅いことも発見しました。ここでの結果は次のとおりです。

1. 最初のケース：経過時間= 70.496秒

は、誰もが、なぜ私に説明してもらえ：時間= 29.187秒

セカンドケースを経過？

PS：両方のケースの結果は確かに同じです。

Answer 1

最適化の一部は、実装によって選択されたヒューリスティックに基づいています。 あなたは完全に確定的な説明を得るつもりはありません。 Fortranのような完全な配列操作を可能にする言語でプログラムを書く場合、主なポイントは です。完全な配列/ベクトル演算として何かを表現できれば、それを行い、コンパイラにループを生成させます。そうすれば、コンパイラで最も効率的にテストし、それに固執するだけです。

コンパイラに依存するので、コンパイラによって変更されることに注意してください。 たとえば、プログラムをそのまま使用している場合（を100000から10000に変更して速度を上げ、それぞれ平均5回実行）、これはコンパイラが異なるコンピュータ上のタイミングです。 新しいバージョンのコンパイラで確認する時間がありません。

pgf90 14 
A: 5.05 s 
B: 0.18 s 

gfortran 4.9 
A: 1.05 s 
B: 4.02 s 

ifort 13 
A: 2.01 s 
B: 1.08 s 

あなたはのgfortranは、Bが不良であることを示していますどこていることがわかります、pgfortran は反対のことを告げると、私は、コンパイラが仕事をやらせるためにベクトル化する場合は、完全に今

からの結果を吹きます。ここで私は唯一の を変更し、これを持っているIループを排除：

DO K=1, 10000 
    DO J=1, 5 
     A(I,J)=A(I,J)+SQRT(B(I)) 
    END DO 
END DO 

その後、我々はのgfortranがでトリックを利用している間に

pgf90 14: 5.05 s 

gfortran 4.9: 5.04 

ifort 13: 2.02 s 

pgfortranとのifortが安定している（プログラムのみA）これを取得します最初のケース、恐らくハーラルドクの提案（第5因子参照）。ベクトル化すると、そのトリックは明白ではありません gfortranはうまく機能しません。 ifortとpgfortran は、正しい順序を持つためにループを書き直すだけです。

そして、私は賢く取得し、あまりにも

DO J=1, 5 
     A(:,J)=A(:,J)+10000*SQRT(B(:)) ! this seems to be final result 
    END DO 

をK-ループをelimite場合はその後、我々はほとんど何にもないので、すべてのコンパイラは同等になる

pgf90 14: 0.001 

gfortran 4.9: 0.001 

ifort 13: 0.001 s 

（のみプログラムA）これを取得最適化する。 配列操作を使用するだけですべてを最適化できることがわかります。

---

更新 高性能マークは、結果が使用されていないことが判明した場合、コンパイラは、実際にいくつかの実装で起こるかもしれない、すべての計算をスキップする可能性があることをコメントで指摘しました。この回答に提示された結果は、私が最初にそれを言及しなかったとしても、その可能性を説明しました。コンパイラがコードを完全にスキップするのを防ぐために、計算後の結果のすべての要素の合計（タイミングの後）を表示しました。結果は、小数点以下の3桁目と同じです。これは〜372684326034.9146（〜10^12）の結果に十分適しています。これは、コンパイラが実際の計算を確実に行うのに十分です。私は答えでそれを言及することを完全に忘れてしまった。

Answer 2

コンパイラは、おそらくこのような何かを行います。Prog_Aで

DO K=1, 100000 
     DO I=1, 50000 
      tmp = sqrt(b(i)) 
      A(I,1) = A(I,1) + tmp 
      A(I,2) = A(I,2) + tmp 
      A(I,3) = A(I,3) + tmp 
      A(I,4) = A(I,4) + tmp 
      A(I,5) = A(I,5) + tmp 
     END DO 
    END DO 

をこれはあなたがProg_Bのようにインデックスの順序を変更する場合は、あなたが得るあなたの1のストライドで素敵なアクセスパターンを与えますこのコードのために5のストライド。この効果はマシンに依存しますが、単純なストライド1アクセスよりも明らかに悪いです。