Get Slide

HPCアプリケーションの
OOPを用いた
パフォーマンスチューニング
東京大学大学院
創造情報学専攻
穂積俊平* 伊尾木将之千葉滋
2
HPCの現状
• C言語やFortranによって記述されている
- 実行性能が重要
• 手続きライブラリが広く利用されている
- 関数単位での変更のみ可能
3
HPCの近年の傾向
• 実行環境に合わせたチューニングが必要
- 実行環境のハードウェアが多様化
GPU
マルチCPU
コンピュータ
クラスタ
4
HPCの近年の傾向
• 実行環境に合わせたチューニングが必要
- 実行環境のハードウェアが多様化
GPU
マルチCPU
コンピュータ
クラスタ
5
HPCの問題点
• 粒度の細かいチューニングができない
- 手続きライブラリはブラックボックスであり、関数よ
り粒度の細かい変更が不可能。
入力
出力
メモリ管理
データ転送
6
HPCの問題点
• 粒度の細かいチューニングができない
- 手続きライブラリはブラックボックスであり、関数よ
り粒度の細かい変更が不可能。
入力
出力
メモリ管理
データ転送
処理(関心事)
ごとに実装を
決めたい！
7
例：行列積
Cコード
for (int i = 0; i < L; i++) {
①
②
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k] * B[k * N + j];
}}}
③
A
L
B
M
＊
M
C
N
＝
L
N
8
例：行列積
Cコード
for (int i = 0; i < L; i++) {
①
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k]
* B[k * N + j];
• 素直な２重ループ
• i と j を入れ替えた２重ループ
}}}
• GPUで並列実行
• MPIで並列実行
A
L
B
M
＊
M
C
N
＝
L
i
N
j
9
例：行列積
• 素直なループ
Cコード
for (int i = 0; i < L; i++) {
• 展開したループ
②
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k] * B[k * N + j];
}}}
A
L
M
B
k
＊
M
k
C
N
＝
L
N
10
例：行列積
• １次元配列
• ２次元配列
Cコード
• シェアードメモリ
for (int i = 0; i < L; i++) {
• 疎行列
for (int j = 0; j < N; j++) { • 対角行列
for (int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k] * B[k * N + j];
}}}
③
A
L
M
１次元配列
M
・・・
11
C言語での実装
• 保守性のスケーラビリティが得られない
- 関数ポインタ
- ifdef
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Javaコード
Matmul matmul = new Matmul();
matmul.setTraverse (new Traverse());
①
matmul.setReduction(new Reduction());
②
Mat A = new SingleArray(), B =・・・, C =・・・;
matmul.calc(A, B, C);
③
12
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Javaコード
Matmul matmul = new Matmul();
matmul.setTraverse (new ParallelOnGPU());
①
matmul.setReduction(new Reduction());
②
Mat A = new SingleArray(), B =・・・, C =・・・;
matmul.calc(A, B, C);
③
13
14
オートチューニングへの応用
• 実装の切り替えが容易
Javaコード
List<Traverse> traverses;
traverses.add(new Traverse());
traverses.add(new ParallelOnGPU());
:
for(Traverse tra : traverses) {
matmul.setTraverse(tra);
matmul.calc(A, B, C);
}
Cのたどり方の実装を
変更して実行
15
HPCアプリケーションの特徴
• カーネルコードが計算時間の大半を占める
実行過程
各種設定
カーネル
コード
実行時間
16
WootinJ
• OOPと実行性能を両立する機構
- カーネルコードを強力にJITコンパイルする
- ユーザに最適化の条件を満たしているかを提示
実行時
コンパイラ
コンパイル時
チェッカー
Java
バイトコード
Java
ソースコード
最適化
機械語
警告！
17
通常のJITとの違い
• OOPと実行性能を両立する機構
- カーネルコードを強力にJITコンパイルする
• 静的型
• 動的型
一部をインライン化
• オブジェクト
• メソッド
最適化
Java
バイトコード
機械語
18
通常のJITとの違い
• OOPと実行性能を両立する機構
- カーネルコードを強力にJITコンパイルする
• 静的型
• 動的型
• strictfinal
全てをインライン化
• オブジェクト
• メソッド
最適化
Java
バイトコード
機械語
19
WootinJ
• OOPと実行性能を両立する機構
- カーネルコードを強力にJITコンパイルする
- ユーザに最適化の条件を満たしているかを提示
• strictFinal : 静的に型が一意に決定できる型
- プリミティブな型
- strictFinalの配列
- 自分と親クラスのフィールドがstrictFinalであり、final
な型
20
WootinJ
• OOPと実行性能を両立する機構
- カーネルコードを強力にJITコンパイルする
- ユーザに最適化の条件を満たしているかを提示
Java
ソースコード
strictFinal ?
警告！！
21
WootinJ
• OOPと実行性能を両立する機構
- カーネルコードを強力にJITコンパイルする
ユーザが指定したメソッド
Javaコード
static void main(String[] args) {
CUDARunner.invoke(
new Calc(), “run”, new A()
);
メソッド情報
}
class Calc {
void run(A a){
a.hoge();
}
}
Java
バイトコード
Java
抽象構文木
最適化
CUDA
コード
機械語
実行
22
WootinJ
• OOPと実行性能を両立する機構
- カーネルコードを強力にJITコンパイルする
ユーザが指定したメソッド
Javaコード
static void main(String[] args) {
CUDARunner.invoke(
new Calc(), “run”, new A()
);
メソッド情報
}
class Calc {
void run(A a){
a.hoge();
}
}
メソッドのレシーバ、実引数の
型は変換時に一意に決定できる
メソッドのレシーバ、実引数は
自由にOOPの抽象化を利用できる
23
実験
• 目的
- WootinJの実行性能の測定
• 実験環境
- Tsubame2.0 : 東工大のスパコン
• プログラム
- 行列積
24
実験結果
• 変換によるオーバーヘッドの分だけWootinJの方が遅
かったが、OOPの抽象化による差は見られなかった。
良
25
関連研究
• Firepile [Nathaniel Nystromら・2011]
- ScalaからOpenCLへの実行時変換器。動的束縛は
Switch文を用いて表現
• Aparapi
- JavaからOpenCLへの実行時変換器。オブジェクトの
利用はできない
26
まとめと今後の課題
• まとめ
- オブジェクト指向を利用する事で、実行環境に合わせ
たパフォーマンスチューニングができる事を述べた。
- オブジェクト指向と実行性能を両立する機構として
WootinJを開発した。
• 今後の課題
- WootinJを利用したフレームワークの作成
- C++との比較
36
Cの要素のたどり方
素直な２重ループ
for (int i = 0; i < L; i++) {
for (int i = 0; i < L; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
for (int j = 0; j < N; j++) {
C[i * N + j] += A[i * M + k]*B[k * N + j];
：
}
}
}
}
}
iとjを入れ替えた２重ルー
プ
GPUを利用した並列実行
dim3 grid(N/BS, L/BS), block(BS,BS);
traverse<<<grid, block>>>(A, B, C);
for (int i = 0; i < L; i++) {
for (int j = 0; j < N; j++) {
：
_global_ void traverse(float *A・・){
int i = BS*blockIdx.y + threadIdx.y;
int j = BS*blockIdx.x + threadIdx.x;
：
}
①
}
}
37
Cの１要素の求め方
for (int i = 0; i < L; i++) {
for (int j = 0; j < N; j++) {
素直なループ
for (int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k]*B[k * N + j];
for (int k = 0; k < M; k++) {
}
C[i*N + j] += A[i*M + k]*B[k*N + j];
}
}
}
展開したルー
プ
for (int k = 0; k < M; k+=2) {
C[i*N + j] += A[i*M + k] * B[k*N + j];
C[i*N + j] += A[i*M + k + 1] * B[(k+1)*N + j];
}
②
38
行列の表現方法
• 言語上の確保の仕方の違い
- １次元配列
- ２次元配列
• ハードウェア的な違い
- シェアードメモリの利用
• 行列の種類による違い
- 疎行列
- 対角行列
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Javaコード
Matmul matmul
= new Matmul();
matmul.iterate
= new LoopOnCPU(); ①
matmul.reduction = new Reduction();
②
Matrix A = new SingleArray(),
B =・・・, C =・・・;
matmul.calc(A, B, C);
③
39
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Javaコード
Matmul matmul
= new Matmul();
matmul.iterate
= new LoopOnCPU(); ①
matmul.reduction = new UnrollingReduction();
②
Matrix A = new SingleArray(),
B =・・・, C =・・・;
matmul.calc(A, B, C);
③
40
41
実行環境に合わせたチューニング
• ユーザによる設定ができる形で機能提供すべき
- C言語やFortranでは難しい
• 手続きライブラリはブラックボックス
- ブラックボックス内の実装の変更が困難
入力
出力
メモリ管理
データ転送
複数の処理
(関心事)が
含まれる
42
行列積に含まれる関心事
• 複数の関心事に分割できる
Cコード
for (int i = 0; i < L; i++) {
①
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k] * B[k * N + j];
}}}
A
L
B
M
＊
M
C
N
＝
L
i
N
j
43
行列積に含まれる関心事
• 複数の関心事に分割できる
Cコード
for (int i = 0; i < L; i++) {
②
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k] * B[k * N + j];
}}}
A
L
M
B
k
＊
M
k
C
N
＝
L
N
44
行列積に含まれる関心事
• 複数の関心事に分割できる
Cコード
for (int i = 0; i < L; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k] * B[k * N + j];
}}}
③
A
L
M
１次元配列
M
・・・
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Javaコード
Matmul matmul = new Matmul();
①
matmul.setTraverse(Traverse.factory(“simpleLoop”));
matmul.setReduction(Reduction.factory(“unrolling”));
②
Matrix A = new SingleArray(), B =・・・, C =・・・;
matmul.calc(A, B, C);
③
45
オブジェクト指向を用いたチューニン
グ
46
• ユーザによる設定が可能な形で機能提供ができる
Matmul
void calc(Mat A, Mat B, Mat C) {
tra.calc(A, B, C, red);
}
Traverse
void calc(Mat A, Mat B, Mat C, Reductio
for(int i = 0; i < C.getRows(); i++) {
for(int j = 0; j < C.getCols(); j++)
red.calc(A, B, C);
}}}
ReverseTraverse
void calc(Mat A, Mat B, Mat C, Reduction red) {
for(int j = 0; j < C.getCols(); j++) {
Reduction
for(int i = 0; i < C.getRows(); i++) {
red.calc(A, B, C);
void calc(Mat A, Mat B, Mat C){
}}}{
for(int k = 0; k < A.getCols(); k++)
C[i*C.getCols()+j] += A[i*A.getCols()+k] * B[k*B.getCols()+j];
}}
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Matmul
void calc(Mat A, Mat B, Mat C) {
tra.calc(A, B, C, red);
}
Traverse
void calc(Mat A, Mat B, Mat C, Reduction red) {
for(int i = 0; i < C.getRows(); i++) {
for(int j = 0; j < C.getCols(); j++) {
red.calc(A, B, C);
}}}
ReverseTraverse
void calc(Mat A, Mat B, Mat C, Reduction red) {
for(int j = 0; j < C.getCols(); j++) {
for(int i = 0; i < C.getRows(); i++) {
red.calc(A, B, C);
}}}
47
48
近年の傾向
• 実行環境に合わせたチューニングが必要
- ハードウェアが複雑化している
• GPU
• コンピュータ・クラスタ
• マルチコアCPU
GPU
49
関数による分離
Cコード
void matmul(float *A, float *B, float *C) {
traverse(A, B, C);
}
void traverse(float *A, float *B, float *C) {
for(int i = 0; i < L; i++) {
for(int j = 0; j < N; j++) {
reduction(A, B, C, i, j);
}}}
void reduction(float *A, float *B, float *C, int i, int j) {
for(int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k] * B[k * N + j];
}}
50
手続きライブラリの限界
• 粒度の細かいチューニングができない
- 手続きライブラリはブラックボックスであり、関数よ
り粒度の細かい変更が不可能。
入力
出力
メモリ管理
データ転送
他の実装へ
変更
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Javaコード
class Matmul {
Traverse traverse;
Reduction reduction;
void calc(Matrix A, Matrix B, Matrix C) {
traverse.calc(A, B, C, reduction);
}
}
51
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Javaコード
class SimpleDoubleLoop implements Traverse {
void calc(Matrix A, Matrix B, Matrix C, Reduction red) {
for(int i = 0; i < C.getRows(); i++) {
for(int j = 0; j < C.getColumns(); j++) {
reduction.calc(A, B, C);
}
}
}
}
52
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Javaコード
class SimpleLoop implements Reduction {
void calc(Matrix A, Matrix B, Matrix C){
for(int k = 0; k < A.getColumns(); k++) {
C[i*C.getColumns()+j] +=
A[i*A.getColumns()+k] * B[k*B.getColumns()+j];
}
}
}
53
オブジェクト指向を用いたチューニン
グ
• ユーザによる設定が可能な形で機能提供ができる
Matmul
void calc(Matrix A, Matrix B, Matrix C) {
traverse.calc(A, B, C, reduction);
}
Traverse
Reduction
void calc(Matrix A, Matrix B, Matrix C, Reduction red) {
void calc(Matrix A, Matrix B, Matrix C){
for(int i = 0; i < C.getRows(); i++) {
for(int k = 0; k < A.getColumns(); k++) {
for(int j = 0; j < C.getColumns(); j++) {
C[i*C.getColumns()+j] +=
reduction.calc(A, B, C);
A[i*A.getColumns()+k] * B[k*B.getColumns()+j];
}}}
}}
54
55
関数ポインタによる変更
Cコード
int (*traP)(float *A, float *B, float *C) = &traverse;
int (*redP)(float *A, float *B, float *C, int i, int j) = &reduction;
void matmul(float *A, float *B, float *C) {
(traP)(A, B, C);
}
void traverse(float *A, float *B, float *C) {
for(int i = 0; i < L; i++) {
void traverse(float *A, float *B, float
*C) {j = 0; j < N; j++) {
for(int
for(int i = 0; i < L; i++) {
for(int j = 0; j < N; j++) {
(redP)(A, B, C, i, j);
}}}
(redP)(A, B, C, i, j);
}}}
void reverseTraverse(float *A, float *B, float *C) {
for(int i = 0; i < L; i++) {
void reduction(float *A, float *B, float *C, int i, int j) {
for(int j = 0; j < N; j++) {
for(int k = 0; k < M; k++) {
(redP)(A, B, C, i, j);
C[i * N + j] += A[i * M + k] * B[k * N + j];
}}}
}}
56
関数による分離
Cコード
void matmul(float *A, float *B, float *C) {
traverse(A, B, C);
}
void traverse(float *A, float *B, float *C) {
for(int i = 0; i < L; i++) {
for(int j = 0; j < N; j++) {
reduction(A, B, C, i, j);
}}}
void reduction(float *A, float *B, float *C, int i, int j) {
for(int k = 0; k < M; k++) {
C[i * N + j] += A[i * M + k] * B[k * N + j];
}}
57
手続きライブラリの利用
• 実行環境に合ったライブラリを利用する事で、
アプリケーションのチューニングができる。
線形代数ライブラリ
CPU
• GotoBLAS
• cublas
• ・・・・
GPU
58
関数ポインタによる変更
int (*traP)(float *A, float *B, float *C);
int (*redP)(float *A, float *B, float *C, int i, int j);
void matmul(float *A, float *B, float *C) {
(traP)(A, B, C);
}
void reverseTraverse(float *A, float *B, float *C) {
for(int j = 0; j < N; j++) {
for(int i = 0; i < L; i++) {
(redP)(A, B, C, i, j);
}}}
void traverse(float *A, float *B, float *C) {
for(int i = 0; i < L; i++) {
for(int j = 0; j < N; j++) {
(redP)(A, B, C, i, j);
}}}
59
C言語による実装の限界
• 関数ポインタ
- 安全でない
• フラグによる制御
- ライブラリ作成者がすべての状況を想定できない
オブジェクト指向を用いたチューニン
グ
• 安全に実装の変更が可能
Matmul
void calc(Mat A, Mat B, Mat C) {
tra.calc(A, B, C, red);
}
Traverse
void calc(Mat A, Mat B, Mat C, Reduction red) {
for(int i = 0; i < C.getRows(); i++) {
for(int j = 0; j < C.getCols(); j++) {
red.calc(A, B, C);
}}}
ReverseTraverse
void calc(Mat A, Mat B, Mat C, Reduction red) {
for(int j = 0; j < C.getCols(); j++) {
for(int i = 0; i < C.getRows(); i++) {
red.calc(A, B, C);
}}}
60
61
モジュラリティと実行性能
• WootinJが生成するコードにはJavaの抽象化が
含まれていない
Java
CUDA
• 動的束縛
どうする？？
• オブジェクト
• switch文？
• 構造体？
Javaのサブセットを提供
62
実行時情報を利用した最適化
• 動的メソッド呼び出しの除去
A
Javaコード
static void main(String[] args) {
CUDARunner.invoke(
new Calc(), “run”, new B()
);
実行時情報
}
class Calc {
void run(A a){
a.hoge();
}
}
静的呼び出し
に変換
+hoge()
B
+hoge()
void run(A a) {
B_hoge();
}
void B_hoge() {
:
}
63
実行時情報を利用した最適化
• オブジェクトの除去
Javaコード
A
int x;
static void main(String[] args) {
int y;
CUDARunner.invoke(
new Calc(), “run”, new A()
);
実行時情報
}
プリミティブな
値の利用に変換
class Calc {
void run(int a_x, int a_y) {
void run(A a){
int sum = a_x + a_y;
int sum = a.x + a.y
}
}
}
64
WootinJ
• JavaバイトコードからCUDA Cへの実行時変換器
- 実行時情報を利用し、抽象化のオーバーヘッドを除去
Javaコード
static void main(String[] args) {
CUDARunner.invoke(
new Calc(), “run”, new A()
);
メソッド情報
}
class Calc {
void run(A a){
a.hoge();
}
}
Java
バイトコード
Java
抽象構文木
最適化
CUDA
コード
機械語
実行
65
WootinJ
• OOPと実行性能を両立する機構
- カーネルコードをアグレッシブにJITコンパイルする
- コンパイル時に条件(strictFinal)を満たしているか確認
以下が含まれない
• 動的束縛
• オブジェクト
OOPの抽象化が
含まれないコード
66
実験結果
• 変換によるオーバーヘッドの分だけWootinJの方が遅
かったが、OOPの抽象化による差は見られなかった。
良

Download Report