Get Slide

HPC
Unit
科学技術計算における最適化に伴う
分割の正しさを検査する
ユニットテストフレームワーク
穂積俊平1 佐藤芳樹2 千葉滋3
1,3東京大学大学院
情報理工学系研究科創造情報学専攻
2東京大学情報基盤センター
Shumpei Hozumi
2
科学技術計算プログラマーを手助けしたい
科学技術計算プログラムのバグ検出は難しい作業となっている
 様々な最適化が施され, プログラムが複雑化している
‣ 科学技術計算のプログラムは規模が大きいため, 実行性能が重要視される
‣ 流体力学シミュレーション
‣ 分子動力学シミュレーション
 ヒアリングしてみた
‣ 岩田先生@東京大学
‣ 川村研究室＠大阪大学
 実際に体験してみた
‣ RSDFT のグラムシュミットの正規直交化法を Fortran から Java に移植
Shumpei Hozumi
3
計算の分割による最適化
計算の分割
for i in [0..1]
for j in [0..3]
kernel(i,j)
 例：for ループの分割
‣ 計算順序の変更
：ブロック化
‣ 並列分散実行
：MPI
j
‣ 計算のオフロード：GPGPU
 科学技術計算でよく利用される
‣ 科学技術計算のプログラムは
カーネル計算（中心となる計算）を
繰り返すものが多い
i
0
1
2
3
4
5
6
7
ブロック化
0
1
4
5
2
3
6
7
GPGPU
MPI
 バグの温床
‣ 誤った範囲指定
0
0
0
0
1
1
1
1
0
1
0
1
2
3
2
3
‣ 誤った順序指定
Shumpei Hozumi
4
例：グラムシュミットの正規直交化法 @ RSDFT
RSDFT [岩田先生 @ 東京大学]
 物理シミュレーションソフトウェア
 2011ゴードンベル賞受賞
 1 2
) E XC [  ] 

(
r
    vion  dr
 r  r  (r)  j (r)  j  j (r)
 2


計算の分割によって高速化を実現
 計算順序を変更し, 一部の計算をより局所性の高い計算に変換
‣ 行列積（gemm）
‣ 行列ベクトル積（gemv）
 MPI を利用した並列分散実行
Shumpei Hozumi
5
グラムシュミットの正規直交化法（GS法）
線形独立なベクトルの組（A）から正規直交系（Q）を作るアルゴリズム
 カーネル計算（中心となる計算）が
 計算空間 (パラメータ i, j, k が作る空間) を巡回
計算空間
プログラム
for (i = 0; i < N; i++) {
for (j = 0; j <= i-1; j++) {
ip = 0;
for (k = 0; k < M; k++)
ip += Q[j][k] * A[i][k];
for (k = 0; k < M; k++)
Q[i][k] -= Q[j][k] * ip;
}
カーネル計算
Q[i] /= |Q[i]|;
}
k
i
j
N：ベクトル数, M：ベクトルの長さ
Shumpei Hozumi
6
最適化による計算空間の分割
“i”, “j”, “k” ループが分割される
 行列積, 行列ベクトル積の利用
 MPI による並列分散実行
計算空間
プログラム
k
k k
行列積
行列ベクトル積
ランク 2
i
ランク 1
ランク 0
j
Shumpei Hozumi
7
計算空間の分割が及ぼすプログラムへの悪影響
可読性や保守性が低下
 部分空間の大きさを決定するコードの追加
 境界判定コードの追加
計算空間
プログラム
for (int is=istart; is<=iend; is+=L1) {
ie = min(is+L1-1, iend);
il = ie-is+1;
for (int js=jstart; js<=jend; js+=L1) {
je = min(js+L1-1, jend);
je = min(je, je-1);
jl = je-js+1;
if (jl <= 0) continue;
if (is >= je+1)
gsGemm(is, ie, js, je);
else if (il <= L2)
gsGemv(is, ie, js);
else {
gs(is, ie, js, je, max(L2/2, L1));
}
k
k
行列積
行列ベクトル積
ランク 2
i
ランク 1
ランク 0
j
Shumpei Hozumi
8
計算空間の分割が及ぼすプログラムへの悪影響
可読性や保守性が低下
 部分空間の大きさを決定するコードの追加
 境界判定コードの追加
計算空間
プログラム
for (int is=istart; is<=iend; is+=L1) {
ie = min(is+L1-1, iend);
il = ie-is+1;
for (int js=jstart; js<=jend; js+=L1) {
je = min(js+L1-1, jend);
je = min(je, je-1);
jl = je-js+1;
if (jl <= 0) continue;
if (is >= je+1)
gsGemm(is, ie, js, je);
else if (il <= L2)
gsGemv(is, ie, js);
else {
gs(is, ie, js, je, max(L2/2, L1));
}
k
k
行列積
行列ベクトル積
ランク 2
i
ランク 1
ランク 0
j
Shumpei Hozumi
9
可読性や保守性の低下に伴うバグ
計算の漏れや重複、依存関係の破壊
 誤った範囲指定
 誤った順序指定
検出が難しい
計算漏れ
 計算結果の突合による検出は困難
‣ 浮動小数点演算の誤差を考慮する必要がある
 直接サポートするツールがない
依存関係の破壊
‣ 通常のユニットテストフレームワークでは, プ
ロファイリング情報をテストに活用できない
計算重複
Shumpei Hozumi
10
HPCUnit：計算空間の正しさをテストするフレームワーク
実行ログを利用してバグを検出するための機能を提供
1. メソッド呼び出しの実引数とコンテキスト情報を実行ログとして取得
2. 実行ログをタプルの順序付き集合として保存
3. 問題や環境に合わせたテスト方法
Java 向けフレームワークとして開発
 JVM 周辺のプログラミング資産を活用
テスト対象アプリケーション
..
kernel (i, j, k);
..
①
‣ JUnit, AspectJ, Scala
②
 科学技術計算では Fortran が使われる
==
③
v
バグを検出！
Shumpei Hozumi
11
HPCUnit：計算空間の正しさをテストするフレームワーク
実行ログを利用してバグを検出するための機能を提供
1. メソッド呼び出しの実引数とコンテキスト情報を実行ログとして取得
2. 実行ログをタプルの順序付き集合として保存
3. 問題や環境に合わせたテスト方法
Java 向けフレームワークとして開発
 JVM 周辺のプログラミング資産を活用
テスト対象プログラム
OptimizedGS.java
class OptimizedGS {
void calc(..){
blas.gemv(..);
blas.gemm(..);
}
}
‣ JUnit, AspectJ, Scala
BLAS.java
class BLAS {
void gemv(..){
kernel(i,j,k);
}
void gemm(..){
kernel(i,j,k);
}}
 科学技術計算では Fortran が使われる
∪
==
v
バグを検出！
Shumpei Hozumi
12
HPCUnit を利用してできること
計算の分割によるバグの検出や性能評価
テスト対象プログラム
OptimizedGS.java
class OptimizedGS {
void calc(..){
blas.gemv(..);
blas.gemm(..);
}
}
BLAS.java
class BLAS {
void gemv(..){
kernel(i,j,k);
}
void gemm(..){
kernel(i,j,k);
}}
 計算漏れ
∪
==
∩
 計算重複
{}
==
==
∪
バグの検出や性能評価

‣
‣
‣
その他
依存関係を満たしているか
プログラムの局所性の評価
実行結果の突合
13
テストコードの記述方法
対象プログラムとは別のクラスを作成し, テスト内容を記述
 テストドライバメソッド
‣ 対象プログラムの呼び出し
@RunWith("HUTestRunner.class")
public class GSTest {
 テストメソッド
‣ 実行ログ取得方法
‣ 実行ログ検証方法
@HUBeforeClass
public static void driver() {
new OptimizedGS().calc(..);
}
@HUTest
public void kernelTest(
@HUSet(/* 取得方法 */) HUSet calcArea){
/* 検証方法 */
}
}
Shumpei Hozumi
14
実行ログの取得方法の記述
HPCUnit が提供する「専用言語」を用いて記述
 内包的表記を用いて宣言的に記述
{(i,j,k) | call(void kernel(int i, int j, int k))}
 制御フローやクラスによって対象メソッドを制限
{(i,j,k) | call(void kernel(int i, int j, int k)) &&
cflow(call(void gemm(..)))}
 予約語を用いることでコンテキスト情報を取得
{(count
, i,j,k) | call(void kernel(int i, int j, int k))}
{(mpiRank, i,j,k) | call(void kernel(int i, int j, int k))}
Shumpei Hozumi
15
実行ログの検証方法の記述
HPCUnit が提供する「API」を用いて記述
計算漏れ
 集合演算を用いて実行ログを加工
==
‣ 和集合, 積集合, 差集合, 写像, 畳み込み
 正解集合を作成
‣ 空集合, 直線, 正方形, 三角柱等
∪
計算重複
{}
==
∩
public void kernelTest(@HUSet(..) HUSet gemm, @HUSet(..) HUSet gemv) {
HUSet correct = HUSet.getTriangularPrism(L1,L2,L3);
HUSet nullSet = HUSet.getNull();
assertThat(correct, is(gemm.union(gemv)));
assertThat(nullSet, is(gemm.intersection(gemv)));
}
Shumpei Hozumi
16
テスト方法の指定
テスト内容やプログラムの特性に合わせてテスト方法を選択
 JUnit を用いた通常のテスト（@Test）
 HPCUnit を用いたテスト
（@HUTest）
 MPI 向けの分散, 集約テスト（@HUDistributedTest, @HUGatheredTest）
▸集約テスト
▸分散テスト
それぞれのランクでテストを実行
ランク０にログを集め, テストを実行
スケーラビリティがある
動的な計算空間の分配に対応しやすい
=
=
=
=
Shumpei Hozumi
17
JUnit を用いた通常のテストとの共存
アノテーションに応じてクラスローダを切り替える事で実現
 通常のテストコードには実行ログ取得コードが埋め込まれない
‣ ログ取得コードによるオーバーヘッドが発生しない
‣ ログ取得コードによる挙動の変化が生じない
@Test
通常のクラスローダでテストクラスをロード
@..
メソッド
@HUTest
1. 専用言語で記述された実行ログ取得方法を
AspectJ のソースコードにコンパイル
2. コンパイル結果を対象プログラムに織り込み
3. HPCUnit テスト専用のクラスローダで
ストクラスをロード
テ
Shumpei Hozumi
18
実験
目的
 HPCUnit によるオーバーヘッド, メモリ使用量の程度を知る
内容
 GS 法に対し３つのシナリオでテストを実行し, 時間とメモリ使用量を測定
‣
‣
‣
‣
(a) 元プログラム
(b) 行列書き込み追跡：計算結果の比較
(c) カーネル計算追跡：計算の漏れ, 重複をテスト
(d) 行列読み込み追跡：プログラムの局所性を評価
環境：FX10 １ノード
 Linux ベースの専用 OS (カーネル 2.6.25.8)
 SPARC64TM IXfx 1.848 GHz, Memory 32GB
 OpenJDK Runtime Environment (IcedTea6 1.11.5)
Shumpei Hozumi
19
結果と考察
結果
 テストする空間が大きくなるほど, 実行時間, メモリ使用量ともに増大する
空間のサイズ（個）
(a) 元プログラム
0
(b) 行列書き込み
524288
(c) カーネル計算
33292288
(d) 行列読み込み
133169152
■
オ
ー
バ
ー
ヘ
ッ
ド
（
％
）
140
250
120
200 ■
メ
モ
150 リ
使
用
100
量
（
50 ％
）
100
80
60
40
20
0
考察
0
(b) 行列書き込み (c) カーネル計算 (d) 行列読み込み
 大量のログオブジェクトを生成するコストやそのサイズが原因
 ログオブジェクトの生成方法を変えることで改善できる
‣ タプルの集合ではなく, 範囲の集合として表現する
‣ オブジェクトの生成を一斉に行う
Shumpei Hozumi
20
関連研究
pFUnit [’05 http://pfunit.sourceforge.net/]
 Fortran 向けのユニットテストフレームワーク
 MPI の利用を想定したテストケースを備える
 プロファイリング情報を利用したテストは行えない
Monitoring Oriented Programming [F.Chen et al OOPSLA’07]
 トレースをベースとした実行時検査ツール
 プログラムのある実行点における情報を元に検査できる, しかし, ログ全体を
必要とする計算の漏れや重複のテストには向かない
Shumpei Hozumi
21
まとめ
科学技術計算プログラムによくあるバグを指摘
 計算の分割によって計算の漏れや重複が発生
HPCUnit を開発
 実行ログを利用して計算空間の正しさをテストするための機能を提供
1.
メソッド呼び出しの実引数とコンテキスト情報を実行ログとして取得
2.
実行ログをタプルの順序付き集合として保存
3.
問題や環境に合わせたテスト方法
Shumpei Hozumi

Download Report