分散処理を用いた大規模ソフトウェアに対するコーディングパターン検出ツール

Slides:



Advertisements
Similar presentations
シーケンス図の生成のための実行履歴圧縮手法
Advertisements

MPIを用いたグラフの並列計算 情報論理工学研究室 藤本 涼一.
LZ圧縮回路の設計とハード・ソフト 最適分割の検討 電子情報デザイン学科 高性能計算研究室 4回生 中山 和也 2009/2/27.
シーケンシャルパターンマイニングに基づくオブジェクト指向プログラムのための 欠陥検出手法
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
JavaによるCAI学習ソフトウェアの開発
P,Q比が変更可能なScaLAPACKの コスト見積もり関数の開発
変数間データフローグラフを用いた ソースコード間の移動支援
複数のモジュールに共通する ソースコード片の検出と活用
メソッド名とその周辺の識別子の 相関ルールに基づくメソッド名変更支援手法
川口真司 松下誠 井上克郎 大阪大学大学院情報科学研究科
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
プログラム実行履歴を用いたトランザクションファンクション抽出手法
プログラム実行時情報を用いたトランザクションファンクション抽出手法
ソースコードの変更履歴における メトリクス値の変化を用いた ソフトウェアの特性分析
過負荷時の分散ソフトウェアの 性能劣化を改善する スケジューリングの提案
類似するコーディングパターンの 利用状況調査ツールの提案
コーディングパターンと キーワードを用いて生成したコードスニペットの推薦
MPIを用いた最適な分散処理 情報論理工学研究室 角 仁志
コードクローンに含まれるメソッド呼び出しの 変更度合の分析
コードクローンに含まれるメソッド呼び出しの 変更度合の調査
ソードコードの編集に基づいた コードクローンの分類とその分析システム
オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現
インラインスクリプトに対するデータフロー 解析を用いた XHTML 文書の構文検証
シーケンス図を用いて実行履歴を可視化するデバッグ環境の試作
クローンセットに対する主要編集者の分析法の提案と調査
実行時情報に基づく OSカーネルのコンフィグ最小化
コードクローン検出ツールを用いた ソースコード分析システムの試作と プログラミング演習への適用
リファクタリング支援のための コードクローンに含まれる識別子の対応関係分析
Internet広域分散協調サーチロボット の研究開発
通信機構合わせた最適化をおこなう並列化ンパイラ
動的データ依存関係解析を用いた Javaプログラムスライス手法
オープンソース開発支援のための ソースコード及びメールの履歴対応表示システム
ソースコードの特徴量を用いた機械学習による メソッド抽出リファクタリング推薦手法
オープンソース開発支援のための リビジョン情報と電子メールの検索システム
コードクローンの動作を比較するためのコードクローン周辺コードの解析
コードクローンに対する一貫性のない変更に起因する欠陥の検出
Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現
コードクローン検出に基づくデザイン パターン適用支援手法の提案と実現
GPGPUによる 飽和高価値 アイテム集合マイニング
不確実データベースからの 負の相関ルールの抽出
プログラム理解におけるThin sliceの 統計的調査による有用性評価
バイトコードを単位とするJavaスライスシステムの試作
コード片に共通した特性を自動抽出する ソースコード閲覧ツールの試作
○ 後藤 祥1,吉田 則裕2 ,井岡 正和1 ,井上 克郎1 1大阪大学 2奈良先端科学技術大学院大学
ソフトウェア保守のための コードクローン情報検索ツール
パターンマイニング技術を 用いた実時間プログラムの コーディングパターン検出
コードクローンの理解支援を目的としたコードクローン周辺コードの解析
コードクローン分類の詳細化に基づく 集約パターンの提案と評価
既存ソフトウェア中の 頻出コード片を用いた コード補完手法の提案
コーディングパターンの あいまい検索の提案と実装
インスタンスの型を考慮したJavaプログラムの実行経路の列挙手法の提案
コードクローン間の依存関係に基づく リファクタリング支援環境の実装
オブジェクトの協調動作を用いた オブジェクト指向プログラム実行履歴分割手法
プログラムスライスを用いた凝集度メトリクスに基づく 類似メソッド集約候補の順位付け手法
設計情報の再利用を目的とした UML図の自動推薦ツール
保守請負時を対象とした 労力見積のためのメトリクスの提案
「マイグレーションを支援する分散集合オブジェクト」
オープンソースソフトウェアに対する コーディングパターン分析の適用
分散処理を用いたコーディングパターン検出ツールの実装
MPIを用いた並列処理計算 情報論理工学研究室 金久 英之
ソースコードの編集状況に応じた ソフトウェア部品の自動推薦システム
UMLモデルを対象とした リファクタリング候補検出手法の提案と実現
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
プログラムの一時停止時に 将来の実行情報を提供するデバッガ
コードクローン解析に基づく デザインパターン適用候補の検出手法
木構造の比較に基づく メソッド呼び出し履歴の変化の可視化手法
オブジェクト指向言語における セキュリティ解析アルゴリズムの提案と実現
プログラム依存グラフを用いた ソースコードのパターン違反検出法
Presentation transcript:

分散処理を用いた大規模ソフトウェアに対するコーディングパターン検出ツール 井上研究室 悦田 翔悟

研究の概要 コーディングパターンの検出 解析対象が大きくなると,処理時間が大幅に増加 分散処理を用いたコーディングパターン検出ツールの実装 メソッド呼び出し要素,制御構造要素で構成される頻出する定型的なコード片 プログラム理解支援,欠陥検出に利用 解析対象が大きくなると,処理時間が大幅に増加 分散処理を用いたコーディングパターン検出ツールの実装 パターン検出の高速化を実現 開発プロセスへの組み込みが容易になる 我々の研究グループではコーディングパターンの検出を行っています。 コーディングパターンとは、メソッド呼び出し要素,制御構造要素で構成される頻出する定型的なコード片のことを指し これを検出することでプログラム理解支援や、欠陥検出に利用することができます。 コーディングパターン検出において解析対象が大きくなると,処理時間が大幅に増加するという問題があります。 そこで本研究では分散処理を用いたコーディングパターン検出ツールの実装を行い、 パターン検出の高速化を実現します。 これによりコーディングパターンの検出、その利用が開発プロセスへ組み込み易くなります。 2018/9/21

コーディングパターンの例 テキスト編集ソフトJEdit中で発見されたコーディングパターン コーディングパターンの利用法 現在編集可能でなければビープ音を鳴らす機能 コーディングパターンの利用法 コーディング時のルールの発見 プログラム読解のサポート パターン違反による欠陥検出 if (!buffer.isEditable()){ getToolkit().beep(); return; } isEditable() IF beep() END-IF コーディングパターン ソースコード上の複数のメソッド ますコーディングパターンの具体的な例を説明します。 下の図はテキスト編集ソフトJEdit中で発見されたコーディングパターンです。 「現在編集可能でなければビープ音を鳴らす機能」を実装した複数のメソッドで類似した記述があり、 図のようなコーディングパターンが検出されました。 このようなコーディングパターンを知ることにより、 開発者は同じような機能を実装する際のコーディングのルールを発見したり、 プログラムの重要な箇所の把握、 またパターン違反の記述を発見することで欠陥検出などにも利用することができます。 2018/9/21

コーディングパターン検出の流れ v() LOOP a() b() w() x() END-LOOP y() z() public B m1() { … } メソッド集合 メソッドごとに分割 public class A { public B m1() { } public B m2() { 入力 v() LOOP a() b() w() x() END-LOOP y() z() 要素列データベース ソースコード ・複数の文字列から頻出する部分列を検出  どの程度頻出すれば検出を行うかはユーザが最小サポート値として設定 ・処理時間が長いため分散処理させる  例 Apache Antではパターンマイニング部分で6140秒かかる メソッド内の正規化 A.m1 IF B.m2 LOOP A.m2 END-LOOP END-IF 要素列データベース 次にコーディングパターン検出の流れを説明します。 まず解析対象のソースコードを入力し、 それらをメソッドごとに分割、メソッド集合を得ます。 そしてメソッド集合の中身を正規化し、要素列データベースを得ます。 図のように要素列データベースの中身はメソッド呼び出し要素と制御構造要素からなる複数の文字列になっています。 このデータベースに対してシーケンシャルパターンマイニングを行い、コーディングパターンを検出します。 シーケンシャルパターンマイニングとは複数の文字列から頻出する部分列を検出する手法で、 どの程度頻出すれば検出を行うかはユーザが最小サポート値として設定します。 全体の処理の中でこのシーケンシャルパターンマイニングに長い時間がかるため本研究ではこの部分を分散処理させます。 コーディングパターン シーケンシャル パターンマイニング 2018/9/21 3

シーケンシャルパターンマイニングの実行例 a:1 b:2 c:2 d:1 ab,ac,を 長さ2の パターン b c a b c d 接尾辞の 取り出し a:4 b:3 c:3 d:1 各要素が 出現する列数 a,b,c,を 長さ1のパターン b c パターンの 2要素目 パターンの 1要素目 a b c c c:1 d d:1 a c d a b c c b a a a b c d a:1 c:1 b:1 d:1 a b a 結果 a:4 ab:2 ac:2 b:3 c:3 パターン 最小サポート値2 2回以上出現するパターンの検出 次にシーケンシャルパターンマイニングの実行例についてですが、 最小サポート値を2としたときのパターンの検出、すなわち2回以上出現するパターンを検出するときの実行例を説明します 検出対象はこちらの4本の文字列とします この文字列はコーディングパターン検出における要素列データベースに対応するもので、 アルファベットはメソッド呼び出し要素や制御構造要素に対応します。 まずは各要素がいくつの文字列に出現するかを数え、 このうち2回以上出現するa,b,cを長さ1のパターンとします。 次に、a、b、cを先頭の文字とするような長さ2のパターンの検出を行います。 aから始まるパターンを見つけるには、まずは元の文字列から a の出現位置を見つけ、その接尾辞を取り出します。 これらに対して最初のステップと同じように各要素の出現回数を数え、 やはり2回以上出現する要素を、パターンの2要素目とします。 ここでは、bとcが2回出現しているので、ab、acが長さ2のパターンとなります。 さらに長さ2のパターンに続く文字列を調べることで長さ3のパターンを取り出すというように探索を行い、パターンの候補を探索していきます。 b、cから始まるパターンの探索も同様に行います。 その結果このようなパターンが検出されます。 a、b、cから始まるパターンの検出はそれぞれ独立しています。 複数の文字列 コーディングパターン検出 における 要素列データベースに対応する 2018/9/21

計算量の問題 解析対象ソフトウェアの規模が増えると計算量が大幅に増加する 例 SableCC(3.5 万行)に対して42秒     Apache Ant(20万行)に対して6140秒 処理時間の増加,メモリ不足などの問題から,コーディングパターン検出が困難である コーディングパターン検出を行う上で、解析対象ソフトウェアの規模が増えると計算量が大幅に増加するという問題があります。 例を挙げると3.5万行のSableCCに対しては42秒で処理が終了しますが、 20万行のApache Antに対しては6140秒も処理に時間がかかってしまします。 このような処理時間の増加,メモリ不足などの問題から,大規模ソフトウェアに対してのコーディングパターン検出は困難となります。 そこで本研究では、複数台の計算機による分散処理により,対象ソフトウェアの大規模化へ対応する 複数台の計算機による分散処理により,対象ソフトウェアの大規模化へ対応する 2018/9/21

マスタ・ワーカ法による分散処理[1] a:1 b:2 c:2 d:1 c c:1 d ジョブ a : ワーカ1の処理範囲 b c a b a c d a b c c b a a a b a:1 b:1 d:1 ジョブ c: ワーカ3の処理範囲 d c:1 ジョブ b: ワーカ2の処理範囲 c a b a a:4 b:3 c:3 d:1 b c シーケンシャルパターンマイニングの分散処理手法には既にマスタ・ワーカ法とマスタ・タスク・スティール法という手法が提案されています。 マスタ・ワーカ法ではマスタがジョブの生成、管理を行い複数のワーカでパターンの探索を行います。 具体的には図のようにaから始まるパターンの探索をジョブa、bから始まるパターンの探索をジョブb、cから始まるパターンの探索をジョブc というようにとらえ、それぞれのジョブを異なるワーカに割り当てます。 このときジョブaを処理するワーカ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) 2018/9/21

マスタ・タスク・スティール法による分散処理[2] ジョブa:ワーカ1の処理範囲 c d ジョブab a:1 b:2 c:2 d:1 c c:1 b c ジョブac a b a c d a b c c b a a a b ジョブb:ワーカ2の処理範囲 a:4 b:3 c:3 d:1 c a:1 c:1 a マスタがジョブの回収を行えるよう、ワーカ1は長さ2のパターン検出以後の探索をジョブab、ジョブacのように保持し、 まずジョブabから処理を始めます。 このときワーカ2がジョブbを終えると、マスタがワーカ1からジョブacを回収、ワーカ2に再割り当てしています。 これにより動的な負荷分散を実現しています。 a:1 b:1 d:1 ジョブc:ワーカ3の処理範囲 d 処理が終わった! b a [2] 高木充,田村慶一,周藤俊秀,北上始 並列 Modified PrefixSpan 法における動的負荷分散手法, 情報処理学会研究報告,Vol.2004, pp. 9-15 (2004) 2018/9/21

評価実験 実験の目的 実験環境 評価基準: Javaソースコードを対象とした場合の分散処理法の有効性の調査 従来の対象データはアミノ酸データベースなど 実験環境 マスタ:Pentium4 3.2GHz 搭載の計算機1台 ワーカ:Pentium4 1.5GHz 搭載の計算機6台 通信:Ethernet 100base-TX 最小サポート値:4 評価基準: 実験の目的は・・・ 従来はアミノ酸データベースなどを実験対象としいたので、 実験環境は 評価基準ですが、ワーカ1台のときの処理時間をワーカN台のときの処理時間で割ったものを性能向上比とし、 この値で分散手法の有効性を評価します。 ワーカ1台のときの処理時間 性能向上比= ワーカN台のときの処理時間 2018/9/21

実験対象 実験対象 LOC 前処理時間*1 ワーカ1台のときの処理時間*2 検出したコーディングパターン数 Antlr 5.6万 35秒 2982秒 58545 Apache Ant 20万 69秒 6140秒 134568 *1 シーケンシャルパターンマイニングより前の処理時間   メソッド分割、正規化など *2 シーケンシャルパターンマイニング部分の処理時間 実験対象は2つ 前処理時間とは ワーカ1台の時の処理時間とは 2018/9/21

マスタ・ワーカ法を用いた場合の性能向上比 理想的な性能向上比とは、ワーカの台数に比例して性能が向上する場合で、 マスタ・ワーカ法による 台数を増やしても性能向上比は伸びなくなりました。これについて各ジョブの処理時間を分析したところ・・・ 2018/9/21

各ジョブの処理時間が全ジョブの処理時間 の合計に占める割合 各ワーカに割り当てられたジョブの処理時間に偏りがあることがわかりました。 上位5つのみを示し,残りはその他としました。 図より上位5つのジョブが全処理時間の90%近くを占めていることがわかります。 このような重たいジョブを受け取ったワーカは、なかなか処理を終えることができず、結果として全体の処理向上比が 伸びなかったと考えられます。 これに対して・・・ 2018/9/21

マスタ・タスク・スティール法を用いた場合の 性能向上比 動的に負荷分散を行うマスタ・タスク・スティール法の性能向上比は図のとおりです antlrでは6台で5.2倍、antでは6台で4.0倍の性能向上比が得られた 2018/9/21

考察 マスタ・ワーカ法ではうまく負荷分散することができなかった マスタ・タスク・スティール法が有効である ジョブに大きな偏りがあるため 台数を増やしてもある程度の性能向上比が期待できる また台数を増やしても性能向上比が順調に伸びていることから、6台以上に台数を増やしてもある程度の性能向上比が期待できます 2018/9/21

まとめと今後の課題 分散処理を用いたコーディングパターン検出ツールの実装 今後の課題 パターン検出の高速化を実現 マスタ・タスク・スティール法の有効性を確認 今後の課題 ワーカの台数を増やして大規模ソフトウェアを対象とするパターン検出 検出したパターンから有用性の高いパターンの自動抽出 2018/9/21