分散処理を用いた大規模ソフトウェアに対するコーディングパターン検出ツール井上研究室特別研究報告会悦田翔悟研究の概要 • コーディングパターンの検出 – メソッド呼び出し要素，制御構造要素で構成される頻出する定型的なコード片 – プログラム理解支援，欠陥検出に利用 • 解析対象が大きくなると，処理時間が大幅に増加 • 分散処理を用いたコーディングパターン検出ツールの実装 – パターン検出の高速化を実現 – 開発プロセスへの組み込みが容易になる 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 ｂ 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 最小サポート値：４ • 評価基準：性能向上比＝ワーカ１台のときの処理時間ワーカ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