協調動作するオブジェクト群に着目した Javaプログラムの実行履歴分割

Report
協調動作するオブジェクト群に着目した
Javaプログラムの実行履歴分割手法の提案
大平直宏†,谷口考治†,石尾隆†,
神谷年洋‡,楠本真二†,井上克郎†
†大阪大学大学院情報科学研究科
‡科学技術振興機構さきがけ
2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
発表の流れ

背景と目的
プログラムの実行履歴を用いたオブジェクト指向プログラム
の理解支援とその問題点

提案手法
実行履歴の分割手法
適用事例
 まとめと今後の課題

2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
2
背景と目的
2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
3
オブジェクト指向プログラムの理解支援

プログラムの実行履歴(メソッド呼び出し系列)を取得し,
UMLのシーケンス図として可視化
 時系列にそってオブジェクト間のメソッド呼び出し関係を可視化
 プログラムの実行時に決定する情報を可視化できる
オブジェクト
A(1).a() {
B(1).b() {
C(1).c1() {
}
C(2).c2() {
}
D(1).d1() {
D(1).d2() {
}
}
}
実行履歴
A-1
時間
B-1
C-1
C-2
D-1
シーケンス図
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
4
実行履歴を利用する際の問題点

プログラムの実行履歴のサイズは巨大になる
プログラム中のループ,再帰構造によって実際に実行され
た全てのメソッド呼び出しを記録
全てを1つのシーケンス図として表現するのは望ましくない

実行履歴を複数のブロックに分割し,分割した各ブ
ロック単位でシーケンス図として可視化したい
→ 動作するオブジェクト群に着目した実行履歴の分割
手法を提案
2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
5
分割のアプローチと提案手法
2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
6
実行履歴分割のアプローチ

プログラムの1つの実行履歴はシステムの複数のフェイズを含み,各フェ
イズ毎に動作しているオブジェクト群は異なるはず


ユーザ入力 → 内部計算 → GUI出力
プログラムの実行がシステムの異なるフェイズに入れば,動作しているオ
ブジェクト群も大きく変化するはず
オブジェクト
A-1
動作するオブジェクト群
の変化を捉えて分割す
ることで,ある程度意味
のある機能単位での分
割が可能
B-1
C-1
C-2
D-1
X-1
X-2
X-3
Y-1
ク ラ ス B,C,D,… の オ ブ ジ ェ
クトがユーザ入力部を実現
クラスX,Y,…のオブジェク
トがGUI出力部を実現
時間
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
7
実行履歴の分割手法
キャッシュ・アルゴリズムを用いたフェイズ境界の特定
 キャッシュには最近「動作した」オブジェクト群をオブジェクトIDで記憶


「動作した」 = メソッドを呼び出したか,呼び出された
実行履歴中の各メソッド呼び出し毎に以下を実行



(呼び出し元オブジェクト,呼び出し先オブジェクト)の組をキャッシュに追加
キャッシュ内の古いオブジェクトが捨てられたとき,キャッシュが更新されたとみなす
(Least Recently Usedキャッシュ)
キャッシュの更新頻度を計算
t番目のメソッド呼び出しに対するキャッシュの更新頻度
f(t) = 過去n回([t-n+1, t])のメソッド呼び出しでキャッシュが更新された割合



f(t) = 0 ⇔ 過去n回のメソッド呼び出しはキャッシュ内のオブジェクトのみ動作
f(t) = 0.5 ⇔ n回中n/2回キャッシュ内のオブジェクトが入れ替わった
キャッシュの更新頻度大 ⇒ 異なるフェイズに処理が移行したとみなす
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
8
キャッシュ・アルゴリズムの動作例
OLD
t番目
a
NEW
b
c
d
e
キャッシュサイズ = 5
更新頻度
= 過去3回の平均更新回数
実行履歴(入力)
更新
t+1番目
a
t+2番目
b
c
d
e
f
c
d
e
f
b
d
e
f
b
a
f(t+2)
= 1/3
t: …
t+1: e → f
t+2: f → b
t+3: b → a
t+4: …
更新
t+3番目
c
f(t+3)
= 2/3
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
9
適用事例
2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
10
適用事例

単一の実行履歴に対して適用してみる
人間が考えたフェイズの境界で,実際にキャッシュの更新
頻度が大きくなっているか

対象プログラム
バイトコード解析ツール
入力として与えられた各メソッド毎に以下の処理を実行
Java
制御フローグラフ構築
 制御依存関係の探索
 データ依存関係の探索

各処理が明確に区分されている
2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
11
動作するオブジェクトの時間による変化
各メソッド毎に,(呼び出し元,呼び出し先)オブジェクトの組をプロット
1個データ処理
制御フロー解析
結果出力
1個データ処理
制御依存解析
データ依存解析
望まれる区切り
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
12
キャッシュの更新頻度

キャッシュサイズを50とし,過去20回分のメソッド呼び出しに
おけるキャッシュの更新頻度f(t)を計測してグラフ化
 更新頻度≧0.5となったのは5ヶ所
0.5
2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
13
処理の区切り
更新のピーク
人間が予想した
結果とほぼ整合
フェイズ開始直後に
オブジェクトを作る
フェイズ開始位置と
キャッシュの更新ピー
クがずれることもある
2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
14
考察

「新しいオブジェクト」は,まとめて登場することが多い
ユーザインタフェース用,データ表現用オブジェクトなど
新しいフェイズが始まったことは認識しやすい

キャッシュサイズの影響
キャッシュサイズが大きい
⇒ 「新しいオブジェクト」が登場
しにくくなる

分割の単位が大きくなりやすい
キャッシュサイズが小さい
2005/3/22
⇒ その逆
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
15
まとめと今後の課題

まとめ
動作するオブジェクト群に着目することで,プログラムの実
行履歴を複数のブロックに分割する手法を提案
適用事例を紹介

今後の課題
他のプログラムの実行履歴に対する適用
分割によってどのくらいサイズが減るのか
 パラメータの影響がどのくらい大きいか

2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
16
おわり
2005/3/22
電子情報通信学会 総合大会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
17

similar documents