Javaバイトコード変換による細粒度CPU資源管理 ~Progress Report for SWoPP2001~ hayami 1 背景 Javaの普及・用途の多様化  アプレット信頼できないコードも安全に実行したい Security Manager, Verifier…  CPU、メモリといった資源の管理が不充分  悪意のあるプログラムが資源を独占する可能性がある 2 本研究の目的ユーザレベルでCPU資源を管理 Management = Accounting + Restriction* Accounting プログラム毎にCPU資源の消費量を計測 Restriction 資源を独占しているプログラムに対処 * ” + Reservation” も考えられる 3 発表の概要アプローチ問題の定式化アルゴリズムの提案実装・実験関連研究卒論からの進展・TODO 今後の予定 4 アプローチ JVMを改変  命令を実行しながら直接資源を管理  直接的 OSの機能を利用  native codeを使用してOSの資源管理機能を利用  特定のOSに限定される。ポータビリティが悪いバイトコード変換  資源管理を適用する対象プログラムを変換既存のどのJVMでも動作  JIT(Just in Time Compiler)の恩恵にあずかれる  柔軟性が高い  ただし、実行時のオーバーヘッドは比較的大きい  5 バイトコード変換例ソース class NullLoop { public static void main(String[] args) { for (int i=0; i<100; i++) ; CPURes.incrementAndCheck(3) } } バイトコード Method void main(java.lang.String[]) iconst_0 istore_0 goto 36 iinc 0 1 iload_0 iconst_3 ldc #31 <Integer 100> invokestatic #34 <Method if_icmplt 9 incrementAndCheck(int)> return 6 変換を行う際の方針プログラム中に適切なコードを挿入、実行命令数を動的にカウント  オーバーヘッドは小さく   管理のきめ細かさを保証   1命令ずつカウントしていては話にならないカウンタの値と実際のカウントがあまりに乖離するのは不都合カウントは正確に 7 対象プログラムのモデル化 ~コード挿入コストの定義~ Control Flow Graph(CFG)でモデル化    Basic Block → Node 制御の移動 → Edge Blockの実行頻度 → 重みコード挿入コスト Ctotal = （コードを挿入したNodeの重みの総和重複を許す） iconst_0 istore_0 goto 8 1 iinc 0 1 100 iload_0 ldc #1 <Integer 100> if_icmplt 5 101 return 1 8 「きめ」に関する制約条件 ~Lmax制約~ 高々Lmax命令以内に、少なくとも１回はインクリメントされることを保証    Lmax ：インクリメントｆｒｅｅの間隔 Lmax ：「きめ」に関する定数 e.g. Lmax制約はループ中に最低1つはコードを挿入することを要請 9 問題の定式化(1) 入力: CFG  重み  G  (V , E ) wv v V , wvは自然数出力:  Lmax制約を満たし、かつ実行命令数を正確にカウントするようなコード挿入のうち、コスト Ctotalを最小にするようなもの 10 問題の定式化(2) 1in 1out … 新たに2|V|個の変数を導入 vin: vの先頭における真のカウントとのズレ  vout: vの末尾における真のカウントとのズレ  1 2 4 3 0  vin , vout  Lmax , vin , vout  整数 cv: vin,voutから一意に定まる部分コスト  vin  lv  vout  cv  wv  , Lmax   (lv : vの長さ ) 11 問題の定式化(3) 「Edgeにはコードを挿入しない」条件(VFreq(G,vpl)) pout  sin , ( p, s)  E のもと、全体のコスト Ctotal   cv (vin , vout ) vV を最小化せよ 12 変換アルゴリズム(案) 1. 全探索で厳密解を求める 2. wvの大きいところから決めていく 3. いくつかの制約を緩和して近似 4. EachBlock ∀vin,vout = 0とする Ceach  li    cv (0,0)     L vV vV  max  13 例題問題: Lmax=10, 1in=0 1(5,1) 2(5,101) 4(5,1) 3(1,100) 制約: 1in=0 2in=1out=3out 3in=2out=4in 0≦1in,1out,…,4in,4out<Lmax の下、 Ctotalを最小にするような整数 1in,1out,…,4in,4outを計算せよ ※解が求まれば最適なコードの挿入位置は簡単に決定できる v(lv,wv) 14 EachBlock 問題: Lmax=10, 1in=0 1(5,1) 2(5,101) 4(5,1) 各ブロックの末尾に挿入  1in=1out=,…,=4in=4out=0 は制約を満たすが最適解ではない Ctotal = 1+101+100+1 = 203 3(1,100) v(lv,wv) 15 wvの大きいところから決めていく問題: Lmax=10, 1in=0 重み最大のノードから決定 1. 1(5,1) 2. 2(5,101) 4(5,1)  2in=0 (→1out=3out=0) 2out=5(→4in=3in=5) Ctotal = 1+100+1 = 102 3(1,100)  最適解と一致 v(lv,wv) 16 実装 JOIE(バイトコード変換ツール)を利用 Pure Java  クラスローダの機能を利用しロード時に変換  使い方 > Java Main –a プログラム名 arg1 arg2 … e.g. > Java Main –a Hello 17 実験クラスロード時間と総実行時間を計測  -classic と -hotspot の2通りアルゴリズム  Each Block(他のアルゴリズムは未実装) 環境  K6-2 450MHz, mem 128M, Win98, Java2 SDK1.3 •Fib: Naïveな再帰でfib(35)を計算 •Linpack: floatのベンチマーク •Caffeine: sieve, loop, logic, string, float, method… •Raytrace: レイトレ(Frame版) •JLex: A Lexical Analyzer Generator for Java 18 実験結果(classic) #class 挿入前 (msec) Load Total 挿入後 (msec) Load Total Fib 1 440 16,800 550 51,410 Linpack 1 530 1,040 750 1,790 Caffeine 11 570 24,180 1,710 26,240 RayTrace 17 660 275,230 2,140 383,600 JLex 24 680 4,480 2,660 7,700 19 実験結果(HotSpot) 挿入前 (msec) 挿入後 (msec) #class Load Total Load Total Fib 1 480 1,650 550 2,860 Linpack 1 470 660 770 970 Caffeine 11 510 19,220 1,720 21,500 RayTrace 17 890 55,400 2,400 71,500 JLex 24 650 3,300 4,580 1,580 20 関連研究資源管理  Jres[Czajkowski,Eicken 98] コード挿入アルゴリズム  Punctual Polling[田中 01] バイトコード変換ツール  JOIE[Cohen,Chase 98] 21 卒論後の進展使い勝手の向上  クラスローダを利用して実行時に変換コード挿入アルゴリズムの改良ノードの重みを考慮  実行命令数の正確なカウント  より詳しい性能評価  さまざまなベンチマークで実験・評価 22 TODO コストの最小化がNP完全であることの証明  流量保存則を満たすグラフに限定してもNP完全か? アルゴリズム  拡張   Intraprocedural → Interprocedural ループ展開実装   現在“java”で始まるパッケージには変換を不適用(クラスローダに関する制約) 簡単な最適化(メソッド呼出でincrementは酷い) 名前がほしい 23 今後の日程 6/13(水) 本日 7/3(火) 論文提出締め切り 7/25(水) ~ 27(金) SWoPP@おきなわ 24 To be continued... 25