並列コンピュータ AzusA の高速化技法
メモリアクセスの効率化
左近
日本電気株式会社

彰一

第一コンピュータソフトウェア事業部

概要
並列コンピュータ TX7/AzusA（以下、AzusA という）は、１つのプログラムを最大16 個の CPU で分担して実行する並列処理によって高速化を実現していますが、高速化のためには単一 CPU で実行するときの性能をできるかぎり向上させておくことが重要です。そこで、本稿では AzusA の単一 CPU 上での実行性能向上（チューニング）のための、主としてメモリアクセスの削減による高速化技法を紹介します。例題として、行列積のプログラムの高速化方法を説明します。

1. AzusA のメモリとキャッシュ
AzusA の CPU は、メモリとの間に L1 キャッシュ、L2 キャッシュ、L3 キャッシュの3 階層のキャッシュを持っています（図１）。[1][2]各々の容量と性能を表１に示します。浮動小数点データは L1 キャッシュを用いませんので、L2 キャッシュが最も CPU に近い高速なキャッシュとなります。
AzusA 1CPU の倍精度浮動小数点演算性能は、最大 3.2GFLOPS ですから、倍精度浮動小数点の計算が連続的に行われる場合、L2 キャッシュにデータがあれば、1 つのデータに対して 1 演算を行うことによって、データ供給のバンド幅と演算の速度がつり合います（3.2G[Flops]*8B=25.6GB）。
しかし、同様の計算により、データが L3 キャッシュにある場合は、1 つの倍精度要Ｌ１命令キャッシュ

レジスタ

Ｌ１データキャッシュ

Ｌ２キャッシュ

図１Ｌ３キャッシュ

キャッシュメモリの階層

メモリ

素に対して 2 演算、メモリの場合は 12 演算を行わないと、データ供給スピードと演算性能がつり合いません。逆に言うと、L3 キャッシュやメモリにデータがある場合、1 データに対して上記の数程度の演算を行わない場合、データ供給ネックとなり、最大演算性能を出すことができません。またレーテンシ（要求してからデータが届くまでの時間）も L2→L3→メモリへ行くほど長くなっています。

L1 データ
L2L3

表１ キャッシュとメモリの特性
サイズ レーテンシ
バンド幅
バンド幅：倍精度(サイクル数)
演算性能比
16KB
212.8GB/s‑96KB
6‑925.6GB/s
1 : 14MB
21‑2412.8GB/s
1 : 2メモリ<160‑240

2.1GB/s

1 : 12

図２は積和演算 a(i)=a(i)*x+y の性能をループ長を変えながら測定したものです。
このループの外側にダミーのループを入れて計測し、キャッシュの効果を見ています。
図で分かるように、データが L2 キャッシュに乗っている間は高い性能が出ています
が、L2 キャッシュを外れて L3 キャッシュの領域に入ると急に性能が低下し、さらにL3 キャッシュを外れると著しく性能が悪くなってしまいます。
do k=1,kk !ダミーのループ
do i=1,n !計測ループ。n=ループ長a(i)= a(i) *x + yenddo
enddo
Ｌ２キャッシュ1800

Ｌ３キャッシュ

1600
1400

MFLOPS

1200
1000
800
600
400
200010100

1,000

10,000100,000

1,000,000

ループ長

図２

積和演算の性能

10,000,000 100,000,000これから分かるように、AzusA においては、できるだけメモリにデータを取りにいかずに、CPU のレジスタやキャッシュ上にデータを保持し、それを再利用するようにすることが、性能向上に重要です。

2 . メモリ関連の高速化技法
ここでは、メモリ関連の高速化技法のいくつかを紹介します。ここでは一般的に性能向上に有効と考えられる手法について述べますが、ここで述べた方法も万能ではな
く、場合によっては単純に適用すると、逆の効果が発生して性能が向上しないこともあります。実際のプログラムはさまざまであり、各プログラムの特性に応じて対応する必要があります。実際のプログラムに適用した場合の例は 3.行列積プログラムを見てください。

2.1. メモリアクセスそのものを減らす
高速化のために最も効果的なのは、メモリアクセスそのものを減らしてしまうことです。例えば、以下のようなプログラムでは、内側ループにある配列参照が、外側ループのインデックス変数に依存していないので、外側ループのアンローリングを行うことによって、B(J)をレジスタ中などに保持し、メモリからのロードを減らすことができます。
do i=1,ndo j=1,ma(j,i)=a(j,i)*b(j)...

do i=1,n‑3,4
do j=1,ma(j,i)=a(j,i)*b(j)a(j,i+1)=a(j,i+1)*b(j)a(j,i+2)=a(j,i+2)*b(j)a(j,i+3)=a(j,i+3)*b(j)...
上の例では４段のアンロールを行っています。アンロール段数を多くすれば、メモリアクセスは減らせますが、あまり多くするとレジスタが足りなくなってソフトウェアパイプライニングが出来なくなり逆に性能が低下してしまいます。したがって、性能が向上するアンロール段数には限界があります。手作業でアンローリングを行う場
合は、コンパイラの最適化レポートを見ながら、ソフトウェアパイプライニングが行われる範囲内でアンロールする必要があります。
このプログラムの場合、以下のようにループを入れ換えることによってもメモリアクセスを減らすことができます。これは、ループ入れ換えにより B(J)がループ内で一定となり、ループの外で一度だけロードすれば良いようになるからです。
do j=1,m
do i=1,na(j,i)=a(j,i)*b(j)...
しかし、この例の場合は、ループ入れ換えを行うと、配列Ａの I に関するアクセスが連続でなくなるので、高速化の効果が減ってしまいます。従って、この場合はアンローリングを行うほうが有効と考えられます。
このような外側ループのアンローリングあるいはループの入れ換えは、ある程度はコンパイラが自動的に行います。[3] どのような変形を行ったかは、コンパイルオプ
ション‑opt̲report を指定したときに出力される最適化リストに表示されます。コン
パイラが判断できなかった場合や、人手によるチューニングが効果を発揮すると思われる場合に手作業によるチューニングを検討することになります。

2.2. データをキャッシュに置いて再利用するプログラム中で同一のデータを何度も使う場合、それをキャッシュ上に保持しておくのは性能を出す上で重要です。キャッシュの大きさには限りがあるので、データをキャッシュサイズに収まるようにしなければなりません。そのため、例えば１つのループをキャッシュのサイズのループとそれ以外の部分の２重ループに分解し、さらに外側ループとの入れ換えを行うことによって、同一データを小さい範囲で再利用する方法があります。この技法をキャッシュブロッキングと言います。
DO I=1,N
DO J=1,M... = ... *B(J)DO J2=1,M,JB
DO I=1,N
DO J=J2,min(J2+JB‑1,M)... = ... *B(J)
配列Ｂ

配列Ｂ
キャッシュ
サイズ

再利用
されない

再利用
される

J

JB

Ｉ

J

Ｉ
...

...
Ｉ
JＩ

Ｊ

図３

キャッシュブロッキング

2.3. データを連続アドレスでアクセスするＬ2 キャッシュはラインサイズが 64 バイト（倍精度浮動小数点データ 8 要素）です。
キャッシュとメモリのやり取りはこのライン単位で行われるため、配列データを連続アドレスでデータをアクセスすると、キャッシュ上のデータが有効に使われ、非常に効率が良いです。逆に、配列のとびアクセスを行うと、キャッシュにロードされたデータの内、実際に使うのはそのうち一部のデータとなるため効率が悪くなります。
データを連続アドレスでアクセスするには、ループの入れ換えを行って、一次元目の添字で回るようにする方法があります。また、同一データを何度も参照する場合、作業配列を確保してそこに連続になるようにデータを詰めなおす方法があります。データの参照回数が多ければ詰めなおしのオーバーヘッドを考えても有利な場合があります。
連続アクセス...

キャッシュにロードされたデータをすべて利用

とびアクセスキャッシュにロードされたデータの一部しか利用しない

図４

連続アクセスと、とびアクセス

3 . 行列積プログラム
次の行列積のプログラムを例題にいくつかのチューニングを適用していきたいと思います(配列 a,b は、一次元目を+3 するパディングを行っています[4])。
parameter ( n=2048 )double precision a(n+3,n),b(n+3,n),c(n,n)(配列の初期値の設定は省略)
do j=1,ndo k=1,ndo i=1,na(i,j)=a(i,j)+b(i,k)*c(k,j)
end doend doend do3.1. ループの入れ換え
このプログラムでは、ループをどのようにも入れ換えることができますが、性能上はどの順番にするのがいいのでしょうか？ メモリアクセスを数えてみると以下のようになります。
表２最内側ループ
ijk

最内側ループ変数の選択と配列アクセスの特性
メモリへのストア
メモリからのロード
a のストア（連続） a のロード（連続） b のロード（連続）a のストア（とび） a のロード（とび） c のロード（とび）−b のロード（とび） c のロード（連続）i や j のループを内側にする（積和型）よりも、k のループを内側にする（内積型）の方がストアが不要であり、メモリアクセスが少ないことが分かります。従って k のループを内側にし、その外側を i のループにします。
このループでは、ストアするもの(a(i,j))と同じものをロードしているためその影響は顕著ではありませんが、AzusA では、ある要素をロードせずにストアする場合、キャッシュライン上にデータを持ってきてからストアを行うため、ストアは 2 回のメモリアクセスがあるとしなければなりません。
k のループを内側にすると、配列 b は 2 次元目でアクセスするため、連続ではなく、とびアクセスとなりキャッシュの利用面では不利になります。これは後で対策を考えます。
k のループを最内側にした結果は以下のようになります。
do j=1,ndo i=1,ndo k=1,na(i,j)=a(i,j)+b(i,k)*c(k,j)
end doend doend do3.2. 外側ループアンローリングによるメモリアクセスの削減
上記のループを観察すると、配列 c(k,j)は i に依存しないので、i のループをアンローリングすると c(k,j)のメモリアクセスが共通化され削減されることが分かります。また、同様に b(i,k)は j に依存しないので、j のループでアンローリングするとメモリアクセスが削減されます。
アンローリング段数をいくらにするかですが、段数を多くすればするほどメモリアクセスを削減できるのですが、先ほど述べたように、あまり多くしすぎると、ループ内の要素が増えるために、ソフトウェアパイプライニング(SWP)を行うためのレジスタが足りなくなり、SWP ができなくなって、かえって遅くなってしまいます。コンパ
イラの SWP に関するレポート(‑opt̲report)を見ながら、SWP が行われる最も多い段数を実験的に調べると、このループでは i に関して 4 段、j に関して 5 段のアンローリングまで行えることがわかりました。この結果、以下のようなループとなりました。
do j=1,n‑4,5
do i=1,n‑3,4
do k=1,na(i,j)=a(i,j)+b(i,k)*c(k,j)
a(i+1,j)=a(i+1,j)+b(i+1,k)*c(k,j)
a(i+2,j)=a(i+2,j)+b(i+2,k)*c(k,j)
a(i+3,j)=a(i+3,j)+b(i+3,k)*c(k,j)
a(i,j+1)=a(i,j+1)+b(i,k)*c(k,j+1)
a(i+1,j+1)=a(i+1,j+1)+b(i+1,k)*c(k,j+1)
a(i+2,j+1)=a(i+2,j+1)+b(i+2,k)*c(k,j+1)
a(i+3,j+1)=a(i+3,j+1)+b(i+3,k)*c(k,j+1)
a(i,j+2)=a(i,j+2)+b(i,k)*c(k,j+2)
a(i+1,j+2)=a(i+1,j+2)+b(i+1,k)*c(k,j+2)
a(i+2,j+2)=a(i+2,j+2)+b(i+2,k)*c(k,j+2)
a(i+3,j+2)=a(i+3,j+2)+b(i+3,k)*c(k,j+2)
a(i,j+3)=a(i,j+3)+b(i,k)*c(k,j+3)
a(i+1,j+3)=a(i+1,j+3)+b(i+1,k)*c(k,j+3)
a(i+2,j+3)=a(i+2,j+3)+b(i+2,k)*c(k,j+3)
a(i+3,j+3)=a(i+3,j+3)+b(i+3,k)*c(k,j+3)a(i,j+4)=a(i,j+4)+b(i,k)*c(k,j+4)a(i+1,j+4)=a(i+1,j+4)+b(i+1,k)*c(k,j+4)
a(i+2,j+4)=a(i+2,j+4)+b(i+2,k)*c(k,j+4)
a(i+3,j+4)=a(i+3,j+4)+b(i+3,k)*c(k,j+4)
end doend doend do(n を 4,5 で割った余りがある場合のループ処理は省略)
これによって、１メモリアクセス当たりの演算数は、2/2=１から 40/9=4.4 になりました。ただし、このプログラムでは‑O3 オプションでコンパイルすると、コンパイラが自動的に i に関して 4 段、j に関して 4 段のアンローリングを行ってくれます。
上記の手動アンローリングはループが複雑でコンパイラが自動的にアンローリングできない場合向けです。

3.3. キャッシュブロッキング
本ループは、b(i,k)が j に依存しないため、i,k に関してブロッキングを行えば、b(i,k)をキャッシュに乗せることができます。ここでは L2 キャッシュに乗せるため、ブロッキングファクタを ib=108, kb=108 とします。（108*108*8 バイト=93K<96K バイト）。
do is=1,n,ib
do ks=1,n,kb
do j=1,n‑4,5do i=is,min(is+ib‑1,n)‑3,4
do k= ks,min(ks+kb‑1,n)ループ内は前と同じ
end doend doend doend doend do3.4. 配列アクセスの連続化
配列 b はとびアクセスになっているため、これを連続アクセスになるようにします。
作業配列 bb を用意し（サイズは ib*kb）、配列 b を転置してコピーします。これによって、キャッシュへのロード時の性能がさらに改善されます。配列 bb にいったんコピーするオーバーヘッドは n が大きければ無視できます。
do is=1,n,ib
do ks=1,n,kb
do i=is,min(is+ib‑1,n)do k= ks,min(ks+kb‑1,n)bb(k‑ks+1,i‑is+1)=b(i,k)
end doend dodo j=1,n‑4,5
do i=is,min(is+ib‑1,n)‑3,4do k= ks,min(ks+kb‑1,n)a(i,j)=a(i,j)+bb(k‑ks+1,i‑is+1)*c(k,j)...
(上記の文で i を 4 段、j を 5 段アンローリング)
end doend doend doend doend do配列b連続方向123

作業配列bb1 2 3あるブロックで使用する部分

図５

転置
詰め直し

配列の詰め直し3.5. プリフェッチの最適化
AzusA では、メモリロードのレーテンシを隠すためにプリフェッチの生成が有効です。プリフェッチとは、実際のメモリアクセスの前にキャッシュにデータを持ってきておくことです。プリフェッチは、‑O3 オプション指定時にはコンパイラが自動的に行いますが、コンパイラはその配列が現れる内側ループ内にプリフェッチを行おうとします。しかし、たとえば配列 c のアクセスに関しては i に依存しないので、i のループの外側でプリフェッチを行うことによって、プリフェッチ命令実行のオーバーヘ
ッドを削減できます。手動でプリフェッチを行うには、lfetch 組込みサブルーチンを呼び出します。
do is=1,n,ib
do ks=1,n,kb
do i=is,min(is+ib‑1,n)do k= ks,min(ks+kb‑1,n)bb(k‑ks+1,i‑is+1)=b(i,k)
end doend dodo j=1,n‑4,5
do k=ks,min(ks+kb‑1,n),8
call lfetch(c(k,j))call lfetch(c(k,j+1))

call lfetch(c(k,j+2))
call lfetch(c(k,j+3))
call lfetch(c(k,j+4))
end dodo i=is,min(is+ib‑1,n)‑3,4
call lfetch(a(i+8,j))call lfetch(a(i+8,j+1))
call lfetch(a(i+8,j+2))
call lfetch(a(i+8,j+3))
call lfetch(a(i+8,j+4))
do k= ks,min(ks+kb‑1,n)a(i,j)=a(i,j)+bb(k‑ks+1,i‑is+1)*c(k,j)...
(上記の文を使って i を 4 段、j を 5 段アンローリング)
end doend doend doend doend doc(k,j)のプリフェッチで k を 8 とびに回しているのは、L2 キャッシュのラインサイズが 64 バイトであるので、１ライン当たり 1 要素のプリフェッチ（これで、そのライン全体が取ってこられる）で十分だからです。なお、手動でプリフェッチを行った
場合、コンパイラがプリフェッチを余分に生成しないように‑O2 でコンパイルします。
また、‑O2 でコンパイルすると、a に関しても、手動でプリフェッチを行う必要が出てくるので、そのための lfetch 呼び出しコードも入れておきます。

4 . 性能測定結果
上記のチューニングを行った行列積プログラムの性能を AzusA で測定しました。行
列のサイズは 2048*2048 とし、L2 および L3 キャッシュサイズよりかなり大きなものとしました。コンパイラの最適化レベルは既定値（‑O2）です。
オリジナルプログラムに対して、まずループ入れ換えを行うと、配列アクセスが連続でなくなるので性能が一時的に大きく低下します。しかし、その後、各種の最適化を適用することにより、1741MFLOPS を達成しました。これは、図 2 の積和演算のグラフからみても、データが L2 キャッシュに載った時の性能と同じレベルであり、最大性能を達成できていると言えます。
なお、オリジナルプログラムで‑O3 オプションを指定するとコンパイラによって外側ループのアンロールとプリフェッチが行われているので、約 1000MFLOPS という性能が出ます。

1

表３ チューニング性能測定結果行ったチューニング
時間
性能（秒） （MFLOPS）
オリジナル
325.5
57

2

ループ入れ換え

497.1

34

3

2 + 外側ループアンロール

76.022643 + キャッシュブロッキング

33.35145

4 + 配列連続化

11.1

1542

6

5 + プリフェッチの最適化

9.8

1741

−

オリジナル(‑O3 でコンパイル)

17.0

1009

5. おわりにメモリアクセスの削減の観点から AzusA 向けプログラムのチューニング方法を説明しました。AzusA ではコンパイラの最適化機能を利用して自動的に性能を出すことができますが、ここで説明したような技法を適用することにより、さらに性能向上できる場合があります。本稿がチューニングの参考になれば幸いです。その他さまざまなチューニング技法は、参考文献[5]に記述されています。
なお、今回はシングル CPU でのチューニングを説明いたしましたが、並列処理向けのチューニング技法については、別の機会にご紹介したいと思います。
参考文献[1] 鈴木 重信, 高木 均, 横山 淳,

汎用コンピュータシステム「TX7/AzusA」,SENAC Vol.34, No.3, 2001
[2] Intel株式会社,ンス

Itanium(R)プロセッサ・マイクロアーキテクチャ・リファレ

資料番号: 245473J‑002, 2000

(ftp://download.intel.co.jp/jp/developer/jpdoc/24547302‑s̲j.pdf)[3] 山本 秀喜, 左近 彰一, TX7/AzusA Fortran , SENAC Vol.34, No.3, 2001
[4] 左近 彰一,

TX7/AzusA Fortranプログラムの高速化技法, SENAC Vol.35, No.2,

2002[5] 寒 川光 , RISC 超 高 速 化 プ ロ グ ラ ミ ン グ 技 法(ISBN4‑320‑02750‑7), 共 立 出 版 , 1995