ソフテック・トップページへ
ホーム 製品 セキュリティ・サービス HPCサービス ダウンロード 企業情報

PGI compiler Tutorial
行列積プログラムでメモリアクセス最適化
PGI チュートリアル > 行列積プログラム最適化

 
行列積のプログラムで、メモリアクセス方法の違いによる性能差を較べる

 本稿では、行列積のプログラムを用いて、最内側ループのメモリアクセス方法の変化により、性能が大きく異なることを説明します。行列積の性能最適化については他に多くの文献があり、メモリアクセス最適化の教科書的題材ですが、ここで理解していただきたいことは、プログラムの実効性能の大小は、実は配列計算時のメモリアクセスに関連したキャッシュの有効活用の度合いによって変化すると言うことです。ユーザが直面する、プログラムの性能が速い、遅いと言う問題の多くは、ソースレベルでのプログラムの特性によるものが多く、特に性能が遅い場合はキャッシュがうまく活用できていないことがほとんどです。ここでは、その事実を説明し、キャッシュ利用の操作をコマンドオプションレベルで行うことができるソフトウェア・プリフェッチについて、別稿で説明している記事に繋げたいと思います。

ここで例題に使用したソースファイルは、以下のものです。ご自由にダウンロードして試して見てください。

  使用ソースファイル : mm1.f (一般的なコーディング)
                  mm2.f (キャッシュ有効活用のため一時配列を追加)
  時間計測ルーチン  : wallclock.c(Elapsed timeベース:並列処理時の時間計測に便利、CPU 時間ベースではない)
  

KEYWORD: 行列積、 メモリアクセスのパターン、 計算密度、 最適化方法、 キャッシュの有効活用プリフェッチ機能


使用したシステム構成

本項で説明した性能を測定するために使用したシステムは、以下の AMD のプロセッサとインテル(R) のデュアル・プロセッサを有する二つのシステムです。

表 1 行列積の演算の性能測定に用いたシステム
AMD Dual Core プロセッサ インテル(R) Dual Core プロセッサ
システム名 White Box EPSON Endeavor Pro3300
プロセッサ AMD Athlon64X2 4400+
Pentium® D 820
Clock 2.2 GHz 2.8 GHz
L2 cache 1MB + 1MB 1MB + 1MB
使用メモリ(最大帯域) DDR400 PC3200 CL3 3-3-3 (6.4GB/s)
512MB x 2 枚(バルク製品)
DDR2-667 (10.6GB/s) 1GB x 2 枚
STREAM メモリ実効帯域(SSEベクトル処理付) 4290 MB/sec 4863 MB/sec
STREAM メモリ実効帯域
(ベクトル処理なし)
2551 MB/sec 3583 MB/sec
使用 OS SUSE 10.0 (kernel 2.6.13) SUSE 10.0 (kernel 2.6.13)
64ビット環境 AMD64 EM64T
使用コンパイラ PGI 6.1 PGI 6.1


行列積演算のメモリアクセス特性

  行列積を計算するプログラムは、一般的に mm1.f で示すような i、j、k の三つの多重ループで構成されるものであり、どのループ・インデックスの順番でネストしても、データの依存性はありません。従って、ループの i、j、k の順番はどのような形態でも良いのですが、一般に、最内側ループでの配列のメモリアクセスが連続で行えるようなループ・インデックスを最内側にします。これは、メモリアクセスが十分に長いストライドで、すなわち「とび」で行われた場合、キャッシュ内のデータの有効活用ができないため、性能が大幅に低下することを避けるためです。行列積は、以下のような演算式となります。Fortran の場合は、配列の1次元目で連続アクセスが行われ、C 言語の場合は、配列の最後の次元で連続アクセスが行われます。

    c(i,j) = c(i,j) + a(i,k) * b(k,j)

 このような形式の演算の場合、最内側のループのインデックスによって、メモリのアクセス・パターンが以下に示した表のように変化します。性能を高速化する上で、非常に重要な視点は、メモリアクセスが「連続」か「とびアクセス」かと言うことと、できるだけ、メモリ・ロード/ストアの数をが少なくすることです。一般に、演算における「計算密度」と言う定義があります。これは、一つの最内側ループ内で、メモリ・アクセスの回数と浮動小数点演算(積・和・除算)の回数の比率を言います。上記の行列積の演算では、積と和で二つの浮動小数点演算があります。それに対して、メモリのロード・ストアの回数は、最内側のループ・インデックスにより異なります。以下の表に、それぞれの計算密度を示しましたが、この数字が大きいほどメモリ負荷が軽く、相対的に性能は向上することになります。
 そして、性能の決め手となるもう一つの指標は、メモリアクセスのパターンです。このパターンの違いによって、キャッシュのデータの使い方が異なってきます。特に重要なことは、一度ロードしたデータをキャッシュ内に存在するうちに有効活用できるかと言うことと、限られたサイズのキャッシュ容量を無駄に汚染させないようにすることです。前者のキャッシュ有効活用に関しては、ソース最適化あるいはコンパイラ最適化の役目です。一方、後者のキャッシュ汚染の最小化は、プロセッサ機能の役目であり、現在は、特にソフトウェア・プリフェッチ(prefetch) 機能によって、ある程度制御できるようになっており PGI コンパイラはこの制御が可能です。この点については、別の記事で説明します

表 2 メモリアクセスの特性と計算密度
最内側ループ
インデックス
メモリからデータ・ロード
配列とアクセス特性
メモリへデータ・ストア
配列と特性
計算密度
(演算数/メモリ回数)
i c のロード(連続) a のロード(連続) c のストア(連続) 2/3 = 0.66
j c のロード(とび) b のロード(とび) c のストア(とび) 2/3 = 0.66
k a のロード(とび) b のロード(連続)   2/2 = 1.0

 上表において、計算密度の観点で性能を最も最適化できるのは、インデックス k を最内側のループにすることのように見えます。この場合は、二つの積・和の演算とメモリのロードが二つで、それぞれのコストの重み付けは異なりますが、計算密度は 1.0 で他のものよりも優れています。これは、あくまでも回数と言う観点での相対的な見方であり、絶対的な性能を支配するものではありません。性能を落とす要因となる絶対的なペナルティ・コストは、このような相対的な計算密度ではなく、別のところにある場合が多いのです。この性能低下の原因の多くは、「キャッシュ」の有効活用がなされないことにあります。キャッシュの有効活用の大前提は、「メモリアクセスの連続化」であり、こう言った観点では、最内側ループが i の方が性能が高いことが予想できます。

行列積のオリジナルコードをコンパイルして得られる性能

 さて、ここで用意した mm1.f プログラムを実際にコンパイルして実行してみましょう。プログラム 1 の mm1.f は、行列積計算を素直にコーディングしたプログラムであり、さらに、「計算密度」が高い、最内側のループを k インデックスにしてあります。これをコンパイルすると、PGI コンパイラは、以下のようにループのネストを入れ替え、最内側のインデックスが i となるように変換します。。コンパイラは、ロード・ストアの回数は多くなるものの、 i インデックスを最内側にした方が、メモリアクセスが連続となり、性能が最適化されると判断したわけです。現在のコンパイラは、依存性のない多重ループに関して、最内側のメモリアクセスが連続になるように、ループ・ネストの入れ替えを自動的に行います
 一方、こうしたコンパイラの最適化を抑止し、オリジナルとおり、k インデックスを最内側ループになるようにコンパイルしてみました(コンパイル指示行 novector を挿入)。それぞれの性能差に着目してください。

プログラム 1 (mm1.f) 】

PGIコンパイラは、最内側ループのメモリ・アクセスができるだけ連続になるように、i と k ループ、
38と39のループ・ネストを入れ替えた。

(   37)          do j = 1, p
(   38)             do i = 1, m
(   39)                do k = 1, n
(   40)                   c(i,j) = c(i,j) + a(i,k) * b(k,j)
(   41)                enddo
(   42)             enddo
(   43)          enddo

$ pgf95 -fastsse -Minfo mm1.f wallclock.o 
    37, Interchange produces reordered loop nest: 37, 39, 38 (ループネストの入れ替え)
    38, Generated an alternate loop for the inner loop
        Generated vector sse code for inner loop
        Generated 2 prefetch instructions for this loop
        Generated vector sse code for inner loop
        Generated 2 prefetch instructions for this loop
$ a.out
 Elapsed time =    3.196152091026306       (sec)
 M =         1000 , N =         1000 , P =         1000
 MFLOPS =     625.4395732958088コンパイラの最適化を抑止し、コーディングの通りにコンパイルすることを指示 】

38 行目にコンパイラ指示行を入れて、ループの入れ替えを明示的に抑止した。 a(i,k) 配列が
「とびアクセス」となるため、性能低下を招いている。

(   37)          do j = 1, p
(   38) !pgi$l novector
(   39)             do i = 1, m
(   40)                do k = 1, n
(   41)                   c(i,j) = c(i,j) + a(i,k) * b(k,j)
(   42)                enddo
(   43)             enddo
(   44)          enddo

$ pgf95 -fastsse -Minfo mm1.f wallclock.o
    40, Generated vector sse code for inner loop
        Generated 1 prefetch instructions for this loop
$ a.out
 Elapsed time =    13.80639398097992       (sec)
 M =         1000 , N =         1000 , P =         1000
 MFLOPS =     144.7879875624207

上記の数値実験で分かる通り、計算密度と言う観点よりも、キャッシュの活用度の高い、メモリアクセスの連続性のある方が性能が良いことになります。性能も大きく異なっています。ベクトル・プロセッサのように、メモリと CPU のレジスタ間に「キャッシュ」を置かず直接アクセスできる場合は、「計算密度」と言う観点は性能を左右するファクタとなりますが、現在のマイクロプロセッサのように「キャッシュ」を介在する場合は、メモリアクセスの連続性とキャッシュの有効活用最適化の方が性能に大きく寄与することが理解できます。

配列のアクセスの連続化による最適化性能

 オリジナルのコード上で、「計算密度」が高い k インデックス・ループを最内側にすることが、性能を大きく低下させることが分かりました。しかし、この原因は、計算密度の云々よりもメモリアクセスの「とび」による問題のファクタが大きいと言うことが考えられます。もし、何らかのソースの変更で、この問題が解決した場合、今度は計算密度の良し悪しは、性能を左右するファクタとなります。そこで、用意した mm2.f プログラムは、 a(i,k) 配列のとびアクセスを回避するため、一時的な作業一次元配列 arow を作成し、これを利用して行列積の計算を行うものです。 44 行目の演算部の配列では、全て連続アクセスの形態になります。( k ループ内の c(i,j) は一変数と同じ扱いになります)
 これをコンパイルして得た性能は、668MFLOPS であり、オリジナルコードの性能である 625MFLOPS から向上しております。

プログラム 2 (mm2.f) 】

最内側ループ軸は、43 行目のループである k となる。オリジナル上の a(i,k) 配列が「とびアクセス」
となるため、一時的配列 arow を用意して、連続アクセスできるように一次元配列に退避しておく。
40行目の arow(ii) = a(i,ii) は、a(i,ii) において「とびアクセス」であるが、二重ループ内の
44 行目に置かれるよりも、実行回数が少ない。また、最も演算コストの大きい 44 行目で処理される
CPU 内部の実行パイプラインをストールさせることも少なくなる。

(   38)          do i = 1, m
(   39)             do ii = 1, n
(   40)                arow(ii) = a(i,ii)
(   41)             enddo
(   42)             do j = 1, p
(   43)                do k = 1, n
(   44)                   c(i,j) = c(i,j) + arow(k) * b(k,j)
(   45)                enddo
(   46)             enddo
(   47)          enddo

$ pgf95 -fastsse -Minfo mm2.f wallclock.o
    39, Generated vector sse code for inner loop
    43, Generated an alternate loop for the inner loop
        Generated vector sse code for inner loop
        Generated 2 prefetch instructions for this loop
        Generated vector sse code for inner loop
        Generated 2 prefetch instructions for this loop
$ a.out
 Elapsed time =    2.990319967269897       (sec)
 M =         1000 , N =         1000 , P =         1000
 MFLOPS =     668.4903361111043

行列積の性能(標準的なコンパイル・オプション使用)

 上記の mm1.f、mm2.f を使用した1000x1000 の行列積計算の性能結果は、以下の表の通りです。ここで、AMD のプロセッサと Intel(R) のプロセッサでは、このプログラムでは性能が大きく異なることが分かります。もちろんクロック差は異なりますが、これは、マイクロアーキテクチャレベルにおけるプロセッサ内部のキャッシュ利用の制御方法の違いが性能に現れたものと思われます。ただ、誤解していただきたくないことは、AMD社のプロセッサが常に性能が劣ると言うことではありません。たまたま、このプログラム特性において、このような結果が現れたものです。プログラムが異なれば、全く逆の形態もあります。
 さて、このような性能差が、プロセッサのマイクロアーキテクチャの動作の違いによって現れた原因は何でしょう?内部の動きの詳細は分かりませんが、それぞれのキャッシュラインサイズ(64B or 128B)の違い、キャッシュの動作法の違い、メモリアーキテクチャの違いによるメモリ上のデータをプリフェッチするハードウェア機能の差が現れたものと推察されます。Pentium(R) 4 以降のプロセッサあるいは Athlon64/Opteron のプロセッサには、ハードウェアレベルの自動プリフェッチ機能が備わっております。一言で言えば、実行時に規則的なアクセスのパターンを見出して、自動的に必要とするデータを前以ってキャッシュに取り込む(プリフェッチと言う)機能です。Pentium(R) D プロセッサは、このプリフェッチがうまく機能していると言うことなのかもしれません。そこで、明示的にプリフェッチをソフトウェアで制御できるソフトウェア・プリフェッチの指示を PGI コンパイラ・オプションで指定してみると、下記の通り、 Athlon64x2 においても性能が大きく向上することが分かります。この「ソフトウェア・プリフェッチ」の制御の方法に関しては、別記事で説明することにします。

表3 行列積計算 性能の推移 (1000x1000)
システム クロック mm1.f
(MFLOPS)
mm2.f
(MFLOPS)
プリフェッチ
制御をすると
mm1.f
-Mprefetch
(MFLOPS)
mm2.f
-Mprefetch
(MFLOPS)
Athlon64x2 2.2GHz 625 668    ==>   1088 1392
Pentium(R)D 2.8GHz 1142 1150    ==> 1365 1492


Athlon64x2 の性能が低下していることに関して、キャッシュの活用がうまくなされていないことを実証するため、行列のサイズを変化させて性能を測定して見ました。下表の通り、サイズ 400 の辺りから急激に性能が低下し、600〜670 MFLOPSで一定になります。それに対して、Pentium(R) D では、サイズが大きくなるに従い徐々に低下していることが分かります。さらに、1000〜1100 MFLOPS で性能が落ち着きます。従って、性能の低下はキャッシュ内のデータが活用できるかどうかの差が現れたものであることが理解できます。
また、サイズ 300 程度までは、どちらのプロセッサもキャッシュ内のデータが活用できるサイズとなっており、クロック差があるにも拘らず、同じ性能値であることが分かります。この部分だけを見れば、クロックが低くても Athlon64x2 のプロセッサの方が性能的に優れていることも分かります。

表 4 mm2.f の行列積計算の性能
Matrix Size 100 200 300 400 500 700 1000 2000
Athlon64x2 1641 1762 1566 718 610 622 668 679
Pentium(R)D 1625 1780 1401 1073 1057 1102 1150 1141



この画面トップへ

技術情報 TIPS トップに戻る >>




 ソフテックは、PGI 製品の公認正規代理店です

サイトマップ お問合せ
Copyright 2004-2006 SofTek Systems Inc. All Rights Reserved.