「Cell Speed Challenge 2008 規定課題部門」 2008 年 6 月

オンチップ並列処理を利用した密行列 LU 分解の実装
里城 晴紀

小長谷 明彦

東京工業大学 情報理工学研究科 計算工学専攻
本稿では Cell Speed Challenge 2008 規定課題である連立一次方程式を解くために開発した left-looking 法による 32 × 32 のブロック LU 分解について報告する. 規定課題では, 与えられる係数行列のサイズは 32 の倍数という制約が課せられていた. 32 × 32 のブロック LU 分解は計算量に対してデータ転送量の比率が大きい.
このため, 高い演算性能を持つ Cell BE においては, 頻繁なメモリアクセスを必要とする right-looking 法はメモリアクセスが性能ボトルネックとなる. 一方,left-looking 法はデータの時間的局所性が高く, ローカルストア内にキャッシュを用意することで, メモリアクセス回数を大幅に減少させることが期待できる.Left-looking 法
において, 参照の局所性を活かしたタスクスケジューリング法を採用することで最大実行性能 137.8Gﬂops(理論性能の 76.9 ％) を達成した.

1

はじめにSPE

本稿では, Cell Speed Challenge 2008 規定課題にて開A ← A − LU

L U A

発した連立一次方程式求解プログラムに用いた最適化技法について報告する. 規定課題のために作成したプログラ

AMain Memory

ムは, LU 分解, 前進消去および後退消去のモジュールかL U Aらなる. 各モジュールの最適化においては, 自由課題部門
で報告した PDS 最適化サイクル [1] を適用し, 常にメモリアクセスと計算量のバランスを確認しながら最適化した [2]. 前進消去, 後退消去については SIMD 化とループアSPEンローリング, ダブルバッファリングを施した. これらの最適化技法については [3, 4] が詳しい. LU 分解においてLL

図 1: タスクの内容とタスクの待ち行列. 同色のタスクは同じ更新行列 Aij を読み込む.

は,32 × 32 のブロック LU 分解を採用したため, これまで報告されていた 64 × 64 のブロック LU 分解の実装 [5, 6]では生じなかったメモリアクセスボトルネックを解決することが性能向上のポイントとなった.

るためには, メモリアクセス回数そのものを減少させる方法の開発が必要である.

2

性能向上の課題
Cell BE は非常に高い浮動小数点数演算性能を持つた

3

め, メモリアクセスがボトルネックとなりやすい. ブロッ

設計思想

ク LU 分解で最も計算量の多い演算は更新行列 A から L成分と U 成分の積を引いて更新行列 A に戻す行列積差（A ← A − LU）であり（図 1）, 各 SPE の行列積差演算

メモリアクセス回数を減少させることが性能向上に必の逐次実行性能の差がそのまま Cell BE 全体での性能差要である. そこで, 更新領域の時間的局所性が高い left-となる. 32 × 32 のブロック分割では, 計算に必要な 4 つ間は計算時間の 2 倍であり, 通常のタスクスケジューリン

looking 法を採用し, キャッシングを行うことでメモリア
クセス回数を減少させる. キャッシングの効果を確実に得るためのタスクの割り当て方も工夫する. 本節ではこれ

グ法では, ダブルバッファリングを用いても隠蔽不可能ならを実現するための left-looking 法, キャッシング, ロード

メモリアクセスボトルネックが生じる. この問題を解決す

バランシングについて述べる.のブロック (A,L,U, および更新後の A）のデータ転送時1

 A00 A1 0
 M

 Ai0
 M

A
 n0

A1 1 LM O
A i1 LM
A n1 L A 0 0k=0 A 0 1 L A 0 j L A1 0 A1 1k=1L A1 j L
 M
M O M

 A i 0 A i1 L A ij k=i L
 MMM O
A
 n 0 A n1 L A n j Lk=0

L A 0n 
L A1n A1 j k=1
MM 
k=i
A ij L A in 
M O M A n j L A n n 

A01 L A0 j

図 2: Left-looking 法の更新領域.1 列ずつ集中して計算を終わらせる. データの依存関係により SPE 間通信が増加するが, 時間的局所性が高い.

3.1

A 0n 

A1n M 
A in M k=n 
A n n 図 3: Right-looking 法の更新領域. データの依存関係のない広い範囲を計算する. データの依存関係はないが,時間的局所性もない.

Left-looking 法

トすると更新領域 A の読み書き 2 回分のアクセスは不要になる.U 行列成分は他の SPE から転送されるものを連Left-looking 法は更新領域の時間的局所性が高く, データを一時的に保持することができれば, メモリアクセス回数を大幅に減少させることが期待できる. 一方, 最大並列続して利用できるため, タスク中のメモリアクセスは L行列成分を取得するときのみになる. Right-looking 法で度が確保できる right-looking 法は広い範囲の更新を同時は更新領域が広いためキャッシングするのは困難であり,に行うため, メモリアクセスがボトルネックとなり性能が連続で利用できるデータは L 行列成分, または U 行列成向上しない.

分のどちらか一方しかない. そのため right-looking 法ではタスク中のメモリアクセス回数は 3 回必要となる.

図 2,3 に left-looking 法と right-looking 法のそれぞれの更新領域を示す.Right-looking 法は更新領域が広く並

現行の Cell BE のメモリ転送速度は 25.6GB/秒である

列度が高い. しかし, データの依存関係が少ないために通が,Right-looking 法ではタスク中にブロックの転送を 3 回信回数は O(n) 回で済むが, 一度使った更新領域を保持し行うので必要な転送速度は 33.6GB/秒となりメモリアク2ても次に同じものが使われるまでには O(n ) の時間がかセスボトルネックが発生する. 一方, キャッシングを用いかる. 一方,left-looking 法は更新領域が 1 ブロック幅に限た left-looking 法ではタスク中のブロックの転送回数は 1定されているため同じ更新領域が使われるまでの時間は回であるから必要な転送速度は 11.2GB/秒になり, メモO(n) となる. よって,right-looking 法よりも left-looking法を採用したほうがデータキャッシングに必要なローカルリアクセスボトルネックは生じない.

ストアの容量を少なくできる. ローカルストアの容量は十分にあるので, データキャッシングによりメモリアクセスの大幅な減少が期待できる. ただし,left-looking 法ではク3.3

リティカルとなるデータ更新を他の SPE にブロードキャロードバランシングストする必要があるため, 通信回数が O(n2 ) に増えるという問題を持つ. しかし,Cell BE においては,SPE 間通信キャッシングの効果を得るため, また, 各 SPE の計算量は非常に速いため係数行列が十分大きい場合は性能律速をバランスさせるために, SPE の担当領域は 32 行ごと要因とはならない.に巡回させる（図 4）. キャッシュの効果を得るためにはSPE の保持するデータとそれを参照するタスクが一致し3.2なければならないので, 担当領域を固定する必要がある.

キャッシングまた, タスクの数は係数行列の右下ほど多くなるため, 計

Left-looking 法においては更新領域の時間的局所性が高算量を均等に配分するために担当領域は巡回させる必要いため, キャッシュのヒット率が高く, メモリアクセス回がある.32 × 32 のブロック分割で計算する場合は, 担当領数を 3 分の 1 まで減らすことができる. キャッシュがヒッ域を 32 行ごとに巡回させて各 SPE に振り分ければよい.

2

SPE0
SPE1

SPE(i%7)SPE(n%7)

 A 00 A10 M
 Ai0
 M

A
 n0A 01 L A 0 j L A 0 n 
A11 L A1 j L A1n M O MM 
A i1 L A ij L A in MMM 
A n1 L A nj L A nn 

k =lSPE0

LLBroadcast

SPE1

L

Ul +2LBroadcast

M

図 4: SPE の担当領域. ここで Aij は 32 × 32 の行列である. 担当領域が明確に分かれているので, それぞれの SPE の更新作業は他の SPE のキャッシュに影響を与えない.

SPE6

LL

図 5: 各 SPE が実行するタスク.k = l + 1 のときのタス
クには Ul+1 が必要であるから, 計算可能になった直後に計算し, ブロードキャストを行う. ブロードキャストにかかる時間は他のタスクを実行することで隠蔽できる.

実装方法

4

U l +1k = l +1

本節では left-looking 法による 32 × 32 のブロック LU
表 1: 最内ループの命令列の一部.D は 2 命令同時発行を示す. 浮動小数点数演算命令 fnms がすべてのサイクルで発行されている.
D fnms$37,$65,$77,$37
D lqd$77,320($55)
D fnms$38,$67,$7,$9
D shufb $67,$8,$8,$101
D fnms$43,$66,$7,$4
D shufb $66,$94,$94,$101
D fnms$46,$65,$7,$6
D shufb $65,$113,$113,$101
fnms$17,$64,$93,$88
fnms$16,$64,$27,$89
fnms$54,$64,$25,$3
fnms$82,$65,$25,$85
fnms$26,$67,$25,$87
fnms$24,$66,$25,$86
fnms$22,$66,$27,$84
fnms$15,$65,$27,$83

分解の実装についてを述べる.

4.1

ソフトウェアキャッシュ

各 SPE のローカルストア内に 20 ブロック（80KB）分のキャッシュ領域を用意し, 読み込んだ更新領域はこのキャッシュ領域に保持する.Left-looking 法では更新領域が 1 ブ
ロック幅であるから, 7 基の SPE をあわせると係数行列のサイズが 4480 までならば更新領域をキャッシュに格納できる. データはダイレクトマップ方式で格納し, スラッシングを防ぐために置換は行わない. キャッシュに格納したデータは更新がすべて終わった後にメモリに書き戻す.
このとき, 各 SPE の担当領域は重なっていないためキャッシュコヒーレンシを考える必要はない.

4.2

シャッフル命令などはすべて浮動小数点数演算との 2 命

タスクスケジューリング

令同時発行になり, 余った浮動小数点数演算は 1 命令発行

U 行列成分の更新を含むタスクがクリティカルパスとなるため, 各 SPE において最優先に実行する. 各 SPE はになっている. SIMD 命令の記述は [7] を参考にした.SPU
命令セットは [8] で確認できる.

他に計算可能なタスクを割り当てられているので, ブロードキャストにかかる時間は隠蔽できる（図 5）.

54.3

行列積差演算の最適化

性能評価
図 6 に係数行列の大きさごとの実行性能を示す. ただ

行列積差演算には SIMD 化, ループアンローリング, パし, すべての場合で右辺ベクトルは 1 本である. 係数行列イプライン化を施し, さらにループカウンタの計算をシャッが 4096 × 4096 の密行列のとき,7 基の SPE を用いたとフル演算で代用することで, 最内ループで理論性能と同じきの理論性能 179.2Gﬂops の 76.9 パーセントに相当する性能を引き出した. 表 1 は最内ループの命令列の一部であ137.8Gﬂops を達成した. 図 7 に係数行列を 4096 × 4096

る. 演算パイプラインが 1 本しかないため,2 命令同時発行に固定したときの SPE 数と性能の関係を示す. メモリア

比率は 59/128 = 0.46 · · · となっている. ロード, ストア,クセスボトルネックが解消され,SPE 数に比例して性能が3160
140120Gflops

Gflops200180160140120
100806040200

Peak
Performance
05121024 1536

2048 2560 3072

3584

100806040Linear
Perform ance

20040960Matrix Size
図 6: 問題サイズごとの実行性能. 係数行列が 4096× 4096 のとき理論性能の 76.9 パーセントに当たる
137.8Gﬂops を達成した.

123456Num ber of SPEs78

図 7: 係数行列を 4096 × 4096 に固定したときの SPE 数ごとの性能. メモリアクセスボトルネックの解消と SPE間通信の隠蔽に成功したので, SPE 数に比例した性能の向上が見られる.

向上していることがわかる.

[5] Thomas Chen, Ram Raghavan, Jason Dale, Eiji

6Iwata. Cell Broadband Engine Architecture and its
ﬁrst implementation, 2005.

まとめ
データの時間的局所性を利用することで,Cell BE の性[6] Jakub Kurzak, Jack Dongarra. Implementation of能を引き出せることを示した. 本プログラムの実行に必

the Mixed-Precision High Performance LINPACK
Benchmark on the CELL Processor. Concurrency

要なメモリ転送速度は 11.2GB/秒であり, ハードウェア性能の半分以下となっている. したがって,SPE の演算性能

and Computation: Practice and Experience, Volume19, Issue 10, Jul 2007.

が 2 倍になってもメモリアクセスボトルネックは発生しない. このことは現行の Cell BE アーキテクチャには性[7] Sony Computer Entertainment Inc. SPU C/C++ 言

能改善の余地があることを示唆している.

語拡張 Version 2.3, 2006.

[8] Sony Computer Entertainment Inc. Synergistic Pro-

参考文献

cessor Unit 命令セット・アーキテクチャ Version 1.2,
2007.

[1] Haruki Satoshiro, Akihiko Konagaya. PDS Optimization Cycle: New Programming Optimization
Methodology for Cell BE Architecture.
2008.

SACSIS[2] 里城晴紀, 小長谷明彦. オンチップ並列処理を利用した密行列 LU 分解の高速化. SACSIS 2008.

[3] IBM. Cell Broadband Engine Programming Tutorial
Version 3.0, 2007.
[4] IBM. Cell Broadband Engine Programming Handbook Version 1.1, 2006.
4