キャッシュ階層を意識したプログラミング

出典: トータル・ディスクロージャ・サイト(事実をありのままに)

読者の皆様が触られているCPUには、おそらくキャッシュメモリが搭載されていると思われる。キャッシュメモリはCPUに付属する高速なメモリであり、CPUに対して比較的低速なメインメモリのアクセスに割り込み、アクセス頻度の多いデータを保持することで高速にアクセスできるようにした機構である。ただし、現在のメモリの原理上、高速と大容量を両立することは不可能であるため、容量はかなり限られている。

これからStreamベンチマークで測定したメモリバンド幅を示すが、キャッシュメモリによる性能向上の程を確認していただきたい。なお、配列サイズが小さい場合の値を正確に測定するため、オリジナルのStreamベンチマークと違い、ベンチマーク結果の平均値を以て帯域を計算する変更を加えている。

--- stream.f    2012-08-27 13:34:45.355009673 +0900
+++ mystream.f  2012-08-27 13:36:51.261075168 +0900
@@ -94,7 +94,7 @@
 *     IMPLICIT NONE
 C     .. Parameters ..
       INTEGER n,offset,ndim,ntimes
-      PARAMETER (n=2000000,offset=0,ndim=n+offset,ntimes=10)
+      PARAMETER (n=KB*128,offset=0,ndim=n+offset,ntimes=8388608/KB)
 C     ..
 C     .. Local Scalars ..
       DOUBLE PRECISION scalar,t
@@ -233,7 +233,7 @@
       WRITE (*,FMT=9040)
       DO 100 j = 1,4
           avgtime(j) = avgtime(j)/dble(ntimes-1)
-          WRITE (*,FMT=9050) label(j),n*bytes(j)*nbpw/mintime(j)/1.0D6,
+          WRITE (*,FMT=9050) label(j),n*bytes(j)*nbpw/avgtime(j)/1.0D6,
      $      avgtime(j),mintime(j),maxtime(j)
   100 CONTINUE
       PRINT *,'----------------------------------------------------'
@@ -246,7 +246,7 @@
  9030 FORMAT (1x,a,i3,a,a)
  9040 FORMAT ('Function',5x,'Rate (MB/s)  Avg time   Min time  Max time'
      $       )
- 9050 FORMAT (a,4 (f10.4,2x))
+ 9050 FORMAT (a,4 (f11.4,2x))
       END

 *-------------------------------------

測定環境は、以下の通りである。

CPU Core i7 2600K (3.3 GHz Downclocked, 4 cores)
OS Ubuntu 11.10
Compiler Intel Fortran Compiler 12.1 Update 5 (-fast -xAVX)
配列長 Copy (MB/s) Scale (MB/s) Add (MB/s) Triad (MB/s)
8 KiB 91378.2733 89965.9717 129464.9675 126409.3187
16 KiB 83885.2813 58684.2063 45586.3273 52237.7809
32 KiB 55401.8159 49643.6213 50371.9098 52869.1101
64 KiB 50997.3009 45111.4964 46579.6316 47778.2010
128 KiB 45411.7727 34395.0335 35491.2994 36803.5258
256 KiB 44446.4838 32645.2128 34738.7397 35570.0766
512 KiB 41892.4403 32471.0212 34963.5884 35615.4180
1024 KiB 40602.7212 32109.7400 34319.3453 34093.1042
2048 KiB 21049.3965 18661.9849 19719.7847 21720.1495
4096 KiB 16802.8972 18723.2895 18137.9277 19333.5568
8192 KiB 15187.6718 17649.6033 18789.3898 19054.6876
16384 KiB 15468.6220 17593.9592 18309.3283 18337.4547
32768 KiB 15975.5504 17704.0426 18343.4273 18353.1709
65536 KiB 16425.3289 17835.8001 18470.1165 18439.7427
131072 KiB 16503.3996 17858.3831 18614.5554 18554.3623
262144 KiB 16282.3627 17740.0616 18661.9331 18593.5017
524288 KiB 15583.3825 17742.2979 18709.7493 18608.4087

Streamベンチマークの場合、配列を3つ使うので、表に「配列長8 KiB」とあるテストの場合、使用しているメモリ量は計24 KiBである。2600KのL1データキャッシュの容量は32 KiBであるので、配列長8 KiBのベンチマーク結果は、配列長16 KiB以上の結果を圧倒し、これがL1データキャッシュの速度であると推測される。そこからなだらかに結果を落としつつ、配列長64 KiB(メモリ量192 KiB)と配列長128 KiB(メモリ量384 KiB)との間で、やや大きな性能低下を見せるが、ここまでが容量256 KiBのL2キャッシュの効果であろう。配列長1024 KiB(メモリ量3 MiB)と配列長2048 KiB(メモリ量6 MiB)の間の性能低下も大きいが、容量8 MiBのL3キャッシュの効果が、容量に多少の余裕のあるここで消えてしまうのであろうか。

ともかく、キャッシュメモリのサポートを得られる場合と得られない場合とで、ベンチマークの結果が5倍以上違ってくる点は間違いが無いと考えられる。この点を意識してプログラムをチューニングすると、時にして大きな性能向上を得られる場合があるが、今度は行列積のプログラムを組みながら、この点を考えてみよう。

ここから先の測定環境は、以下の通りである。

CPU Core i7 2600K (3.3 GHz Downclocked, 4 cores)
OS Ubuntu 11.10
Compiler GCC 4.6.1 (-Ofast -march=native)

Intel Compilerは最適化が効きすぎて、行列積計算を検出すると自動的に最適化されたコードを出力するため、今回の実験には不適であった。

まずは、何も考えずに組んだプログラムである。

      SUBROUTINE INIMAT(A,N)
      DIMENSION A(N,N)
      DO 20 J=1,N
         DO 10 I=1,N
            A(I,J)=I+(J-1)*N
 10      CONTINUE
 20   CONTINUE
      END
      PROGRAM MATMUL
      PARAMETER(N=3000)
      DIMENSION A(N,N),B(N,N),C(N,N)
      CALL INIMAT(A,N)
      CALL INIMAT(B,N)
      CALL INIMAT(C,N)
      CALL SYSTEM_CLOCK(ISTART,IRATE,IMAX)
      DO 30 J=1,N
         DO 20 I=1,N
            DO 10 K=1,N
               C(I,J)=C(I,J)+A(I,K)*B(K,J)
 10         CONTINUE
 20      CONTINUE
 30   CONTINUE
      CALL SYSTEM_CLOCK(IEND,IRATE,IMAX)
      SUM=0.0
      DO 50 J=1,N
         DO 40 I=1,N
            SUM=SUM+C(I,J)
 40      CONTINUE
 50   CONTINUE
      WRITE(*,*)'TIME:     ',REAL(IEND-ISTART)/REAL(IRATE)
      WRITE(*,*)'CHECKSUM: ',SUM
      END

これの実行結果は、以下の通り。

 TIME:        28.632999
 CHECKSUM:   5.46810854E+23

行列積であるので、理想的にはCPUのピーク性能がそのまま出ると期待されるが、メモリアクセスがボトルネックになっているために、このプログラムのFLOPS値は1.89 GFLOPS、ピーク性能52.8 GFLOPSの3.5 %程度しか出ていない。

これを、「L1データキャッシュが効く程度のサイズの小行列を作り、一度データを移し替えてから計算を行い、結果を書き戻す。」というポリシーで計算してみる。

      SUBROUTINE INIMAT(A,N)
      DIMENSION A(N,N)
      DO 20 J=1,N
         DO 10 I=1,N
            A(I,J)=I+(J-1)*N
 10      CONTINUE
 20   CONTINUE
      END
      PROGRAM MATMUL
      PARAMETER(NB=64)
      PARAMETER(N=3000)
      DIMENSION AB(NB,NB),BB(NB,NB),CB(NB,NB)
      DIMENSION A(N,N),B(N,N),C(N,N)
      CALL INIMAT(A,N)
      CALL INIMAT(B,N)
      CALL INIMAT(C,N)
      CALL SYSTEM_CLOCK(ISTART,IRATE,IMAX)
      DO 30 JJ=1,N,NB
         DO 20 II=1,N,NB
            DO 70 JB=1,NB
               DO 60 IB=1,NB
                  CB(IB,JB)=0.0
 60            CONTINUE
 70         CONTINUE
            DO 10 KK=1,N,NB
               DO 90 JB=1,NB
                  K0=KK+JB-1
                  J=JJ+JB-1
                  DO 80 IB=1,NB
                     I=II+IB-1
                     K1=KK+IB-1
                     IF(I.LE.N.AND.K0.LE.N)THEN
                        AB(IB,JB)=A(I,K0)
                     ELSE
                        AB(IB,JB)=0.0
                     ENDIF
                     IF(K1.LE.N.AND.J.LE.N)THEN
                        BB(IB,JB)=B(K1,J)
                     ELSE
                        BB(IB,JB)=0.0
                     ENDIF
 80               CONTINUE
 90            CONTINUE
               DO 120 JB=1,NB
                  DO 110 IB=1,NB
                     DO 100 KB=1,NB
                        CB(IB,JB)=CB(IB,JB)+AB(IB,KB)*BB(KB,JB)
 100                 CONTINUE
 110              CONTINUE
 120           CONTINUE
 10         CONTINUE
            DO 140 JB=1,MIN(N-JJ+1,NB)
               J=JJ+JB-1
               DO 130 IB=1,MIN(N-II+1,NB)
                  I=II+IB-1
                  C(I,J)=C(I,J)+CB(IB,JB)
 130           CONTINUE
 140        CONTINUE
 20      CONTINUE
 30   CONTINUE
      CALL SYSTEM_CLOCK(IEND,IRATE,IMAX)
      SUM=0.0
      DO 50 J=1,N
         DO 40 I=1,N
            SUM=SUM+C(I,J)
 40      CONTINUE
 50   CONTINUE
      WRITE(*,*)'TIME:     ',REAL(IEND-ISTART)/REAL(IRATE)
      WRITE(*,*)'CHECKSUM: ',SUM
      END
 TIME:        6.0920000
 CHECKSUM:   5.54475548E+23

8.86 GFLOPS、ピークの16 %程度まで性能が向上している。

このように、キャッシュメモリを意識してプログラムを組むことで、大きな性能向上のメリットを得られることが分かる。プログラムのチューニングの際には、この点を意識されると良いと思われる。


この記事へのコメントをお寄せください

  • サイトへの書き込みに差し支えございましたら トータルディスクロージャーサイトサポート係へメールをお送りください
  • トータル・ディスクロージャ・サイトに投稿された文章と画像は、すべてその著作権がHPCシステムズ株式会社に帰属し、HPCシステムズ株式会社が著作権を所有することに同意してください。
  • あなたの文章が他人によって自由に編集、配布されることを望まない場合は、投稿を控えてください。
  • コメントを書き込む場合は名前にひらがなを織り交ぜてください。
  • あなたの投稿する文章と画像はあなた自身によって書かれたものであるか、パブリック・ドメインかそれに類する自由なリソースからの複製であることを約束してください。あなたが著作権を保持していない作品を許諾なしに投稿してはいけません!

<comments hideform="false" />


Comments

ノート:キャッシュ階層を意識したプログラミング

個人用ツール