スライド 0

分散処理を用いた大規模ソフトウェアに
対するコーディングパターン検出ツール
井上研究室
特別研究報告会
悦田 翔悟
研究の概要
• コーディングパターンの検出
– メソッド呼び出し要素,制御構造要素で構成される頻出す
る定型的なコード片
– プログラム理解支援,欠陥検出に利用
• 解析対象が大きくなると,処理時間が大幅に増加
• 分散処理を用いたコーディングパターン検出ツール
の実装
– パターン検出の高速化を実現
– 開発プロセスへの組み込みが容易になる
2015/9/30
特別研究報告会
1
コーディングパターンの例
• テキスト編集ソフトJEdit中で発見されたコーディングパターン
– 現在編集可能でなければビープ音を鳴らす機能
• コーディングパターンの利用法
• コーディング時のルールの発見
• プログラム読解のサポート
• パターン違反による欠陥検出
if (!buffer.isEditable()){
getToolkit().beep();
return;
}
isEditable()
IF
beep()
END-IF
ソースコード上の複数のメソッド
コーディングパターン
2015/9/30
特別研究報告会
2
コーディングパターン検出の流れ
public class A {
public B m1() {
}
public B m2() {
}
}
メソッドごとに分割
入力
ソースコード
public B m1() {
public B m1() {
…
public B m1() {
} … public B m1() {
} … public B m1() {
} … public B m1() {
} …
} …
}
メソッド集合
・複数の文字列から頻
出する部分列を検出
どの程度頻出すれば検
出を行うかはユーザが最
小サポート値として設定
・処理時間が長いため
分散処理させる
例 Apache Antではパ
ターンマイニング部分で
6140秒かかる
メソッド内の正規化
A.m1
IF A.m1
IF A.m1
B.m2
IF A.m1
B.m2
LOOP
IF A.m1
B.m2
LOOP
A.m2
IF A.m1
B.m2
LOOP
A.m2
IF
END-LOOP
B.m2
LOOP
A.m2
END-LOOP
B.m2
END-IFA.m2
LOOP
END-LOOP
END-IF
LOOP
A.m2
END-LOOP
END-IF
A.m2
END-LOOP
END-IF
END-LOOP
END-IF
END-IF
v()
LOOP
a()
b()
w()
x()
END-LOOP
y()
z()
要素列データベース
要素列データベース
シーケンシャル
パターンマイニング
特別研究報告会
コーディングパターン
2015/9/30
3
シーケンシャルパターンマイニングの実行例
ab,ac,を
長さ2の
接尾辞の
パターン
取り出し
a,b,c,を
長さ1のパターン
パターンの
1要素目
a
a c d
a b c
最小サポート値2
2回以上出現する
パターンの検出
c b a
a:4
b:3
c:3
d:1
b
c
c d
b c
a b
c
a
a a b
複数の文字列
コーディングパターン検出
における
要素列データベースに対応する
各要素が
出現する
列数
d
b a
a:1
b:2
c:2
d:1
a:1
c:1
a:1
b:1
d:1
パターンの
2要素目
b
c
c
c:1
d
d:1
結果
a:4
ab:2
ac:2
b:3
c:3
パターン
2015/9/30
特別研究報告会
4
計算量の問題
• 解析対象ソフトウェアの規模が増えると計算
量が大幅に増加する
– 例 SableCC(3.5 万行)に対して42秒
Apache Ant(20万行)に対して6140秒
• 処理時間の増加,メモリ不足などの問題から,
コーディングパターン検出が困難である
複数台の計算機による分散処理により,
対象ソフトウェアの大規模化へ対応する
2015/9/30
特別研究報告会
5
マスタ・ワーカ法による分散処理[1]
a
ジョブ b: ワーカ2の処理範囲
a c d
a b c
c b a
a a b
ジョブ a : ワーカ1の処理範囲
c d
a:1
c
c:1
b:2
b c
c:2
d
d:1
a b
d:1
a:4
b:3
c:3
d:1
[1] Design and Implementation of Parallel Modified
PrefixSpan Method,
Sutou ,T. Tamura, K. Mori, Y. and Kitakami, H.,
High Performance Computing Volume 2858/2003
(Springer Berlin / Heidelberg), pp. 412-422 (2003)
b
c
c
a
a:1
c:1
ジョブ c: ワーカ3の処理範囲
d
a:1
b:1
b a
d:1
2015/9/30
特別研究報告会
6
マスタ・タスク・スティール法による分散処理[2]
ジョブa:ワーカ1の処理範囲
c d
a:1
c ジョブab
c:1
b:2
b c
c:2
a b
ジョブac
d:1
ジョブb:ワーカ2の処理範囲
a c d
a b c
c b a
a a b
a:4
b:3
c:3
d:1
[2] 高木充,田村慶一,周藤俊秀,北上始
並列 Modified PrefixSpan 法における動的負荷分散
手法,
情報処理学会研究報告,Vol.2004, pp. 9-15 (2004)
c
a
a:1
c:1
ジョブc:ワーカ3の処理範囲
d
a:1
処理が終わった!
b a
b:1
d:1
2015/9/30
特別研究報告会
7
評価実験
• 実験の目的
– Javaソースコードを対象とした場合の分散処理法の有効
性の調査
従来の対象データはアミノ酸データベースなど
• 実験環境
–
–
–
–
マスタ:Pentium4 3.2GHz 搭載の計算機1台
ワーカ:Pentium4 1.5GHz 搭載の計算機6台
通信:Ethernet 100base-TX
最小サポート値:4
• 評価基準: 性能向上比=
ワーカ1台のときの処理時間
ワーカN台のときの処理時間
2015/9/30
特別研究報告会
8
実験対象
ワーカ1台のとき 検出したコーディング
の処理時間*2
パターン数
実験対象
LOC
前処理時間
*1
Antlr
5.6万
35秒
2982秒
58545
Apache
Ant
20万
69秒
6140秒
134568
*1 シーケンシャルパターンマイニングより前の処理時間
メソッド分割、正規化など
*2 シーケンシャルパターンマイニング部分の処理時間
2015/9/30
特別研究報告会
9
マスタ・ワーカ法を用いた場合の性能向上比
Apache-Ant
Antlr
理想的な性能向上比
マスタ・ワーカ法
7
7
6
6
5
5
性能向上比(倍)
性能向上比(倍)
理想的な性能向上比
4
3
マスタ・ワーカ法
4
3
2
2
1
1
0
0
1
2
3
4
5
1
6
2
3
4
5
6
ワーカ台数(台)
ワーカ台数(台)
2015/9/30
特別研究報告会
10
各ジョブの処理時間が全ジョブの処理時間
の合計に占める割合
Antlr
7%
13%
Apache-Ant
(ジョブ数1370)
match(antlr.colle
ctions.AST, int)
6%
CONTROL_STA
RT[IF]
31%
getFirstChild()
4%
4%
CONTROL_START
[IF]
createArgument()
13%
setValue(string)
9%
getType()
(ジョブ数3847)
13%
getNextSibling()
30%
その他
17%
53%
getProject()
hasMoreElements()
その他
2015/9/30
特別研究報告会
11
マスタ・タスク・スティール法を用いた場合の
性能向上比
Antlr
マスタ・タスク・スティール法
理想的な性能向上比
マスタ・タスク・スティール法
7
7
6
6
5
5
マスタ・ワーカ法
性能向上比(倍)
理想的な性能向上比
性能向上比(倍)
Apache-Ant
4
3
4
3
2
2
1
1
0
1
2
3
4
5
6
マスタ・ワーカ法
0
1
ワーカ台数(台)
2
3
4
5
6
ワーカ台数(台)
2015/9/30
特別研究報告会
12
考察
• マスタ・ワーカ法ではうまく負荷分散すること
ができなかった
• ジョブに大きな偏りがあるため
• マスタ・タスク・スティール法が有効である
• 台数を増やしてもある程度の性能向上比が期待できる
2015/9/30
特別研究報告会
13
まとめと今後の課題
• 分散処理を用いたコーディングパターン検出ツール
の実装
– パターン検出の高速化を実現
– マスタ・タスク・スティール法の有効性を確認
• 今後の課題
– ワーカの台数を増やして大規模ソフトウェアを対象とする
パターン検出
– 検出したパターンから有用性の高いパターンの自動抽出
2015/9/30
特別研究報告会
14