Javaバイトコード変換による 細粒度CPU資源管理 ~Progress Report for SWoPP2001~ hayami

背景 Javaの普及・用途の多様化 信頼できないコードも安全に実行したい アプレット Security Manager, Verifier… CPU、メモリといった資源の管理が不充分 悪意のあるプログラムが資源 を独占する可能性がある

本研究の目的 ユーザレベルでCPU資源を管理 Management = Accounting + Restriction* 資源を独占しているプログラムに対処 * ” + Reservation” も考えられる

発表の概要 アプローチ 問題の定式化 アルゴリズムの提案 実装・実験 関連研究 卒論からの進展・TODO 今後の予定

アプローチ JVMを改変 OSの機能を利用 バイトコード変換 命令を実行しながら直接資源を管理 直接的 OSの機能を利用 native codeを使用してOSの資源管理機能を利用 特定のOSに限定される。ポータビリティが悪い バイトコード変換 資源管理を適用する対象プログラムを変換 既存のどのJVMでも動作 JIT(Just in Time Compiler)の恩恵にあずかれる 柔軟性が高い ただし、実行時のオーバーヘッドは比較的大きい

CPURes.incrementAndCheck(3) バイトコード変換例 ソース 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 ldc #31 <Integer 100> if_icmplt 9 return iconst_3 invokestatic #34 <Method incrementAndCheck(int)>

変換を行う際の方針 プログラム中に適切なコードを挿入、実行命令数を動的にカウント オーバーヘッドは小さく 管理のきめ細かさを保証 1命令ずつカウントしていては話にならない 管理のきめ細かさを保証 カウンタの値と実際のカウントがあまりに乖離するのは不都合 カウントは正確に

対象プログラムのモデル化 ~コード挿入コストの定義~ Control Flow Graph(CFG)でモデル化 Basic Block → Node 制御の移動 → Edge Blockの実行頻度 → 重み iconst_0 istore_0 goto 8 iinc 0 1 iload_0 ldc #1 <Integer 100> if_icmplt 5 return 1 100 101 コード挿入コスト Ctotal = （コードを挿入したNodeの 重みの総和 重複を許す）

「きめ」に関する制約条件 ~Lmax制約~ e.g. Lmax制約はループ中に最低1つはコードを挿入することを要請 　　　： インクリメントｆｒｅｅの間隔 　　　：「きめ」に関する定数

問題の定式化(1) 入力: CFG 重み 出力: Lmax制約を満たし、かつ実行命令数を正確にカウントするようなコード挿入のうち、コストCtotalを最小にするようなもの

問題の定式化(2) 新たに2|V|個の変数を導入 cv: vin,voutから一意に定まる部分コスト 1 4 2 3 1in 1out … 新たに2|V|個の変数を導入 vin: vの先頭における真のカウントとのズレ vout: vの末尾における真のカウントとのズレ cv: vin,voutから一意に定まる部分コスト

問題の定式化(3) 「Edgeにはコードを挿入しない」条件(VFreq(G,vpl)) のもと、全体のコスト を最小化せよ

変換アルゴリズム(案) 全探索で厳密解を求める wvの大きいところから決めていく いくつかの制約を緩和して近似 EachBlock ∀vin,vout = 0とする

例題 v(lv,wv) 問題: Lmax=10, 1in=0 制約: 1in=0 2in=1out=3out 3in=2out=4in 1(5,1) 4(5,1) 2(5,101) 3(1,100) 制約: 　1in=0 2in=1out=3out 3in=2out=4in 0≦1in,1out,…,4in,4out<Lmax の下、 Ctotalを最小にするような整数 1in,1out,…,4in,4outを計算せよ ※解が求まれば最適なコードの 挿入位置は簡単に決定できる

EachBlock 各ブロックの末尾に挿入 v(lv,wv) Ctotal = 1+101+100+1 問題: Lmax=10, 1in=0 1in=1out=,…,=4in=4out=0 は制約を満たすが最適解ではない Ctotal = 1+101+100+1 = 203 1(5,1) 2(5,101) 4(5,1) 3(1,100)

wvの大きいところから決めていく 重み最大のノードから決定 Ctotal = 1+100+1 最適解と一致 v(lv,wv) 問題: 　　Lmax=10, 1in=0 v(lv,wv) 重み最大のノードから決定 2in=0 (→1out=3out=0) 2out=5(→4in=3in=5) Ctotal = 1+100+1 = 102 最適解と一致 1(5,1) 2(5,101) 4(5,1) 3(1,100)

実装 JOIE(バイトコード変換ツール)を利用 使い方 Pure Java クラスローダの機能を利用しロード時に変換 e.g. > Java Main –a プログラム名 arg1 arg2 … > Java Main –a Hello

実験 クラスロード時間と総実行時間を計測 アルゴリズム 環境 -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

実験結果(classic) #class 挿入前 (msec) 挿入後 Load Total Fib 1 440 16,800 550 51,410 Linpack 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 2,660 4,480 7,700

実験結果(HotSpot) #class 挿入前 (msec) 挿入後 Load Total Fib 1 480 1,650 550 2,860 Linpack 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 1,580 3,300 4,580

関連研究 資源管理 コード挿入アルゴリズム バイトコード変換ツール Jres[Czajkowski,Eicken 98] Punctual Polling[田中 01] バイトコード変換ツール JOIE[Cohen,Chase 98]

卒論後の進展 使い勝手の向上 コード挿入アルゴリズムの改良 より詳しい性能評価 クラスローダを利用して実行時に変換 ノードの重みを考慮 実行命令数の正確なカウント より詳しい性能評価 さまざまなベンチマークで実験・評価

TODO コストの最小化がNP完全であることの証明 アルゴリズム 実装 名前がほしい 流量保存則を満たすグラフに限定してもNP完全か? 拡張 Intraprocedural → Interprocedural ループ展開 実装 現在“java”で始まるパッケージには変換を不適用(クラスローダに関する制約) 簡単な最適化(メソッド呼出でincrementは酷い) 名前がほしい

今後の日程 6/13(水) 本日 7/3 (火) 論文提出締め切り 7/25(水) ~ 27(金) SWoPP@おきなわ

To be continued...