分散処理を用いたコーディング パターン検出ツールの実装 大阪大学 ○悦田翔悟,伊達浩典,石尾隆,井上克郎 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 研究の概要 • コーディングパターンの検出 – メソッド呼び出し要素,制御構造要素で構成される頻出す る定型的なコード片 – プログラム理解支援,欠陥検出に利用 • 解析対象が大きくなると,処理時間が大幅に増加 • 分散処理を用いたコーディングパターン検出ツール の実装 – パターン検出の高速化を実現 – 開発プロセスへの組み込みが容易になる 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 1 発表の内容 • • • • • コーディングパターンの例 コーディングパターン検出手法 分散処理法 評価実験 まとめ 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 2 コーディングパターンの例 if (!buffer.isEditable()){ getToolkit().beep(); return; } ソースコード上の複数のメソッド isEditable() IF beep() END-IF コーディングパターン • テキスト編集ソフトjEdit中で発見されたコーディングパターン – 現在編集可能でなければビープ音を鳴らす機能 • コーディングパターンの利用法 • コーディング時のルールの発見 • プログラム読解のサポート • パターン違反による欠陥検出 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 3 コーディングパターン検出の流れ メソッドごとに分割 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/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 4 シーケンシャルパターンマイニングの実行例 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 d b c a b コーディングパターン検出 における 要素列データベースに対応する b c c c:1 d d:1 b c c a a a b 複数の文字列 a:1 b:2 c:2 d:1 パターンの 2要素目 各要素が 出現する 列数 d b a a:1 c:1 a:1 b:1 d:1 結果 a:4 ab:2 ac:2 b:3 c:3 パターン 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 5 計算量の問題 • 解析対象ソフトウェアの規模が増えると計算 量が大幅に増加する – 例 SableCC(3.5 万行)に対して42秒 Apache Ant(20万行)に対して6140秒 • 処理時間の増加,メモリ不足などの問題から, コーディングパターン検出が困難である 複数台の計算機による分散処理により, 対象ソフトウェアの大規模化へ対応する 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 6 マスタ・ワーカ法による分散処理[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/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 7 マスタ・タスク・スティール法による分散処理[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/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 8 評価実験 • 実験の目的 – Javaソースコードを対象とした場合の分散処理法の有効 性の調査 従来の対象データはアミノ酸データベースなど • 実験環境 – – – – • マスタ:Pentium4 3.2GHz 搭載の計算機1台 ワーカ:Pentium4 1.5GHz 搭載の計算機6台 通信:Ethernet 100base-TX 最小サポート値:4 ワーカ1台のときの処理時間 評価基準: 性能向上比= ワーカN台のときの処理時間 N台で性能向上比がN倍になるのが理想 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 9 実験対象 ワーカ1台のとき 検出したコーディング の処理時間*2 パターン数 実験対象 LOC 前処理時間 *1 Antlr 5.6万 35秒 2982秒 58545 Apache Ant 20万 69秒 6140秒 134568 *1 シーケンシャルパターンマイニングより前の処理時間 メソッド分割、正規化など *2 シーケンシャルパターンマイニング部分の処理時間 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 10 実験結果 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/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 11 各ジョブの処理時間が全ジョブの処理時間 の合計に占める割合 Antlr 7% 13% Apache Ant (ジョブ数1370) match(antlr.colle ctions.AST, int) 6% CONTROL_STA RT[IF] 31% getFirstChild() getType() 4% 4% 30% その他 CONTROL_START [IF] createArgument() 13% setValue(string) 9% 13% getNextSibling() (ジョブ数3847) 17% 53% getProject() hasMoreElements() その他 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 12 考察 • マスタ・ワーカ法ではうまく負荷分散すること ができなかった • ジョブに大きな偏りがあるため • マスタ・タスク・スティール法が有効である • 台数を増やしてもある程度の性能向上比が期待できる 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 13 まとめと今後の課題 • 分散処理を用いたコーディングパターン検出ツール の実装 – パターン検出の高速化を実現 – マスタ・タスク・スティール法の有効性を確認 • 今後の課題 – ワーカの台数を増やして大規模ソフトウェアを対象とする パターン検出 – 検出したパターンから有用性の高いパターンの自動抽出 2015/10/1 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 14
© Copyright 2024 ExpyDoc