Get Slide

HPC
Unit
HPCアプリケーション向け
計算網羅性 / 計算順序を
テストするツール
穂積俊平* 佐藤芳樹
千葉滋
東京大学大学院情報理工学系研究科
創造情報学専攻
2
計算の分割によるバグの混入
計算の分割
 1つのループを複数のループに分割
| キャッシュヒット率の改善 (e.g. 行列積におけるブロック化)
| 並列分散実行 (e.g. MPI)
| 計算のオフロード (e.g. GPGPU)
バグの温床
 分割の境界の計算間違い (e.g. 抜け, 重複)
 分割による計算順序の変更 (e.g. 依存関係の破壊)
3
グラムシュミットの正規直交化法 @ RSDFT
RSDFT [岩田氏@東京大学]
 物理シミュレーションソフトウェア
 2011 ゴードン・ベル賞
計算の分割による実行性能の改善
 行列積を利用したキャッシュヒット率の改善
 MPIを利用した並列分散実行
4
グラムシュミットの正規直交化法
線形独立なベクトルの組 (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
N:ベクトル数, M:ベクトルの長さ
j
5
計算の分割 @グラムシュミットの正規直交化法
行列積を利用したキャッシュヒット率の改善
 i, j のループを分割, 計算の一部を行列積に委譲
MPIによる並列分散実行
 k のループを分割, 各ノードに計算を割り当て
プログラム
ループが分割される
k
シミュレーション領域
k k
行列積
行列ベクトル積
- 境界判定コードの増加
- カーネル計算がコード中に分散
ランク 2
i
ランク 1
ランク 0
j
6
計算の分割 @グラムシュミットの正規直交化法
行列積を利用したキャッシュヒット率の改善
 i, j のループを分割, 計算の一部を行列積に委譲
MPIによる並列分散実行
 k のループを分割, 各ノードに計算を割り当て
プログラム
ループが分割される
- 境界判定コードの増加
- カーネル計算がコード中に分散
・抜け / 重複
・依存関係の破壊
・誤った計算結果
・終了しない可能性
行列積
抜け
重複
シミュレーション領域
k k
行列積
行列積
行列積
k
行列積
依存関係
の破壊
ランク 2
i
ランク 1
ランク 0
j
7
計算の分割の正しさをユニットテストする
HPCUnit：ユニットテストに必要な機能を提供
 パラメータの変化の追跡と記録
| 範囲, 順序, 文脈 (MPIのランク, 計算結果 etc.)の取得
| ユニットテストの間だけ追跡コードを埋め込める
 HUList : 追跡結果を表すデータ構造
| パラメータの組をタプルの順序付き集合として表現
| 計算の抜けや重複を見つけやすい
| 計算の依存関係を無視したパラメータ変化を見つけやすい
| 正解集合を作るためのAPIも提供
注：現在は Java 向けに開発
8
HPCUnit のテスト方法
パラメータの変化を追跡し, 正解領域と比較
対象アプリケーション
OptimizedGS.java
class
void
...
...
}
}
OptimizedGS {
calc(..){
BLAS.gemv(..);
BLAS.gemm(..);
BLAS.java
class BLAS {
static void gemv(..){
... kernel(i,j,k);
}
static void gemm(..){
... kernel(i,j,k);
}}
CollectingLogs.aj
・カーネル計算の指定
・追跡パラメータの指
定
GSTest.java
・追跡結果と正解集合
の比較
計算に抜けがない事を保証
==
テストコード
∪
9
HPCUnit ができるテスト
計算の分割によって発生するバグを検出 / 特定
 計算の抜け
対象アプリケーション
OptimizedGS.java
class
void
...
...
}
}
OptimizedGS {
calc(..){
BLAS.gemv(..);
BLAS.gemm(..);
==
BLAS.java
class BLAS {
static void gemv(..){
... kernel(i,j,k);
}
static void gemm(..){
... kernel(i,j,k);
}}
 計算の重複
計算に抜けがない事を保証
==
∪
{}
==
∩
∪

|
|
|
応用
依存関係の検査
プログラムの局所性の評価
計算結果の突合
10
MPIアプリケーションのテストも可能
追跡したMPIランクから各ノードのオフセット値を計算
 分散メモリにより、各ノードの担当領域の始点は０
 HUList の map メソッドを利用
0
k
ランク 0
0
0
ランク 1
0
ランク 2
.map(
(rank, i, j, k) ->
(i, j, k + 10*rank)
)
注擬似コード
10
20
11
パラメータの変化の追跡
アスペクトで追跡方法を記述
 監視対象とするカーネル計算の指定
| 制御フローやクラスによってカーネル計算を絞り込める
 追跡するパラメータの指定
| 範囲, 順序, 文脈の取得
CollectingLogs.aj
pointcut atGemvKernel(int i, int j, int k):
args(i,j,k, ..) &&
within(BLAS) &&
cflow(call(void gemm(..))) &&
call(void kernel(int, int, int, ..));
before (int i, int j, int k) :
atGemvKernel(int i, int j, int k) {
GSTest.gemmArea.add(new HPCTuple3(i, j, k));
}
BLAS.java
class BLAS {
static void gemv(..){
... kernel(i,j,k);
}
static void gemm(..){
... kernel(i,j,k);
}
}
12
HUList : 追跡結果を表すデータ構造
パラメータの組の順序付き集合
計算の抜け
 正解集合と比較し, 抜けや重複を発見
==
 様々な集合演算を提供
GSTest.java
class GSTest {
static HUList simuArea, nullArea;
static HUList gemvArea, gemmArea;
計算の重複
{} ==
HUList API
void gsTest() {
/* テストドライバ */
GS gs = new OptimizedGS();
gs.calc(arr, N, N-1, M);
/* 不変条件式 */
simuArea.equals(gemvArea.union(gemmArea)));
nullArea.equals(gemvArea.intersection(gemmArea))
}}
∪
∩
意味
equals
等価性
union
和集合
intersection
積集合
difference
差集合
map
写像
fold
畳み込み
13
正解集合の作成方法
典型的なシミュレーション領域を作るメソッドを利用
 引数で領域サイズを指定
 e.g. 直線, 長方形, 直方体, 三角柱...
意味
HUList API
HUList getLine (int L1)
直線
HUList getRectangle (int L1, int L2)
長方形
HUList getCuboid (int L1, int L2, int L3)
直方体
HUList getTriangularPrism (int L1, int L2, int L3)
三角柱
最適化前のアプリケーションを追跡
 テスト対象アプリケーションと同様の方法で追跡
14
実験
目的
 HPCUnit によるオーバーヘッドの程度を知る
 HPCUnit のオーバーヘッドの原因を探る
内容
1. マイクロベンチマーク
2. グラムシュミットの正規直交化法に適用
オーバーヘッドが
大きすぎると,
実データサイズの
ユニットテストが
できない
実験環境






FUJITSU Supercomputer PRIMEHPC FX10 1 ノード
Linux ベースの専用 OS (カーネル 2.6.25.8)
SPARC64TM IXfx 1.848 GHz
Memory 32GB
OpenJDK Runtime Environment (IcedTea6 1.11.5)
実行オプションデフォルト
15
１.マイクロベンチマーク
5つのプログラムの実行時間を測定 / 比較
 配列の要素を添え字の2倍にするプログラムに対し
 4つの方法でパラメータの変化を追跡するコードを埋め込んだ
 (配列の長さ = 10^7)
実行時間 (ms)
(1) 元プログラム
42 ± 0.5
(2) HUList (オブジェクト) + AspectJ
12800 ± 215
(3) HUList (オブジェクト)+ 手織り込み
12690 ± 135
(3) HUList (配列) + AspectJ
143 ± 0.4
(4) HUList (配列) + 手織り込み
82 ± 0.4
タプルオブジェクトの生成コストが大きい
アスペクトによるオーバーヘッドが見られる
16
2. グラムシュミットの正規直交化に適用
４つのプログラムの実行時間を測定 / 比較
 3つの目的を達成するためにパラメータの変化を追跡
| カーネル計算追跡：計算の重複, 抜けをテスト
| 行列読み込み追跡：プログラムの局所性を評価
| 行列書き込み追跡：計算結果の比較
N (ベクトル数, ベクトルの長さ) = 128
実行時間 (ms)
相対時間
取得した領域のサイズ
(1) 元プログラム
625 ± 20
1
0
(2) カーネル計算追跡
1800 ± 98
3
N x N x (N – 1) / 2
(3) 行列読み込み追跡
3556 ± 15
6
N x N x (N – 1) * 2
(4) 行列書き込み追跡
715 ± 35
1.2
NxN
テストケース毎にオーバーヘッドが大きく異な
る
17
関連研究
ユニットテスト
 e.g. JUnit [Yoonsik Cheon et al ECOOP’02]
 HPCUnit は HPC に特化したテストフレームワーク
モデル検査
 e.g. SPIN, Java Path Finder [Klaus Havelund et al STTT’00]
 HPCUnit のような HPC に特化したサポートが必要
追跡ベースの検査
 e.g. tracematch [Chris Allan et al OOPSLA’05]
 部分的な制御フローの検査が目的
18
まとめと今後の課題
まとめ
 HPC 向けユニットテストツール HPCUnit を提案
| パラメータの変化の追跡と記録
| 追跡結果を表すデータ構造
 HPCUnit のオーバーヘッドを計測
今後の課題
 オーバーヘッドの削減
 メモリ使用量の削減
 Domain Specific Language の設計

Download Report