進捗 Javaバイトコード変換による 細粒 度CPU資源管理

進捗
Javaバイトコード変換による
細粒度CPU資源管理
hayami
2015/9/30
1
本研究の概要
Javaプログラムの消費資源を細粒度に管理
 実行命令数を正確にカウント
 カウントをもとに何かおもしろいことをする(未定)
バイトコード変換による実装
 移植性、柔軟性はよい
 Time overheadが大きい (11~45%)
2015/9/30
2
Overheadをどうするか?
バイトコード変換アルゴリズムの改良
 Trivial: 1命令ずつカウント
 EachBlock: 基本ブロック単位でカウント
 WeightFirst: 基本ブロックの重みを利用
実装の改良
 高速なthead local
 シグニチャ書換
2015/9/30
3
目次
概要
バイトコード変換アルゴリズム
実装
まとめ・ToDo
2015/9/30
4
バイトコード変換アルゴリズム
(review)
2015/9/30
5
変換アルゴリズム
入力
 対象プログラム
出力
 制約*を満たすコードの挿入位置
 各ポイントでいくつカウンタを増加するか
*正確なカウント&Lmax制約 (後述)
2015/9/30
6
アルゴリズム適用例
入力例
Method void main(java.lang.String[])
iconst_0
← +1
istore_0
← +1
goto 36
← +1
iinc 0 1
← +1
iload_0
← +1
ldc #31 <Integer 100>
← +1
if_icmplt 9
← +1
return
← +1
2015/9/30
出力例1:
Trivial
← +3
← +1
← +3
← +4
← +3
← +1
← +4
出力例2: 出力例3:
EachBlock WeightFirst
7
変換アルゴリズムへの要求
実行命令数の正確なカウント
実行時のオーバーヘッド小
 1命令おきにコード挿入は非現実的
 ある程度まとめてカウンタをインクリメントするべき
Lmax制約
0    Lmax
 :カウンタの値と正確なカウントとの誤差
Lmax:「きめ」に関する定数
2015/9/30
8
EachBlock
基本ブロックの末尾でまとめて増加
+3
+1
+3
+1
2015/9/30
9
WeightFirst
基本ブロックを実行頻度に応じて重み付け
重いブロック優先
+3
+4
2015/9/30
+4
重いブロック
10
実装の改良
2015/9/30
11
Thread Localな変数
各threadの実行命令数をカウント
→ 各Threadに別々のカウンタ変数が必要
Java.lang.ThreadLocal
 非常に高コスト
 currentThread() invocation + Table lookup
2015/9/30
12
java.lang.Theadの書き換え
フィールドの追加
 Table lookupは不要 (ただのフィールド参照)
public class java.lang.Thread {
CPURes cpures;
}
2015/9/30
// フィールドの追加
private void init(…) {
// インスタンスの生成時に
cpures = new CPURes(); // フィールドも初期化
…
}
13
シグニチャの書換(引数+1)
CPUResを引数で渡す
 currentThread()も、Table lookupも不要
void a() {
b();
}
2015/9/30
void A(CPURes res) {
b(res);
}
14
実験
 実行時間の計測
1. シグニチャ書換の影響


Signature Unmodified: シグニチャ書換前
Signature Modified: シグニチャ書換後
2. アルゴリズムの比較

2015/9/30
Eachblock v.s. WeightFirst
15
1. 実行時間 (シグニチャ書換前
後)
 シグニチャの書換で実行時間が改善
(2~10倍 → 1.x倍)
Normalized Execution Time (EachBlock, Lmax=100)
6.00
5.00
4.00
Signaure Unmodified
Signaure Modified
3.00
2.00
1.00
2015/9/30
ga
u
k
pe
jac
dio
ac
jav
db
ss
je
es
s
po
r
ee
n
m
co
m
Qu
Fi
b
0.00
Benchmarks
16
2. 実行時間 (EB v.s. WF)
WFでもあまり改善は見られない
Normalized Execution Time (Lamx=100)
1.80
1.60
1.40
1.20
1.00
EachBlock
WeightFirst
0.80
0.60
0.40
0.20
k
jac
dio
m
pe
g
au
ac
jav
db
ss
re
co
m
po
je
ss
n
ee
Qu
Fi
b
0.00
Benchmarks
2015/9/30
17
まとめ
バイトコード変換による実装は一段落
変換アルゴリズム
 WeightFirstでは物足りない
2015/9/30
18
ToDo
1. Brute Forceで最適解を求めてみる
2. 「おもしろいこと」とは何か?
2015/9/30
19