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

Cell BE 向け連立一次方程式の求解プログラムの開発
田原 慎也
東京工業大学 大学院理工学研究科
Cell Broadband Engine 向けとして，連立一次方程式を高速に解くプログラムの開発に取りくんだ．CellBroadband Engine 特有のアーキテクチャは高い理論ピーク性能を誇るが，性能を十分に引き出すためにはそのアーキテクチャを熟知した上で様々なテクニックを駆使しなければならない．今回開発したプログラム
は，縦ブロック分割 LU 分解を用いて係数行列を分解し，前進消去と後退消去により解を求めるアルゴリズ
ムを用いた．係数行列の LU 分解では，32 × 32 のブロックごとに DMA 転送を行い処理を進めることで，データの利用効率を高め，種々の高速化手法を適用し易くしている．高速化手法としては，SIMD 化，DMA転送時間の隠蔽，ループアンローリングなどを利用した．

与えられている．これらのデータの総容量は 80M B 以下はじめに1である．その先頭アドレス（ポインタ buf ）や行列のサ

Cell Broadband Engine(以下 Cell) は，1 つの汎用的なプロセッサコアと 8 つのマルチメディア処理に適したシ

イズ N や M などの情報は，プログラム実行時に SPE に渡され利用することができる．

ンプルなプロセッサコアを持つ，ヘテロジニアスなマルチコア・プロセッサである．その特徴的なアーキテクチャ

2は，非常に高い理論ピーク性能を誇るが，性能を十分に引設計き出すことは難しい．今回，Cell Speed Challenge 2008の規定課題部門において，Cell 向けにプログラム開発を連立一次方程式の解法は，直接法と反復法の２つに大行った．その開発過程や性能を引き出すための高速化手きく分かれる．直接法は，所定の回数の演算を実行すれ法などをここに述べる．

ば必ず求解できる解法で，ガウス消去法や LU 分解を用いた解法が有名である．反復法は，解に適当な初期値を与えて正しい解へと収束させる方法で，直接法より高速な

1.1

規定課題ことが多いが必ず求解できるとは限らない．代表的な解法としては，ヤコビ法やガウス・ザイデル法などがある．

まず，規定課題について説明する．今回出題された課

今回作成したプログラムは，直接法である LU 分解を題は，「連立一次方程式の求解」である．次のように，係用いて連立一次方程式を解くプログラムである．どんな数行列 A，右辺ベクトル B が与えられたときに解ベクト連立一次方程式に対しても求解可能で，多くの並列化手

ル X を求めるプログラムを作成する．

AX = B法が研究されていることからこの解法を選択した．また解ベクトルが複数ある場合にも，LU 分解は一度だけで済(1)

むために有利である．
解ベクトルを求めるまでの計算時間を測定し，それによLU 分解を用いた連立一次方程式の解法は，次のようなりプログラム性能を決定する．競技チームは，このプロ流れである．まず，係数行列 A を下三角行列 L と上三角グラム性能を競うことになる．

行列 U に LU 分解する．

LU X = B

1.2

データ形式と初期配置(2)

ここで U X を C とおいて，係数行列 A は，N × N 行列で各要素は f loat 型である．
右辺ベクトル B と解ベクトル X は，M × N 行列である．

LC = B(3)

ここで，N は 32 の倍数という制約が設けられている．こを C について解く．これを前進消去という．最後に，れらの行列は，メインメモリ上に A，X ，B の順で確保

UX = Cされており，さらにその合計サイズと同等の空き領域が1

(4)

未更新
更新済み
更新中
図 1: 縦ブロック分割 LU 分解

を X について解く．これを後退消去という．前進消去や高速化手法

3

後退消去は，三角行列を利用しているため計算量が少なくて済む．LU 分解には大きく分けて right-looking 法と実装したプログラムの主な高速化手法について述べる．

left-looking 法，crout 法の３つのアルゴリズムが存在する．作成したプログラムは，right-looking 法をもとにしている．

3.1

2.1

ブロック化

ブロック化により，DMA 転送の回数を減らすことがで縦ブロック分割 LU 分解きる．また，問題によっては行列同士の計算でデータの再利用性が高まり，後述する SIMD 演算による高速化の恩恵を受けやすくなる．

LU 分解の並列化にあたって，どの作業領域をどのプロセスに割り当てるか，どのような情報をどんな方法で同前述したように，LU 分解はブロック化アルゴリズムを期するかなど考慮する必要がある．例えば，行列の分配用いている．このときのブロック幅は，問題の制約から 32

方法としては，ブロック分割やサイクリック分割，ブロッとした．各 SPE のデータ保存領域である Local Store(以ク・サイクリック分割などがある．

下 LS) は 256KB と限られているため，n × n のブロック単位で DMA 転送を行い，処理を進めることにしている．

係数行列 A の LU 分解において，係数行列 A をブロッ
ク幅 n を用いて n × n の小行列のブロックに分割し，ブ更新領域の最左ブロック列は，すべての SPE を用いて更ロック単位で計算することが望ましい．これは，LU 分解

新する．このときのピボッティングに関しては，更新をを行列積で実現することが可能で，データの利用効率が行いながら各 SPE で次のピボッティングの候補となる行高くなるからである．また，ブロックごとに SPE を割りを挙げておき，1 列更新が完了する度に同期をとり，最終当てて計算させることで，並列に処理を進めることが安的なピボッティングの行を決定する．最左ブロック列以易になる．しかし，これではピボッティングがブロック外は，それぞれのブロック列を各 SPE が担当して更新す内のみで局所的に行われるため，解の誤差が大きくなる

る．これらのブロック列には依存関係がないので，依存可能性が高い．この誤差の拡大をなくすために，ピボッ関係を気にすることなく並列処理が可能である．

ティングは列全体で行う縦ブロック分割並列 LU 分解の前進代入や後退代入もブロック化により高速化をはかっ考えを取り入れた．係数行列 A を幅 n のブロック列に分た．係数行列は，n×n のブロック単位，右辺行列は，n×4割し，最左ブロック列に対して LU 分解の処理を行う．次のブロック単位で DMA 転送し処理を行う．ただし，右に，この最左ブロックの情報を用いて他のブロック列を辺行列において，m が 4 場合より小さい場合や 4 で割り更新する．このとき，個々のブロック列は独立して処理切れずに余りがでた場合には，n × 1 のブロック単位と可能なので並列に処理を進めることが可能である．

する．

2問題

NM
行列の種類
時間 (msec)
順位

1768
1
非対称密2962224
896
非対称密11732,688
1
非対称密37254256
20,000非対称密204
751,7921
対称密1765632131,072
対称密381
772,7201
三重対角
288
782,240
224
帯行列
294
4

92,656
100
対角優位
334
5

103,200
7
ブロック5804

表 1: 決勝ラウンド結果

3.2

インデックスの作成

3.5SPE は，SPU という演算処理を担当する機構と MFC

LU 分解において，ピボッティングにより係数行列の行交換が必要になる．その度にメモリ上のデータ配置を変という転送処理を担当する機構があり，それぞれ独立して動作することができる．これを利用して，複数のバッ更すると，多くの転送処理が発生してしまう．これを防ファを用意し，演算処理と DMA 転送処理を並行して行ぐために，あらかじめ係数行列の行に関するインデックうことで転送にかかる時間を隠蔽することができる．こスを各 SPE の LS に配列としてつくっておき，行交換がれをマルチバッファリングといい，用意するバッファが発生する度に対応する行の配列要素の交換を行う．ただ２つの場合を特にダブルバッファリングという．プログ

し，係数行列のサイズがある程度大きい場合は，メインラムでは，ブロック単位でのデータ転送・演算処理を行う

メモリ上にインデックスをつくることにする．

ような多くの部分でダブルバッファリングを利用してい係数行列からデータを持ってくる場合には，このインる．特に，LU 分解のブロック列の更新には 1 ブロック列デックスを参照して DMA 転送する．また，LU 分解後はごとに 2 つのバッファを用意しているので，1 つの SPE

このインデックスをもとに係数行列 B の行ソーティングが複数のブロック列を同時並列的に更新するときにはマを行う．

3.3

ダブル（マルチ）バッファリング

ルチバッファリングとなっている．

SIMD 演算4

評価結果

Cell には SIMD 命令があり，16 バイトのデータをまと決勝ラウンドで出題された 10 の問題を今回作成したプ

めて 1 命令で実行することができる．例えば，要素が ﬂoat

ログラムで解くのにかかった時間は図 1 のようになった．

型の場合，4 要素に対して同じ演算を 1 つの SIMD 命令

残念ながら，特に高速に解くような高順位の成績を残すで処理可能である．SIMD 演算は，LU 分解，前進代入とような問題はなかったが，ある程度の性能を引き出しつ後退代入の処理の核となる部分をはじめ，LU 分解後の右つ，指定された誤差の範囲内ですべての問題を解くこと

辺行列 B の行ソーティングにも利用している．

ができている．

3.4

5

ループアンローリング

まとめ
Cell 上で連立一次方程式を高速に解くプログラムの開ループ処理を明示的にアンロールすることで，分岐の発を行った．プログラムでは，縦ブロック分割 LU 分解を削減し豊富なレジスタを有効に利用して高速化をはかっ用いて係数行列を LU 分解し，前進代入と後退代入によりた．Cell には複雑な分岐予測機構がなく分岐ペナルティ解を求めるアルゴリズムを採用した．高速化手法としてが高いため，他のプロセッサと比較して特に有効な高速は，ブロック化によってデータの利用効率を高めて，さら化手法である．今回のような行列演算が主要な処理の場に SIMD 演算やループアンローリングによるテクニック

合は，ループ処理が多いのでループアンローリングの恩を用いた．また，複数のバッファを利用することで DMA恵を受けやすい．

転送時間を隠蔽する手法も用いた．

3

参考文献
[1] Cell Speed Challenge 2008.
http://www.hpcc.jp/sacsis/2008/cell/.

.

[2] Sony Computer Entertainment Inc. Cell Broadband
Engine アーキテクチャ Ver 1.01, 2006.
[3] Sony Computer Entertainment Inc. SPU C/C++ 言語拡張 Version 2.3, 2006.

[4] 今村俊幸．分散メモリ型並列計算機における縦ブロッ
ク分割並列 LU 分解．日本応用数理学会論文誌, Vol.8,No.3, pp. 373–388, 1998.

4